## Non-convex optimization for linear system with pregaussian matrices and recovery from multiple measurements

##### Abstract

The extremal singular values of random matrices in ell_{2}-norm, including Gaussian random matrices, Bernoulli random matrices, subgaussian random matrices, etc, have attracted major research interest in recent years. In this thesis, we study the q-singular values, defined in terms of the ell_{q}-quasinorm, of pregaussian random matrices. We give the upper tail probability estimate on the largest q-singular value of pregaussian random matrices for 0<qle1, and also the lower tail probability estimate. Particularly, these estimates show that the largest q-singular value is of order m^{1/q} with high probability for pregaussian random matrices of size m by m. Moreover, we also give probabilistic estimates for the smallest q-singular value of pregaussian random matrices. In addition, we also present some results on the largest p-singular value for p>1, and some numerical-experimental results as well.
Compressed sensing, a technique for recovering sparse signals, has also been an active research topic recently. The extremal singular values of random matrices have applications in compressed sensing, mainly because the restricted isometry constant of sensing matrices depends on them. We prove that pregaussian random matrices with m much less than N but much larger than N^{q/2} have the q-modified restricted isometry property for 0<qle1 with overwhelming probability. As a result, we show that every sparse vector can be recovered as a solution to the ell_{q}-minimization problem with overwhelming probability if m is much less than N but much larger than N^{q/2}.
In compressed sensing, we also show that the real and complex null space properties (NSP) are equivalent for the sparse recovery by ell_{q}-minimization and more generally for the NSP for the joint-sparse recovery from multiple measurements via ell_{q}-minimization. These results answer the open questions raised by Foucart and Gribonval. We also extend Berg and Friedlander's theorem on NSP for recovery from multiple measurements. As a consequence of the equivalence on the NSP and the extension, we give a necessary and sufficient condition for the uniqueness of the solution to the multiple-measurement-vector non-convex optimization problem.