Probabilistic Signal Recovery and Random Matrices
Abstract
Our research program spanned several areas of mathematics and data science. In the area of high dimensional inference, we showed that classical methods for linear regression (such as Lasso) are applicable for non-linear data. This surprising finding has already found several applications in the analysis of genetic, fMRI and proteomic data, compressed sensing, coding and quantization. In the area of network analysis, we showed how to detect communities in sparse networks by using semi-definite programming and regularized spectral clustering. In high dimensional convex geometry, we studied the complexity of convex sets. In numerical linear algebra, we analyzed the fastest known randomized approximation algorithm for computing the permanents of matrices with non-negative entries. In computational graph theory, we studied a randomized algorithm for estimating the number of perfect matchings in general graphs. In random matrix theory, we established delocalization of eigenvectors for a wide class of random matrices, proved a sharp invertibility result for sparse random matrices, showed how to improve the norm of a general random matrix by removing a small submatrix, and developed a simple and general tool for bounding the deviation of random matrices on arbitrary geometric sets. This has applications for dimension reduction, regression and compressed sensing.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 08, 2016
- Accession Number
- AD1023348
Entities
People
- Roman Vershynin
Organizations
- University of Michigan