An Efficient Randomized Hierarchical Tucker Decomposition
Abstract
We introduce randomized algorithms for computing the hierarchical Tucker decomposition of high-order tensors. Unlike traditional algorithms performed in a sequential leaves-to-root direction, our algorithms traverse the dimension tree in a root-to-leaves direction, leveraging randomized sequential projections to accelerate the computation of intermediate subspaces. This strategy can reduce the computation time by an order of magnitude relative to prior randomized algorithms using the leaves-to-root direction, while guaranteeing quasi-optimal approximation. Although the theoretical error bound is slightly larger than for leaves-to-root methods, in all our experiments the practical error adheres to the classic bound. Our results highlight the method's potential for scalable tensor decompositions in high-dimensional data analysis.
Related
- Rank-Dependent Error Bounds and Near-Optimality in Quantum Control via Hierarchical Tucker Surrogates
- Mixed Precision Compression of Tucker Decomposition
- A Benders decomposition approach for hierarchical k-medoids
- Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees
- Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
BibTeX
@misc{leys2026efficient,
title = {{An Efficient Randomized Hierarchical Tucker Decomposition}},
author = {Bram Leys and Karl Meerbergen and Nick Vannieuwenhoven and Mathijs Vivet},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41554},
eprint = {2610.41554},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41554},
}
RIS
TY - UNPB
TI - An Efficient Randomized Hierarchical Tucker Decomposition
AU - Bram Leys
AU - Karl Meerbergen
AU - Nick Vannieuwenhoven
AU - Mathijs Vivet
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41554
UR - https://arxiv.org/abs/2610.41554
AB - We introduce randomized algorithms for computing the hierarchical Tucker decomposition of high-order tensors. Unlike traditional algorithms performed in a sequential leaves-to-root direction, our algorithms traverse the dimension tree in a root-to-leaves direction, leveraging randomized sequential projections to accelerate the computation of intermediate subspaces. This strategy can reduce the computation time by an order of magnitude relative to prior randomized algorithms using the leaves-to-root direction, while guaranteeing quasi-optimal approximation. Although the theoretical error bound is slightly larger than for leaves-to-root methods, in all our experiments the practical error adheres to the classic bound. Our results highlight the method's potential for scalable tensor decompositions in high-dimensional data analysis.
ER -