Incremental Hierarchical Tucker Decomposition
Doruk Aksoy [email protected], Alex A. Gorodetsky [email protected] · 2024
Read Incremental Hierarchical Tucker Decomposition by Doruk Aksoy [email protected], Alex A. Gorodetsky [email protected] (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-16544.txt.
Introduction
Doruk Aksoy and Alex Gorodetsky present a 2024 paper on compressing streams of tensors, the multi-way arrays used in physics simulations. The hierarchical Tucker format stores such data compactly, but rebuilding it for each new batch is wasteful. The authors offer two algorithms that reuse prior work instead.
The first builds the format for a batch of similar tensors more cheaply, working from the leaves of the tree to its root. The second updates the stored form as fresh batches arrive, without ever holding all the data at once. Both carry theoretical guarantees. On physical and cyber-physical data, the batch method gave up to 6.2 times compression and 3.7 times less time. The updater also beat a rival method.
Catalog record
| CREATOR | Doruk Aksoy [email protected], Alex A. Gorodetsky [email protected] |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 153 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-16544
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Incremental Hierarchical Tucker Decomposition Doruk Aksoy [email protected], Alex A. Gorodetsky [email protected] Abstract We present two new algorithms for approximating and updating the hierarchical Tucker decomposition of tensor streams. The first algorithm, Batch Hierarchical Tucker - leaf to root ( BHT-l2r ), proposes an alternative and more efficient way of approximating a batch of similar tensors in hierarchical Tucker format. The second algorithm, Hierarchical Tucker - Rapid Incremental Subspace Expansion ( HT-RISE ), updates the batch hierarchical Tucker representation of an accumulated tensor as new batches of tensors become available. The HT-RISE algorithm is suitable for the online setting and never requires full storage or reconstruction of all data while providing a solution to the incremental Tucker decomposition problem. We provide theoretical guarantees for both algorithms and demonstrate their effectiveness on physical and cyber-physical data. The proposed BHT-l2r algorithm and the batch hierarchical Tucker format offers up to 6.2 × 6.2\times compression and 3.7 × 3.7\times reduction in time over the hierarchical Tucker format. The proposed HT-RISE algorithm also offers up to 3.1 × 3.1\times compression and 3.2 × 3.2\times reduction in time over a state of the art incremental tensor train decomposition algorithm. Doruk Aksoy and Alex A. Gorodetsky. DISTRIBUTION A. Approved for public release; distribution unlimited. OPSEC#9305 † † heading: 00 0000 1- 0/00; Revised 0/00 0/00 00-0000 † † shortheadings: Incremental Hierarchical Tucker / Aksoy and Gorodetsky † † firstpage: 1 † † editor: My editor keywords Tensor decompositions, incremental algorithms, streaming data, scientific machine learning, data compression, latent representation, low-rank factorization 1 Introduction Low-rank tensor decomposition formats ( Oseledets, 2011 ; Tucker, 1966 ; Grasedyck, 2010 ; De Lathauwer et al., 2000b ) provide an efficient way of representing multidimensional data arising from a large number of applications that include videos ( Tian et al., 2023 ; Chen et al., 2024 ; Panagakis et al., 2021 ) , MRI scan images ( Zhang et al., 2019 ; Lehmann et al., 2022 ; Mai and Zhang, 2023 ) , deep learning ( Kossaifi et al., 2023 ; Luo et al., 2024 ; Yang et al., 2024 ) , and solutions of scientific simulations ( Marks and Gorodetsky, 2024 ; Pfaff et al., 2020 ) . There does not exist a single, univerally optimal, low-rank tensor format. Instead, some well-known low-rank tensor formats are the CP format ( Harshman et al., 1970 ; Carroll and Chang, 1970 ) , the Tucker format ( Tucker, 1966 ) , the Tensor Train (TT) format ( Oseledets, 2011 ) , and the hierarchical Tucker (HT) format ( Oseledets and Tyrtyshnikov, 2009 ; Grasedyck, 2010 ) . These formats provide different forms of compression that exploit slightly different types of low-rank structure in data. Figure 1 : Flow of the proposed HT-RISE algorithm. The algorithm updates the hierarchical Tucker representation of an accumulated tensor in batch hierarchical Tucker form as new batches of tensors become available. Green represents the input data and red represents the output data. In this paper, we consider the problem decomposing data in batches. This problem is motivated by the fact that data in many applications is not available at once, and/or the size of the data makes it infeasible or impossible to compute an approximation using a one-shot tensor decomposition algorithm due to computational issues (e.g., memory limits). For these scenarios, incremental algorithms can be effective by incrementally compress new data as it becomes available. They are particularly useful in the online setting where the data comes from a streaming process. While the literature has numerous incremental algorithms to compute the CP decomposition ( Zeng and Ng, 2021 ; Smith et al., 2018 ) , the Tucker decomposition ( De et al., 2023 ; Malik and Becker, 2018 ) , and the TT decomposition ( Aksoy et al., 2024a ; Liu et al., 2018 ; Kressner et al., 2023 ) , we are not aware of incremental approaches for the HT format. The main contribution of this paper is providing the first algorithm to incrementally construct a HT decomposition from streaming data. Furthermore, many applications that leverage compressed representations use it as a latent space for performing downstream tasks. In this setting, it is important to have both an encoding and decoding procedure between the full data and the latent space. While the HT format has some advantages over other formats, it does not immediately provide an efficient latent vector that represents an encoding of a batch of data. Straight-forward applications of existing HT decomposition algorithms ( Kressner and Tobler, 2014 ) treat the batch dimension same as an additional dimension identical to existing ones — so that when a batch of d -dimensional tensors \mathcal{Y}\in\mathbb{R}^{n_{1}\times\cdots\times n_{d}\times N} is compressed, the batch dimension is represented as an HT leaf node with orthonormal columns. We improve upon this approach by modifying the HT format to more efficiently represent the batch latent space by the HT root node. Formally, we describe the problem as follows. We consider a d -way tensor to be a multidimensional array \mathcal{Y}\in\mathbb{R}^{n_{1}\times\cdots\times n_{d}} with d dimensions. Parallel to the definition in Aksoy et al. (2024a) , a tensor stream (or alternatively, stream of tensors ), is a sequence of d+1 -way tensors \mathcal{Y}^{1},\mathcal{Y}^{2} ,…, where each element in the sequence \mathcal{Y}^{k}\in\mathbb{R}^{n_{1}\times\cdots\times n_{d}\times N^{k}} is a N^{k} batch of d -dimensional tensors. A finite stream of tensors is called an accumulation and can be viewed as a (d+1) -way tensor \mathcal{X}^{k}\in\mathbb{R}^{n_{1}\times\cdots\times n_{d}\times\mathbf{n}^{k}} by concatenating the tensors in the stream along the last dimension, with \mathbf{n}^{k}=\sum_{i=1}^{k}N^{i} . Taken together, the above setting motivates the following problem as the first one that we solve. Problem 1 . (Approximating a batch of similar tensors in hierarchical Tucker format) Construct a scheme to compute an approximation \hat{\mathcal{Y}} for a batch of d -dimensional tensors \mathcal{Y}\in\mathbb{R}^{n_{1}\times\cdots\times n_{d}\times N} in a (batch-modified) hierarchical Tucker format. Furthermore, the computed representation should approximate the original batch of tensors with error \|\mathcal{Y}-\hat{\mathcal{Y}}\|_{F}\leq\varepsilon_{des}\|\mathcal{Y}\|_{F} . The scheme should also create individual latent representations for all tensors in a batch, and provide a means to decode a latent representation into the full tensor. Next, we seek to perform the same task, but incrementally: Problem 2 . (Updating an existing hierarchical Tucker representation as new batches of tensors become available) Construct a scheme to update the approximation \hat{\mathcal{X}}^{k} of the accumulation tensor \mathcal{X}^{k} after every increment k in hierarchical Tucker format. The constructed scheme should maintain the guaranteed bounds on the error \|\mathcal{X}^{k}-\hat{\mathcal{X}}^{k}\|_{F} for all k . Furthermore, this approximate accumulation should represent all previous tensor increments \mathcal{Y}^{\ell} with error \|\mathcal{Y}^{\ell}-\hat{\mathcal{Y}}^{\ell}\|_{F}\leq\varepsilon_{des}\|\mathcal{Y}^{\ell}\|_{F} for any \ell\leq k , where \hat{\mathcal{Y}}^{\ell} can be extracted from \hat{\mathcal{X}}^{k} . Our contributions are algorithms to solve these two problems: 1. The Batch Hierarchical Tucker - leaf to root , Algorithm 1 , computes an approximate hierarchical Tucker representation of a batch of tensors \mathcal{Y} . 2. The Hierarchical Tucker - Rapid Incremental Subspace Expansion , Algorithm 2 , updates an existing batch HT with new data. Moreover, HT-RISE is suitable for the online setting and never requires full storage or reconstruction of all data while providing a solution to Problem 2 . These algorithms are both rank adaptive and have provable error bounds. A high