Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization

Abstract

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems. Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 x 1000 matrices of rank 50 with a relative error of 1e-5 in about 3 minutes by sampling only 20 percent of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.

References in corpus (3)

• Consistency of trace norm minimization
• Exact Matrix Completion via Convex Optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion

Cited by in corpus (22)

• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Robust Low-rank Tensor Recovery: Models and Algorithms
• Matrix Completion from Noisy Entries
• Matrix Completion With Noise
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Efficient tensor completion: Low-rank tensor train
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms
• Regularization methods for learning incomplete matrices
• Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
• An Alternating Direction Method for Total Variation Denoising
• Efficient and Guaranteed Rank Minimization by Atomic Decomposition
• Rank-one Solutions for Homogeneous Linear Matrix Equations over the Positive Semidefinite Cone
• Reduced Rank Vector Generalized Linear Models for Feature Extraction
• Matrix recovery using Split Bregman
• Increasing Energy Efficiency in Sensor Networks: Blue Noise Sampling and Non-Convex Matrix Completion
• The Stability of Low-Rank Matrix Reconstruction: a Constrained Singular Value View
• Revisiting L21-norm Robustness with Vector Outlier Regularization
• Generalized singular value thresholding operator to affine matrix rank minimization problem
• Decomposition of Longitudinal Deformations via Beltrami Descriptors
• The Minimum-Rank Gram Matrix Completion via Modified Fixed Point Continuation Method
• Accurate low-rank matrix recovery from a small number of linear measurements