Reweighted Solutions for Weighted Low Rank Approximation
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 22 of its 56 references that are in the map. First posted on arXiv 4 Jun 2024.
Builds on
22 of 56 references.
References · 22
- 2022Language model compression with weighted low-rank factorizationcited by 192
- 2015Compression of Deep Convolutional Neural Networks for Fast and Low Power Mobile Applicationscited by 161
- 2014Matrix Completion and Low-Rank SVD via Fast Alternating Least Squarescited by 104
- 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
- 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
- 2015Frequent Directions : Simple and Deterministic Matrix Sketchingcited by 39
- 2018GroupReduce: Block-Wise Low-Rank Approximation for Neural Language Model Shrinkingcited by 32
- 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
- 2016Recovery guarantee of weighted low-rank approximation via alternating minimizationcited by 20
- 2016Sharper Bounds for Regularized Data Fittingcited by 19
- 2022Numerical Optimizations for Weighted Low-rank Estimation on Language Modelcited by 14
- 2016Greedy Column Subset Selection: New Bounds and Distributed Algorithmscited by 13
10 more
- 2019Regularized Weighted Low Rank Approximationcited by 10
- 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
- 2013Principal Component Analysis and Higher Correlations for Distributed Datacited by 7
- 2015Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Datacited by 6
- 2020Generalized Matrix Factorization: efficient algorithms for fitting generalized linear latent variable models to large data arrayscited by 4
- 2021Local Search Algorithms for Rank-Constrained Convex Optimizationcited by 3
- 2017A Batch-Incremental Video Background Estimation Model using Weighted Low-Rank Approximation of Matricescited by 2
- 2018Weighted Low-Rank Approximation of Matrices and Background Modelingcited by 2
- 2019Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximationcited by 2
- 2017On Approximation Guarantees for Greedy Low Rank Optimizationcited by 1
Built on by
Citing papers per year: 2025: 1.
1 paper.