A Randomized Algorithm for a Tensor-Based Generalization of the Singular Value Decomposition

Abstract

An algorithm is presented and analyzed that, when given as input a d-mode tensor A, 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 \epsilon, and a failure probability \sigma) 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 \le \sum_{i=1}^d ||A_{[i]}-(A_{[i]})_k_i||_F + d\epsilon ||A||_F$

are obtained, where A_[i] is the matrix formed by "unfolding" the tensor along the i-th mode and where (A_{[i]})_k_i is the best rank k_i approximation to the matrix A_[i]. Each ||A_{[i]}-(A_{[i]})_k_i||_F term is a measure of the extend to which the matrix A_[i] is not well-approximated by a rank-k_i matrix, and the \epsilon ||A||_F term is a measure of the loss in approximation quailty due to the choice of columns (rather than, e.g., the top k_i 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 decomoposition that is expressed in terms of the columns and rows of the orignal matrix, rather than in terms of its singular vectors. Connections with several similar recently-developed matrix decompositions are discussed.

Back to publications
Back to previous page