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

许多数据处理任务，例如图像、视频和音乐压缩和分类，都涉及寻找数据文件的紧凑表示形式。出于许多实际原因，简洁地表示这类文件通常是个好主意。压缩的音乐和图像文件(MP3、JPG等)与原版相比，沟通和存储要快得多，成本也更低。在分类应用程序中，通常从较大类别的数据中选择少量信息丰富的文件特征，以帮助提高准确性和效率(这类似于只关注歌曲中的声音，目的是识别歌手)。在更极端的情况下，数据信号可能太大或变化太快，以至于除非首先快速压缩，否则根本无法存储或分析它们。在与用于互联网数据分析的算法相关的研究领域中存在许多这类有趣的问题，例如，旨在快速检测特定类型的大规模网络攻击。作为该项目的一部分，调查人员将为复杂数据开发和实施新的更快的压缩和数据分析技术，然后这些技术可用于在无数大规模数据处理应用程序中促进更快的数据处理。该项目还将产生教育效益，旨在增加STEM研究领域中代表性不足和服务不足群体的学生人数。这将通过研究人员为来自不同背景的本科生主持和指导研究项目来完成，他们将作为本研究的一部分开发的压缩和数据分析技术应用于特定的应用数据，例如，分析和更好地理解莱姆病数据。这项研究包括一类丰富的实用的Johnson-Lindenstrauss(JL)矢量数据地图，这些地图不仅可以以比快速傅里叶变换时间序列更快的速度应用于矢量，而且还可以微不足道地并行化。嵌入将是随机化的，它们的分析将得到基于一般链的新的浓度不等式和结构化张量数据嵌入的混沌上确界方法的发展的支持。这些技术将允许，例如，在大张量数据的分析中，利用值的张量限制等距性质来构造新的快速和存储高效的嵌入。此外，该研究还将开发用于张量数据的线性模式JL-映射的新的非线性双Lipitz扩展，该扩展能够保持给定数据库中的所有低阶张量与所有其他低阶张量之间的距离，即使在数据库之外也是如此。这些新的非线性嵌入技术将为空间受限学习和多项式核分类提供更好的理论保证。最后，这些嵌入还将用于解决量子多体理论和核物理中的数据密集型问题。这一奖项反映了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.