Fetching the paper…
Reading the bibliography…
This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method.
Über die zerlegung definiter funktionen in quadrate
Emil Artin · 1927
Earlier work this paper cites.
Anneaux préordonnés
Jean-Louis Krivine · 1964
Earlier work this paper cites.
A nullstellensatz and a positivstellensatz in semialgebraic geometry
Gilbert Stengle · 1974
Earlier work this paper cites.
An approach to obtaining global extremums in polynomial mathematical programming problems
N.Z. Shor · 1987
Earlier work this paper cites.
A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems
Hanif D. Sherali and Warren P. Adams · 1990
Earlier work this paper cites.
Cones of matrices and set-functions and 0–1 optimization
L. Lovász and A. Schrijver · 1991
Earlier work this paper cites.
Thek-moment problem for compact semi-algebraic sets
Konrad Schmüdgen · 1991
Earlier work this paper cites.
Positive polynomials on compact semi-algebraic sets
Mihai Putinar · 1993
Earlier work this paper cites.
De-noising by soft-thresholding
D. L. Donoho · 1995
Earlier work this paper cites.
Decoupling inequalities for the tail probabilities of multivariate u-statistics
Victor H. de la Pena and S. J. Montgomery-Smith · 1995
Earlier work this paper cites.
Computational sample complexity
Scott Decatur, Oded Goldreich, and Dana Ron · 1997
Earlier work this paper cites.
Minimax estimation via wavelet shrinkage
David L. Donoho and Iain M. Johnstone · 1998
Earlier work this paper cites.
Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays
U. Alon, N. Barkai, D. A. Notterman, K. Gish, S. Ybarra, D. Mack, and A. J. Levine · 1999
Earlier work this paper cites.
Squared functional systems and optimization problems
Yurii Nesterov · 2000
Earlier work this paper cites.
Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization
Pablo A. Parrilo · 2000
Earlier work this paper cites.
Computational sample complexity and attribute-efficient learning
Rocco A. Servedio · 2000
Earlier work this paper cites.
Weak Convergence and Empirical Processes: With Applications to Statistics (Springer Series in Statistics)
Aad van der Vaart and Jon Wellner · 2000
Earlier work this paper cites.
Complexity of positivstellensatz proofs for the knapsack
D. Grigoriev · 2001
Earlier work this paper cites.
Linear lower bound on degrees of positivstellensatz calculus proofs for the parity
Dima Grigoriev · 2001
Cited alongside, same era.
On the distribution of the largest eigenvalue in principal components analysis
Iain M. Johnstone · 2001
Cited alongside, same era.
Global optimization with polynomials and the problem of moments
Jean B. Lasserre · 2001
Cited alongside, same era.
Function estimation and gaussian sequence models
IM Johnstone · 2002
Cited alongside, same era.
A direct formulation for sparse pca using semidefinite programming
Alexandre d’Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet · 2007
Cited alongside, same era.
Linear level lasserre lower bounds for certain k-csps
Grant Schoenebeck · 2008
Cited alongside, same era.
Sparse principal component analysis and iterative thresholding
Zongming Ma · 2013
Later among the works it cites.
Minimax sparse principal subspace estimation in high dimensions
Vincent Q. Vu and Jing Lei · 2013
Later among the works it cites.
Truncated power method for sparse eigenvalue problems
Xiao-Tong Yuan and Tong Zhang · 2013
Later among the works it cites.
Rounding sum-of-squares relaxations
Boaz Barak, Jonathan A. Kelner, and David Steurer · 2014
Later among the works it cites.
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak and David Steurer · 2014
Later among the works it cites.
Sparse PCA via covariance thresholding
Yash Deshpande and Andrea Montanari · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
High-dimensional analysis of semidefinite relaxations for sparse principal components
Arash A. Amini and Martin J. Wainwright · 2009
Cited alongside, same era.
On consistency and sparsity for principal components analysis in high dimensions
Iain M. Johnstone and Arthur Yu Lu · 2009
Cited alongside, same era.
Sums of squares, moment matrices and optimization over polynomials
Monique Laurent · 2009
Cited alongside, same era.
Structured sparse principal component analysis
Rodolphe Jenatton, Guillaume Obozinski, and Francis R. Bach · 2010
Cited alongside, same era.
Adaptive elastic-net sparse principal component analysis for pathway association testing
Xi Chen · 2011
Cited alongside, same era.
Augmented sparse principal component analysis for high dimensional data
Debashis Paul and Iain M Johnstone · 2012
Cited alongside, same era.
Sparse CCA: Adaptive Estimation and Computational Barriers
C. Gao, Z. Ma, and H. H. Zhou · 2014
Later among the works it cites.
personal communication, 2014
Tengyu Ma and Philippe Rigollet · 2014
Later among the works it cites.
Tighten after relax: Minimax-optimal sparse PCA in polynomial time
Zhaoran Wang, Huanran Lu, and Han Liu · 2014
Later among the works it cites.
Dictionary learning and tensor decomposition via the sum-of-squares method
Boaz Barak, Jonathan A. Kelner, and David Steurer · 2015
Closest in time.
Tensor prediction, rademacher complexity and random 3-xor
Boaz Barak and Ankur Moitra · 2015
Closest in time.
Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
Y. Deshpande and A. Montanari · 2015
Closest in time.
Samuel B. Hopkins, Pravesh K. Kothari, and Aaron Potechin · 2015
Closest in time.
Do semidefinite relaxations solve sparse pca up to the information limit?
Robert Krauthgamer, Boaz Nadler, and Dan Vilenchik · 2015
Closest in time.
An introduction to polynomial and semi-algebraic optimization
Jean Bernard Lasserre · 2015
Closest in time.
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, and Avi Wigderson · 2015
Closest in time.
Tight lower bounds for planted clique in the degree-4 SOS program
Prasad Raghavendra and Tselil Schramm · 2015
Closest in time.
Statistical Limits of Convex Relaxations
Z. Wang, Q. Gu, and H. Liu · 2015
Closest in time.