Source-linked AI summary
Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm
Canyi Lu, Jinhui Tang, Shuicheng Yan, Zhouchen Lin
TL;DR
Convex nuclear-norm relaxation makes low-rank recovery tractable but often yields solutions suboptimal to rank minimization. The paper applies nonconvex L0 surrogates to singular values and proposes IRNN, extending it to multiple variable blocks. IRNN has closed-form weighted nuclear-norm updates, convergence guarantees, and experimentally improves recovery over state-of-the-art convex algorithms.
Problem
The nuclear norm is a loose convex surrogate for rank, so nuclear-norm minimization usually produces solutions suboptimal to the original rank-minimization problem.
Source: §I · p. 1Method
The paper applies nonconvex L0 surrogates to singular values and solves the resulting nonsmooth problems with IRNN, including a multi-block extension.
Source: §I · pp. 2–3, B. IRNN for the Multi-Blocks Problem (5) · p. 6Results
IRNN decreases the objective monotonically, has stationary limit points, and experimentally outperforms state-of-the-art convex algorithms on synthetic and real data.
Source: B. Iteratively Reweighted Nuclear Norm… · p. 5, A. Low Rank Matrix Recovery on the… · p. 8, §V · p. 9Takeaways & Limitations
Abstract
from arXiv · showhide
The nuclear norm is widely used as a convex surrogate of the rank function in compressive sensing for low rank matrix recovery with its applications in image recovery and signal processing. However, solving the nuclear norm based relaxed convex problem usually leads to a suboptimal solution of the original rank minimization problem. In this paper, we propose to perform a family of nonconvex surrogates of $L_0$-norm on the singular values of a matrix to approximate the rank function. This leads to a nonconvex nonsmooth minimization problem. Then we propose to solve the problem by Iteratively Reweighted Nuclear Norm (IRNN) algorithm. IRNN iteratively solves a Weighted Singular Value Thresholding (WSVT) problem, which has a closed form solution due to the special properties of the nonconvex surrogate functions. We also extend IRNN to solve the nonconvex problem with two or more blocks of variables. In theory, we prove that IRNN decreases the objective function value monotonically, and any limit point is a stationary point. Extensive experiments on both synthesized data and real images demonstrate that IRNN enhances the low-rank matrix recovery compared with state-of-the-art convex algorithms.
I. INTRODUCTION
Low-rank recovery replaces rank with the nuclear norm for tractability, but this convex surrogate can be suboptimal. The paper transfers nonconvex L0 surrogates to singular values and develops IRNN, including a multi-block extension with convergence guarantees.
- Low-rank matrix models support applications including matrix completion, background modeling, motion segmentation, and collaborative filtering.Source: §I · p. 1
- The nuclear norm provides an efficiently solvable convex relaxation of rank minimization but is usually a loose, suboptimal approximation.Source: §I · p. 1
- The paper applies concave, monotonically increasing nonconvex surrogates of the L0-norm to matrix singular values to better approximate rank.Source: §I · pp. 2–3
- IRNN solves the resulting nonconvex nonsmooth problem through weighted nuclear-norm updates with a closed-form proximal solution based on decreasing nonnegative supergradients.Source: §I · p. 3
- The paper proves monotonic objective decrease and stationarity of any limit point, while experiments report that nonconvex IRNN models outperform convex counterparts.Source: §I · p. 3
- IRNN is extended to problems with p ≥ 2 variable blocks, using a new multivariable Lipschitz-continuity definition and retaining convergence guarantees.Source: §I · p. 3
II. NONCONVEX NONSMOOTH LOW-RANK MINIMIZATION
The paper introduces the general nonconvex, possibly nonsmooth low-rank minimization problem and uses supergradients to handle nonsmooth penalties.
- The method addresses a general low-rank minimization problem with a penalty that may be nonconvex and nonsmooth.Source: §II · p. 3
- Supergradients of the concave penalty are introduced to handle its nonsmooth points.Source: §II · p. 3
A. Supergradient of a Concave Function
The section defines supergradients for concave functions, relates them to convex subgradients, and establishes their antimonotone behavior.
- At differentiable points the supergradient is unique, whereas Figure 3 illustrates nonunique supergradients at a nondifferentiable point.Source: Figure 3 · p. 4, A. Supergradient of a Concave Function · p. 4
- A vector is a supergradient of a concave function when it satisfies the global upper-support inequality at a point.Source: A. Supergradient of a Concave Function · p. 4
- At nonsmooth points, a concave function may have multiple supergradients; their collection is the superdifferential.Source: A. Supergradient of a Concave Function · p. 4
- For concave g, supergradients of g correspond to negated subgradients of the convex function −g.Source: A. Supergradient of a Concave Function · p. 4
- The superdifferential of a concave function is antimonotone, so supergradients decrease as the input increases on [0, ∞).Source: A. Supergradient of a Concave Function · p. 4
B. Iteratively Reweighted Nuclear Norm Algorithm
IRNN linearizes the concave singular-value penalty, solves weighted nuclear-norm subproblems by WSVT, and provides convergence guarantees for the resulting iterations.
- IRNN assigns weights from supergradients of the concave penalty evaluated at the current singular values.Source: B. Iteratively Reweighted Nuclear Norm… · p. 4
- The weights are nonnegative and nonincreasing because the penalty is increasing and concave.Source: B. Iteratively Reweighted Nuclear Norm… · p. 4
- Each iteration updates the matrix by solving a weighted nuclear-norm problem obtained from a penalty surrogate and a proximal linearization of the loss.Source: B. Iteratively Reweighted Nuclear Norm… · p. 4
- Unlike weighted L1 reweighting, IRNN solves a nonconvex weighted nuclear-norm problem, requiring different convergence analysis.Source: B. Iteratively Reweighted Nuclear Norm… · pp. 4–5
- The weighted nuclear-norm subproblem has a closed-form solution through Weighted Singular Value Thresholding.Source: B. Iteratively Reweighted Nuclear Norm… · p. 5
- When g(x)=x, the weights equal 1 and WSVT reduces to conventional Singular Value Thresholding.Source: B. Iteratively Reweighted Nuclear Norm… · p. 5
- IRNN has convergence guarantees, including a nonincreasing rank sequence and convergence of the objective values.Source: B. Iteratively Reweighted Nuclear Norm… · p. 5
- IRNN uses shared properties of nonconvex L0 surrogates, making it applicable to a broader class of low-rank solvers.Source: B. Iteratively Reweighted Nuclear Norm… · p. 5
III. EXTENSIONS OF IRNN AND THE CONVERGENCE ANALYSIS
The paper extends IRNN to more general nonconvex penalties and to problems with multiple variable blocks.
- The extension covers both broader nonconvex penalties and low-rank problems with p ≥ 2 blocks of variables.Source: §III · p. 5
A. IRNN for the Problems with More General Nonconvex Penalties
The paper extends IRNN to broader nonconvex rank surrogates and compares it with an alternating method, claiming greater efficiency and stronger convergence guarantees.
- IRNN is extended to problems whose penalty functions are concave and whose supergradients are ordered across singular values.Source: A. IRNN for the Problems with More… · p. 5
- The extension uses a truncated nuclear norm with zero weights on the first r singular values and unit weights on the remaining singular values.Source: A. IRNN for the Problems with More… · p. 5
- Compared with the alternating updating algorithm, IRNN avoids double loops and provides stronger convergence guarantees.Source: A. IRNN for the Problems with More… · p. 5
B. IRNN for the Multi-Blocks Problem (5)
IRNN is extended to multi-block problems, including tensor low-rank representation, with parallel block updates and convergence to stationary points under stated assumptions.
- The multi-block framework applies IRNN to problems with multiple variable blocks and block-specific nonconvex singular-value penalties.Source: B. IRNN for the Multi-Blocks Problem (5) · pp. 5–6
- For tensor low-rank representation, X is a p-way tensor and X ×j Pj denotes the j-mode product.Source: B. IRNN for the Multi-Blocks Problem (5) · p. 6
- Each block is updated using a gradient-based subproblem with parameters μj exceeding the block Lipschitz constants Lj(f).Source: B. IRNN for the Multi-Blocks Problem (5) · p. 6
- The block updates can be computed in parallel, yielding the IRNN with Parallel Splitting method.Source: B. IRNN for the Multi-Blocks Problem (5) · p. 6
- Under the stated assumptions, IRNN-PS monotonically decreases the objective and every accumulation point is stationary.Source: C. Convergence Analysis · p. 6
IV. EXPERIMENTS
Experiments evaluate IRNN on synthetic matrix completion, real-image recovery, and tensor low-rank representation for face clustering using several nonconvex penalties.
- The experiments assess convergence behavior for matrix completion on synthetic data and real images, plus tensor low-rank representation for face clustering.Source: §IV · pp. 6–7
- Figure 4 compares successful-recovery frequency, running time, relative error, and convergence curves on noisy and noise-free random data.Source: Figure 4 · p. 7
- Figure 5 compares recovered images from APGL, LMaFit, TNNR-ADMM, IRNN-Lp, and IRNN-SCAD.Source: Figure 5 · p. 7
- The matrix-completion experiments use five nonconvex surrogates: Lp-norm, SCAD, Logarithm, MCP, and ETP.Source: §IV · p. 7
A. Low Rank Matrix Recovery on the Synthetic Data
Synthetic experiments compare nonconvex IRNN matrix recovery with convex baselines under noise-free and noisy settings, measuring recovery frequency, error, and runtime.
- The study tests matrix recovery without noise and with noise, comparing nonconvex model (32) against convex nuclear-norm methods.Source: A. Low Rank Matrix Recovery on the… · p. 7
- A recovery is successful when relative error is below 10^-3, with success frequency computed over 100 trials.Source: A. Low Rank Matrix Recovery on the… · p. 7
- IRNN with nonconvex rank surrogates significantly outperforms convex ALM on noise-free recovery frequency.Source: A. Low Rank Matrix Recovery on the… · p. 8
- In the noise-free case, IRNN achieves much smaller recovery error than APGL for the convex problem.Source: A. Low Rank Matrix Recovery on the… · p. 8
- The authors state that no best rank surrogate can yet be identified because the nonconvex solutions are generally not globally optimal.Source: A. Low Rank Matrix Recovery on the… · p. 8
- IRNN is slower than convex ALM because continuation reinitializes the algorithm, while its objective values decrease across iterations.Source: A. Low Rank Matrix Recovery on the… · p. 8
B. Application to Image Recovery
The paper evaluates nonconvex low-rank matrix completion for removing pixel noise and overlaid text from real images. IRNN achieves stronger recovery metrics than convex methods, while retaining a runtime advantage over truncated nuclear norm.
Experimental setting
- The experiment removes either random replacement of 50% of pixels or unrelated text using low-rank matrix completion.Real images may not themselves be low-rank.Source: B. Application to Image Recovery · p. 8
Results
- IRNN with the evaluated nonconvex surrogates achieves higher PSNR and smaller relative error across the tested images.The comparison includes IRNN-Lp and IRNN-SCAD because the different nonconvex surrogates produced similar performance.Source: B. Application to Image Recovery · p. 8
- The nonconvex truncated nuclear norm has similar recovery performance but requires 3∼5 times the running time of the proposed methods.Source: B. Application to Image Recovery · p. 8
C. Tensor Low-Rank Representation
This section extends low-rank representation to tensors for face clustering and solves the resulting multi-block nonconvex model with IRNN-PS. NTLRR improves over related representation methods, although the best nonconvex surrogate remains theoretically unresolved.
Tensor low-rank representation
- TLRR is used for face clustering, extending low-rank representation to tensor data with mode-wise products.Source: C. Tensor Low-Rank Representation · p. 8
Optimization
- The convex tensor formulation can be solved by APG, while the corresponding multi-block nonconvex formulation is solved by IRNN-PS.The APG formulation has optimal convergence rate O(1/K^2).Source: C. Tensor Low-Rank Representation · p. 9
Clustering procedure
- The clustering pipeline constructs an affinity matrix from the learned tensor representation and applies Normalized Cuts to obtain k groups.Source: C. Tensor Low-Rank Representation · p. 9
Experimental setting
- The evaluation uses Extended Yale B and UMIST face databases, including varying subjects, poses, lighting, and illumination conditions.Extended Yale B contains 2,414 images of 38 subjects, with 64 faces per subject.Source: C. Tensor Low-Rank Representation · p. 9
Results
- NTLRR achieves higher face-clustering accuracy than TLRR, LRR, and LatLRR, while TLRR already benefits from exploiting spatial structure among samples.The paper notes that theoretical support for this improvement remains open.Source: C. Tensor Low-Rank Representation · p. 9
Conclusion and future work
- The paper concludes that IRNN extends to multi-block nonconvex problems and that experiments on synthetic and real data usually outperform state-of-the-art convex algorithms.Future work includes identifying the best nonconvex surrogate and proving convergence for additional formulations.Source: §V · p. 9