BIGDATA: F: DKA: Collaborative Research: Randomized Numerical Linear Algebra (RandNLA) for multi-linear and non-linear data

数据通常被建模为矩阵；因此，诸如矩阵分解之类的线性代数算法在许多数据集的分析中被证明是极其成功的。随机数值线性代数(RandNLA)融合了理论计算机科学和数值线性代数给矩阵计算带来的互补视角，是设计和分析此类算法以及使用由此产生的洞察力来解决重要的科学和社会问题的新范式。当前的RandNLA算法从数据矩阵中提取线性结构。这项工作将把RandNLA方法扩展到数据矩阵中的多线性和其他非线性结构。更详细地，该工作将调查两个重要的、非线性的结构设置，以便开始在底层数据呈现非线性结构的情况下使用RandNLA方法：它将调查如何设计下一代RandNLA算法，它可以处理由张量捕获的呈现多线性结构的数据；它将调查RandNLA方法对通过非线性降维技术、局部谱方法和相关的半监督特征向量工具捕获的非线性结构数据的适用性。此外，它还将评估私人投资机构具有重要专业知识的数据应用方面的拟议方法，例如人口遗传学数据和天文数据的统计分析。该项目的更广泛影响包括研究生和本科生培训、研讨会和RandNLA的代码开发。有关更多信息，请参阅项目网站at:http://www.stat.berkeley.edu/~mmahoney/projects/nsf-multilinear/

Data are often modeled as matrices; and, as a result, linear algebraic algorithms such as matrix decompositions have proven extremely successful in the analysis of many data sets. Randomized Numerical Linear Algebra (RandNLA) integrates the complementary perspectives that Theoretical Computer Science and Numerical Linear Algebra bring to matrix computations, and it is a new paradigm for the design and analysis of such algorithms and for using the resulting insight to solve important scientific and societal problems. Current RandNLA algorithms extract linear structure from data matrices. The proposed work will extend RandNLA methods to multi-linear and other non-linear structure in data matrices.In more detail, the proposed work will investigate two important, non-linear, structural settings in order to start making progress towards using RandNLA approaches in situations where the underlying data exhibit non-linear structure: it will investigate how to design the next generation of RandNLA algorithms that can handle data that exhibit multi-linear structures captured by tensors; and it will investigate the applicability of RandNLA approaches to data that exhibit non-linear structure, as captured by non-linear dimensionality reduction techniques, local spectral methods, and related semi-supervised eigenvector tools. In addition, it will evaluate the proposed approaches on data applications where the PIs have significant expertise, such as the statistical analysis of population genetics data and astronomical data. Broader impacts of the project include graduate and undergraduate training, workshops and code development for RandNLA. For further information see the project web site at:http://www.stat.berkeley.edu/~mmahoney/projects/nsf-multilinear/