# Generalized Nonconvex Nonsmooth Low-Rank Minimization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2014.

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

- [Is Attention Better Than Matrix Decomposition?](https://mlsanity.com/paper/2109.04553/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Irregular Tensor Low-Rank Representation for Hyperspectral Image Representation](https://mlsanity.com/paper/2410.18388/) (2024)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Region-wise matching for image inpainting based on adaptive weighted low-rank decomposition](https://mlsanity.com/paper/2303.12421/) (2023)
- [Robust Low-Rank Matrix Completion via a New Sparsity-Inducing Regularizer](https://mlsanity.com/paper/2310.04762/) (2023)
- [A framework to generate sparsity-inducing regularizers for enhanced low-rank matrix completion](https://mlsanity.com/paper/2310.04954/) (2023)
- [Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization](https://mlsanity.com/paper/2406.15713/) (2024)
- [HOME-3: High-Order Momentum Estimator with Third-Power Gradient for Convex and Smooth Nonconvex Optimization](https://mlsanity.com/paper/2505.11748/) (2025)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [Matrix Completion Via Reweighted Logarithmic Norm Minimization](https://mlsanity.com/paper/2512.21050/) (2025)
- [LORE: Jointly Learning the Intrinsic Dimensionality and Relative Similarity Structure From Ordinal Data](https://mlsanity.com/paper/2602.04192/) (2026)
- [Inductive Convolution Nuclear Norm Minimization for Tensor Completion with Arbitrary Sampling](https://mlsanity.com/paper/2604.17001/) (2026)

## Abstract (arXiv)

As surrogate functions of L0-norm, many nonconvex penalty functions have been proposed to enhance the sparse vector recovery. It is easy to extend these nonconvex penalty functions on singular values of a matrix to enhance low-rank matrix recovery. However, different from convex optimization, solving the nonconvex low-rank minimization problem is much more challenging than the nonconvex sparse minimization problem. We observe that all the existing nonconvex penalty functions are concave and monotonically increasing on [0,∞). Thus their gradients are decreasing functions. Based on this property, we propose an Iteratively Reweighted Nuclear Norm (IRNN) algorithm to solve the nonconvex nonsmooth low-rank minimization problem. IRNN iteratively solves a Weighted Singular Value Thresholding (WSVT) problem. By setting the weight vector as the gradient of the concave penalty function, the WSVT problem has a closed form solution. In theory, we prove that IRNN decreases the objective function value monotonically, and any limit point is a stationary point. Extensive experiments on both synthetic data and real images demonstrate that IRNN enhances the low-rank matrix recovery compared with state-of-the-art convex algorithms.