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

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

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.