Statistical and computational trade-offs in estimation of sparse principal components
From MaRDI portal
Publication:342660
DOI10.1214/15-AOS1369zbMath1349.62254arXiv1408.5369OpenAlexW3104095169MaRDI QIDQ342660
Tengyao Wang, Richard J. Samworth, Quentin Berthet
Publication date: 18 November 2016
Published in: The Annals of Statistics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.5369
polynomial time algorithmsparse principal component analysiscomputational lower boundsplanted clique problem
Factor analysis and principal components; correspondence analysis (62H25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (23)
Isotonic regression with unknown permutations: statistics, computation and adaptation ⋮ Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Discussion of the paper ‘A review of distributed statistical inference’ ⋮ Wald Statistics in high-dimensional PCA ⋮ High-resolution signal recovery via generalized sampling and functional principal component analysis ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Sparse SIR: optimal rates and adaptive estimation ⋮ Efficient estimation of linear functionals of principal components ⋮ Using ℓ1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA ⋮ Minimax estimation in sparse canonical correlation analysis ⋮ Free Energy Wells and Overlap Gap Property in Sparse PCA ⋮ Sparse principal component analysis for high‐dimensional stationary time series ⋮ Statistical and computational limits for sparse matrix detection ⋮ High Dimensional Change Point Estimation via Sparse Projection ⋮ Unnamed Item ⋮ Sparse power factorization: balancing peakiness and sample complexity ⋮ Optimal testing for planted satisfiability problems ⋮ Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation ⋮ Statistical and computational tradeoff in genetic algorithm-based estimation ⋮ Exact recovery in the Ising blockmodel ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ A Unifying Tutorial on Approximate Message Passing ⋮ A sieve stochastic gradient descent estimator for online nonparametric regression in Sobolev ellipsoids
This page was built for publication: Statistical and computational trade-offs in estimation of sparse principal components
