The Sparse Principal Component of a Constant-Rank Matrix

DOI10.1109/TIT.2014.2303975MaRDI QIDQ2986449zbMATH OpenOpenAlexFDO

Authors Megasthenis Asteris, Dimitris S. Papailiopoulos, George N. Karystinos

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The computation of the sparse principal component of a matrix is equivalent to the identification of its principal submatrix with the largest maximum eigenvalue. Finding this optimal submatrix is what renders the problem $mathcalNP$-hard. In this work, we prove that, if the matrix is positive semidefinite and its rank is constant, then its sparse principal component is polynomially computable. Our proof utilizes the auxiliary unit vector technique that has been recently developed to identify problems that are polynomially solvable. Moreover, we use this technique to design an algorithm which, for any sparsity value, computes the sparse principal component with complexity $mathcalOleft(N^{D+1}ight)$, where $N$ and $D$ are the matrix size and rank, respectively. Our algorithm is fully parallelizable and memory efficient.

Recommendations

• Sparse PCA on fixed-rank matrices
• Sparse principal component analysis via regularized low rank matrix approximation
• An exact approach to sparse principal component analysis
• The sparse principal component analysis problem: optimality conditions and algorithms
• Approximation bounds for sparse principal component analysis
• Sparse principal component analysis in Hilbert space
• Sparse principal component analysis by choice of norm
• scientific article; zbMATH DE number 6129459
• Sparse Principal Component Analysis via Axis-Aligned Random Projections
• Optimal solutions for sparse principal component analysis

Cited in

(5)

• A fast, provably accurate approximation algorithm for sparse principal component analysis reveals human genetic variation across the world
• Sparse PCA on fixed-rank matrices
• scientific article; zbMATH DE number 440639 (Why is no real title available?)
• Cutting plane generation through sparse principal component analysis
• Solving sparse principal component analysis with global support

This page was built for publication: The Sparse Principal Component of a Constant-Rank Matrix

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