Fast HOSVD via Randomized Preconditioning and Mixed Precision

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21049
Primary Topic
Tensor decomposition and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Fast HOSVD via Randomized Preconditioning and Mixed Precision

Anonymous, Yuning Yang
arXiv (Cornell University)
Tensor decomposition and applications
preprint

Fast HOSVD via Randomized Preconditioning and Mixed Precision

Anonymous, Yuning Yang
preprint en

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.

arXiv (Cornell University)
Tensor decomposition and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon