Generalized Nonconvex Nonsmooth Low-Rank Minimization

Abstract

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.

IEEE International Conference on Computer Vision and Pattern Recognition, 2014

References in corpus (2)

• Nearly unbiased variable selection under minimax concave penalty
• Nonsmooth Analysis and Optimization

Cited by in corpus (41)

• Weighted Schatten $p$-Norm Minimization for Image Denoising and Background Subtraction
• Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm
• A Nonconvex Low-Rank Tensor Completion Model for Spatiotemporal Traffic Data Imputation
• Simultaneously sparse and low-rank abundance matrix estimation for hyperspectral image unmixing
• Enhanced Low-Rank Matrix Approximation
• ${\ell }_0$-Motivated Low-Rank Sparse Subspace Clustering
• Quaternion-based bilinear factor matrix norm minimization for color image inpainting
• Is Attention Better Than Matrix Decomposition?
• Improved Sparse Low-Rank Matrix Estimation
• Generalized Singular Value Thresholding
• Robust Subspace Clustering via Smoothed Rank Approximation
• Visual Processing by a Unified Schatten-$p$ Norm and ${\ell }_q$ Norm Regularized Principal Component Pursuit
• Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization
• Robust Subspace Clustering via Tighter Rank Approximation
• Top-N Recommender System via Matrix Completion
• Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints
• Fast Low-Rank Matrix Learning with Nonconvex Regularization
• Tensor factorization based method for low rank matrix completion and its application on tensor completion
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Proximal Iteratively Reweighted Algorithm with Multiple Splitting for Nonconvex Sparsity Optimization
• Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity
• Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning
• Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization
• From Rank Estimation to Rank Approximation: Rank Residual Constraint for Image Restoration
• Efficient Inexact Proximal Gradient Algorithm for Nonconvex Problems
• Top-N Recommendation with Novel Rank Approximation
• Regularized deep learning with nonconvex penalties
• Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization
• Frequency-Weighted Robust Tensor Principal Component Analysis
• Enhanced nonconvex low-rank approximation of tensor multi-modes for tensor completion
• A Unified Convex Surrogate for the Schatten-$p$ Norm
• Exploring Algorithmic Limits of Matrix Rank Minimization under Affine Constraints
• Multiplicative Noise Removal: Nonlocal Low-Rank Model and Its Proximal Alternating Reweighted Minimization Algorithm
• Inertial Bregman Proximal Gradient Algorithm For Nonconvex Problem with Smooth Adaptable Property
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Nonconvex Nonsmooth Low-Rank Minimization for Generalized Image Compressed Sensing via Group Sparse Representation
• An Iteratively Re-weighted Method for Problems with Sparsity-Inducing Norms
• Online high rank matrix completion
• Low Rank Regularization: A Review
• Enhanced image approximation using shifted rank-1 reconstruction
• From Group Sparse Coding to Rank Minimization: A Novel Denoising Model for Low-level Image Restoration