"Big-Data" Asymptotics: Theory and Large-Scale Experiments

大型数据集在科学和技术中变得越来越可用和重要。该项目将开发用于处理大型数据集的新工具，以及对高维数据中出现的一些迷人现象的新理解。该项目将开发从高度欠采样测量（也称为压缩感知和矩阵完成）中恢复信号（矢量和矩阵）的方法，以及从噪声和欠采样测量中恢复低秩矩阵的方法，以及在预测变量数量非常大时稳健拟合预测模型的工具。所有这些工具都具有广泛的适用性-基本上，无论在哪里收集大数据，研究人员都希望使用这些工具。将探讨的现象包括一些算法经历的相变，突然从成功恢复到失败，作为欠采样和/或污染的数据量的增加，以及经典统计的基本公式，如Fisher信息公式的方差的最大似然估计，不再适用于高维统计。我们期望能对这些现象作出精确的定量解释。 我们的定量解释将帮助工程师和科学家计划实验，并从大型数据集作出可靠的推断。当变量数p和观测数n都很大时，多元数据分析中的几个经典问题发展出一个新的性质。这些问题包括线性模型中的估计，线性模型中的稳健估计，线性模型中的稀疏惩罚估计，以及服从因子模型的协方差矩阵的估计。特别是，在一系列领域的工作表明，如果问题的某些基本特征是随机的（如iid高斯预测变量，或均匀分布的特征向量），那么当p和n以固定比例趋于无穷大时，极限会出现各种意外。 这些惊喜包括尖锐的相变的成功/失败的恢复感兴趣的对象和额外的高斯噪声超出所造成的测量，没有经典的对应物在p固定n趋于无穷大的情况下。在拟议的工作中，我们将使用大量的计算实验和精确的理论计算，预测和验证这种令人惊讶的现象在大n，大p设置。我们的技术包括（在计算方面）用于设计和执行计算实验的新工具，涉及基于云的配置中的许多处理器，以及（在理论方面）用于理解压缩传感中的相变的分析工具，无论是在精确重建无噪声测量和渐近均方误差的凸优化重建以及渐近均方误差的非，凸优化在矩阵的低秩模型的研究中，我们将发展和适应随机矩阵理论的最新进展，例如所谓的尖峰协方差模型的最新进展。

Large datasets are becoming increasingly available and important in science and technology. This project will develop new tools for dealing with large datasets, as well as a new understanding of some of the fascinating phenomena that emerge with high-dimensional data. This project will develop methods for recovering signals (vectors and matrices) from highly undersampled measurements (also known as compressed sensing and matrix completion), and for recovering low-rank matrices from noisy and under sampled measurements, and tools for robustly fitting predictive models when the number of predictor variables is very large. All of these tools have broad domains of applicability -- basically wherever big data are being gathered, researchers will want to use such tools. Phenomena that will be explored include the phase transitions that some algorithms undergo, going abruptly from successful recovery to failure, as the amount of undersampling and/or contamination of the data increases, and the fact that fundamental formulas of classical statistics, such as the Fisher information formula for variance of the maximum-likelihood estimator, no longer apply in high-dimensional statistics. We expect to develop quantitatively precise explanations of these phenomena. Our quantitative explanations will help engineers and scientists plan experiments and make reliable inferences from large datasets.Several classical problems in multivariate data analysis develop a new character when the number of variables p and the number of observations n are both large. These problems include estimation in the linear model, robust estimation in the linear model, sparsity-penalized estimation in the linear model, and estimation of covariance matrices obeying a factor model. In particular, work in a range of fields shows that if certain underlying features of the problem are random (such as iid Gaussian predictor variables, or uniformly distributed eigenvectors), then various surprises occur in the limit when p and n tend to infinity in a fixed proportion. These surprises include sharp phase transitions in the success/failure of recovering the object of interest and extra gaussian noise beyond that caused by the measurements which have no classical counterpart in the p fixed n tending to infinity case. In the proposed work, we will use both massive computational experiments and precise theoretical calculations, to predict and verify such surprising phenomena in the large n, large p setting. Our techniques involve (on the computing side) new tools for design and execution of computational experiments involving many processors in cloud-based configurations, as well as (on the theoretical side) analysis tools for understanding phase transitions in compressed sensing, both in exact reconstruction from noiseless measurements and in asymptotic mean-squared error of convex optimization reconstructions as well as asymptotic mean-squared error of non-convex optimizations. In the study of low-rank models for matrices, we will develop and adapt recent advances in random matrix theory, such as recent progress in the so-called spiked covariance model.