# Recovery guarantee of weighted low-rank approximation via alternating minimization

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2016.

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

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [LQ-LoRA: Low-rank Plus Quantized Matrix Decomposition for Efficient Language Model Finetuning](https://mlsanity.com/paper/2311.12023/) (2023)
- [Parameter-Efficient Fine-Tuning for Foundation Models](https://mlsanity.com/paper/2501.13787/) (2025)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Adaptive Low Rank Adaptation of Segment Anything to Salient Object Detection](https://mlsanity.com/paper/2308.05426/) (2023)
- [Dynamic Rank Adjustment in Diffusion Policies for Efficient and Flexible Training](https://mlsanity.com/paper/2502.03822/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [Structured Unrestricted-Rank Matrices for Parameter Efficient Fine-tuning](https://mlsanity.com/paper/2406.17740/) (2024)
- [Revealing the Utilized Rank of Subspaces of Learning in Neural Networks](https://mlsanity.com/paper/2407.04797/) (2024)
- [DeltaLLM: Compress LLMs with Low-Rank Deltas between Shared Weights](https://mlsanity.com/paper/2501.18596/) (2025)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Weighted Low-Rank Matrix Approximation: Acceleration and Applications](https://mlsanity.com/paper/2109.11057/) (2021)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [AILS-NTUA at SemEval-2024 Task 9: Cracking Brain Teasers: Transformer Models for Lateral Thinking Puzzles](https://mlsanity.com/paper/2404.01084/) (2024)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)

## Abstract (arXiv)

Many applications require recovering a ground truth low-rank matrix from noisy observations of the entries, which in practice is typically formulated as a weighted low-rank approximation problem and solved by non-convex optimization heuristics such as alternating minimization. In this paper, we provide provable recovery guarantee of weighted low-rank via a simple alternating minimization algorithm. In particular, for a natural class of matrices and weights and without any assumption on the noise, we bound the spectral norm of the difference between the recovered matrix and the ground truth, by the spectral norm of the weighted noise plus an additive error that decreases exponentially with the number of rounds of alternating minimization, from either initialization by SVD or, more importantly, random initialization. These provide the first theoretical results for weighted low-rank via alternating minimization with non-binary deterministic weights, significantly generalizing those for matrix completion, the special case with binary weights, since our assumptions are similar or weaker than those made in existing works. Furthermore, this is achieved by a very simple algorithm that improves the vanilla alternating minimization with a simple clipping step. The key technical challenge is that under non-binary deterministic weights, na"ive alternating steps will destroy the incoherence and spectral properties of the intermediate solutions, which are needed for making progress towards the ground truth. We show that the properties only need to hold in an average sense and can be achieved by the clipping step. We further provide an alternating algorithm that uses a whitening step that keeps the properties via SDP and Rademacher rounding and thus requires weaker assumptions. This technique can potentially be applied in some other applications and is of independent interest.