This proposal will advance and apply the techniques of geometric functional analysis for theoretical and computational problems related to random operators. The classical random matrix theory traditionally focuses on the asymptotic regime, when the dimensions of the matrices increase to infinity. However, many of today's applications operate in the non-asymptotic regime, with fixed but large dimensions, and they require explicit probability bounds. A systematic development of the non-asymptotic random matrix theory will be carried out. Special attention will be paid to advancing the invertibility theory of random operators. Building on the recent progress on estimating the condition numbers and the smallest singular values of random matrices with independent entries, the program will now be expanded to include some more difficult classes or random operators: random Hermitian matrices, randomly perturbed deterministic matrices, random submatrices of deterministic matrices, operators that factor through random matrices, sums of independent random matrices and random matrices with independent columns. These advances will be based on on parallel development of probabilistic, analytical and geometric tools, including the Littlewood-Offord theory of small ball probabilities and its connections with additive combinatorics.
In high dimensional spaces, random operators/matrices are widely used to model transformations that are too complicated or too general to be understood deterministically or explicitely. The more classical applications of this randomized approach, including those in mathematical physics, operate in the asymptotic regime. This means that the random operators act on spaces whose dimension increases indefinitely, and one seeks to capture the limiting picture as the dimension approaches infinity. In contrast, many of today's applications operate in the non-asymptotic regime, acting on spaces of large but fixed dimensions. This happens in particular in functional analysis where random operators model typical operators; numerical analysis of algorithms where random matrices model typical inputs; the new area of compressed sensing where random operators are the best known measurement systems; statistics where random matrices capture the dependencies among the various parameters of a sample of a population. This proposal will systematically advance and unite the random matrix theory in the non-asymptotic regime, with a view toward applications in the areas mentioned above. The program is based on collaboration with researchers in geometric functional analysis, statistics, electrical engineering, and computer science. A graduate student is expected to join the PI's efforts starting the second year of the program.
One major goal of this project was to reveal fundamental properties of random matrices. Random matrices are arrays of numbers chosen at random, such as 0 or 1. They are widely used in theoretical mathematics, statistical physics and applied areas. It is traditional to accept asymptotic approach when analyzing random matrices, thereby increasing the dimension to infinity and trying to capture the limiting picture. In this project, new techniques were developed for non-asymptotic analysis, where the dimensions of matrices stay fixed. Being able to working in a non-asymptotic regime is a must for many applications in signal processing and statistics. One key outcomes of this project include a proof that many natural classes of random matrices are "well conditioned", which in particular means that algorithms that use these matrices run stably. Anotheroutcome is that such matrices are "delocalized", which means that when they operatein roughly the same way in all canonical directions (called eigenvectors). Another facet of this project is a new geometric way to look at estimation problems in high dimensions, for example a problem of recovering an audio signal from a coarsely quantized sample, such as a string of 0/1 numbers. A key outcome is an estimatefor the optimal size of the sample needed for signal recovery based on our prior information about the signal. This and other applied problems form a class of high-dimensional estimation problems with constraints, for which a general approach is found in this project.
