Paperlane

no. 16 · Tuesday 17 November 2026

Fast HOSVD via Randomized Preconditioning and Mixed Precision

Yiying Chen and Yuning Yang

math.NA

Abstract

Computing dominant mode subspaces is a major cost in the higher-order singular value decomposition (HOSVD) and its sequentially truncated variant (STHOSVD). Randomized Tucker algorithms can reduce this cost by approximating the required subspaces from small sketches, but may introduce additional approximation errors. We exploit the extreme aspect ratios of tensor unfoldings, whose mode dimensions can remain manageable while being orders of magnitude smaller than the products of the remaining dimensions. Instead of directly approximating the desired subspaces, we sketch the entire unfolding at a scale comparable to its mode dimension to preserve its full row-space geometry, and use randomized preconditioning to recover the desired singular subspaces through small matrix factorizations. We develop randomized preconditioned HOSVD and STHOSVD algorithms incorporating numerical truncation, and further accelerate their large matrix multiplications using mixed precision. Our analysis shows that truncation adds only a term quadratic in the numerical threshold to the classical HOSVD tail-energy bound, while mixed precision introduces a relative \(O(\sqrt{u_\ell})\) correction to the tail-energy term and an additive \(O(u_\ell)\) term under suitable conditions, where \(u_\ell\) is the lower-precision unit roundoff. On synthetic and real tensors, our methods achieve speedups of a fewfold to several dozenfold over classical HOSVD and STHOSVD, with runtimes competitive with those of other randomized methods. The double-precision versions match the classical reconstruction errors to numerical precision, and the mixed-precision variants yield nearly identical errors.

fields
Numerical Analysis
pdf ↗ page arXiv:2611.21049 ↗