## Abstract

We consider Tucker-like approximations with an τ × τ × τ core tensor for three-dimensional n × n × n arrays in the case of r « n and possibly very large n (up to 10^{4}-10^{6}). As the approximation contains only O(rn + r^{3}) parameters, it is natural to ask if it can be computed using only a small amount of entries of the given array. A similar question for matrices (two-dimensional tensors) was asked and positively answered in [S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudo-skeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1-21]. In the present paper we extend the positive answer to the case of three-dimensional tensors. More specifically, it is shown that if the tensor admits a good Tucker approximation for some (small) rank r, then this approximation can be computed using only O(nr) entries with O(nr^{3}) complexity.

Original language | English |
---|---|

Pages (from-to) | 939-956 |

Number of pages | 18 |

Journal | SIAM Journal on Matrix Analysis and Applications |

Volume | 30 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2008 |

Externally published | Yes |

## Keywords

- Data compression
- Data-sparse methods
- Dimensionality reduction
- Large-scale matrices
- Low-rank approximations
- Multidimensional arrays
- Skeleton decompositions
- Tensor approximations
- Tucker decomposition