Show simple item record

dc.contributor.authorLiu, Yang
dc.description.abstractThe 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.
dc.subjectRandom Matrices
dc.subjectSparse Recovery
dc.subjectNull Space Property
dc.titleNon-convex optimization for linear system with pregaussian matrices and recovery from multiple measurements
dc.description.advisorMing-Jun Lai
dc.description.committeeMing-Jun Lai
dc.description.committeeJingzhi Tie
dc.description.committeeAndrew Sornborger
dc.description.committeeAlexander Petukhov
dc.description.committeeEdward Azoff

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record