Reconstructing Matrices and Tensors from Few Vectors

CESAR F. CAIAFA; ANDRZEJ CICHOCKI

Sapporo, JAPON

Simposio; International Symposium on Nonlinear Theory and its Applications NOLTA 2009; 2009

Muroran Institute of Technology

We introduce a new algorithm, namely the Greedy-CUR algorithm for calculating a CUR decomposition of a given matrix. This deterministic algorithm allows one to obtain a low-rank approximation based only on the entries of a reduced set of rows and columns. The concept of a ”greedy” algorithm is used to sample rows and columns of thematrix (or unfolded (matricized) tensor) by sequentially adding one row/column that minimizes the achieved error at every iteration. We also use Greedy-CUR to develop a method for approximating a 3D-tensor based only on the entries of few rows, columns and tubes fibers. Its extension to N−dimensional tensors is straightforward by using a hierarchical decomposition of a unfolded tensor and by applying CUR approximation sequentially. We analyze the quality of our CUR based approximations and show how the approximation error depends on the singular values distribution of corresponding matrices.