Summary
International Symposium on Nonlinear Theory and its Applications
2009
Session Number:B3L-C
Session:
Number:B3L-C2
Reconstructing matrices and tensors from few vectors
Cesar F. Caiafa, Andrzej Cichocki,
pp.-
Publication Date:2009/10/18
Online ISSN:2188-5079
Summary:
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 the matrix (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.