This paper presents a method for solving affine rank minimization problems using nuclear norm minimization. The affine rank minimization problem involves finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems are NP-hard in general, but the paper shows that under certain conditions, 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. The nuclear norm is a convex function that can be optimized efficiently and is the best convex approximation of the rank function over the unit ball of matrices with norm less than one. The paper discusses several random ensembles of equations where the restricted isometry property holds with overwhelming probability, provided the codimension of the subspace is Ω(r(m+n)log mn), where m, n are the dimensions of the matrix, and r is its rank. The techniques used in the analysis have strong parallels in the compressed sensing framework. The paper also discusses several algorithmic approaches to solving the norm minimization relaxations and illustrates the results with numerical examples. The main contribution of the paper is the development of a restricted isometry property (RIP) under which the nuclear norm heuristic can be guaranteed to produce the minimum-rank solution. The paper also shows that the RIP holds with overwhelming probability for several families of random matrices. The results extend the compressed sensing machinery to a more general direction by allowing a much more general notion of parsimonious models that rely on low-rank assumptions instead of cardinality restrictions. The paper also provides a dictionary between the matrix rank and nuclear norm minimization problems and the vector sparsity and ℓ₁ norm problems. The paper concludes with a discussion of possible directions for future research.This paper presents a method for solving affine rank minimization problems using nuclear norm minimization. The affine rank minimization problem involves finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems are NP-hard in general, but the paper shows that under certain conditions, 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. The nuclear norm is a convex function that can be optimized efficiently and is the best convex approximation of the rank function over the unit ball of matrices with norm less than one. The paper discusses several random ensembles of equations where the restricted isometry property holds with overwhelming probability, provided the codimension of the subspace is Ω(r(m+n)log mn), where m, n are the dimensions of the matrix, and r is its rank. The techniques used in the analysis have strong parallels in the compressed sensing framework. The paper also discusses several algorithmic approaches to solving the norm minimization relaxations and illustrates the results with numerical examples. The main contribution of the paper is the development of a restricted isometry property (RIP) under which the nuclear norm heuristic can be guaranteed to produce the minimum-rank solution. The paper also shows that the RIP holds with overwhelming probability for several families of random matrices. The results extend the compressed sensing machinery to a more general direction by allowing a much more general notion of parsimonious models that rely on low-rank assumptions instead of cardinality restrictions. The paper also provides a dictionary between the matrix rank and nuclear norm minimization problems and the vector sparsity and ℓ₁ norm problems. The paper concludes with a discussion of possible directions for future research.