Research map / Learning theory and algorithms / Matrix and tensor methods
Asymptotics for Sketching in Least Squares Regression
Edgar Dobriban, Sifan Liu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use orthogonal Haar projection instead of iid projection | Sketch-and-solve least squares · Linear regression, arbitrary X; asymptotic VE | VE: VE_iid=VE_Haar+1 | Improved |
| Use SRHT instead of iid projection | Sketch-and-solve least squares · Linear regression, arbitrary X; asymptotic VE | VE: VE_iid=VE_Hadamard+1 | Improved |
| Use uniform sampling instead of orthogonal projection | Sketch-and-solve least squares · Rotationally invariant X | VE | No clear effect |
| Use uniform sampling on non-rotationally-invariant data | Sketch-and-solve least squares · Million Song and New York flights datasets | RE | Mixed |
| Increase projection dimension r | Sketch-and-solve least squares · Linear regression | VE | Improved |
| Use Gaussian projection even when sample size is not reduced | Ordinary least squares · Linear regression | VE: 2 | Hurt |
Closest papers by meaning
- A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares (JMLR 2016 · similarity 0.92)
- Optimal Iterative Sketching Methods with the Subsampled Randomized Hadamard Transform (NeurIPS 2020 · similarity 0.89)
- Iterative Hessian Sketch: Fast and Accurate Solution Approximation for Constrained Least-Squares (JMLR 2016 · similarity 0.89)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.87)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.87)
- Matrix Product Sketching via Coordinated Sampling (ICLR 2025 · similarity 0.86)
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.
