A Caltech Library Service

Simultaneously Structured Models with Application to Sparse and Low-rank Matrices

Oymak, Samet and Jalali, Amin and Fazel, Maryam and Eldar, Yonina C. and Hassibi, Babak (2015) Simultaneously Structured Models with Application to Sparse and Low-rank Matrices. IEEE Transactions on Information Theory, 61 (5). pp. 2886-2908. ISSN 0018-9448.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Recovering structured models (e.g., sparse or group-sparse vectors, low-rank matrices) given a few linear observations have been well-studied recently. In various applications in signal processing and machine learning, the model of interest is structured in several ways, for example, a matrix that is simultaneously sparse and low rank. Often norms that promote the individual structures are known, and allow for recovery using an order-wise optimal number of measurements (e.g., ℓ_1 norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable to minimize a combination of such norms. We show that, surprisingly, using multiobjective optimization with these norms can do no better, orderwise, than exploiting only one of the structures, thus revealing a fundamental limitation in sample complexity. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation. Further, specializing our results to the case of sparse and low-rank matrices, we show that a nonconvex formulation recovers the model from very few measurements (on the order of the degrees of freedom), whereas the convex problem combining the ℓ_1 and nuclear norms requires many more measurements, illustrating a gap between the performance of the convex and nonconvex recovery problems. Our framework applies to arbitrary structure-inducing norms as well as to a wide range of measurement ensembles. This allows us to give sample complexity bounds for problems such as sparse phase retrieval and low-rank tensor completion.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper DOIArticle
Additional Information:© 2015 IEEE. Manuscript received February 11, 2013; revised July 21, 2014; accepted October 29, 2014. Date of publication February 9, 2015; date of current version April 17, 2015. A. Jalali and M. Fazel were supported by the National Science Foundation under Grant ECCS-0847077 and Grant CCF-1409836. Y. C. Eldar was supported in part by the Israel Science Foundation under Grant 170/10, in part by SRC, and in part by the Intel Collaborative Research Institute for Computational Intelligence. B. Hassibi was supported in part by the National Science Foundation under Grant CNS-0932428, Grant CCF-1018927, Grant CCF-1423663, and Grant CCF-1409204, in part by the Office of Naval Research through the MURI under Grant N00014-08-0747, in part by Qualcomm Inc., San Diego, CA, USA, and in part by King Abdulaziz University, Jeddah, Saudi Arabia.
Funding AgencyGrant Number
Israel Science Foundation170/10
Intel Collaborative Research Institute for Computaional IntelligenceUNSPECIFIED
Office of Naval Research (ONR)N00014-08-0747
King Abdulaziz UniversityUNSPECIFIED
Subject Keywords:Compressed sensing, convex relaxation, regularization, sample complexity
Issue or Number:5
Record Number:CaltechAUTHORS:20150126-073012139
Persistent URL:
Official Citation:Oymak, S.; Jalali, A.; Fazel, M.; Eldar, Y.C.; Hassibi, B., "Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices," Information Theory, IEEE Transactions on , vol.61, no.5, pp.2886,2908, May 2015 doi: 10.1109/TIT.2015.2401574 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54047
Deposited By: Shirley Slattery
Deposited On:27 Jan 2015 00:30
Last Modified:03 Oct 2019 07:54

Repository Staff Only: item control page