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

Purdue University, West Lafayette IN

Investigators

Abstract

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/