Full text  Click to download. 
Citation  Technical Report, YALEU/DCS/TR1327, June 2005

Authors  Petros Drineas
Michael W. Mahoney 
An algorithm is presented and analyzed that, when given as input a dmode
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 ith 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 wellapproximated by a rankk_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 lowrank 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 recentlydeveloped matrix
decompositions are discussed.