# Reweighted Solutions for Weighted Low Rank Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 56 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 22 of 22)

- [Language model compression with weighted low-rank factorization](https://mlsanity.com/paper/2207.00112/) (2022)
- [Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applications](https://mlsanity.com/paper/1511.06530/) (2015)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [GroupReduce: Block-Wise Low-Rank Approximation for Neural Language Model Shrinking](https://mlsanity.com/paper/1806.06950/) (2018)
- [Optimal Principal Component Analysis in Distributed and Streaming Models](https://mlsanity.com/paper/1504.06729/) (2015)
- [Recovery guarantee of weighted low-rank approximation via alternating minimization](https://mlsanity.com/paper/1602.02262/) (2016)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [Numerical Optimizations for Weighted Low-rank Estimation on Language Model](https://mlsanity.com/paper/2211.09718/) (2022)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Regularized Weighted Low Rank Approximation](https://mlsanity.com/paper/1911.06958/) (2019)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Principal Component Analysis and Higher Correlations for Distributed Data](https://mlsanity.com/paper/1304.3162/) (2013)
- [Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data](https://mlsanity.com/paper/1505.04343/) (2015)
- [Generalized Matrix Factorization: efficient algorithms for fitting generalized linear latent variable models to large data arrays](https://mlsanity.com/paper/2010.02469/) (2020)
- [Local Search Algorithms for Rank-Constrained Convex Optimization](https://mlsanity.com/paper/2101.06262/) (2021)
- [A Batch-Incremental Video Background Estimation Model using Weighted Low-Rank Approximation of Matrices](https://mlsanity.com/paper/1707.00281/) (2017)
- [Weighted Low-Rank Approximation of Matrices and Background Modeling](https://mlsanity.com/paper/1804.06252/) (2018)
- [Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation](https://mlsanity.com/paper/1904.09841/) (2019)
- [On Approximation Guarantees for Greedy Low Rank Optimization](https://mlsanity.com/paper/1703.02721/) (2017)

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

- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)

## Abstract (arXiv)

Weighted low rank approximation (WLRA) is an important yet computationally challenging primitive with applications ranging from statistical analysis, model compression, and signal processing. To cope with the NP-hardness of this problem, prior work considers heuristics, bicriteria, or fixed parameter tractable algorithms to solve this problem. In this work, we introduce a new relaxed solution to WLRA which outputs a matrix that is not necessarily low rank, but can be stored using very few parameters and gives provable approximation guarantees when the weight matrix has low rank. Our central idea is to use the weight matrix itself to reweight a low rank solution, which gives an extremely simple algorithm with remarkable empirical performance in applications to model compression and on synthetic datasets. Our algorithm also gives nearly optimal communication complexity bounds for a natural distributed problem associated with this problem, for which we show matching communication lower bounds. Together, our communication complexity bounds show that the rank of the weight matrix provably parameterizes the communication complexity of WLRA. We also obtain the first relative error guarantees for feature selection with a weighted objective.