AF: Small: Sublinear Algorithms for Visual Properties

次线性算法领域旨在为处理大数据建立算法基础。次线性算法在只检查输入的一小部分后就能产生快速、近似的答案。该项目特别关注视觉和几何数据的次线性算法，目的是为在次线性背景下研究此类数据奠定基础。这需要开发新的工具，并将开辟新的连接以及新的应用领域。有效利用大数据可以带来巨大的社会效益。该项目所进行的研究为利用大数据提供了必要的理论基础。它有可能改变视觉数据的处理和分析方式。这项研究的结果将被整合到研究员的研究生课程的次线性algorithms.The主要目标的这个项目是一个系统的调查视觉数据的次线性上下文中。尽管在次线性算法和函数、代码（以及更一般的代数性质）、图形和离散分布的性质测试方面有着成熟和成功的研究路线，但次线性算法的一些潜在应用需要使用视觉和几何数据。具体来说，可以测试基本视觉属性（如对称性、凸性和低亏格）的次线性算法有可能大大加快图像处理应用程序的速度。其中一些性质在次线性算法中根本没有被研究过。该项目研究测试视觉特性的基本问题，考虑更高维度的问题，并研究新的计算任务，重点是鲁棒性。为了充分发挥其潜力，次线性算法需要能够处理几何和视觉数据。该奖项反映了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.