BIGDATA: F: Algorithms for Tensor-Based Modeling of Large Scale Structured Data

该项目旨在利用其丰富的结构，为大数据应用开发高效的算法。大数据通常包含高维数组。一维数组是向量，二维数组是矩阵。三维或三维以上的数组称为张量，具有复杂的结构。研究团队将解决的一些挑战是噪声去除，通过推理恢复丢失的数据，以及通过提取相关信息减少数据大小。由此产生的方法将应用于败血症的早期检测，败血症导致美国每年有20万人死亡。大多数低秩结构张量的算法都是基于正则多进分解（也称为CP， Parafac或Candecomp）。这些算法可能收敛缓慢，数值不稳定，难以扩展到大数据。所使用的张量分解的理论框架是基于利用彩色布劳尔图获得显式公式的代数图形演算。图形演算也将用于对这些算法的计算和内存复杂度给出准确的估计。研究人员将为关键张量操作设计高效、数值稳定和计算可行的算法，这些算法广泛适用于大数据应用。具体来说，该项目预计将为张量分析创建快速、可扩展和可靠的算法，并将其应用于关键的大数据任务，包括噪声去除、降维、缺失数据的输入和各种结构化数据应用中的分类。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The project aims to develop efficient algorithms for big data applications by exploiting its rich structure. Big data often contains higher-dimensional arrays. One dimensional arrays are vectors and two dimensional arrays are matrices. Arrays of dimension three or more are called tensors and have a complex structure. Some of the challenges that the research team will address are noise removal, recovery of missing data by inference and data size reduction by distilling relevant information. The resulting methods will be applied to early detection of sepsis, which contributes to the death of 200,000 people in the United States every year.Most algorithms for low rank structured tensors are based on the Canonical Polyadic decomposition (also known as CP, Parafac or Candecomp). These algorithms may converge slowly, are numerically unstable and are difficult to scale to big data. The theoretical framework for tensor decompositions that is used is based on an algebraic graphical calculus that utilizes colored Brauer diagrams to obtain explicit formulas. The graphical calculus will also be used to give accurate estimates for the computational and memory complexity of these algorithms. The investigators will design efficient, numerically stable and computationally feasible algorithms for crucial tensor operations that are widely applicable to big data applications. Specifically, the project isexpected to create fast, scalable and reliable algorithms for tensor analysis, and apply them to crucial big data tasks including noise removal, dimension reduction, imputation of missing data and classification in a variety of applications with structured 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.