Tight query complexity lower bounds for PCA via finite sample deformed wigner law

DOI10.1145/3188745.3188796zbMath1428.68168arXiv1804.01221OpenAlexW2963794660MaRDI QIDQ5230378

Max Simchowitz, Benjamin Recht, Ahmed El Alaoui

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.01221

zbMATH Keywords

optimizationlower boundsrandom matrix theoryPCAquery complexity

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Random matrices (algebraic aspects) (15B52) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

First-Order Methods for Nonconvex Quadratic Minimization ⋮ Lower bounds for finding stationary points II: first-order methods ⋮ The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output ⋮ Uniform Error Estimates for the Lanczos Method ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Randomized block Krylov methods for approximating extreme eigenvalues ⋮ Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step

This page was built for publication: Tight query complexity lower bounds for PCA via finite sample deformed wigner law