A Caltech Library Service

Tight Recovery Thresholds and Robustness Analysis for Nuclear Norm Minimization

Oymak, Samet and Hassibi, Babak (2011) Tight Recovery Thresholds and Robustness Analysis for Nuclear Norm Minimization. In: 2011 IEEE International Symposium on Information Theory Proceedings. IEEE , Piscataway, NJ, pp. 2323-2327. ISBN 978-1-4577-0596-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 significant attention for its use in rank minimization problems. Using null space characterizations, recovery thresholds for NNM have been previously studied for the case of Gaussian measurements as matrix dimensions tend to infinity. However simulations show that the thresholds are far from optimal, especially in the low rank region. In this paper we apply the recent analysis of Stojnic for ℓ_1-minimization to the null space conditions of NNM. The results are significantly better and in particular our weak threshold appears to match with simulation results. Further, our closed form bounds suggest for any rank growing linearly with matrix size n one needs only three times of oversampling (the model complexity) for weak recovery and eight times for strong recovery. Additionally, the results for robustness analysis are given which indicate with slightly more measurements recovery guarantees for approximately low rank matrices can be given.

Item Type:Book Section
Related URLs:
Additional Information:© 2011 IEEE. Date of Current Version: 03 October 2011.
Subject Keywords:nuclear norm minimization, recovery thresholds, robustness analysis
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12300288
Record Number:CaltechAUTHORS:20120406-113136818
Persistent URL:
Official Citation:Oymak, S.; Hassibi, B.; , "Tight recovery thresholds and robustness analysis for nuclear norm minimization," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , vol., no., pp.2323-2327, July 31 2011-Aug. 5 2011 doi: 10.1109/ISIT.2011.6033977 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:30016
Deposited By: Ruth Sustaita
Deposited On:06 Apr 2012 20:21
Last Modified:03 Oct 2019 03:46

Repository Staff Only: item control page