On the Universal Phase Transitions of Linear Inverse Problems

The recent advances in compressed sensing allowed us to have a unified understanding of linear dimensionality reduction. For instance, for the task of low-dimensional model recovery, we have a precise characterization of sample complexity when the sampling matrix is i.i.d. standard normal. For other ensembles, there are various promising results, for instance, subgaussian matrices have the same sample complexity up to a constant. In this work, given a subset C of the unit ball we investigate the loss min_{v in C}||Av||^2 for a matrix A with i.i.d. zero-mean, unit variance entries. We show the universality of this loss for convex sets C and obtain universal lower bounds to this loss for nonconvex sets. As an implication, we find that for linear inverse problems the sample complexity of an i.i.d. matrix is at least as good as that of a Gaussian matrix. In particular, Gaussian width determines the sample complexity. Application of our results to the lasso formulation indicates that not only the sample complexity but even the noise sensitivity is universal.