AF: Small: Geometry and High-dimensional Inference

从计算机图形学到地理信息系统，从传感器网络到社会网络，从经济到医学，数据分析在广泛的应用领域中无处不在。它代表了计算科学中的一个基本问题。该项目将推进对数据分析背后的基本问题的理论理解，并开发实用的算法，这些算法将对科学和工程中的广泛问题有用。该项目解决了从采样数据重建概率分布结构的基本问题。它将研究张量和其他高阶方法的使用，特别是那些允许有效优化的方法。该项目涉及理论计算机科学、机器学习、信号处理和统计学，并将在所有这些领域产生潜在影响。近年来，张量方法在数据分析和推理中的兴趣重新抬头，特别是在理论计算机科学中。这些方法将在机器学习、信号处理和其他领域的各种应用中被证明是有用的。该项目将开发一系列算法来解决一系列问题，包括盲源分离、谱聚类、混合模型中的推理和估计分布的几何。它将分析这些问题及相关问题的复杂性。特别是，它将努力了解计算效率的变化和对空间维度的依赖，研究“维度的诅咒与祝福”。它还将解决我们在理解许多高维推理问题时样本和算法复杂性之间的神秘差异。这项工作的结果将通过在期刊、会议和包括教程在内的各种场所的演示文稿向广泛的科学界传播。这个项目的目标包括实现实用的算法和使软件在网上可用。研究成果也将纳入国际和联合国际教授的研究生班的课程。该项目资助的研究生将接受理论、算法开发和应用方面的广泛培训。

Data analysis is ubiquitous in a broad range of application fields, from computer graphics to geographic information systems, from sensor networks to social networks, from economics to medicine. It represents a fundamental problem in computational science. The project will advance the theoretical understanding of fundamental issues behind data analysis, and develop practical algorithms that will be useful for a broad range of problems in science and engineering.The project addresses the fundamental problem of reconstructing structure of probability distributions from sampled data. It will investigate the use of tensor-based and other higher order methods, in particular those that allow for efficient optimization. The project lies at the interface of theoretical computer science, machine learning, signal processing and statistics and will have potential impact in all of these fields. In recent years there has been a resurgence of interest in tensor methods in data analysis and inference, particularly in theoretical computer science. These methods will prove useful in a variety of applications in machine learning, signal processing and other fields.The project will develop algorithms for solving a range of problems including blind source separation, spectral clustering, inference in mixture models and estimating geometry of distributions. It will analyze the complexity of these and related problems. In particular, it will strive to understand the computational efficiency  and dependence on the dimension of the space, studying "the curses and blessings of dimensionality". It will also address a somewhat mysterious discrepancy between sample and algorithmic complexity in our understanding of many high dimensional inference problems.The results of this work will be disseminated to the broad scientific community through publications in journals, conferences and presentations in various venues, including tutorials. The goals of this project include to implement the practical algorithms and to make the software available online. The research results will also be incorporated in the curriculum of graduate classes taught by the PI and the co-PI. Graduate students supported by this project will receive extensive training in theory, algorithm development and applications.