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 A, computes an approximation (A) over tilde. The approximation (A) over tilde 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 delta) 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 parallel to A-A parallel to(F) <= (d)Sigma(i=1) parallel to A([i])-(A([i]))k(i) parallel to(F) +d epsilon parallel to(F)+parallel to A parallel to(F) are obtained, where A([i]) is the matrix formed by "unfolding" the tensor along the ith mode and where (A([i]))k(i) is the best rank k(i) approximation to the matrix A([i]). Each parallel to A([i]) - (A([i]))k(i) parallel to(F) term is a measure of the extent to which the matrix A([i]) is not well-approximated by a rank-k(i) matrix, and the epsilon parallel to A parallel to(F) term is a measure of the loss in approximation quality 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 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. (c) 2006 Elsevier Inc. All rights reserved.