Collaborative Research: RUI: Multilinear Algebra Computations with Higher-Order Tensors

合作研究：RUI：高阶张量的多线性代数计算

• 批准号: 0914957
• 负责人: Misha Kilmer
• 金额: $ 22.12万
• 依托单位: Tufts University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914957&HistoricalAwards=false
• 关键词: Collaborative; Research; RUI; Multilinear; Algebra

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).Many real world applications need to compress, sort, and otherwise manipulate large volumes of multidimensional data arrays (i.e., higher-order tensors), so there is an increasing need for theoretical and computational tools to deal with multiway data. The subject of multilinear algebra and tensors has gained increasing prominence in the past decade due to a surge in applications such as approximation of Newton potentials and stochastic PDEs, image compression and deblurring, network traffic analysis, biological assay interpretation, unmixing of signals, and many more. Such applications with higher-ordertensors involve factorizations of the tensor. There are multiple possible extensions of matrix factorizations to higher-order tensors (e.g. extensions of the matrix SVD), with some more amenable to certainapplications. The investigators are advancing the state-of-the-art in both theoretical and computational multilinear algebra via several newlydeveloped tensor constructions based on new notions of tensor multiplication, orthogonality and diagonalizability. Algorithms with compression schemes based on these new constructions are being implemented by the investigators and tested on several datasets from various applications including handwritten digit identification, genomics, the spectral unmixing problem, video compression, and computerimage recognition.Current applications in the sciences can involve analysis, classification, searching and compression of large volumes of data that is "multidimensional" in nature. Consider, for example, the problem of facial recognition, used to identify a terrorist from within a database of images of known terrorists. The database can be considered multidimensional data in the sense that for each individual there corresponds a specific viewpoint, illumination, and facial expression. It is critical in this scenario to have an accurate and fast algorithm to match an unknown image against a database of images of known terrorists. Another example where a multidimensional representation is useful is genomic data. Here, DNA microarray two-dimensional tabular data from different experiments is concatenated into a multidimensional array. Recently published results have indicated that so-called 'factorizations' of this multidimensional data can be used to discover new molecular-level interactions. Hence, along with advances in computer architecture to store large datasets must come mathematically sound models for the compression and/or analysis of such data. Development of new concepts and ideas is therefore required to deal withthe different geometries that arise in the multidimensional case. The investigators are contributing directly to this effort by developing innovative mathematical theory for multidimensional objects that is consistent with two-dimensional proven ideas. With theoretical constructs in place, the investigators are able to create computationaltools and algorithms to analyze and compress multidimensional data. A significant component of the proposal is the involvement of undergraduates, graduate students, and researchers. The investigators are leveraging the strengths of both universities in a novel, inter-institutional vertical integrative experience for all students (undergraduate and graduate) involved in the research. This arrangementallows students at all levels, mentored by leading researchers in the field, to advance the state-of-the-art in the analysis and compressionof multidimensional data.

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。许多现实世界的应用程序需要压缩、排序和以其他方式操作大量多维数据数组（即高阶张量），因此越来越需要理论和计算工具来处理多路数据。在过去的十年中，由于牛顿势和随机偏微分方程的近似、图像压缩和去模糊、网络流量分析、生物分析解释、信号解混等应用的激增，多线性代数和张量的主题得到了越来越多的重视。这种高阶张量的应用涉及张量的因式分解。有多种可能的矩阵分解扩展到高阶张量（例如矩阵SVD的扩展），其中一些更适合于某些应用。研究人员通过基于张量乘法、正交性和对角化等新概念的几种新发展的张量构造，在理论和计算上都取得了最新的进展。研究人员正在实施基于这些新结构的压缩方案算法，并在不同应用的几个数据集上进行测试，包括手写数字识别、基因组学、光谱解混问题、视频压缩和计算机图像识别。目前在科学领域的应用可能涉及分析、分类、搜索和压缩本质上是“多维”的大量数据。例如，考虑面部识别问题，用于从已知恐怖分子图像的数据库中识别恐怖分子。数据库可以被认为是多维数据，因为每个个体都对应一个特定的视点、光照和面部表情。在这种情况下，有一个准确而快速的算法将未知图像与已知恐怖分子图像数据库进行匹配是至关重要的。另一个使用多维表示的例子是基因组数据。在这里，DNA微阵列二维表格数据从不同的实验被连接到一个多维数组。最近发表的结果表明，这种多维数据的所谓“因子分解”可以用来发现新的分子水平的相互作用。因此，随着存储大型数据集的计算机体系结构的进步，必须有数学上合理的模型来压缩和/或分析这些数据。因此，需要开发新的概念和想法来处理多维情况下出现的不同几何形状。研究人员通过发展创新的多维对象数学理论，与二维已证实的想法相一致，直接为这一努力做出了贡献。有了理论结构，研究人员就能够创建计算工具和算法来分析和压缩多维数据。该提案的一个重要组成部分是本科生、研究生和研究人员的参与。研究人员正在利用两所大学的优势，为参与研究的所有学生（本科生和研究生）提供一种新颖的、跨机构的垂直整合体验。这种安排允许各级学生在该领域领先的研究人员的指导下，在多维数据的分析和压缩方面推进最先进的技术。