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.