Timezone: »
Poster
Universality in Learning from Linear Measurements
Ehsan Abbasi · Fariborz Salehi · Babak Hassibi
Thu Dec 12 05:00 PM  07:00 PM (PST) @ East Exhibition Hall B + C #56
We study the problem of recovering a structured signal from independently and identically drawn linear measurements. A convex penalty function $f(\cdot)$ is considered which penalizes deviations from the desired structure, and signal recovery is performed by minimizing $f(\cdot)$ 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(\cdot)$ 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 rankone projections) required to recover a low rank positive semidefinite 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$.
Author Information
Ehsan Abbasi (Caltech)
Fariborz Salehi (California Institute of Technology)
Babak Hassibi (Caltech)
More from the Same Authors

2020 Poster: Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems »
Sahin Lale · Kamyar Azizzadenesheli · Babak Hassibi · Anima Anandkumar 
2019 Poster: The Impact of Regularization on Highdimensional Logistic Regression »
Fariborz Salehi · Ehsan Abbasi · Babak Hassibi 
2018 Poster: Learning without the Phase: Regularized PhaseMax Achieves Optimal Sample Complexity »
Fariborz Salehi · Ehsan Abbasi · Babak Hassibi 
2017 Poster: A Universal Analysis of LargeScale Regularized Least Squares Solutions »
Ashkan Panahi · Babak Hassibi 
2017 Spotlight: A Universal Analysis of LargeScale Regularized Least Squares Solutions »
Ashkan Panahi · Babak Hassibi 
2016 Poster: Fundamental Limits of BudgetFidelity Tradeoff in Label Crowdsourcing »
Farshad Lahouti · Babak Hassibi 
2015 Poster: LASSO with Nonlinear Measurements is Equivalent to One With Linear Measurements »
CHRISTOS THRAMPOULIDIS · Ehsan Abbasi · Babak Hassibi 
2015 Spotlight: LASSO with Nonlinear Measurements is Equivalent to One With Linear Measurements »
CHRISTOS THRAMPOULIDIS · Ehsan Abbasi · Babak Hassibi