The PI will extend extensive studies in numerical linear algebra to the numerical multilinear algebra setting, which complements and enriches the underlying linear framework. The PI's prior work has laid foundations for this new subject via (1) mapping the boundary between the possible and impossible, the computable and non-computable; and (2) extending several matrix notions to tensors (e.g. eigenvalues, singular values, Schatten, Ky Fan norms, Perron-Frobeniuis theorem). This project takes the next step -- developing the requisite algorithms for problems that sit within these boundaries. While almost all 'algorithms' currently in use for tensor problems lack correctness and convergence guarantees, the ones developed for this project strive to be algorithms in the true sense of the word, i.e. meeting the basic requirement of convergence to a true solution and not just a stationary or fixed point. This is in general not possible but the PI will (i) identify large classes of interesting cases for which efficient, provably convergent algorithms exist; and (ii) exploit multilinearity and tap the existing rich collection of linear techniques. These design principles and goals will be applied to algorithmic development of all following problems: (a) Low rank tensor approximations; (b) eigenvalues and singular values for tensors; (c) systems of multilinear equations in the exact and least-squares sense. The PI will also demonstrate the utility of numerical multilinear algebra by proposing several new tools in telecommunications, bioinformatics, and neuroimaging.
Almost all engineering, scientific, and statistical computing problems may ultimately be reduced to a handful of standard problems in linear algebra. Therefore one may argue that computational linear algebra is the workhorse of computations in science and engineering. This project is about expanding this fundamental arsenal of tools by going from "linear" to "multilinear". To achieve this, one must first realize that while there are natural extensions of the aforementioned handful of linear problems, there are also subtle difficulties and even impossibilities associated with these multilinear analogues. The crux of the project is to carve out a substantial tractable subclass of problems that are nevertheless still useful in applications. The project would also examine three concrete applications to brain imaging, cellular phone communication, and analytical chemistry.
