Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2015 | Submitted
Journal Article Open

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

Abstract

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.

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.

Attached Files

Submitted - Simultaneously_Structured_Models.pdf

Files

Simultaneously_Structured_Models.pdf
Files (447.2 kB)
Name Size Download all
md5:f05ad41394373a0d3b1d83e658a679ee
447.2 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
March 5, 2024