Fetching the paper…
Reading the bibliography…
We study the computational cost of recovering a unit-norm sparse principal component $x \in \mathbb{R}^n$ planted in a random matrix, in either the Wigner or Wishart spiked model (observing either $W + \lambda xx^\top$ with $W$ drawn from the Gaussian orthogonal ensemble, or $N$ independent samples from $\mathcal{N}(0, I_n + \beta xx^\top)$, respectively).
Large cliques elude the Metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
Beatrice Laurent and Pascal Massart · 2000
Earlier work this paper cites.
On the distribution of the largest eigenvalue in principal components analysis
Iain M Johnstone · 2001
Earlier work this paper cites.
Spectral partitioning of random graphs
Frank McSherry · 2001
Earlier work this paper cites.
Sparse principal components analysis
Iain M. Johnstone and Arthur Yu Lu · 2004
Earlier work this paper cites.
Asymptotics of the leading sample eigenvalues for a spiked covariance model
Debashis Paul · 2004
Earlier work this paper cites.
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Jinho Baik, Gérard Ben Arous, and Sandrine Péché · 2005
Earlier work this paper cites.
A direct formulation for sparse PCA using semidefinite programming
Alexandre d’Aspremont, Laurent El Ghaoui, Michael I Jordan, and Gert R Lanckriet · 2005
Earlier work this paper cites.
Eigenvalues of large sample covariance matrices of spiked population models
Jinho Baik and Jack W Silverstein · 2006
Earlier work this paper cites.
Spectral bounds for sparse PCA: Exact and greedy algorithms
Baback Moghaddam, Yair Weiss, and Shai Avidan · 2006
Earlier work this paper cites.
The largest eigenvalue of small rank perturbations of hermitian random matrices
Sandrine Péché · 2006
Earlier work this paper cites.
Sparse principal component analysis
Hui Zou, Trevor Hastie, and Robert Tibshirani · 2006
Earlier work this paper cites.
The largest eigenvalue of rank one deformation of large wigner matrices
Delphine Féral and Sandrine Péché · 2007
Earlier work this paper cites.
Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
Debashis Paul · 2007
Earlier work this paper cites.
High-dimensional analysis of semidefinite relaxations for sparse principal components
Arash A Amini and Martin J Wainwright · 2008
Earlier work this paper cites.
Optimal solutions for sparse principal component analysis
Alexandre d’Aspremont, Francis Bach, and Laurent El Ghaoui · 2008
Earlier work this paper cites.
Finite sample approximation results for principal component analysis: A matrix perturbation approach
Boaz Nadler · 2008
Earlier work this paper cites.
The largest eigenvalues of finite rank deformation of large wigner matrices: convergence and nonuniversality of the fluctuations
Mireille Capitaine, Catherine Donati-Martin, and Delphine Féral · 2009
Earlier work this paper cites.
On consistency and sparsity for principal components analysis in high dimensions
Iain M Johnstone and Arthur Yu Lu · 2009
Earlier work this paper cites.
A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
Daniela M Witten, Robert Tibshirani, and Trevor Hastie · 2009
Earlier work this paper cites.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Earlier work this paper cites.
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
Florent Benaych-Georges and Raj Rao Nadakuditi · 2011
Earlier work this paper cites.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová · 2011
Earlier work this paper cites.
Inference and phase transitions in the detection of modules in sparse networks
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová · 2011
Earlier work this paper cites.
Angular synchronization by eigenvectors and semidefinite programming
Amit Singer · 2011
Earlier work this paper cites.
Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming
Amit Singer and Yoel Shkolnisky · 2011
Earlier work this paper cites.
Augmented sparse principal component analysis for high dimensional data
Debashis Paul and Iain M Johnstone · 2012
Earlier work this paper cites.
Minimax rates of estimation for sparse PCA in high dimensions
Vincent Vu and Jing Lei · 2012
Earlier work this paper cites.
Computational lower bounds for sparse PCA
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Optimal detection of sparse principal components in high dimension
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Sparse PCA: Optimal rates and adaptive estimation
T Tony Cai, Zongming Ma, and Yihong Wu · 2013
Cited alongside, same era.
The isotropic semicircle law and deformation of wigner matrices
Antti Knowles and Jun Yin · 2013
Cited alongside, same era.
Asymptotic power of sphericity tests for high-dimensional data
Alexei Onatski, Marcelo J Moreira, and Marc Hallin · 2013
Cited alongside, same era.
On finite rank deformations of wigner matrices
Alessandro Pizzo, David Renfrew, and Alexander Soshnikov · 2013
Community detection and stochastic block models: recent developments
Emmanuel Abbe · 2017
Later among the works it cites.
Finite size corrections and likelihood ratio fluctuations in the spiked wigner model
Ahmed El Alaoui, Florent Krzakala, and Michael I Jordan · 2017
Later among the works it cites.
The power of sum-of-squares for detecting hidden structures
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer · 2017
Later among the works it cites.
Bayesian estimation from few samples: community detection and related problems
Samuel B Hopkins and David Steurer · 2017
Later among the works it cites.
Fundamental limits of low-rank matrix estimation: the non-symmetric case
Léo Miolane · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Information-theoretically optimal sparse PCA
Yash Deshpande and Andrea Montanari · 2014
Cited alongside, same era.
Sparse PCA via covariance thresholding
Yash Deshpande and Andrea Montanari · 2014
Cited alongside, same era.
Hidden cliques and the certification of the restricted isometry property
Pascal Koiran and Anastasios Zouzias · 2014
Cited alongside, same era.
A statistical model for tensor PCA
Emile Richard and Andrea Montanari · 2014
Cited alongside, same era.
Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems
Yash Deshpande and Andrea Montanari · 2015
Cited alongside, same era.
Tensor principal component analysis via sum-of-square proofs
Samuel B Hopkins, Jonathan Shi, and David Steurer · 2015
Cited alongside, same era.
The computer science and physics of community detection: Landscapes, phase transitions, and hardness
Cristopher Moore · 2017
Later among the works it cites.
Strongly refuting random CSPs below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2017
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2018
Later among the works it cites.
Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
Jess Banks, Cristopher Moore, Roman Vershynin, Nicolas Verzelen, and Jiaming Xu · 2018
Later among the works it cites.
Sparse PCA from sparse linear regression
Guy Bresler, Sung Min Park, and Madalina Persu · 2018
Later among the works it cites.
Estimation in the spiked wigner model: A short proof of the replica formula
Ahmed El Alaoui and Florent Krzakala · 2018
Later among the works it cites.
Fundamental limits of detection in the spiked wigner model
Ahmed El Alaoui, Florent Krzakala, and Michael I Jordan · 2018
Later among the works it cites.
Statistical Inference and the Sum of Squares Method
Samuel Hopkins · 2018
Later among the works it cites.
Phase transitions in spiked matrix estimation: information-theoretic analysis
Léo Miolane · 2018
Later among the works it cites.
Message-passing algorithms for synchronization problems over compact groups
Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra · 2018
Later among the works it cites.
Optimality and sub-optimality of PCA I: Spiked random matrix models
Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra · 2018
Later among the works it cites.
High-dimensional estimation via sum-of-squares proofs
Prasad Raghavendra, Tselil Schramm, and David Steurer · 2018
Later among the works it cites.
A simple SVD algorithm for finding hidden partitions
Van Vu · 2018
Later among the works it cites.
Tensor SVD: Statistical and computational limits
Anru Zhang and Dong Xia · 2018
Later among the works it cites.
Optimal average-case reductions to sparse PCA: From weak assumptions to strong hardness
Matthew Brennan and Guy Bresler · 2019
Closest in time.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin · 2019
Closest in time.
Computational hardness of certifying bounds on constrained PCA problems
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 2019
Closest in time.
A greedy anytime algorithm for sparse PCA
Guy Holtzman, Adam Soffer, and Dan Vilenchik · 2019
Closest in time.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Closest in time.
Fundamental limits of symmetric low-rank matrix estimation
Marc Lelarge and Léo Miolane · 2019
Closest in time.
The Kikuchi hierarchy and tensor PCA
Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore · 2019
Closest in time.
Reducibility and statistical-computational gaps from secret leakage
Matthew Brennan and Guy Bresler · 2020
Closest in time.