Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

By B. Recht, Maryam Fazel, Pablo A. Parrilo. 2007

3,954 citations recorded by the source corpus.

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard because it contains vector cardinality minimization as a special case. In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum-rank solution can be recovered by solving a convex optimization problem, namely, the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability, provided the codimension of the subspace is sufficiently large. The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this preexisting concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization. We also discuss several algorithmic approaches to minimizing the nuclear norm and illustrate our results with numerical examples.

Subfields: Computational Mechanics, Electrical and Electronic Engineering, Signal Processing

How researchers see this paper

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

In Computational Mechanics

In Electrical and Electronic Engineering

In Signal Processing

Citations in the corpus

Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “Lemma 6 is stronger than similar results appearing in Rennie and Srebro (2005) and Abernethy et al.”
Exact Matrix Completion via Convex Optimization (2008, methodology): “In these experiments, the recovery regime is far larger than in the case of that of sampling entries, but this is not particularly surprising as each Gaussian observation measures a contribution from every entry in the matrix M. These Gaussian models were studied extensively in [ 29 ].”
Geometric median and robust estimation in Banach spaces (2013, background): “The problem of low-rank matrix estimation has attracted a lot of attention during the last several years, for example, see [11,39] and references therein.”
A Singular Value Thresholding Algorithm for Matrix Completion (2008, background): “This more general formulation is considered in [16] and [57] as an extension of the matrix completion problem.”
Implicit Regularization in Matrix Factorization (2017, background): “The emerging story is that gradient descent biases us to a low nuclear norm solution, and we already know how having low nuclear norm can ensure generalization [17, 6] and minimizing the nuclear norm ensures reconstruction [15, 5].”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, background): “In 2007, Recht, Fazel, and Parillo demonstrated that it is possible to reconstruct a rank-deficient matrix from Gaussian measurements [112].”
Provable Inductive Matrix Completion (2013, background): “That is, using nearly linear number of measurements in d 1 , d 2 , one can exactly recover the Note that several similar recovery results for the matrix sensing problem already exist in the literature that guarantee exact recovery using Ω( k ( [1, 10, 9].”
Sparse Bayesian Methods for Low-Rank Matrix Estimation (2011, background): “Formal equivalence of these two problems is established in [1] and recovery guarantees exist under some conditions (see, for example, [3], [21]).”
Optimization for machine learning (2010, background): “In terms of norms, we did not consider regularization by the nuclear norm, also known as the trace norm, which seeks low-rank matrix solutions (Fazel et al., 2001; Srebro et al., 2005; Recht et al., 2007; Bach, 2008b).”
The Convex Geometry of Linear Inverse Problems (2010, methodology): “More recently the nuclear norm has been proposed as an effective convex surrogate for solving rank minimization problems subject to various affine constraints [62, 17].”
Kernel and Deep Regimes in Overparametrized Models (2019, methodology): “In contrast, in the “deep” regime, as was previously observed by Gunasekar et al., training leads to the minimum nuclear norm solution, a rich inductive bias that allows for generalization [3, 20].”