Sparse PCA via Bipartite Matchings

Abstract

We consider the following multi-component sparse PCA problem: given a set of data points, we seek to extract a small number of sparse components with disjoint supports that jointly capture the maximum possible variance. These components can be computed one by one, repeatedly solving the single-component problem and deflating the input data matrix, but as we show this greedy procedure is suboptimal. We present a novel algorithm for sparse PCA that jointly optimizes multiple disjoint components. The extracted features capture variance that lies within a multiplicative factor arbitrarily close to 1 from the optimal. Our algorithm is combinatorial and computes the desired components by solving multiple instances of the bipartite maximum weight matching problem. Its complexity grows as a low order polynomial in the ambient dimension of the input data matrix, but exponentially in its rank. However, it can be effectively applied on a low-dimensional sketch of the data; this allows us to obtain polynomial-time approximation guarantees via spectral bounds. We evaluate our algorithm on real data-sets and empirically demonstrate that in many cases it outperforms existing, deflation-based approaches.

References in corpus (5)

• Generalized power method for sparse principal component analysis
• Structured Sparse Principal Component Analysis
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Sparse PCA via Bipartite Matchings
• Optimal Sparse Linear Auto-Encoders and Sparse PCA

Cited by in corpus (7)

• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Dropping Convexity for Faster Semi-definite Optimization
• Sparse PCA via Bipartite Matchings
• Bipartite Correlation Clustering -- Maximizing Agreements
• Approximation Algorithms for Sparse Principal Component Analysis
• On the Worst-Case Approximability of Sparse PCA
• Certifiably Optimal Sparse Sufficient Dimension Reduction