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

“大数据”渐进：理论和大规模实验

• 批准号: 1418362
• 负责人: David Donoho
• 金额: $ 70.06万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-15 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1418362&HistoricalAwards=false
• 关键词: Big; Data; Asymptotics; Theory; Large

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.

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