A randomized algorithm for a tensor-based generalization of the singular value decomposition

An algorithm is presented and analyzed that, when given as input a d  -mode tensor AA, computes an approximation A∼. The approximation A∼ is computed by performing the following for each of the d modes: first, form (implicitly) a matrix by “unfolding” the tensor along that mode; then, choose columns from the matrices thus generated; and finally, project the tensor along that mode onto the span of those columns. An important issue affecting the quality of the approximation is the choice of the columns from the matrices formed by “unfolding” the tensor along each of its modes. In order to address this issue, two algorithms of independent interest are presented that, given an input matrix A and a target rank k, select columns that span a space close to the best rank k subspace of the matrix. For example, in one of the algorithms, a number c (that depends on k, an error parameter ϵ, and a failure probability δ) of columns are chosen in c independent random trials according to a nonuniform probability distribution depending on the Euclidean lengths of the columns. When this algorithm for choosing columns is used in the tensor approximation, then under appropriate assumptions bounds of the form‖A-A∼‖F⩽∑i=1d‖A[i]-(A[i])ki‖F+dϵ‖A‖Fare obtained, where A[i] is the matrix formed by “unfolding” the tensor along the i  th mode and where (A[i])ki(A[i])ki is the best rank ki approximation to the matrix A[i]. Each ‖A[i]-(A[i])ki‖F‖A[i]-(A[i])ki‖F term is a measure of the extent to which the matrix A[i] is not well-approximated by a rank-ki matrix, and the ϵ‖A‖Fϵ‖A‖F term is a measure of the loss in approximation quality due to the choice of columns (rather than, e.g., the top ki singular vectors along each mode). Bounds of a similar form are obtained with the other column selection algorithm. When restricted to matrices, the main tensor decomposition provides a low-rank matrix decomposition that is expressed in terms of the columns and rows of the original matrix, rather than in terms of its singular vectors. Connections with several similar recently-developed matrix decompositions are discussed.