Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm

Canyi Lu; Jinhui Tang; Shuicheng Yan; Zhouchen Lin

Source-linked AI summary

Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm

Canyi Lu, Jinhui Tang, Shuicheng Yan, Zhouchen Lin

arXiv:1510.06895v1Oct 23, 2015cs.LGcs.CVmath.NA

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.
Method
The paper applies nonconvex L0 surrogates to singular values and solves the resulting nonsmooth problems with IRNN, including a multi-block extension.
Results
IRNN decreases the objective monotonically, has stationary limit points, and experimentally outperforms state-of-the-art convex algorithms on synthetic and real data.
Takeaways & Limitations
Nonconvex singular-value penalties provide a broader low-rank recovery framework than convex nuclear-norm models, with IRNN applicable to single- and multi-block problems.

Abstract

from arXiv · show

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.
The nuclear norm provides an efficiently solvable convex relaxation of rank minimization but is usually a loose, suboptimal approximation.
The paper applies concave, monotonically increasing nonconvex surrogates of the L0-norm to matrix singular values to better approximate rank.
IRNN solves the resulting nonconvex nonsmooth problem through weighted nuclear-norm updates with a closed-form proximal solution based on decreasing nonnegative supergradients.
The paper proves monotonic objective decrease and stationarity of any limit point, while experiments report that nonconvex IRNN models outperform convex counterparts.
IRNN is extended to problems with p ≥ 2 variable blocks, using a new multivariable Lipschitz-continuity definition and retaining convergence guarantees.

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.
Supergradients of the concave penalty are introduced to handle its nonsmooth points.

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.
A vector is a supergradient of a concave function when it satisfies the global upper-support inequality at a point.
At nonsmooth points, a concave function may have multiple supergradients; their collection is the superdifferential.
For concave g, supergradients of g correspond to negated subgradients of the convex function −g.
The superdifferential of a concave function is antimonotone, so supergradients decrease as the input increases on [0, ∞).

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.
The weights are nonnegative and nonincreasing because the penalty is increasing and concave.
Each iteration updates the matrix by solving a weighted nuclear-norm problem obtained from a penalty surrogate and a proximal linearization of the loss.
Unlike weighted L1 reweighting, IRNN solves a nonconvex weighted nuclear-norm problem, requiring different convergence analysis.
The weighted nuclear-norm subproblem has a closed-form solution through Weighted Singular Value Thresholding.
When g(x)=x, the weights equal 1 and WSVT reduces to conventional Singular Value Thresholding.
IRNN has convergence guarantees, including a nonincreasing rank sequence and convergence of the objective values.
IRNN uses shared properties of nonconvex L0 surrogates, making it applicable to a broader class of low-rank solvers.

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.

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.
The extension uses a truncated nuclear norm with zero weights on the first r singular values and unit weights on the remaining singular values.
Compared with the alternating updating algorithm, IRNN avoids double loops and provides stronger convergence guarantees.

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.
For tensor low-rank representation, X is a p-way tensor and X ×j Pj denotes the j-mode product.
Each block is updated using a gradient-based subproblem with parameters μj exceeding the block Lipschitz constants Lj(f).
The block updates can be computed in parallel, yielding the IRNN with Parallel Splitting method.
Under the stated assumptions, IRNN-PS monotonically decreases the objective and every accumulation point is stationary.

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.
Figure 4 compares successful-recovery frequency, running time, relative error, and convergence curves on noisy and noise-free random data.
Figure 5 compares recovered images from APGL, LMaFit, TNNR-ADMM, IRNN-Lp, and IRNN-SCAD.
The matrix-completion experiments use five nonconvex surrogates: Lp-norm, SCAD, Logarithm, MCP, and ETP.

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.
A recovery is successful when relative error is below 10^-3, with success frequency computed over 100 trials.
IRNN with nonconvex rank surrogates significantly outperforms convex ALM on noise-free recovery frequency.
In the noise-free case, IRNN achieves much smaller recovery error than APGL for the convex problem.
The authors state that no best rank surrogate can yet be identified because the nonconvex solutions are generally not globally optimal.
IRNN is slower than convex ALM because continuation reinitializes the algorithm, while its objective values decrease across iterations.

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.
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.
Results: The nonconvex truncated nuclear norm has similar recovery performance but requires 3∼5 times the running time of the proposed methods.

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.
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).
Clustering procedure: The clustering pipeline constructs an affinity matrix from the learned tensor representation and applies Normalized Cuts to obtain k groups.
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.
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.
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.