Non-iterative low-multilinear-rank tensor approximation with application to decomposition in rank-(1,L,L) terms

Submitted to SIAM Journal on Scientific ComputingComputing low-rank approximations is one of the most important and well-studied problems involving tensors. In particular, approximations of low multilinear rank (mrank) have long been investigated by virtue of their usefulness for subspace analysis and dimensionality reduction purposes. The first part of this paper introduces a novel algorithm which computes a low-mrank tensor approximation non-iteratively. This algorithm, called sequential low-rank approximation and projection (SeLRAP), generalizes a recently proposed scheme aimed at the rank-one case, SeROAP. We show that SeLRAP is always at least as accurate as existing alternatives in the rank-(1,L,L) approximation of third-order tensors. By means of computer simulations with random tensors, such a superiority was actually observed for a range of different tensor dimensions and mranks. In the second part, we propose an iterative deflationary approach for computing a decomposition of a tensor in low-mrank blocks, termed DBTD. It first extracts an initial estimate of the blocks by employing SeLRAP, and then iteratively refines them by recomputing low-mrank approximations of each block plus the residue. Our numerical results show that, in the rank-(1,L,L) case, this remarkably simple scheme outperforms existing algorithms if the blocks are not too correlated. In particular, it is much less sensitive to discrepancies among the block's norms