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.