Generalized Nonconvex Nonsmooth Low-Rank Minimization
This work addresses a specific bottleneck in low-rank matrix recovery for applications like image processing, but it is incremental as it builds on existing nonconvex penalty functions with a novel optimization approach.
The authors tackled the challenge of solving nonconvex nonsmooth low-rank minimization problems, which are more difficult than sparse minimization, by proposing an Iteratively Reweighted Nuclear Norm (IRNN) algorithm that enhances low-rank matrix recovery compared to state-of-the-art convex methods, as demonstrated in experiments on synthetic data and real images.
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.