Solving sparse principal component analysis with global support

DOI10.1007/S10107-022-01857-WMaRDI QIDQ6038649zbMATH OpenOpenAlexWikidataFDO

Authors Santanu S. Dey, Marco Molinaro, Guanyi Wang

Publication date 2 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.11152

zbMATH Keywords

convex hullmatrix sparsificationrow sparse PCA

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Mixed integer programming (90C11) Nonlinear programming (90C30)

Abstract: Sparse principal component analysis with global support (SPCAgs), is the problem of finding the top-$r$ leading principal components such that all these principal components are linear combinations of a common subset of at most $k$ variables. SPCAgs is a popular dimension reduction tool in statistics that enhances interpretability compared to regular principal component analysis (PCA). Methods for solving SPCAgs in the literature are either greedy heuristics (in the special case of $r=1$) with guarantees under restrictive statistical models or algorithms with stationary point convergence for some regularized reformulation of SPCAgs. Crucially, none of the existing computational methods can efficiently guarantee the quality of the solutions obtained by comparing them against dual bounds. In this work, we first propose a convex relaxation based on operator norms that provably approximates the feasible region of SPCAgs within a $c_1+c_{2}sqrtlogr=O(sqrtlogr)$ factor for some constants $c_1,c_2$. To prove this result, we use a novel random sparsification procedure that uses the Pietsch-Grothendieck factorization theorem and may be of independent interest. We also propose a simpler relaxation that is second-order cone representable and gives a $(2sqrtr)$-approximation for the feasible region. Using these relaxations, we then propose a convex integer program that provides a dual bound for the optimal value of SPCAgs. Moreover, it also has worst-case guarantees: it is within a multiplicative/additive factor of the original optimal value, and the multiplicative factor is $O(logr)$ or $O(r)$ depending on the relaxation used. Finally, we conduct computational experiments that show that our convex integer program provides, within a reasonable time, good upper bounds that are typically significantly better than the natural baselines.

Recommendations

• Using \(\ell_1\)-relaxation and integer programming to obtain dual bounds for sparse PCA
• An exact approach to sparse principal component analysis
• Optimal solutions for sparse principal component analysis
• Sparse PCA: convex relaxations, algorithms and applications
• Certifiably optimal sparse principal component analysis

Cites work

• Alternating direction method of multipliers for sparse principal component analysis
• Approximation bounds for sparse principal component analysis
• Column subset selection, matrix factorization, and eigenvalue optimization
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Generalized power method for sparse principal component analysis
• scientific article; zbMATH DE number 1667417 (Why is no real title available?)
• scientific article; zbMATH DE number 3620605 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• NP-hardness and inapproximability of sparse PCA
• Optimal detection of sparse principal components in high dimension
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Optimal solutions for sparse principal component analysis
• Principal component analysis: a review and recent developments
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Randomized algorithms in numerical linear algebra
• Sparse PCA on fixed-rank matrices
• Sparse PCA via covariance thresholding
• Sparse PCA: convex relaxations, algorithms and applications
• Sparse PCA: optimal rates and adaptive estimation
• Sparse principal component analysis via variable projection
• Sparsistency and agnostic inference in sparse PCA
• The Sparse Principal Component of a Constant-Rank Matrix
• Truncated power method for sparse eigenvalue problems
• User-friendly tail bounds for sums of random matrices

Cited in

(5)

• Certifiably optimal sparse principal component analysis
• rs-sparse principal component analysis: a mixed integer nonlinear programming approach with VNS
• scientific article; zbMATH DE number 7625166 (Why is no real title available?)
• Using \(\ell_1\)-relaxation and integer programming to obtain dual bounds for sparse PCA
• Cardinality minimization, constraints, and regularization: a survey

This page was built for publication: Solving sparse principal component analysis with global support

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038649)