Probabilistic Signal Recovery and Random Matrices
Roman Vershynin · 2016
Abstract : Our research program spanned several areas of mathematics and data science. In the area of highdimensionalinference, we showed that classical methods for linear regression (such as Lasso) areapplicable for non-linear data. This surprising finding has already found several applications in theanalysis of genetic, fMRI and proteomic data, compressed sensing, coding and quantization. In the area ofnetwork analysis, we showed how to detect communities in sparse networks by using semidefiniteprogramming and regularized spectral clustering. In high dimensional convex geometry, we studied thecomplexity of convex sets. In numerical linear algebra, we analyzed the fastest known randomizedapproximation algorithm for computing the permanents of matrices with non-negative entries. Incomputational graph theory, we studied a randomized algorithm for estimating the number of perfectmatchings in general graphs. In random matrix theory, we established delocalization of eigenvectors for awide class of random matrices, proved a sharp invertibility result for sparse random matrices, showed howto improve the norm of a general random matrix by removing a small submatrix, and developed a simpleand general tool for bounding the deviation of random matrices on arbitrary geometric sets. This has applications for dimension reduction, regression and compressed sensing.