Generalized Nonconvex Nonsmooth Low-Rank Minimization

By Canyi Lu, Jinhui Tang, Shuicheng Yan, Zhouchen Lin. 2014

292 citations recorded by the source corpus.

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.

Subfields: Biomedical Engineering, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

1. Mark Hasegawa-Johnson
2. Minh N. Do
3. Raymond A. Yeh
4. Teck-Yian Lim
5. Shuicheng Yan
6. Wangmeng Zuo
7. Deyu Meng
8. Qi Xie

In Computational Mechanics

1. Wangmeng Zuo
2. Lei Zhang
3. Xiangchu Feng
4. Deyu Meng
5. Shuhang Gu
6. Zhouchen Lin
7. Canyi Lu
8. Jiashi Feng

In Computer Vision and Pattern Recognition

1. Luc Van Gool
2. Wangmeng Zuo
3. Lei Zhang
4. Ming-Hsuan Yang
5. Dacheng Tao
6. Jiashi Feng
7. Chen Change Loy
8. Chunhua Shen

In Optimization & Training

1. Mark Hasegawa-Johnson
2. Minh N. Do
3. Raymond A. Yeh
4. Teck-Yian Lim
5. Deyu Meng
6. Yuan Xie
7. Shuicheng Yan
8. Wangmeng Zuo

Citations in the corpus

• Semantic Image Inpainting with Deep Generative Models (2016, methodology): “We compare our method with TV inpainting [1] and LR inpainting [24, 12] on images with small random holes.”
• Semantic Image Inpainting with Perceptual and Contextual Losses (2016, methodology): “We compare our method with local methods using Total Variation (TV) regularization [2] and low rank minimization [11, 16].”
• Weighted Schatten $p$ -Norm Minimization for Image Denoising and Background Subtraction (2015, background): “Thanks to the current convex/non-convex optimization techniques, a large amount of modified models and improved algorithms have been proposed for LRMA [1], [10]–[12], [28], [30], [31].”
• Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization (2016, background): “It is also interesting to consider nonconvex low-rank tensor models [17, 18].”
• Weighted Nuclear Norm Minimization and Its Applications to Low Level Vision (2016, background): “(Lu et al, 2014a,b) studied the generalized nonconvex nonsmooth rank minimization problem and validated that if the penalty function is monotonic and lower bounded, a generalized singular value soft-thresholding operation is able to get the optimal solution.”