A Caltech Library Service

Improved thresholds for rank minimization

Oymak, Samet and Khajehnejad, M. Amin and Hassibi, Babak (2011) Improved thresholds for rank minimization. In: 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE , Piscataway, NJ, pp. 5988-5991. ISBN 978-1-4577-0538-0.

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

Use this Persistent URL to link to this item:


Nuclear norm minimization (NNM) has recently gained attention for its use in rank minimization problems. In this paper, we define weak, sectional and strong recovery for NNM to succeed at finding the low rank solution. We find tight conditions for these and analyze them for the case where the linear measurement operator consists of i.i.d. Gaussian entries. Finally we calculate the so called weak, sectional and strong thresholds for the success of nuclear norm minimization. To obtain our results, we generalize the notion of sign and support from sparse vectors to low rank matrices, and achieve a weak threshold which is much closer to the empirical phase transition curve of nuclear norm minimization than the existing bounds available in the literature.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Caltech’s Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20150204-070559629
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54341
Deposited By: Shirley Slattery
Deposited On:04 Feb 2015 22:53
Last Modified:03 Oct 2019 07:57

Repository Staff Only: item control page