CAREER: Approximate Algorithms for High-dimensional Geometric Problems

这一职业发展计划涉及集中于高维几何问题算法的综合研究和教育活动。高维数据的几何计算对计算机科学的许多领域至关重要，包括机器学习、数据挖掘、数据库和信息检索、计算机视觉和计算生物学。这个领域的例子问题是：最近邻搜索，数据聚类的许多变体，以及发现数据的线性结构（例如通过主成分分析（PCA））。不幸的是，许多此类问题的经典几何算法不能很好地随维数缩放。例如，最近邻搜索的经典算法的运行时间以指数方式依赖于维度，这使得它们对于维度大于20的算法效率低下。这是不幸的，因为许多应用程序涉及的维数从几百到几百万不等。近年来，人们发现了解决这些问题的新的、强大的技术，最著名的是几何空间中的降维和随机抽样。使用这些技术获得的算法对维度的依赖性非常低（最多是线性的），代价是提供近似的答案。适用于这些技术的问题包括最近邻搜索、聚类和PCA。然而，这些问题的算法解决方案仍然具有（有时相当严重的）局限性。我们的目标是确定绕过这些限制的方法，使算法在理论和实践中都有效。导致上述算法发展的技术是新的，仍然不广为人知。它们包括许多工具，这些工具是在70年代和80年代在数学领域开发的，称为泛函分析。然而，计算机科学家直到最近才意识到这些方法，许多基本结果仍然没有被广泛了解或使用。因此，重要的是让大量的计算机科学读者能够访问这些结果，以便能够成功地使用、研究和开发它们。在教育计划部分，我们概述了如何使学生和计算机科学家更容易使用它们的计划。

This Career Development Plan involves an integrated collection of research and educational activities focused on algorithms for high-dimensional geometric problems.Geometric computing with high-dimensional data is of crucial importance to many areas of computer science, including machine learning, data mining, databases and information retrieval, computer vision and computational biology.Example problems in this area are: nearest neighbor search, many variants of data clustering, and discovering linear structure of the data (e.g. via Principal Component Analysis (PCA)). Unfortunately, the classical geometric algorithms for many of these problems do not scale well with the dimension. For example, the running times of the classical algorithms for the nearest neighbor search depend exponentially on the dimension, which makes them inefficient for dimension higher than, say, 20. This is unfortunate, since many applications involve number of dimensions anywhere from a few hundred to a few million.In recent years, new, powerful techniques for solving theseproblems have been discovered, most notably dimensionality reduction and random sampling in geometric spaces. The algorithms obtained using those techniques enjoy very low (at most linear) dependence on the dimension, at the cost of providing approximate answers. The problems amenable to these techniques include nearest neighbor search, clustering and PCA.However, the algorithmic solutions to these problems still possess (sometimes quite severe) limitations. Our goal is to identify methods for circumventing these limitations and making the algorithms efficient, both in theory and in practice.The techniques which led to the development of the aforementioned algorithms are new and still not widely known. They include many tools which have been developed during 70s and 80s in the field of mathematics called functional analysis. However, computer scientists became aware of those methods only very recently,and many of the fundamental results are still not widely known or used.Therefore, it is important to make these results accessible to large computer science audience so that they can be successfully used, investigated and developed. In the Education Plan section we outline a plan on how to make them more accessible to students as well as computer scientists.