High-dimensional analysis of semidefinite relaxations for sparse principal components

DOI10.1214/08-AOS664MaRDI QIDQ834367zbMATH OpenFDO

Authors Arash A. Amini, Martin J. Wainwright

Publication date 19 August 2009

Published in The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

high-dimensional statisticssparsitysemidefinite programmingspectral analysisconvex relaxationprincipal components analysisrandom matricesspiked covariance ensemblesWishart ensembles

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Factor analysis and principal components; correspondence analysis (62H25) Large deviations (60F10) Applications of mathematical programming (90C90)

Abstract: Principal component analysis (PCA) is a classical method for dimensionality reduction based on extracting the dominant eigenvectors of the sample covariance matrix. However, PCA is well known to behave poorly in the ``large $p$, small $n$ setting, in which the problem dimension $p$ is comparable to or larger than the sample size $n$. This paper studies PCA in this high-dimensional regime, but under the additional assumption that the maximal eigenvector is sparse, say, with at most $k$ nonzero components. We consider a spiked covariance model in which a base matrix is perturbed by adding a $k$-sparse maximal eigenvector, and we analyze two computationally tractable methods for recovering the support set of this maximal eigenvector, as follows: (a) a simple diagonal thresholding method, which transitions from success to failure as a function of the rescaled sample size $het{a}_{mathrmdia}(n,p,k)=n/[k^{2}log(p-k)]$; and (b) a more sophisticated semidefinite programming (SDP) relaxation, which succeeds once the rescaled sample size $het{a}_{mathrmsdp}(n,p,k)=n/[klog(p-k)]$ is larger than a critical threshold. In addition, we prove that no method, including the best method which has exponential-time complexity, can succeed in recovering the support if the order parameter $het{a}_{mathrmsdp}(n,p,k)$ is below a threshold. Our results thus highlight an interesting trade-off between computational and statistical efficiency in high-dimensional inference.

Recommendations

• On consistency and sparsity for principal components analysis in high dimensions
• Sparse non Gaussian component analysis by semidefinite programming
• The sparse principal component analysis problem: optimality conditions and algorithms
• Approximation bounds for sparse principal component analysis
• scientific article; zbMATH DE number 6129459
• Sparse PCA: convex relaxations, algorithms and applications
• An exact approach to sparse principal component analysis
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Sparse principal component analysis via regularized low rank matrix approximation

Cites work

• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 4062374 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 53571 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1528193 (Why is no real title available?)
• scientific article; zbMATH DE number 1433619 (Why is no real title available?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• A Lower Bound on the Risks of Non-Parametric Estimates of Densities in the Uniform Metric
• A limit theorem for the norm of random matrices
• Adaptive estimation of a quadratic functional by model selection.
• An alternative point of view on Lepski's method
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• Chi-square oracle inequalities
• Compressed sensing
• Convex Analysis
• Eigenvalues of large sample covariance matrices of spiked population models
• First-Order Methods for Sparse Covariance Selection
• High-dimensional graphs and variable selection with the Lasso
• Information-theoretic determination of minimax rates of convergence
• Just relax: convex programming methods for identifying sparse signals in noise
• Local operator theory, random matrices and Banach spaces.
• Low-rank approximations with sparse factors. I: Basic algorithms and error analysis
• Model selection and estimation in the Gaussian graphical model
• On the distribution of the largest eigenvalue in principal components analysis
• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Principal component analysis.
• Regularized estimation of large covariance matrices
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• The concentration of measure phenomenon

Cited in

(58)

• Minimax sparse principal subspace estimation in high dimensions
• Learning a factor model via regularized PCA
• Sparse principal component analysis for high‐dimensional stationary time series
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Sparse PCA: convex relaxations, algorithms and applications
• Fundamental limits of detection in the spiked Wigner model
• Large covariance estimation by thresholding principal orthogonal complements. With discussion and authors' reply
• Discussion
• Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes
• Sparse power factorization: balancing peakiness and sample complexity
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• On semidefinite relaxations for the block model
• Dynamic Principal Component Analysis in High Dimensions
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• High-dimensional change-point estimation: combining filtering with convex optimization
• scientific article; zbMATH DE number 7625166 (Why is no real title available?)
• High-dimensional sufficient dimension reduction through principal projections
• Sparse principal component analysis with missing observations
• Directed principal component analysis
• On the optimality of sliced inverse regression in high dimensions
• Sparse PCA: optimal rates and adaptive estimation
• The spectral norm of random inner-product kernel matrices
• Sparse PCA via covariance thresholding
• Random matrix theory in statistics: a review
• Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation
• Sampled forms of functional PCA in reproducing kernel Hilbert spaces
• Envelopes and principal component regression
• Minimax estimation in sparse canonical correlation analysis
• Minimax bounds for sparse PCA with noisy high-dimensional data
• The analysis of multivariate data using semi-definite programming
• Estimation of functionals of sparse covariance matrices
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Computational and statistical tradeoffs via convex relaxation
• Discussion
• Large covariance estimation through elliptical factor models
• A note on probably certifiably correct algorithms
• Statistical and computational trade-offs in estimation of sparse principal components
• Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions
• Scale-invariant sparse PCA on high-dimensional meta-elliptical data
• On the computational tractability of statistical estimation on amenable graphs
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Approximation bounds for sparse principal component analysis
• On statistics, computation and scalability
• Sparse principal component analysis and iterative thresholding
• Rate-optimal posterior contraction for sparse PCA
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Sparse principal component analysis in Hilbert space
• Estimation of high-dimensional low-rank matrices
• Sparse non Gaussian component analysis by semidefinite programming
• Optimal detection of sparse principal components in high dimension
• Principal Component Analysis of High-Frequency Data
• Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements
• Sparsistency and agnostic inference in sparse PCA
• Near-optimal stochastic approximation for online principal component estimation

Describes a project that uses

Uses Software

• DSPCA

This page was built for publication: High-dimensional analysis of semidefinite relaxations for sparse principal components

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