Metraipolis › archive › dc_4f82f059cb05
Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS — arXiv:2608.23765
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.23765
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T06:35:36.225Z
- SHA-256 of the archived text
bf60e23b7035b4962d3a00be63366884706efeb94088e258ae1c0619603ec190- Stable URL of this page
https://metraipolis.com/documento/dc_4f82f059cb05
How to cite
Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS — arXiv:2608.23765 — arXiv (en), https://arxiv.org/abs/2608.23765 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4f82f059cb05 (Metraipolis archive dc_4f82f059cb05, sha256 bf60e23b7035b4962d3a00be63366884706efeb94088e258ae1c0619603ec190)
BibTeX
@misc{dc4f82f059cb05,
title = {Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS — arXiv:2608.23765},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.23765},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4f82f059cb05; sha256 bf60e23b7035b4962d3a00be63366884706efeb94088e258ae1c0619603ec190},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.23765. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-26 in cs.LG). Categorie arXiv: Machine Learning (cs.LG) ; Numerical Analysis (math.NA); Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2608.23765 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-18T06:28:52.181Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-26?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).