# Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 107 references that are in the map.
- First posted on arXiv 24 Aug 2026.

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

- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [Kimi K2: Open Agentic Intelligence](https://mlsanity.com/paper/2507.20534/) (2025)
- [Muon is Scalable for LLM Training](https://mlsanity.com/paper/2502.16982/) (2025)
- [Muon Optimizes Under Spectral Norm Constraints](https://mlsanity.com/paper/2506.15054/) (2025)
- [Iteratively reweighted kernel machines efficiently learn sparse functions](https://mlsanity.com/paper/2505.08277/) (2025)
- [Global Convergence of Iteratively Reweighted Least Squares for Robust Subspace Recovery](https://mlsanity.com/paper/2506.20533/) (2025)
- [IRLS for Sparse Recovery Revisited: Examples of Failure and a Remedy](https://mlsanity.com/paper/1910.07095/) (2019)

## Abstract (arXiv)

Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization, but their convergence rates and the role of the weight operator have remained poorly understood. This paper establishes sharp convergence rates for IRLS methods for constrained nuclear norm minimization in low-rank recovery. A central ingredient is a new majorization analysis for the smoothed nuclear norm: we prove that the harmonic-mean weight operator defines a valid global quadratic majorizer. Furthermore, we show that this weight operator is optimal within the family of power-mean weights, clarifying why it improves over classical one-sided reweighting schemes that use only row- or column-space information. Under a Schatten-1 null space property, we prove global linear convergence of IRLS algorithms using a variety of weight operators, including the harmonic-mean weights. For IRLS with harmonic-mean weights, we prove a dimension-independent, locally linear convergence rate. We provide a counterexample showing that this dimension-independent local rate cannot in general be obtained for IRLS algorithms using one-sided weight operators, which predominate in the literature. Numerical experiments corroborate the theoretical results and illustrate the practical advantage of harmonic-mean reweighting across square, rectangular, and adversarially initialized recovery problems.