Research map / Learning theory and algorithms / Matrix and tensor methods
Reweighted Solutions for Weighted Low Rank Approximation
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.
Proposes reweighting a low-rank approximation of W∘A by W^{∘-1} for weighted low rank approximation, giving provable guarantees when the weight matrix has low rank, with matching communication bounds and feature selection results.
Problem
Weighted low rank approximation (WLRA) is NP-hard to solve exactly or with near-optimal rank-k output; existing methods are heuristics, bicriteria, or exponential in the weight rank.
Approach
Relax the output to a non-low-rank matrix: compute a rank-rk approximation of W∘A (rank r of W) and divide entrywise by W. Since W∘A' has rank at most rk for rank-k A', this yields relative error guarantees and storage of O((n+d)rk) parameters.
Key results
- svd_w achieves rank-20 Fisher-weighted loss of 0.0023 on smallnorb versus 0.0281 for adam and 0.0019 for em, with ~1.06 s vs 26.1 s for em.
- The top singular value of Fisher weight matrices holds 95.4%-99.9% of the Frobenius mass across the four datasets.
- Communication upper bound O((srk/eps + rkd) log(nd)) bits matched by an Omega(rsk) lower bound, showing the weight rank parameterizes communication complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fisher-weighted SVD (svd_w) instead of unweighted SVD (svd) | Rank 20 WLRA for MLP hidden-layer compression · MNIST, Fashion-MNIST, SmallNORB, and Colorectal-Histology | loss: 0.0203 -> 0.0157; 0.0783 -> 0.0689; 0.0380 -> 0.0023; 0.0143 -> 0.0092 | Helped |
| Use svd_w instead of EM | Rank 20 WLRA for MLP hidden-layer compression · MNIST, Fashion-MNIST, SmallNORB, and Colorectal-Histology | loss: 0.0149 -> 0.0157; 0.0627 -> 0.0689; 0.0019 -> 0.0023; 0.0090 -> 0.0092 | Hurt |
| Use svd_w instead of EM | Rank 20 WLRA for MLP hidden-layer compression · MNIST, Fashion-MNIST, SmallNORB, and Colorectal-Histology | running time (s): 0.2356 -> 0.0112; 0.3183 -> 0.0115; 26.1445 -> 1.0586; 206.1457 -> 7.2273 | Helped |
| Use svd_w instead of unweighted SVD | Rank 20 WLRA for MLP hidden-layer compression · MNIST, Fashion-MNIST, SmallNORB, and Colorectal-Histology | running time (s): 0.0055 -> 0.0112; 0.0057 -> 0.0115; 0.2831 -> 1.0586; 2.2419 -> 7.2273 | Hurt |
Surprising findings
- Zero-filling missing entries (dividing by binary W after SVD) gives relative error guarantees for binary weights, contrary to prior work suggesting otherwise.
- The row-norm sampling result of prior work contained an error that the authors correct and tighten.
Limitations
- Guarantees require the weight matrix to be low rank; general dense weights need approximation first.
- Dividing by W is not directly storable or applicable in general unless W has structured inverse form.
- Experiments are small-scale MLPs and synthetic data, not large LLMs.
Experimental setup
Datasets: mnist fashion_mnist smallnorb colorectal_histology synthetic mixture of Gaussians
Benchmarks: mnist fashion_mnist smallnorb colorectal_histology synthetic Gaussian mixture
Metrics: Fisher-weighted approximation loss running time
Baselines: adam em greedy sample svd
Builds on: expectation-maximization for WLRA alternating least squares optimal weight-based LLM compression (Fisher-weighted low rank) randomized SVD
Closest papers by meaning
- Additive Error Guarantees for Weighted Low Rank Approximation (ICML 2021 · similarity 0.90)
- From Low Rank Gradient Subspace Stabilization to Low-Rank Weights: Observations, Theories, and Applications (ICML 2025 · similarity 0.87)
- Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation (ICLR 2025 · similarity 0.86)
- COALA: Numerically Stable and Efficient Framework for Context-Aware Low-Rank Approximation (NeurIPS 2025 · similarity 0.86)
- Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks (NeurIPS 2024 · similarity 0.86)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.84)
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.