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

Stanford University, Stanford CA

Investigators

Abstract

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.