Research map / Learning theory and algorithms / Matrix and tensor methods
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives tight Θ(k²/ε⁴) bilinear sketch bounds for Frobenius residual error estimation (improving O(k²/ε⁶)), and sketching/sparse-recovery bounds for ℓp residual norms with p>2.
Problem
Estimating the rank-k residual error ||A−A_k||_F and the k-sparse residual ||x−x_k||_p (p>2) from a linear sketch, with the goal of determining sketch size lower and upper bounds.
Approach
Shows that bilinear sketches SAT with S and T being rank-k projection-cost-preserving sketches (e.g., sparse CountSketch/OSNAP compositions) suffice, improving the dimension to O(k/ε²) per side and giving matching lower bounds; for ℓp (p>2) residual estimation, combines CountSketch top-k candidate selection with a parallel ℓp norm estimator to get Õ(k^{2/p} n^{1-2/p}) space.
Key results
- Ours with OSNAP sketches achieves error comparable to AN13 (e.g., 0.146 vs 0.135 at k=5, m=50 on MovieLens) while being roughly 4 to 7 times faster to evaluate.
- Theoretical upper bound improved from O(k²/ε⁶) to O(k²/ε⁴) for bilinear sketches, with a matching Ω(k/ε²) per-side lower bound for bilinear sketches.
- For ℓp (p>2) residual estimation, the algorithm uses Õ(ε^{-2p/(p-1)} k^{2/p} n^{1-2/p}) space and sparse recovery has an Ω(k^{2/p} n^{1-2/p}) lower bound up to polylog factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OSNAP sketch matrices with s=2 instead of random Gaussian sketch matrices at the same sketch size | Residual error estimation for low-rank approximation · MovieLens 100K and KOS | error ε: MovieLens 100K, m = 50: 0.146 vs 0.135 (k=5), 0.295 vs 0.287 (k=10), 0.545 vs 0.541 (k=20); KOS, m = 50: 0.135 vs 0.141 | No clear effect |
| Use OSNAP sketch matrices with s=2 instead of random Gaussian sketch matrices | Residual error estimation for low-rank approximation · MovieLens 100K and KOS | runtime: MovieLens 100K, m = 50: 0.105s vs 0.377s (k=5); KOS, m = 50: 0.117s vs 0.399s (k=5) | Helped |
Surprising findings
- Sparse OSNAP sketches (s=2) match the accuracy of dense Gaussian sketches of prior work while being much faster.
Limitations
- For the ℓp residual norm problem, the upper and lower bounds are only tight up to polylog factors and constant ε; the exact sketching dimension for residual norm estimation is unresolved.
- Lower bound for general residual estimation is only shown for bilinear and linear sketches with specific hard distributions; the paper states it does not resolve the sketching dimension for residual norm estimation.
- Experiments are small-scale (KOS, MovieLens 100K) on a CPU-only Python setup.
Experimental setup
Datasets: KOS blog word-frequency matrix (UCI Bag of Words) MovieLens 100K
Benchmarks: KOS MovieLens 100K
Metrics: relative error epsilon vs ||A-A_k||_F runtime (s)
Baselines: Andoni et al. 2013 (AN13) Gaussian bilinear sketch Randomized SVD Streaming LRA Full SVD
Builds on: Andoni et al. SODA 2013 residual estimation projection-cost preserving sketches (Cohen et al.) CountSketch OSNAP
Closest papers by meaning
- Decentralized sketching of low rank matrices (NeurIPS 2019 · similarity 0.90)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.89)
- Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform (NeurIPS 2020 · similarity 0.89)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.88)
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.88)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.