High-dimensional analysis of semidefinite relaxations for sparse principal components

DOI10.1214/08-AOS664zbMath1173.62049arXiv0803.4026MaRDI QIDQ834367

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

semidefinite programmingrandom matricesspectral analysisconvex relaxationsparsityhigh-dimensional statisticsprincipal components analysisspiked covariance ensemblesWishart ensembles

Mathematics Subject Classification ID

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

Related Items

Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes, High-dimensional change-point estimation: combining filtering with convex optimization, Sparse principal component analysis and iterative thresholding, On the optimality of sliced inverse regression in high dimensions, Directed Principal Component Analysis, Minimax bounds for sparse PCA with noisy high-dimensional data, On statistics, computation and scalability, Optimal detection of sparse principal components in high dimension, Large covariance estimation through elliptical factor models, Minimax estimation in sparse canonical correlation analysis, Learning a factor model via regularized PCA, Estimation of functionals of sparse covariance matrices, Sparse principal component analysis for high‐dimensional stationary time series, A note on probably certifiably correct algorithms, Fundamental limits of detection in the spiked Wigner model, Dynamic Principal Component Analysis in High Dimensions, Euclidean Representation of Low-Rank Matrices and Its Geometric Properties, Envelopes and principal component regression, Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements, Minimax sparse principal subspace estimation in high dimensions, Sparse PCA: optimal rates and adaptive estimation, Random matrix theory in statistics: a review, The spectral norm of random inner-product kernel matrices, Approximation bounds for sparse principal component analysis, Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications, Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions, On semidefinite relaxations for the block model, Unnamed Item, Near-optimal stochastic approximation for online principal component estimation, Sparse power factorization: balancing peakiness and sample complexity, Computational and statistical tradeoffs via convex relaxation, Estimation of high-dimensional low-rank matrices, Estimation of (near) low-rank matrices with noise and high-dimensional scaling, Large Covariance Estimation by Thresholding Principal Orthogonal Complements, Sparse Principal Component Analysis in Hilbert Space, ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions, Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach, Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation, Sparse PCA: Convex Relaxations, Algorithms and Applications, Fast global convergence of gradient methods for high-dimensional statistical recovery, Sampled forms of functional PCA in reproducing kernel Hilbert spaces, Scale-Invariant Sparse PCA on High-Dimensional Meta-Elliptical Data, Principal Component Analysis of High-Frequency Data, On the computational tractability of statistical estimation on amenable graphs, Sparse principal component analysis with missing observations, Sparsistency and agnostic inference in sparse PCA, Rate-optimal posterior contraction for sparse PCA, Do semidefinite relaxations solve sparse PCA up to the information limit?

Uses Software

• DSPCA

Cites Work

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