Non-asymptotic problems on random operators in geometric functional analysis and applications

本提案将推进和应用几何泛函分析技术来解决与随机算子相关的理论和计算问题。经典随机矩阵理论传统上关注的是矩阵维数增加到无穷大时的渐近状态。然而，今天的许多应用都是在非渐近状态下运行的，具有固定但大的维度，并且它们需要明确的概率界限。非渐近随机矩阵理论的系统发展将进行。我们将特别注意提出随机算子的可逆性理论。基于最近在估计条件数和具有独立条目的随机矩阵的最小奇异值方面的进展，该程序现在将扩展到包括一些更困难的类或随机算子：随机厄米矩阵，随机摄动确定性矩阵，确定性矩阵的随机子矩阵，通过随机矩阵因子的算子，独立随机矩阵的和和具有独立列的随机矩阵。这些进步将基于概率、分析和几何工具的并行发展，包括小球概率的Littlewood-Offord理论及其与加性组合学的联系。在高维空间中，随机算子/矩阵被广泛用于对过于复杂或过于普遍而无法确定或显式理解的转换进行建模。这种随机化方法的更经典的应用，包括在数学物理中的应用，都是在渐近状态下运行的。这意味着随机算子作用于维度无限增加的空间，当维度接近无穷大时，人们试图捕捉极限图像。相比之下，今天的许多应用程序在非渐近状态下运行，作用于大但固定维度的空间。这尤其发生在泛函分析中随机算子模拟典型算子；随机矩阵模拟典型输入的算法的数值分析；压缩感知的新领域，其中随机算子是最著名的测量系统；随机矩阵捕捉总体样本的各种参数之间的依赖关系的统计学。本文将系统地推进和统一随机矩阵理论在非渐近状态下的应用，以期在上述领域的应用。该计划基于与几何功能分析，统计学，电气工程和计算机科学方面的研究人员的合作。预计一名研究生将从项目的第二年开始加入PI的工作。

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.