Generalizing the CUR Matrix Decomposition to Large-Scale Multi-way Arrays

CESAR F. CAIAFA; ANDRZEJ CICHOCKI

Copenhagen, DENMARK

Workshop; EMMDS 2009. European Workshop on Challenges in Modern Massive Data Sets; 2009

Technical University of Denmark

It is known that, given a matrix Y with rank(Y)=R, one can perfectly reconstruct it by choosing only P=R rows and columns determining a non singular intersection submatrix W and by calculating the corresponding CUR decomposition, i.e. [1]: Y=CUR, with U=W^-1; where matrices C and R are the selected rows and columns respectively. In [2,3], we extended the idea of CUR decomposition to multiway arrays. We provide a Tucker representation of an N-way tensor Y in terms of a reduced subset of n-mode fibers with a core tensor obtained from the entries of the intersection subtensor. In this way, this Fiber Based Tensor Decomposition (FBTD), is completely determined by selecting subsets of P indices in each dimension and it is proven to be exact if the original tensor has an exact Tucker decomposition of order R=P. We also provide an algorithm for the selection of proper fibers which does not require to access to all the entries of the data tensor which is useful for large scale applications. Numerical results show that our FBTD model can also provide good approximations by using less indices than the order of the original Tucker tensor (P