High dimensional data: new phenomena and theory in modeling and approximation

该奖项是根据2009年《美国复苏和再投资法案》(公法111-5)资助的。该项目研究高维环境，例如在潜在预测因素多于观测时选择线性回归模型，以及在可用特征多于观测时进行线性判别分析，在这两种情况下都假设只有一小部分未知因素相关。二维相图索引变量数量与观测数量的比率以及相关变量比例的衡量标准。在此图的一个区域中，分析任务可以成功完成，在其他区域中，分析任务完全失败。研究人员在降维方面提出了四个方面的努力：(1)高维数据分析中相变的现象学：进行结构化的大规模计算研究，深入研究几个这样的相变，并揭示经验规律供理论家研究。(2)支持高维数据分析的理论统计：提出者已经发展出一个“在物理学家的严谨水平上”的推导，粗略地表明，对于相图中高于某一边界的*任何*算法，回归模型的选择一定失败。为这个项目计划的一个严格的证明将涉及经典统计决策理论、随机矩阵理论和统计物理启发式的相互作用。(3)高维凸几何：高维数据分析中的几个相变与高维凸几何中的某些关键现象之间存在着一种令人惊讶但具有启发性的关系。该项目将进一步探索这些阶段转变和联系。(4)用大型随机矩阵进行推理：从随机矩阵理论的角度出发，在经典多变量分析中引入了有用的新问题和新结果，并与预期的相变工作建立了有用的联系。例如，该项目将系统地研究在多变量分析的各种标准统计环境中“连续”备选方案的最大根统计量的分布，并解决相关问题，如双Wishart模型的尾部不平等。从计算生物学到图像理解等领域的科学实践产生了越来越多的数据集，在这些数据集中，每个观测单位测量了大量的特征。所得到的高维数据集通常被挖掘以寻找特征和关联。在许多情况下，特征至少和观测一样多。最近清楚的是，在这种情况下的数据分析提供了对应用程序具有真正重要意义的深刻的新现象。有两个例子--其中有很多--包括：线性回归模型选择，当潜在的预测值比观测值多，但只有一小部分是相关的(哪些是未知的)，以及线性判别分析，当可用的特征比观测值多，但同样只有一小部分未知因素相关时。在这种情况下，有一种用“相图”描述的“分解”现象：相关特征的数目与不可能从数据中学习某些程序的观察数目之间的精确关系。该项目将开发的关于这一现象的新结果将使高维数据分析的实践者更好地理解数据挖掘的尖锐限制，并在统计理论与高维凸几何和统计物理等领域之间建立新的联系。

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The project studies high dimensional settings exemplified by Linear Regression model selection when there are more potential predictors than observations, and Linear Discriminant Analysis when there are more available features than observations, in both cases assuming that only a small unknown fraction are relevant. A two-dimensional phase diagram indexes the ratio of number of variables to number of observations as well as a measure of the fraction of relevant variables. In one region of this diagram, the analysis task can be completed successfully, elsewhere it fails utterly. The investigators propose a four-pronged effort on dimensionality reduction: (1) Phenomenology of Phase Transitions in High-Dimensional Data Analysis: Make structured large-scale computational studies to investigate several such transitions in depth and expose empirical regularities for theoreticians to study. (2) Theoretical Statistics Supporting High-Dimensional Data Analysis: Proposers have developed `at the physicist's level of rigor' a derivation showing roughly that regression model selection must fail for *any* algorithm above a certain boundary in the phase diagram. A rigorous proof, planned for this project, will involve the interplay of classical statistical decision theory, random matrix theory, and statistical physics heuristics. (3) High Dimensional Convex Geometry: A surprising but revealing relationship exists between several of the phase transitions of high-dimensional data analysis and certain key phenomena in high-dimensional convex geometry. The project will further explore these phase transitions and connections. (4) Inference with Large Random Matrices: A random matrix theory perspective leads to useful new questions and results in classical multivariate analysis that will be pursued in this proposal, with useful connections with the phase transition work expected. For example, the project will systematically study the distribution of the largest root statistic at ``contiguous'' alternatives in a variety of the standard statistical settings of multivariate analysis, and address related questions such as tail inequalities for the double Wishart model. Scientific practice in fields ranging from computational biology to image understanding generates ever more datasets in which massive numbers of features are measured per observational unit. The resulting high-dimensional datasets are often mined for features and associations. In many cases, there are at least as many features as observations. It has lately become clear that data analysis in this setting offers deep new phenomena of real importance to applications. Two examples -- of many -- include: Linear Regression model selection when there are more potential predictors than observations, but only a small fraction of these are relevant (and which ones aren't known), and Linear Discriminant Analysis when there are more available features than observations, but again only a small unknown fraction are relevant. In such cases there is a `breakdown' phenomenon, described by a 'phase diagram': a precise relationship between the number of relevant features and the number of observations at which certain procedures for learning from data become impossible. The new results to be developed about this phenomenon by this project will provide practitioners of high-dimensional data analysis with an improved understanding of the sharp limits to data mining, as well as forging new links between statistical theory and fields like high-dimensional convex geometry and statistical physics.