CaltechAUTHORS
  A Caltech Library Service

New Null Space Results and Recovery Thresholds for Matrix Rank Minimization

Oymak, Samet and Hassibi, Babak (2010) New Null Space Results and Recovery Thresholds for Matrix Rank Minimization. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20150129-072018732

[img] PDF - Submitted Version
See Usage Policy.

514Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150129-072018732

Abstract

Nuclear norm minimization (NNM) has recently gained significant attention for its use in rank minimization problems. Similar to compressed sensing, using null space characterizations, recovery thresholds for NNM have been studied in. 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 compressed sensing to the null space conditions of NNM. The resulting thresholds are significantly better and in particular our weak threshold appears to match with simulation results. Further our curves suggest for any rank growing linearly with matrix size n we need only three times of oversampling (the model complexity) for weak recovery. Similar to we analyze the conditions for weak, sectional and strong thresholds. Additionally a separate analysis is given for special case of positive semidefinite matrices. We conclude by discussing simulation results and future research directions.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1011.6326arXivDiscussion Paper
Additional Information: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.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
NSFCNS-0932428
NSFCCF-1018927
Office of Naval Research (ONR)N00014-08-1-0747
Caltech’s Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20150129-072018732
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150129-072018732
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54214
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:30 Jan 2015 22:23
Last Modified:30 Jan 2015 22:23

Repository Staff Only: item control page