Text

Using ℓ1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA

Principal component analysis (PCA) is one of the most widely used dimensionality reduction tools in scientific data analysis. The PCA direction, given by the leading eigenvector of a covariance matrix, is a linear combination of all features with nonzero loadings; this impedes interpretability. Sparse principal component analysis (SPCA) is a framework that enhances interpretability by incorporating an additional sparsity requirement in the feature weights (factor loadings) while finding a direction that explains the maximal variation in the data. However, unlike PCA, the optimization problem associated with the SPCA problem is NP-hard. Most conventional methods for solving SPCA are heuristics with no guarantees, such as certificates of optimality on the solution quality via associated dual bounds. Dual bounds are available via standard semidefinite programming (SDP)–based relaxations, which may not be tight, and the SDPs are difficult to scale using off-the-shelf solvers. In this paper, we present a convex integer programming (IP) framework to derive dual bounds. At the heart of our approach is the so-called ℓ1-relaxation of SPCA. Although the ℓ1-relaxation leads to convex optimization problems for ℓ0-sparse linear regressions and relatives, it results in a nonconvex optimization problem for the PCA problem. We first show that the ℓ1-relaxation gives a tight multiplicative bound on SPCA. Then, we show how to use standard integer programming techniques to further relax the ℓ1-relaxation into a convex IP for which there are good commercial solvers. We present worst-case results on the quality of the dual bound provided by the convex IP. We empirically observe that the dual bounds are significantly better than the worst-case performance and are superior to the SDP bounds on some real-life instances. Moreover, solving the convex IP model using commercial IP solvers appears to scale much better that solving the SDP-relaxation using commercial solvers. To the best of our knowledge, we obtain the best dual bounds for real and artificial instances for SPCA problems involving covariance matrices of size up to 2,000 × 2,000.

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.70 No.3 May-June 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1914-1932

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

SPARSE PRINCIPAL COMPONENT ANALYSIS
DUAL BOUNDS

Info Detail Spesifik

https://doi.org/10.1287/opre.2021.2153

Pernyataan Tanggungjawab

Santanu S. Dey, Rahul Mazumder, Guanyi Wang

Versi lain/terkait

Lampiran Berkas

Komentar