# Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

arXiv: https://arxiv.org/abs/2306.04169 · HTML: https://mlsanity.com/paper/2306.04169/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 55 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 30 of 31)

- [Language model compression with weighted low-rank factorization](https://mlsanity.com/paper/2207.00112/) (2022)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Optimal Principal Component Analysis in Distributed and Streaming Models](https://mlsanity.com/paper/1504.06729/) (2015)
- [Speeding Up Sparsification using Inner Product Search Data Structures](https://mlsanity.com/paper/2204.03209/) (2022)
- [Recovery guarantee of weighted low-rank approximation via alternating minimization](https://mlsanity.com/paper/1602.02262/) (2016)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Towards a Zero-One Law for Column Subset Selection](https://mlsanity.com/paper/1811.01442/) (2018)
- [Average Case Column Subset Selection for Entrywise ℓ1-Norm Loss](https://mlsanity.com/paper/2004.07986/) (2020)
- [Regularized Weighted Low Rank Approximation](https://mlsanity.com/paper/1911.06958/) (2019)
- [Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures](https://mlsanity.com/paper/2207.09002/) (2022)

## Built on by (most cited first, 9 of 9)

- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [A Unified Scheme of ResNet and Softmax](https://mlsanity.com/paper/2309.13482/) (2023)
- [Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretraining](https://mlsanity.com/paper/2502.05790/) (2025)
- [How to Inverting the Leverage Score Distribution?](https://mlsanity.com/paper/2404.13785/) (2024)
- [Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method](https://mlsanity.com/paper/2408.11267/) (2024)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)

## Abstract (arXiv)

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M ∈ ℝn × n, a non-negative weight matrix W ∈ ℝ≥ 0n × n, a parameter k, the goal is to output two matrices X,Y∈ ℝn × k such that | W circ (M - X Y^top) |F is minimized, where circ denotes the Hadamard product. It naturally generalizes the well-studied low rank matrix completion problem. Such a problem is known to be NP-hard and even hard to approximate assuming the Exponential Time Hypothesis [GG11, RSW16]. Meanwhile, alternating minimization is a good heuristic solution for weighted low rank approximation. In particular, [LLR16] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization that allows the alternating updates to be computed approximately. For weighted low rank approximation, this improves the runtime of [LLR16] from |W|0k2 to |W|0 k where |W|0 denotes the number of nonzero entries of the weight matrix. At the heart of our framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization.