Low-Rank Tucker Approximation of a Tensor from Streaming Data
| Autor: | Yang Guo, Joel A. Tropp, Madeleine Udell, Charlene Luo, Yiming Sun |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Rank (linear algebra) Dimensionality reduction Numerical Analysis (math.NA) Sketch Machine Learning (cs.LG) Randomized algorithm Linear map Algebra Tensor (intrinsic definition) FOS: Mathematics Mathematics - Numerical Analysis Streaming algorithm ComputingMethodologies_COMPUTERGRAPHICS Mathematics Tucker decomposition |
| Zdroj: | SIAM Journal on Mathematics of Data Science. 2:1123-1150 |
| ISSN: | 2577-0187 |
| Popis: | This paper describes a new algorithm for computing a low-Tucker-rank approximation of a tensor. The method applies a randomized linear map to the tensor to obtain a sketch that captures the important directions within each mode, as well as the interactions among the modes. The sketch can be extracted from streaming or distributed data or with a single pass over the tensor, and it uses storage proportional to the degrees of freedom in the output Tucker approximation. The algorithm does not require a second pass over the tensor, although it can exploit another view to compute a superior approximation. The paper provides a rigorous theoretical guarantee on the approximation error. Extensive numerical experiments show that that the algorithm produces useful results that improve on the state of the art for streaming Tucker decomposition. Comment: Appendix includes supplement from published version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|