betaFeedback

WorksMathematics

Fast HOSVD via Randomized Preconditioning and Mixed Precision

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(uℓ)O(\sqrt{u_\ell}) correction to the tail-energy term and an additive O(uℓ)O(u_\ell) term under suitable conditions, where uℓ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.

Paper details

vlnc:W_y2j5ebme
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…