Input Sparsity and Hardness for Linear Algebra Problems
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Proves approximate Frobenius low-rank can run in input-sparsity time by sketching: multiply A by a sparse count sketch (one nonzero per column), project rows into O(k/ε) dimensions, then solve smaller SVD — overall time roughly nnz(A)+poly(k/ε)(n+d). For robust p<2 gives same input-sparse front end but an exponential-in-k/ε final search step, and shows an n^k lower bound under ETH when ε=1/d. Shows spectral low-rank currently needs about k·nnz(A)·log(1/ε) via the block power method and its hardness remains open.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:32Low Polynomial Time Linear Algebra Problems
- 3:13Talk Outline
- 5:06What is a good low rank approximation?
- 8:15Sketch and solve paradigm [S]
- 11:14What is the matrix S?
- 14:58Sketch and solve for regression
- 17:14Robust Forms of Low Rank Approximation
- 19:26Prior Work on this Cost Function
- 21:46Our Results for Robust Low Rank Approximation
- 23:36Intuition for the Robust Case
- 26:34Our Algorithm
- 30:59Connecting linear algebra to graph problems
- 35:51Spectral Low Rank Approximation
- 41:27Conclusion