# Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 55 references that are in the map.
- First posted on arXiv 22 Jun 2024.

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

- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [Low Rank Regularization: A Review](https://mlsanity.com/paper/1808.04521/) (2018)
- [Factor Group-Sparse Regularization for Efficient Low-Rank Matrix Recovery](https://mlsanity.com/paper/1911.05774/) (2019)
- [Generalized Nonconvex Nonsmooth Low-Rank Minimization](https://mlsanity.com/paper/1404.7306/) (2014)
- [Local Linear Convergence of Forward-Backward under Partial Smoothness](https://mlsanity.com/paper/1407.5611/) (2014)
- [A proximal difference-of-convex algorithm with extrapolation](https://mlsanity.com/paper/1612.06265/) (2016)
- [Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods](https://mlsanity.com/paper/1810.10167/) (2018)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Generalized Singular Value Thresholding](https://mlsanity.com/paper/1412.2231/) (2014)
- [An Extrapolated Iteratively Reweighted l1 Method with Complexity Analysis](https://mlsanity.com/paper/2101.03763/) (2021)
- [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022)
- [Model identification and local linear convergence of coordinate descent](https://mlsanity.com/paper/2010.11825/) (2020)
- [Iteratively reweighted ℓ1 algorithms with extrapolation](https://mlsanity.com/paper/1710.07886/) (2017)

## Abstract (arXiv)

This paper considers the problem of minimizing the sum of a smooth function and the Schatten-p norm of the matrix. Our contribution involves proposing accelerated iteratively reweighted nuclear norm methods designed for solving the nonconvex low-rank minimization problem. Two major novelties characterize our approach. Firstly, the proposed method possesses a rank identification property, enabling the provable identification of the "correct" rank of the stationary point within a finite number of iterations. Secondly, we introduce an adaptive updating strategy for smoothing parameters. This strategy automatically fixes parameters associated with zero singular values as constants upon detecting the "correct" rank while quickly driving the rest of the parameters to zero. This adaptive behavior transforms the algorithm into one that effectively solves smooth problems after a few iterations, setting our work apart from existing iteratively reweighted methods for low-rank optimization. We prove the global convergence of the proposed algorithm, guaranteeing that every limit point of the iterates is a critical point. Furthermore, a local convergence rate analysis is provided under the Kurdyka-Lojasiewicz property. We conduct numerical experiments using both synthetic and real data to showcase our algorithm's efficiency and superiority over existing methods.