Optimal detection of sparse principal components in high dimension
From MaRDI portal
Publication:385763
DOI10.1214/13-AOS1127zbMath1277.62155arXiv1202.5070WikidataQ59409960 ScholiaQ59409960MaRDI QIDQ385763
Quentin Berthet, Philippe Rigollet
Publication date: 11 December 2013
Published in: The Annals of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1202.5070
semidefinite relaxation; minimax lower bounds; high-dimensional detection; planted cliques; spiked covariance models
62H25: Factor analysis and principal components; correspondence analysis
90C22: Semidefinite programming
Related Items
An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation, Community Detection and Stochastic Block Models, ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions, Unnamed Item, Unnamed Item, Sequential subspace change point detection, Scale-Invariant Sparse PCA on High-Dimensional Meta-Elliptical Data, Gaussian determinantal processes: A new model for directionality in data, Using ℓ1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA, Finding a planted clique by adaptive probing, Proximal Distance Algorithms: Theory and Examples, Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation, Wald Statistics in high-dimensional PCA, Exploring dimension learning via a penalized probabilistic principal component analysis, Optimal multiple change-point detection for high-dimensional data, Solving sparse principal component analysis with global support, Free Energy Wells and Overlap Gap Property in Sparse PCA, Sparse principal component analysis for high‐dimensional stationary time series, Public-key encryption from homogeneous CLWE, Inference for low-rank models, On lower bounds for the bias-variance trade-off, Two-sample Hypothesis Testing for Inhomogeneous Random Graphs, Sharp minimax tests for large covariance matrices and adaptation, Asymptotic power of sphericity tests for high-dimensional data, Approximation bounds for sparse principal component analysis, Comment on ``Hypothesis testing by convex optimization, A robust test for sphericity of high-dimensional covariance matrices, Algorithmic thresholds for tensor PCA, Minimax estimation in sparse canonical correlation analysis, Estimation of functionals of sparse covariance matrices, Community detection in sparse random networks, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, Hypothesis testing for high-dimensional multinomials: a selective review, Multidimensional two-component Gaussian mixtures detection, Recent developments in high dimensional covariance estimation and its related issues, a review, Bayesian inference for spectral projectors of the covariance matrix, Testing the order of a population spectral distribution for high-dimensional data, Optimal rates of statistical seriation, The spectral norm of random inner-product kernel matrices, Notes on computational-to-statistical gaps: predictions using statistical physics, Combinatorial inference for graphical models, High-dimensional covariance matrices in elliptical distributions with application to spherical test, Robust covariance estimation for approximate factor models, Detecting Markov random fields hidden in white noise, Projection tests for high-dimensional spiked covariance matrices, Optimality and sub-optimality of PCA. I: Spiked random matrix models, Slope meets Lasso: improved oracle bounds and optimality, Finding a large submatrix of a Gaussian random matrix, Sparse power factorization: balancing peakiness and sample complexity, Minimax rates in sparse, high-dimensional change point detection, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Isotonic regression with unknown permutations: statistics, computation and adaptation, Tensor clustering with planted structures: statistical optimality and computational limits, Testing for principal component directions under weak identifiability, Efficient estimation of linear functionals of principal components, Sparse signal reconstruction via the approximations of \(\ell_0\) quasinorm, Fundamental limits of detection in the spiked Wigner model, Statistical and computational limits for sparse matrix detection, Phase transitions for detecting latent geometry in random graphs, The limits of the sample spiked eigenvalues for a high-dimensional generalized Fisher matrix and its applications, Tests for covariance matrices in high dimension with less sample size, Optimal testing for planted satisfiability problems, Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting, Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach, Hypothesis testing for densities and high-dimensional multinomials: sharp local minimax rates, Sparse principal component analysis with missing observations, Sparsistency and agnostic inference in sparse PCA, Optimal estimation and rank detection for sparse spiked covariance matrices, Detecting positive correlations in a multivariate sample, Computational barriers in minimax submatrix detection, 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, Sparse PCA: optimal rates and adaptive estimation, Community detection in dense random networks, On the optimality of sliced inverse regression in high dimensions, Sharp detection boundaries on testing dense subhypergraph, Matrix means and a novel high-dimensional shrinkage phenomenon, Estimation of Wasserstein distances in the spiked transport model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse principal component analysis and iterative thresholding
- Minimax bounds for sparse PCA with noisy high-dimensional data
- Asymptotic power of sphericity tests for high-dimensional data
- Detection of correlations
- On combinatorial testing problems
- Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
- High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
- An augmented Lagrangian approach for sparse principal component analysis
- Nuclear norm minimization for the planted clique and biclique problems
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Optimal rates of convergence for covariance matrix estimation
- Covariance regularization by thresholding
- Operator norm consistent estimation of large-dimensional sparse covariance matrices
- Finite sample approximation results for principal component analysis: A matrix perturbation approach
- On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
- A limit theorem for the norm of random matrices
- Expected complexity of graph partitioning problems
- Introductory lectures on convex optimization. A basic course.
- Hiding cliques for cryptographic security
- Approximating the independence number and the chromatic number in expected polynomial time
- Adaptive estimation of a quadratic functional by model selection.
- On the distribution of the largest eigenvalue in principal components analysis
- Non-asymptotic minimax rates of testing in signal detection
- Higher criticism for detecting sparse heterogeneous mixtures.
- On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix
- Consistency of sparse PCA in high dimension, low sample size contexts
- Minimax risks for sparse regressions: ultra-high dimensional phenomenons
- Detection boundary in sparse regression
- Detection of an anomalous cluster in a network
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Sparse PCA: optimal rates and adaptive estimation
- Eigenvalues of large sample covariance matrices of spiked population models
- Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
- Generalized power method for sparse principal component analysis
- Hidden Cliques and the Certification of the Restricted Isometry Property
- Certifying the Restricted Isometry Property is Hard
- How Hard Is It to Approximate the Best Nash Equilibrium?
- The largest eigenvalues of sample covariance matrices for a spiked population: Diagonal case
- Random Tensors and Planted Cliques
- Large Cliques Elude the Metropolis Process
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Finding and certifying a large hidden clique in a semirandom graph
- Computational and statistical tradeoffs via convex relaxation
- On Consistency and Sparsity for Principal Components Analysis in High Dimensions
- Finding Hidden Cliques in Linear Time with High Probability
- Statistical algorithms and a lower bound for detecting planted cliques
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Introduction to nonparametric estimation