Fetching the paper…
Reading the bibliography…
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size.
Probability Inequalities for Sums of Bounded Random Variables
W. Hoeffding · 1963
Earlier work this paper cites.
Maximum likelihood from incomplete data via the EM algorithm (with discussion)
A. Dempster, N. Laird, and D. Rubin · 1977
Earlier work this paper cites.
Least squares quantization in PCM
S. Lloyd · 1982
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. Kearns · 1998
Earlier work this paper cites.
Clustering objects on subsets of attributes
J. Friedman and J. Meulman · 2004
Earlier work this paper cites.
A spectral algorithm for learning mixture models
S. Vempala and G. Wang · 2004
Earlier work this paper cites.
Phase transition of the largest eigenvalue for non-null complex sample covariance matrices
J. Baik, G. Ben Arous, and S. Péché · 2005
Earlier work this paper cites.
A direct formulation of sparse PCA using semidefinite programming
A. d’Aspremont, L. El Ghaoui, M.I. Jordan, and G.R.G. Lanckriet · 2007
Earlier work this paper cites.
On Consistency and Sparsity for Principal Components Analysis in High Dimensions
I.M. Johnstone and A.Y. Lu · 2007
Earlier work this paper cites.
Penalized model-based clustering with application to variable selection
W. Pan and X. Shen · 2007
Earlier work this paper cites.
Approximating k-means-type clustering via semidefinite programming
J. Peng and Y. Wei · 2007
Earlier work this paper cites.
A tutorial on spectral clustering
U. Von Luxburg · 2007
Earlier work this paper cites.
Variable selection for model-based high-dimensional clustering and its application to microarray data
S. Wang and J. Zhu · 2008
Earlier work this paper cites.
High-dimensional analysis of semidefinite relaxations for sparse principal components
A.A. Amini and M.J. Wainwright · 2009
Earlier work this paper cites.
A framework for feature selection in clustering
D.M. Witten and R. Tibshirani · 2010
Earlier work this paper cites.
Statistical and computational tradeoffs in biclustering
S. Balakrishnan, M. Kolar, A. Rinaldo, A. Singh, and L. Wasserman · 2011
Earlier work this paper cites.
Minimax theory for high-dimensional gaussian mixtures with sparse mean separation
M. Azizyan, A. Singh, and L. Wasserman · 2013
Earlier work this paper cites.
Complexity theoretic lower bounds for sparse principal component detection
Q. Berthet and P. Rigollet · 2013
Earlier work this paper cites.
Optimal detection of sparse principal components in high dimension
Q. Berthet and P. Rigollet · 2013
Earlier work this paper cites.
Minimax sparse principal subspace estimation in high dimensions
J. Lei and V.Q. Vu · 2013
Earlier work this paper cites.
Sparse principal component analysis and iterative thresholding
Z. Ma · 2013
Earlier work this paper cites.
Fantope Projection and Selection: A near-optimal convex relaxation of Sparse PCA
V.Q. Vu, J. Cho, J. Lei, and K. Rohe · 2013
Earlier work this paper cites.
Model-based clustering of high-dimensional data: A review
C. Bouveyron and C. Brunet-Saumard · 2014
Cited alongside, same era.
Efficient sparse clustering of high-dimensional non-spherical gaussian mixtures
M. Azizyan, A. Singh, and L. L. Wasserman · 2015
Cited alongside, same era.
Tight bounds for learning a mixture of two Gaussians
M. Hardt and E. Price · 2015
Cited alongside, same era.
Do semidefinite relaxations solve sparse PCA up to the information limit?
R. Krauthgamer, B. Nadler, and D. Vilenchik · 2015
Cited alongside, same era.
Sparsistency and agnostic inference in sparse PCA
J. Lei and V.Q. Vu · 2015
Cited alongside, same era.
Sum-of-squares lower bounds for sparse PCA
T. Ma and A. Wigderson · 2015
Cited alongside, same era.
Lecture notes on high-dimensional statistics
P. Rigollet and J. Hütter · 2017
Later among the works it cites.
Detection and feature selection in sparse mixture models
N. Verzelen and E. Arias-Castro · 2017
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
M. Brennan, G. Bresler, and W. Huleihel · 2018
Later among the works it cites.
Slope meets Lasso: Improved oracle bounds and optimality
P.C. Bellec, G. Lecué, and A.B. Tsybakov · 2018
Later among the works it cites.
Curse of heterogeneity: Computational barriers in sparse mixture models and phase retrieval
J. Fan, H. Liu, Z. Wang, and Z. Yang · 2018
Later among the works it cites.
Statistical Inference and the Sum of Squares Method
S.B. Hopkins · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Computational barriers in minimax submatrix detection
Z. Ma and Y. Wu · 2015
Cited alongside, same era.
Sparse PCA via covariance thresholding
Y. Deshpande and A. Montanari · 2016
Cited alongside, same era.
Mathematical Foundations of Infinite-Dimensional Statistical Methods
E. Giné and R. Nickl · 2016
Cited alongside, same era.
Influential features PCA for high-dimensional clustering
J. Jin and W. Wang · 2016
Cited alongside, same era.
Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
T. Lesieur, C. De Bacco, J. Banks, F. Krzakala, C. Moore, and L. Zdeborová · 2016
Cited alongside, same era.
Statistical and Computational Guarantees of Lloyd’s Algorithm and its Variants
Y. Lu and H.H. Zhou · 2016
Cited alongside, same era.
Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
M. Brennan and G. Bresler · 2019
Later among the works it cites.
Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
M. Brennan and G. Bresler · 2019
Later among the works it cites.
A nearly tight sum-of-squares lower bound for the planted clique problem
B. Barak, S. Hopkins, J. Kelner, P.K. Kothari, A. Moitra, and A. Potechin · 2019
Later among the works it cites.
CHIME: Clustering of high-dimensional gaussian mixtures with EM algorithm and its optimality
T.T. Cai, J. Ma, and L. Zhang · 2019
Later among the works it cites.
Subexponential-Time Algorithms for Sparse PCA
Y. Ding, D. Kunisky, A.S. Wein, and A.S. Bandeira · 2019
Later among the works it cites.
Partial recovery bounds for clustering with the relaxed k-means
C. Giraud and N. Verzelen · 2019
Later among the works it cites.
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
D. Kunisky, A.S. Wein, and A.S. Bandeira · 2019
Later among the works it cites.
Sharp optimal recovery in the two component gaussian mixture model
M. Ndaoud · 2019
Later among the works it cites.
Estimation of wasserstein distances in the spiked transport model
J. Niles-Weed and P. Rigollet · 2019
Later among the works it cites.
Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O ( n ) O(\sqrt{n}) iterations
Y. Wu and H.H. Zhou · 2019
Later among the works it cites.
An ℓ p \ell_{p} theory of PCA and spectral clustering
E. Abbe, J. Fan, and K. Wang · 2020
Closest in time.
Reducibility and statistical-computational gaps from secret leakage
M. Brennan and G. Bresler · 2020
Closest in time.
Sparse principal component analysis via axis-aligned random projections
M. Gataric, T. Wang, and R.J. Samworth · 2020
Closest in time.
A greedy anytime algorithm for sparse PCA
G. Holtzman, A. Soffer, and D. Vilenchik · 2020
Closest in time.
Counterexamples to the low-degree conjecture
J. Holmgren and A.S. Wein · 2020
Closest in time.