The Multilinear Engine—A Table-Driven, Least Squares Program for Solving Multilinear Problems, Including the n-Way Parallel Factor Analysis Model

Abstract

A technique for fitting multilinear and quasi-multilinear mathematical expressions or models to two-, three-, and many-dimensional data arrays is described. Principal component analysis and three-way PARAFAC factor analysis are examples of bilinear and trilinear least squares fit. This work presents a technique for specifying the problem in a structured way so that one program (the Multilinear Engine) may be used for solving widely different multilinear problems. The multilinear equations to be solved are specified as a large table of integer code values. The end user creates this table by using a small preprocessing program. For each different case, an individual structure table is needed. The solution is computed by using the conjugate gradient algorithm. Non-negativity constraints are implemented by using the well-known technique of preconditioning in opposite way for slowing down changes of variables that are about to become negative. The iteration converges to a minimum that may be local or global. Local uniqueness of the solution may be determined by inspecting the singular values of the Jacobian matrix. A global solution may be searched for by starting the iteration from different pseudorandom starting points. Application examples are discussed—for example, n-way PARAFAC, PARAFAC2, Linked mode PARAFAC, blind deconvolution, and nonstandard variants of these.