Principal Components Analysis (PCA) is a dimension-reduction technique widely
used in machine learning and statistics. However, due to the dependence of the
principal components on all the dimensions, the components are notoriously hard to
interpret. Therefore, a variant known as sparse PCA is often preferred. Sparse PCA
learns principal components of the data but enforces that such components must
be sparse. This has applications in diverse fields such as computational biology
and image processing. To learn sparse principal components, it’s well known
that standard PCA will not work, especially in high dimensions, and therefore
algorithms for sparse PCA are often studied as a separate endeavor. Various
algorithms have been proposed for Sparse PCA over the years, but given how
fundamental it is for applications in science, the limits of efficient algorithms
are only partially understood. In this work, we study the limits of the powerful
Sum of Squares (SoS) family of algorithms for Sparse PCA. SoS algorithms have
recently revolutionized robust statistics, leading to breakthrough algorithms for
long-standing open problems in machine learning, such as optimally learning
mixtures of gaussians, robust clustering, robust regression, etc. Moreover, it is
believed to be the optimal robust algorithm for many statistical problems. Therefore,
for sparse PCA, it’s plausible that it can beat simpler algorithms such as diagonal
thresholding that have been traditionally used. In this work, we show that this is not
the case, by exhibiting strong tradeoffs between the number of samples required,
the sparsity and the ambient dimension, for which SoS algorithms, even if allowed
sub-exponential time, will fail to optimally recover the component. Our results
are complemented by known algorithms in literature, thereby painting an almost
complete picture of the behavior of efficient algorithms for sparse PCA. Since SoS
algorithms encapsulate many algorithmic techniques such as spectral or statistical
query algorithms, this solidifies the message that known algorithms are optimal for
sparse PCA. Moreover, our techniques are strong enough to obtain similar tradeoffs
for Tensor PCA, another important higher order variant of PCA with applications
in topic modeling, video processing, etc.
more »
« less
A New Basis for Sparse Principal Component Analysis
Previous versions of sparse principal component analysis (PCA) have presumed that the eigen-basis (a $p \times k$ matrix) is approximately sparse. We propose a method that presumes the $p \times k$ matrix becomes approximately sparse after a $k \times k$ rotation. The simplest version of the algorithm initializes with the leading $k$ principal components. Then, the principal components are rotated with an $k \times k$ orthogonal rotation to make them approximately sparse. Finally, soft-thresholding is applied to the rotated principal components. This approach differs from prior approaches because it uses an orthogonal rotation to approximate a sparse basis. One consequence is that a sparse component need not to be a leading eigenvector, but rather a mixture of them. In this way, we propose a new (rotated) basis for sparse PCA. In addition, our approach avoids ``deflation'' and multiple tuning parameters required for that. Our sparse PCA framework is versatile; for example, it extends naturally to a two-way analysis of a data matrix for simultaneous dimensionality reduction of rows and columns. We provide evidence showing that for the same level of sparsity, the proposed sparse PCA method is more stable and can explain more variance compared to alternative methods. Through three applications---sparse coding of images, analysis of transcriptome sequencing data, and large-scale clustering of social networks, we demonstrate the modern usefulness of sparse PCA in exploring multivariate data.
more »
« less
- Award ID(s):
- 1916378
- NSF-PAR ID:
- 10476150
- Publisher / Repository:
- Journal of Computational and Graphical Statistics
- Date Published:
- Journal Name:
- Journal of Computational and Graphical Statistics
- ISSN:
- 1061-8600
- Page Range / eLocation ID:
- 1 to 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We perform a rigorous study of private matrix analysis when only the last 𝑊 updates to matrices are considered useful for analysis. We show the existing framework in the non-private setting is not robust to noise required for privacy. We then propose a framework robust to noise and use it to give first efficient 𝑜(𝑊) space differentially private algorithms for spectral approximation, principal component analysis (PCA), multi-response linear regression, sparse PCA, and non-negative PCA. Prior to our work, no such result was known for sparse and non-negative differentially private PCA even in the static data setting. We also give a lower bound to demonstrate the cost of privacy in the sliding window model.more » « less
-
In the 1930s, Psychologists began developing Multiple-Factor Analysis to decompose multivariate data into a small number of interpretable factors without any a priori knowledge about those factors. In this form of factor analysis, the Varimax factor rotation redraws the axes through the multi-dimensional factors to make them sparse and thus make them more interpretable. Charles Spearman and many others objected to factor rotations because the factors seem to be rotationally invariant. Despite the controversy, factor rotations have remained widely popular among people analyzing data. Reversing nearly a century of statistical thinking on the topic, we show that the rotation makes the factors easier to interpret because the Varimax performs statistical inference; in particular, principal components analysis (PCA) with a Varimax rotation provides a unified spectral estimation strategy for a broad class of semi-parametric factor models, including the Stochastic Blockmodel and a natural variation of Latent Dirichlet Allocation. In addition, we show that Thurstone’s widely employed sparsity diagnostics implicitly assess a key leptokurtic condition that makes the axes statistically identifiable in these models. PCA with Varimax is fast, stable, and practical. Combined with Thurstone’s straightforward diagnostics, this vintage approach is suitable for a wide array of modern applications.more » « less
-
Oh, Alice ; Agarwal, Alekh ; Belgrave, Danielle ; Cho, Kyunghyun (Ed.)Graph neural networks (GNN) are an effective framework that exploit inter-relationships within graph-structured data for learning. Principal component analysis (PCA) involves the projection of data on the eigenspace of the covariance matrix and draws similarities with the graph convolutional filters in GNNs. Motivated by this observation, we study a GNN architecture, called coVariance neural network (VNN), that operates on sample covariance matrices as graphs. We theoretically establish the stability of VNNs to perturbations in the covariance matrix, thus, implying an advantage over standard PCA-based data analysis approaches that are prone to instability due to principal components associated with close eigenvalues. Our experiments on real-world datasets validate our theoretical results and show that VNN performance is indeed more stable than PCA-based statistical approaches. Moreover, our experiments on multi-resolution datasets also demonstrate that VNNs are amenable to transferability of performance over covariance matrices of different dimensions; a feature that is infeasible for PCA-based approaches.more » « less
-
more » « less
Abstract When the dimension of data is comparable to or larger than the number of data samples, principal components analysis (PCA) may exhibit problematic high-dimensional noise. In this work, we propose an empirical Bayes PCA method that reduces this noise by estimating a joint prior distribution for the principal components. EB-PCA is based on the classical Kiefer–Wolfowitz non-parametric maximum likelihood estimator for empirical Bayes estimation, distributional results derived from random matrix theory for the sample PCs and iterative refinement using an approximate message passing (AMP) algorithm. In theoretical ‘spiked’ models, EB-PCA achieves Bayes-optimal estimation accuracy in the same settings as an oracle Bayes AMP procedure that knows the true priors. Empirically, EB-PCA significantly improves over PCA when there is strong prior structure, both in simulation and on quantitative benchmarks constructed from the 1000 Genomes Project and the International HapMap Project. An illustration is presented for analysis of gene expression data obtained by single-cell RNA-seq.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1080/10618600.2023.2256502
