High-dimensional analysis of semidefinite relaxations for sparse principal components

DOI10.1214/08-AOS664zbMATH Open1173.62049arXiv0803.4026MaRDI QIDQ834367FDOQ834367

Arash A. Amini, Martin J. Wainwright

Publication date: 19 August 2009

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

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.

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)

Cites Work

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

Cited In (52)

• Sparse principal component analysis for high‐dimensional stationary time series
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Learning a factor model via regularized PCA
• Fundamental limits of detection in the spiked Wigner model
• Discussion
• Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes
• Dynamic Principal Component Analysis in High Dimensions
• 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
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• High-dimensional change-point estimation: combining filtering with convex optimization
• Sparse PCA: Convex Relaxations, Algorithms and Applications
• Scale-Invariant Sparse PCA on High-Dimensional Meta-Elliptical Data
• Title not available (Why is that?)
• High-dimensional sufficient dimension reduction through principal projections
• Sparse principal component analysis with missing observations
• 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
• 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
• Sparse Principal Component Analysis in Hilbert Space
• Minimax estimation in sparse canonical correlation analysis
• Minimax bounds for sparse PCA with noisy high-dimensional data
• Estimation of functionals of sparse covariance matrices
• Computational and statistical tradeoffs via convex relaxation
• Discussion
• Directed Principal Component Analysis
• Large covariance estimation through elliptical factor models
• A note on probably certifiably correct algorithms
• ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• On the computational tractability of statistical estimation on amenable graphs
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Large Covariance Estimation by Thresholding Principal Orthogonal Complements
• Approximation bounds for sparse principal component analysis
• On statistics, computation and scalability
• Rate-optimal posterior contraction for sparse PCA
• Sparse principal component analysis and iterative thresholding
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Estimation of high-dimensional low-rank matrices
• Principal Component Analysis of High-Frequency Data
• Optimal detection of sparse principal components in high dimension
• 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
• Minimax sparse principal subspace estimation in high dimensions
• Envelopes and principal component regression
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios

Uses Software

• DSPCA

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)