Wednesday, January 11, 2012

Implementation for the Generalization of the Column-Row Matrix Decomposition to Multi-way Arrays

Cesar Caiafa sent me the following:

Dear Igor;
My name is Cesar Caiafa, some time ago I found your excellent blog with very useful and important references to works on Compressed Sensing and more recently, about matrix factorization (MF) and low rank approximations which is one of my research interests.
One of the generalizations of MF are tensor factorizations, in particular, one of the possible tensor factorizations is the Tucker model used for multiway data since long time ago.
I would like to drive your attention to our work from 2010 in Linear Algebra and Its applications:
Generalizing the Column-Row Matrix Decomposition to Multi-way Arrays”, Cesar F. Caiafa, A. Cichocki, Linear Algebra and its Applications, Vol. 433, pp. 557–573, 2010 (Elsevier).
In this paper, we developed new formulas and algorithms to compute a compressed format of an N-way tensor based only on the information contained in few selected n-mode fibers, i.e. for a 3D tensor, we are able to approximate it based on the entries on few columns (1-mode), rows (2-mode) and tubes (3-modes). We called this method as Fiber Sampling Tensor Decomposition (FSTD). Our idea was motivated by several previous works by M Mahoney, P. Drineas, I. Oseledets and E. Tyrtyshnikov. The abstract reads as follows:
 "In this paper, we provide two generalizations of the CUR matrix decomposition Y=CUR (also known as pseudo-skeleton approximation method [1]) to the case of N-way arrays (tensors). These generalizations, which we called Fiber Sampling Tensor Decomposition types 1 and 2 (FSTD1 and FSTD2), provide explicit formulas for the parameters of a rank-(R,R,…,R) Tucker representation (the core tensor of size R×R×⋯×R and the matrix factors of sizes In×R, n=1,2,…N) based only on some selected entries of the original tensor. FSTD1 uses PN-1(P⩾R)n-mode fibers of the original tensor while FSTD2 uses exactly R fibers in each mode as matrix factors, as suggested by the existence theorem provided in Oseledets et al. (2008) [2], with a core tensor defined in terms of the entries of a subtensor of size R×R×⋯×R. For N=2 our results are reduced to the already known CUR matrix decomposition where the core matrix is defined as the inverse of the intersection submatrix, i.e. U=W-1. Additionally, we provide an adaptive type algorithm for the selection of proper fibers in the FSTD1 model which is useful for large scale applications. Several numerical results are presented showing the performance of our FSTD1 Adaptive Algorithm compared to two recently proposed approximation methods for 3-way tensors."
The preprint of our paper is available at 
Also Matlab codes for FSTD are available at 
You can share this information if you like.
Best Regards

Thank you Cesar.

No comments: