Collaborative Research: Fast, Low-Memory Embeddings for Tensor Data with Applications

许多数据处理任务，如图像、视频和音乐压缩和分类，都涉及到找到数据文件的紧凑表示。出于许多实际原因，压缩表示此类文件通常是一个好主意。压缩的音乐和图像文件（MP3，JPG等）比原始的通信和存储更快更便宜。在分类应用程序中，通常从较大类别的数据中选择少量信息性文件特征，以帮助提高准确性和效率（这类似于当目的是识别歌手时仅关注歌曲中的声音）。在更极端的情况下，数据信号可能如此之大或变化如此之快，以至于如果不首先快速压缩，它们根本无法存储或分析。这种类型的许多有趣的问题存在于与互联网数据分析算法相关的研究领域，例如，旨在快速检测特定类型的大规模网络攻击。作为该项目的一部分，研究人员将为复杂数据开发和实施新的更快的压缩和数据分析技术，这些技术可用于在无数大规模数据处理应用中促进更快的数据处理。该项目还将具有教育效益，旨在增加STEM研究领域代表性不足和服务不足群体的学生代表性。这将由研究人员为来自不同背景的本科生主持和指导研究项目来完成，他们将把作为本研究一部分开发的压缩和数据分析技术应用于特定的应用数据，例如，分析和更好地理解莱姆病数据。这项研究包括一个丰富的新类实用约翰逊-林登施特劳斯（JL）用于矢量数据的映射，不仅可以应用于比快速傅立叶变换时间串行更快的矢量，而且还可以并行化。嵌入将是随机的，他们的分析将支持新的浓度不等式的发展的基础上通用链和结构化张量数据嵌入的混沌方法的上确界。然后，这些技术将允许，例如，构建新的快速和内存高效的嵌入与张量限制等距属性的值在大张量数据的分析。此外，该研究还将为张量数据的线性模态JL映射开发新的非线性双Lipchitz扩展，这些扩展能够保持给定数据库中所有低秩张量与所有其他低秩张量之间的距离，甚至在数据库之外。这些新的非线性嵌入技术将允许改进的空间约束学习和分类与多项式内核的理论保证。最后，这些嵌入也将应用于解决量子多体理论和核物理中的数据密集型问题。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many data processing tasks, such as image, video, and music compression and classification, involve finding compact representations of data files. Compactly representing such files is generally a good idea for many practical reasons. Compressed music and image files (MP3, JPG, etc.) are much faster and cheaper to communicate and store than the originals. In classification applications, a small number of informative file features are often selected from larger categories of data in order to help boost accuracy and efficiency (this is akin to only focusing on the voice in a song when the aim is to identify the singer). In more extreme situations, data signals may be so large or change so rapidly that they cannot be stored or analyzed at all without first being quickly compressed. Many interesting problems of this type exist in research areas related to algorithms for internet data analysis aimed at, for example, quickly detecting particular types of large-scale cyber-attacks. As part of this project, the investigators will develop and implement new faster compression and data analysis techniques for complex data, which can then be used to facilitate faster data processing in a myriad of large-scale data processing applications. The project will also have educational benefits aimed at increasing the representation of students from under-represented and under-served groups in STEM research fields. This will be accomplished by the investigators hosting and mentoring research projects for undergraduate students from diverse backgrounds who will apply the compression and data analysis techniques developed as part of this research to specific application data, for example, to analyze and better understand Lyme disease data.This research includes a rich new class of practical Johnson-Lindenstrauss (JL) maps for vector data that cannot only be applied to vectors faster than Fast Fourier Transform time serially but are also trivially parallelizable. The embeddings will be randomized, and their analysis will be supported by the development of novel concentration inequalities based on generic chaining and supremum of chaos approaches for structured tensor data embeddings. These techniques will then allow, for example, the construction of new fast and memory efficient embeddings with the Tensor Restricted Isometry Property of value in the analysis of large tensor data. In addition, the research will develop new nonlinear bi-Lipchitz extensions of linear modewise JL-maps for tensor data capable of preserving distances between all low rank tensors in a given database and all other lower rank tensors, even outside of the database. These new nonlinear embeddings techniques will allow improved theoretical guarantees for space-constrained learning and classification with polynomial kernels. Finally, these embeddings will also be applied to address data-intensive problems in quantum many-body theory and nuclear physics.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.