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

数据通常被建模为矩阵;因此，线性代数算法（如矩阵分解）在许多数据集的分析中被证明是非常成功的。 Randomized Numerical Linear Algebra（RandNLA）整合了理论计算机科学和数值线性代数为矩阵计算带来的互补观点，它是设计和分析此类算法以及使用由此产生的洞察力来解决重要科学和社会问题的新范式。 当前RandNLA算法从数据矩阵中提取线性结构。 拟议的工作将RandNLA方法扩展到数据矩阵中的多线性和其他非线性结构。更详细地说，拟议的工作将调查两个重要的非线性结构设置，以便在基础数据呈现非线性结构的情况下开始使用RandNLA方法取得进展：它将研究如何设计下一代RandNLA算法，可以处理由张量捕获的呈现多线性结构的数据;它将研究RandNLA方法对表现出非线性结构的数据的适用性，这些数据由非线性降维技术、局部谱方法和相关的半监督特征向量工具捕获。此外，它将评价关于专业人员具有重要专门知识的数据应用的拟议方法，例如人口遗传学数据和天文数据的统计分析。 该项目的更广泛影响包括研究生和本科生培训，研讨会和代码开发RandNLA。 欲了解更多信息，请访问项目网站：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/