Source-linked AI summary
Generalized Nonconvex Nonsmooth Low-Rank Minimization
Canyi Lu, Jinhui Tang, Shuicheng Yan, Zhouchen Lin
TL;DR
The paper addresses the difficulty of solving general nonconvex nonsmooth low-rank minimization beyond nuclear-norm relaxation and existing specialized solvers. It proposes IRNN, which exploits decreasing supergradients to solve weighted nuclear-norm subproblems, and reports convergence guarantees and improved recovery on synthetic data and real images.
Problem
General nonconvex nonsmooth low-rank minimization is more challenging than sparse minimization, while existing solvers do not handle the full problem reliably.
Method
IRNN extends nonconvex penalties to singular values and iteratively solves weighted nuclear-norm problems using nonnegative, decreasing supergradients.
Results
IRNN usually outperforms state-of-the-art convex algorithms on synthetic low-rank recovery and real-image recovery, achieving higher PSNR values on tested images.
Takeaways & Limitations
The method provides a general solver for nonconvex low-rank minimization with a convergence guarantee, including nonsmooth penalties.
Takeaways & Limitations
The discussed DC programming approach does not extend to the low-rank problem because the relevant penalty composition is not guaranteed convex, and it also fails when f is nonconvex.
Abstract
from arXiv · showhide
As surrogate functions of $L_0$-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,\infty)$. 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.
1. Introduction
The paper targets general nonconvex nonsmooth low-rank minimization, motivated by the limitations of nuclear-norm relaxation and existing solvers. It proposes IRNN based on concavity and monotonicity of nonconvex penalties, with convergence guarantees.
- Motivation: Nonconvex low-rank minimization arises in classification, matrix completion, multi-task learning, and subspace segmentation, but can be difficult or NP-hard.
- Motivation: Nuclear-norm minimization is tractable but may be suboptimal because the nuclear norm is not a perfect approximation of rank.Its near-optimality depends on incoherence assumptions that may be violated in real applications.
- Prior Work: Existing nonconvex surrogates, including Lp, SCAD, logarithm, MCP, capped L1, ETP, Geman, Laplace, Schatten-p, and truncated nuclear norm, better approximate sparsity or rank.
- Prior Work: DC programming and proximal-gradient methods face difficulties because the induced matrix objective may be nonconvex or lack a general solvable proximal operator.DC updates also require another iterative solver, while proximal mappings for nonconvex penalties need not preserve convex-case properties.
- Prior Work: IRLS cannot solve the general nonsmooth problem, while truncated-nuclear-norm updating requires two SVD-containing loops and does not generalize to the full problem.
- Contribution: IRNN extends nonconvex penalties to singular values and uses nonnegative, decreasing supergradients to obtain a closed-form weighted nuclear-norm proximal step.The paper proves monotonic objective decrease and that every limit point is stationary.
2. Nonconvex Nonsmooth Low-Rank Minimization
The section develops supergradient-based machinery for nonsmooth concave penalties and uses it to construct IRNN updates with closed-form weighted singular value thresholding.
- Supergradients: Supergradients extend gradients to nonsmooth points of concave functions and form an antimonotone operator.For differentiable points, the superdifferential contains the ordinary gradient; for concave penalties, supergradients decrease with the argument.
- Nonsmooth penalties: For the Lp penalty with ∂g(0) = ∞, the update sets the corresponding next singular value to zero, ensuring nonincreasing ranks.The same framework accommodates nonsmooth penalties such as Capped L1 through superdifferentials.
- Iteratively Reweighted Nuclear Norm: IRNN replaces the concave penalty by a supergradient-based weighted nuclear norm relaxation and alternates updates of X and the weights.The algorithm linearizes the penalty-related term, then updates the weights from supergradients at the current singular values.
- Iteratively Reweighted Nuclear Norm: Concavity makes the weighted nuclear norm subproblem nonconvex, unlike the corresponding weighted L1-norm problem.The resulting subproblem can be as challenging as the original low-rank minimization problem.
- Iteratively Reweighted Nuclear Norm: A proximal linearization of f with µ > L(f) yields the algorithm’s tractable update, which has a closed-form solution.The proximal parameter is chosen above the Lipschitz constant of the gradient, and the resulting update is solved by weighted singular value thresholding.
- Weighted Singular Value Thresholding: When the weights are nondecreasing across singular values, weighted singular value thresholding gives a globally optimal solution.Given Y = UΣV^T, the solution applies Sλw(Σ) = Diag{(Σii − λwi)+}.
3. Convergence Analysis
The convergence analysis establishes that IRNN decreases the objective monotonically and that every accumulation point of its generated sequence is stationary.
- Theorem 1: Under assumptions (A1)–(A2), IRNN generates a sequence whose objective values are monotonically decreasing.The decrease follows from the global solution of each proximal subproblem and the Lipschitz-gradient bound for the loss.
- Theorem 1: The IRNN sequence is bounded under the stated assumptions.Boundedness is used to guarantee the existence of accumulation points for the generated sequence.
- Theorem 2: Any accumulation point of the sequence generated by IRNN is a stationary point of problem (1).Theorem 2 derives stationarity by passing to a convergent subsequence and using the subdifferential’s upper semi-continuity.
4. Extension to Other Problems
IRNN extends to broader low-rank objectives, including grouped singular-value sparsity and truncated nuclear norm structures, while retaining convergence guarantees under the stated supergradient conditions.
- IRNN solves a more general low-rank minimization problem with separable concave penalties on singular values.
- The extension assumes concave component functions whose supergradients are nonnegative and ordered across singular values.
- The truncated nuclear norm satisfies the extension's supergradient assumption.
- The convergence results continue to hold for each component function, while avoiding the double loops required by the alternating truncated-nuclear-norm method.
- Grouped singular-value sparsity can be expressed by partitioning singular values into groups and applying a concave group penalty.
5. Experiments
Experiments evaluate IRNN on synthetic matrix completion and noisy image recovery. Across the tested settings, nonconvex IRNN variants outperform convex baselines, while truncated nuclear norm methods have higher runtime.
- IRNN is evaluated on matrix completion using synthetic data and real images.
- Synthetic matrix recovery: 100 repetitions with rank r varying from 20 to 33 show that all tested nonconvex IRNN penalties recover noiseless matrices more successfully than convex ALM.
- Synthetic matrix recovery: In noisy matrix recovery, nonconvex IRNN penalties outperform convex APGL, although the experiments do not establish a consistent ranking among IRNN penalties.
- Image recovery: Image experiments use Gaussian noise, random pixel replacement, and unrelated text, evaluating recovery with PSNR alongside APGL, LMaFit, and other matrix-completion methods.
- Image recovery: Across the tested images, all evaluated nonconvex IRNN functions achieve higher PSNR values, while truncated nuclear norm recovery takes 3∼5 times longer.
6. Conclusions and Future Work
The paper extends nonconvex sparse penalties to singular values and presents IRNN as a convergent solver for general nonsmooth low-rank minimization. Experiments report stronger recovery than convex algorithms, while affine constraints remain future work.
- Nonconvex surrogate functions of the L0-norm are extended to singular values to approximate the rank function.
- IRNN is presented as a general solver with convergence guarantees for nonsmooth nonconvex low-rank minimization.
- Experiments on synthetic data and real images report that IRNN usually outperforms state-of-the-art convex algorithms.
- Solving nonconvex low-rank minimization with affine constraints is identified as future work, potentially by combining IRNN with ADMM.