Research map / Learning theory and algorithms / Matrix and tensor methods
An Analysis of Sketched IRLS for Accelerated Sparse Residual Regression
Daichi Iwata, Michael Waechter, Wen-Yan Lin, Yasuyuki Matsushita
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 |
|---|---|---|---|
| sketch the weighted least squares once before IRLS iterations (sketch-once) instead of no sketching | IRLS for l1 low-rank approximation · synthetic 10^4 x 10^4 matrix, 10% outliers | convergence speed: about 3 times faster | Improved |
| use uniform sampling with sketch-once instead of canonical IRLS | IRLS for homography estimation · image stitching, 17,076 correspondences | convergence speed: about 5× faster | Improved |
| use sketch-iteratively instead of sketch-once at small sketching sizes (ablation) | sketched IRLS low-rank approximation · 10^4 x 10^4 matrix, 10% noise, rank 10-80 | time to accuracy 10^-5 | Improved |
| use sketch-once instead of sketch-iteratively at large sketching sizes (ablation) | sketched IRLS low-rank approximation · 10^4 x 10^4 matrix, 10% noise | time to accuracy 10^-5 | Improved |
| use sampling-based sketching (uniform sampling, sketch-once) on biased data instead of uniform data (ablation) | sketched IRLS residual minimization · synthetic biased data, n=10^6, d=40 | error | Hurt |
| use CountSketch with sketch-once instead of other sketching methods (ablation) | sketched IRLS ICP point cloud alignment · Stanford Bunny alignment | error convergence | Hurt |
| use l1 minimization instead of l2 minimization | homography estimation · image stitching with AKAZE matches | stitching quality | Improved |
Closest papers by meaning
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms (ICLR 2024 · similarity 0.88)
- Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate (NeurIPS 2021 · similarity 0.88)
- Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression (NeurIPS 2022 · similarity 0.87)
- Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks (NeurIPS 2024 · similarity 0.86)
- Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees (ICLR 2025 · similarity 0.86)
- Distributed Least Squares in Small Space via Sketching and Bias Reduction (NeurIPS 2024 · similarity 0.85)
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.
