AF: Small: Sublinear Algorithms for Visual Properties

次线性算法领域旨在为处理大数据建立算法基础。次线性算法在只检查其输入的一小部分之后，就会产生快速、近似的答案。这个项目特别关注视觉和几何数据的次线性算法，目的是为在次线性背景下研究这类数据奠定基础。这需要开发新的工具，并将开辟新的联系以及新的应用领域。有效利用大数据可以带来显著的社会效益。该项目所进行的研究为利用大数据提供了必要的理论基础。它有可能改变视觉数据的处理和分析方式。这项研究的结果将被整合到研究人员的次线性算法的研究生课程中。这个项目的主要目标是系统地研究次线性背景下的可视数据。虽然在次线性算法和关于函数、代码(更一般地，代数属性)、图形和离散分布的属性测试方面已经建立了成功的研究路线，但次线性算法的一些潜在应用需要处理视觉和几何数据。具体地说，可以测试基本视觉属性(如对称性、凸性和低亏格)的次线性算法具有显著加快图像处理应用的潜力。这些性质中的一些根本没有在次线性算法的背景下进行研究。这个项目研究视觉特性测试中的基本问题，考虑更高维度的问题，并研究新的计算任务，重点是稳健性。为了充分发挥其潜力，次线性算法需要能够处理几何和视觉数据。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The area of sublinear algorithms aims to establish algorithmic foundations for processing big data. Sublinear algorithms produce quick, approximate answers after examining only a tiny fraction of their input. This project focuses specifically on sublinear algorithms for visual and geometric data, with the goal of laying foundations for studying such data in the sublinear context. This requires the development of new tools and will open up new connections as well as new areas of applications. Effectively exploiting big data can provide significant societal benefits. The research pursued by this project contributes the theoretical foundations necessary to take advantage of big data. It has the potential to change how visual data is processed and analyzed. The results of this research will be integrated into the investigator's graduate course on sublinear algorithms.The primary goal of this project is a systematic investigation of visual data in the sublinear context. Whereas there are established and successful lines of research in sublinear algorithms and property testing on functions, codes (and, more generally, algebraic properties), graphs, and discrete distributions, several potential applications of sublinear algorithms require working with visual and geometric data. Specifically, sublinear algorithms that can test basic visual properties, such as symmetry, convexity, and low genus have the potential to dramatically speed up image processing applications. Some of these properties have not been studied at all in the context of sublinear algorithms. This project investigates fundamental problems in testing visual properties, considers problems in higher dimensions, and studies new computational tasks with a focus on robustness. To achieve their full potential, sublinear algorithms need to be able to handle geometric and visual data.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.