Fetching the paper…
Reading the bibliography…
We prove a \emph{query complexity} lower bound on rank-one principal component analysis (PCA).
A class of measures of informativity of observation channels
Imre Csiszár · 1972
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chin Yao · 1977
Earlier work this paper cites.
Phase retrieval algorithms: a comparison
James R Fienup · 1982
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadii Nemirovskii, David Borisovich Yudin, and Edgar Ronald Dawson · 1983
Earlier work this paper cites.
Some np-complete problems in quadratic and nonlinear programming
Katta G Murty and Santosh N Kabadi · 1987
Earlier work this paper cites.
Applied numerical linear algebra
James W Demmel · 1997
Earlier work this paper cites.
Sparse coding with an overcomplete basis set: A strategy employed by v1?
Bruno A Olshausen and David J Field · 1997
Earlier work this paper cites.
Introductory lectures on convex programming volume i: Basic course
Yu Nesterov · 1998
Earlier work this paper cites.
Learning the parts of objects by non-negative matrix factorization
Daniel D Lee and H Sebastian Seung · 1999
Earlier work this paper cites.
The pagerank citation ranking: Bringing order to the web
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd · 1999
Earlier work this paper cites.
Principal component analysis
Ian Jolliffe · 2002
Earlier work this paper cites.
Convex optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Fast maximum margin matrix factorization for collaborative prediction
Jasson DM Rennie and Nathan Srebro · 2005
Earlier work this paper cites.
Random k-sat: Two moments suffice to cross a sharp threshold
Dimitris Achlioptas and Cristopher Moore · 2006
Earlier work this paper cites.
Foundations of modern probability
Olav Kallenberg · 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.
Spectral graph theory and its applications
Daniel A Spielman · 2007
Earlier work this paper cites.
Large-scale parallel collaborative filtering for the netflix prize
Yunhong Zhou, Dennis Wilkinson, Robert Schreiber, and Rong Pan · 2008
Earlier work this paper cites.
Information-theoretic lower bounds on the oracle complexity of convex optimization
Alekh Agarwal, Martin J Wainwright, Peter L Bartlett, and Pradeep K Ravikumar · 2009
Earlier work this paper cites.
Introduction to nonparametric estimation. revised and extended from the 2004 french original. translated by vladimir zaiats, 2009
Alexandre B Tsybakov · 2009
Earlier work this paper cites.
On combinatorial testing problems
Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, Gábor Lugosi, et al · 2010
Earlier work this paper cites.
An introduction to random matrices
Greg W Anderson, Alice Guionnet, and Ofer Zeitouni · 2010
Earlier work this paper cites.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Earlier work this paper cites.
Lower bounds for the minimax risk using f-divergences, and applications
Adityanand Guntuboyina · 2011
Earlier work this paper cites.
Computing a nonnegative matrix factorization–provably
Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra · 2012
Earlier work this paper cites.
Elements of information theory
Thomas M Cover and Joy A Thomas · 2012
Earlier work this paper cites.
Matrix analysis
Roger A Horn and Charles R Johnson · 2012
Earlier work this paper cites.
Query complexity of derivative-free optimization
Kevin G Jamieson, Robert Nowak, and Ben Recht · 2012
Earlier work this paper cites.
Imagenet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton · 2012
Earlier work this paper cites.
Phi-divergences, sufficiency, bayes sufficiency, and deficiency
Friedrich Liese · 2012
Cited alongside, same era.
On the fundamental limits of adaptive sensing
Ery Arias-Castro, Emmanuel J Candes, and Mark A Davenport · 2013
Cited alongside, same era.
Concentration inequalities: A nonasymptotic theory of independence
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart · 2013
Cited alongside, same era.
Low rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2013
Cited alongside, same era.
Distance-based and continuum fano inequalities with applications to statistical estimation
John C Duchi and Martin J Wainwright · 2013
Cited alongside, same era.
Phase retrieval using alternating minimization
Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi · 2013
Finding approximate local minima for nonconvex optimization in linear time
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma · 2016
Later among the works it cites.
On lower and upper bounds in smooth and strongly convex optimization
Yossi Arjevani, Shai Shalev-Shwartz, and Ohad Shamir · 2016
Later among the works it cites.
Oracle complexity of second-order methods for finite-sum problems
Yossi Arjevani and Ohad Shamir · 2016
Later among the works it cites.
Communication efficient distributed kernel principal component analysis
Maria-Florina Balcan, Yingyu Liang, Le Song, David Woodruff, and Bo Xie · 2016
Later among the works it cites.
Sharp nonasymptotic bounds on the norm of random matrices with independent entries
Afonso S Bandeira, Ramon van Handel, et al · 2016
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.
Lower bounds for adaptive sparse recovery
Eric Price and David P Woodruff · 2013
Cited alongside, same era.
Neural machine translation by jointly learning to align and translate
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio · 2014
Cited alongside, same era.
Adaptive sensing performance lower bounds for sparse signal detection and support estimation
Rui M Castro et al · 2014
Cited alongside, same era.
On sketching matrix norms and the top singular vector
Yi Li, Huy L Nguyên, and David P Woodruff · 2014
Cited alongside, same era.
Time lower bounds for nonadaptive turnstile streaming algorithms
Jelani Nelson · 2014
Cited alongside, same era.
On deterministic sketching and streaming for sparse recovery and norm estimation
Jelani Nelson, Huy L Nguyẽn, and David P Woodruff · 2014
Cited alongside, same era.
Dropping convexity for faster semi-definite optimization
Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi · 2016
Later among the works it cites.
Global optimality of local search for low rank matrix recovery
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro · 2016
Later among the works it cites.
Nonconvex phase synchronization
Nicolas Boumal · 2016
Later among the works it cites.
Optimal principal component analysis in distributed and streaming models
Christos Boutsidis, David P Woodruff, and Peilin Zhong · 2016
Later among the works it cites.
Gradient descent efficiently finds the cubic-regularized non-convex newton step
Yair Carmon and John C Duchi · 2016
Later among the works it cites.
On bayes risk lower bounds
Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang · 2016
Later among the works it cites.
Faster eigenvector computation via shift-and-invert preconditioning
Dan Garber, Elad Hazan, Chi Jin, Sham M Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford · 2016
Later among the works it cites.
Optimal best arm identification with fixed confidence
Aurélien Garivier and Emilie Kaufmann · 2016
Later among the works it cites.
Matrix completion has no spurious local minimum
Rong Ge, Jason D Lee, and Tengyu Ma · 2016
Later among the works it cites.
Gradient descent only converges to minimizers
Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht · 2016
Later among the works it cites.
Fundamental limits of symmetric low-rank matrix estimation
Marc Lelarge and Léo Miolane · 2016
Later among the works it cites.
On approximating functions of the singular values in a stream
Yi Li and David P Woodruff · 2016
Later among the works it cites.
Weighted low rank approximations with provable guarantees
Ilya P Razenshteyn, Zhao Song, and David P Woodruff · 2016
Later among the works it cites.
Low rank approximation with entrywise l1 -norm error
Zhao Song, David P Woodruff, and Peilin Zhong · 2016
Later among the works it cites.
A geometric analysis of phase retrieval
Ju Sun, Qing Qu, and John Wright · 2016
Later among the works it cites.
Lifting randomized query complexity to randomized communication complexity
Anurag Anshu, Naresh B Goud, Rahul Jain, Srijita Kundu, and Priyanka Mukhopadhyay · 2017
Closest in time.
Adaptive compressed sensing for support recovery of structured sparse sets
Rui M Castro and Ervin Tánczos · 2017
Closest in time.
Low-rank psd approximation in input-sparsity time
Kenneth L Clarkson and David P Woodruff · 2017
Closest in time.
Communication-efficient algorithms for distributed stochastic principal component analysis
Dan Garber, Ohad Shamir, and Nathan Srebro · 2017
Closest in time.
How to escape saddle points efficiently
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan · 2017
Closest in time.
Optimal lower bounds for universal relation, samplers, and finding duplicates
Jelani Nelson, Jakub Pachocki, and Zhengyu Wang · 2017
Closest in time.
The simulator: Understanding adaptive sampling in the moderate-confidence regime
Max Simchowitz, Kevin Jamieson, and Benjamin Recht · 2017
Closest in time.
Complete dictionary recovery over the sphere i: Overview and the geometric picture
Ju Sun, Qing Qu, and John Wright · 2017
Closest in time.