Sublinear Time Eigenvalue Approximation via Random Sampling
summary
Presents a simple algorithm that samples a random principal submatrix of size about O(log^3 n/ε^3) × O(log^3 n/ε^3), scales it, and uses its eigenvalues to approximate all n eigenvalues of a symmetric n×n matrix up to additive error ±ε n·||A||_∞; shows improved bounds ε·√(nnz(A)) and ε·||A||_F under sparsity- or norm-proportional row sampling, requires a novel “zeroing out” of high-variance entries for nonuniform sampling, and proves new eigenvalue-concentration lemmas.
AI-written summary · about
chapters (9)
- 0:00Sublinear eigenvalue approximation
- 2:11Problem definition and motivation
- 8:59Simple algorithm via random submatrices
- 12:15Interpreting approximate eigenvalues
- 19:02Related work in spectral algorithms
- 24:04Proof overview: eigenvalue decomposition
- 36:22Nonuniform sampling challenges
- 41:55Open questions and future work
- 45:34Q&A
related talks
01h 02mCounting Subgraphs in Sublinear Time
33mLinear and sublinear algorithms for graphlet sampling
35mDistributed Models for Private Analysis of Graph Data
25mErasure-Resilient Sublinear-Time Graph Algorithms
01h 02mThe Complexity of Dynamic Least-Squares Regression
01h 06mSampling in Query Evaluation 1
01h 02mGaussian Free Fields and Computing the Cover Time
26mLow-bandwidth recovery of linear functions of Reed-Solomon-encoded data