Universality in Learning from Linear Measurements

Abstract

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 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$.

References in corpus (8)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Message Passing Algorithms for Compressed Sensing
• Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Upper-bounding ${\ell }_1$-optimization weak thresholds

Cited by in corpus (4)

• Universality Laws for High-Dimensional Learning with Random Features
• Gaussian Universality of Perceptrons with Random Labels
• Optimum GSSK Transmission in Massive MIMO Systems Using the Box-LASSO Decoder
• Asymptotic Behavior of Adversarial Training in Binary Classification