Analysis of High-Dimensional Stochastic Systems

Brown University, Providence RI

Investigators

Abstract

A common theme that arises in many domains of application is that data is high-dimensional and various techniques have to be used to study and analyze such data in a computationally tractable way. The random projection of high-dimensional data is a simple and computationally efficient technique to reduce the dimensionality of a data set by trading a controlled amount of error for faster processing times and smaller model sizes. While several properties of random projections have been studied, the question of what random projections do to outliers in the data, which appear in the tails of the data distribution, is not well understood. This project is to rigorously characterize the tails of random projections of high-dimensional distributions. Understanding such tail behavior will also provide insight into how to distinguish between high-dimensional distributions by looking at their lower-dimensional projections. This has potential applications in a variety of fields including computer science, data analysis, statistics, and convex geometry. Another set of data analysis techniques used for data classification include spectral clustering and correlation clustering. Both these techniques are related to certain operator norms of associated matrices. This project will characterize the asymptotics of operator norms, in the limit of high dimensions, and study potential applications to the stability of numerical methods (for example, matrix condition number estimation) as well as clustering problems. The project has a strong educational component, with provisions for math outreach, research training of graduate students, and development of new courses. The project has two themes. The first theme relates to the study of large deviations or the tail behavior of random projections of high-dimensional measures. These are of interest in high-dimensional statistics and probability, as well as asymptotic convex geometry, where the object of interest is the volume or surface measure of a convex body in high dimensions. While fluctuations of random projections have been well studied, culminating in the celebrated central limit theorem for convex sets, large deviations or tail probabilities of random projections are less well understood. A goal of the project is to establish large deviations principles, both averaged over the direction of projection (the annealed setting) and conditioned on the direction of projection, as well as sharp large deviation estimates, and understand their ramifications for high-dimensional statistics and asymptotic convex geometry. The second theme relates to the study of the asymptotics of operator norms for high-dimensional random matrices, which are relevant in a variety of contexts, including optimization theory, theoretical computer science and functional analysis, with applications to machine learning and data analysis. While the two-to-two norm, which coincides with the singular value, has been well studied, the focus will be to study more general r-to-p norms, where spectral theory can no longer be used and thus will require the development of fundamentally new techniques, involving a combination of tools from algebra, analysis and probability. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.