CAREER: Approximate Algorithms for High-dimensional Geometric Problems

本职业发展计划包括一系列的研究和教育活动，重点关注高维几何问题的算法。高维数据的几何计算对计算机科学的许多领域都至关重要，包括机器学习、数据挖掘、数据库和信息检索、计算机视觉和计算生物学。该领域的示例问题包括：最近邻搜索，数据聚类的许多变体，以及发现数据的线性结构（例如，通过主成分分析（PCA））。不幸的是，许多这些问题的经典几何算法不缩放以及与尺寸。例如，用于最近邻搜索的经典算法的运行时间以指数方式依赖于维度，这使得它们对于维度高于20的情况下效率低下。这是不幸的，因为许多应用涉及的维数从几百到几百万不等。近年来，人们发现了解决这些问题的新的、强大的技术，最著名的是几何空间中的降维和随机抽样。使用这些技术获得的算法对维度的依赖性非常低（最多是线性的），代价是提供近似的答案。这些技术适用的问题包括最近邻搜索、聚类和主成分分析，然而，这些问题的算法解决方案仍然具有（有时相当严重）的局限性。我们的目标是确定方法，以规避这些限制，使算法有效，在理论和实践中。导致上述算法的发展的技术是新的，仍然没有广泛的知名度。它们包括许多在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.