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 programming; random matrices; spectral analysis; convex relaxation; sparsity; high-dimensional statistics; principal components analysis; spiked covariance ensembles; Wishart ensembles

Mathematics Subject Classification ID

62F12: Asymptotic properties of parametric estimators

62H25: Factor analysis and principal components; correspondence analysis

90C90: Applications of mathematical programming

60F10: Large deviations

Related Items

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

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