A Caltech Library Service

Universality in Learning from Linear Measurements

Abbasi, Ehsan and Salehi, Fariborz and Hassibi, Babak (2019) Universality in Learning from Linear Measurements. In: 33rd Conference on Neural Information Processing Systems. Neural Information Processing Systems Foundation, Inc. , Art. No. 9404.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.

[img] Archive (ZIP) - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


We study the problem of recovering a structured signal from independently and identically drawn linear measurements. A convex penalty function f(⋅) is considered which penalizes deviations from the desired structure, and signal recovery is performed by minimizing f(⋅) subject to the linear measurement constraints. The main question of interest is to determine the minimum number of measurements that is necessary and sufficient for the perfect recovery of the unknown signal with high probability. Our main result states that, under some mild conditions on f(⋅) and on the distribution from which the linear measurements are drawn, the minimum number of measurements required for perfect recovery depends only on the first and second order statistics of the measurement vectors. As a result, the required of number of measurements can be determining by studying measurement vectors that are Gaussian (and have the same mean vector and covariance matrix) for which a rich literature and comprehensive theory exists. As an application, we show that the minimum number of random quadratic measurements (also known as rank-one projections) required to recover a low rank positive semi-definite matrix is 3nr, where n is the dimension of the matrix and r is its rank. As a consequence, we settle the long standing open question of determining the minimum number of measurements required for perfect signal recovery in phase retrieval using the celebrated PhaseLift algorithm, and show it to be 3n.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2019 Neural Information Processing Systems Foundation, Inc. This work was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by a grant from Futurewei Inc., by NASA’s Jet Propulsion Laboratory through the President and Director’s Fund, and by King Abdullah University of Science and Technology.
Funding AgencyGrant Number
JPL President and Director's FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Record Number:CaltechAUTHORS:20190628-083750345
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96808
Deposited By: Tony Diaz
Deposited On:28 Jun 2019 17:11
Last Modified:09 Jul 2020 21:14

Repository Staff Only: item control page