A Caltech Library Service

Null space conditions and thresholds for rank minimization

Recht, Benjamin and Xu, Weiyu and Hassibi, Babak (2011) Null space conditions and thresholds for rank minimization. Mathematical Programming, 127 (1). pp. 175-202. ISSN 0025-5610.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm—equal to the sum of the singular values—of the decision variable and has been shown to provide the optimal low rank solution in a variety of scenarios. In this paper, we assess the practical performance of this heuristic for finding the minimum rank matrix subject to linear equality constraints. We characterize properties of the null space of the linear operator defining the constraint set that are necessary and sufficient for the heuristic to succeed. We then analyze linear constraints sampled uniformly at random, and obtain dimension-free bounds under which our null space properties hold almost surely as the matrix dimensions tend to infinity. Finally, we provide empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic’s performance in non-asymptotic scenarios.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2010 Springer and Mathematical Optimization Society. Received: 21 April 2009; Accepted: 26 April 2010; Published online: 12 October 2010. This work was supported in part by the Office of Naval Research under grants N00014-08-1-0749 and MURI N-00014-08-1-0747, by the National Science Foundation under grants CCF-0729203 and CNS-0932428, by the David and Lucille Packard Foundation, and by Caltech's Lee Center for Advanced Networking.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0749
Office of Naval Research (ONR)N00014-08-1-0747
David and Lucile Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Rank; Convex optimization; Matrix norms; Random matrices; Compressed sensing; Gaussian processes
Issue or Number:1
Record Number:CaltechAUTHORS:20110401-112500555
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23202
Deposited By: Jason Perez
Deposited On:04 Apr 2011 18:16
Last Modified:03 Oct 2019 02:44

Repository Staff Only: item control page