Randomized Tucker-Sketched GMRES

DOI10.48550/arXiv.2608.11091MaRDI QIDQ7284761zbMATH OpenarXivFDO

Authors Alberto Bucci, Mirjeta Pasha, Rudi Smith, Martina Iannacito

Publication date 11 August 2026

Published in arXiv

Tldr We propose two randomized algorithms for solving large-scale tensor-structured linear systems in the Tucker format using sketched GMRES to overcome the bottleneck of multilinear ranks growing with iteration count. Our methods leverage randomized HOSVD (RHOSVD-Tucker sGMRES) or multilinear Nyström approximation (MLN-Tucker sGMRES), and achieve state-of-the-art performance, including robustness across a wide range of problems and memory efficiency for streaming computations.

Full work available at URL https://doi.org/10.48550/arXiv.2608.11091

arXiv classification

math.NA

Cites work

• A computational framework for edge-preserving regularization in dynamic inverse problems
• A computational framework for infinite-dimensional Bayesian inverse problems. I: The linearized case, with application to global seismic inversion
• A Flexible Inner-Outer Preconditioned GMRES Algorithm
• A literature survey of low-rank tensor approximation techniques
• A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
• A Multilinear Singular Value Decomposition
• A new truncation strategy for the higher-order singular value decomposition
• A Practical Mode-parallel Implementation of the (H-)Tucker Decomposition via Randomization
• A projection method to solve linear systems in tensor format
• A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format
• Adaptive Randomized Tensor Train Rounding using Khatri-Rao Products
• An efficient randomized algorithm for computing the approximate Tucker decomposition
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
• Computed tomography. Algorithms, insight, and just enough theory. With contributions by Martin S. Andersen, K. Joost Batenburg, Yiqiu Dond, Eric Todd Quinto and Jan Sijbers
• Constructing structured tensor priors for Bayesian inverse problems
• Efficient Dynamic Image Reconstruction with motion estimation
• Efficient Sketching-Based Summation of Tucker Tensors
• Estimation of the \(L\)-curve via Lanczos bidiagonalization
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• GMRES with Deflated Restarting
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Hierarchical Singular Value Decomposition of Tensors
• Iterative Methods for Sparse Linear Systems
• Krylov subspace methods for linear systems with tensor product structure
• Krylov subspace recycling with randomized sketching for matrix functions
• Low-rank tensor methods for partial differential equations
• Low-Rank Tucker Approximation of a Tensor From Streaming Data
• Modified Gram-Schmidt (MGS), Least Squares, and Backward Stability of MGS-GMRES
• On Krylov projection methods and Tikhonov regularization
• Parallel Randomized Tucker Decomposition Algorithms
• Practical sketching algorithms for low-rank Tucker approximation of large tensors
• Preconditioning Low Rank Generalized Minimal Residual Method (GMRES) for Implicit Discretizations of Matrix Differential Equations
• Randomized Algorithms for Computation of Tucker decomposition and Higher Order SVD (HOSVD)
• Randomized Algorithms for Low-Rank Matrix and Tensor Decompositions
• Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
• Randomized algorithms for rounding in the Tensor-Train format
• Randomized algorithms for streaming low-rank approximation in tree tensor network format
• Randomized algorithms for the approximations of Tucker and the tensor train decompositions
• Randomized Flexible LSQR and LSMR with applications to inverse problems
• Randomized Gram-Schmidt process with application to GMRES
• Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Randomized sketched TT-GMRES for linear systems with tensor structure
• Recycling MMGKS for large-scale dynamic and streaming data
• RTSMS: Randomized Tucker with single-mode sketching
• Sketching as a tool for numerical linear algebra
• Some mathematical notes on three-mode factor analysis
• Streaming Tensor Train Approximation
• Subspace gradient descent method for linear tensor equations
• Tensor Decompositions and Applications
• Tensor numerical methods for multidimensional PDEs: theoretical analysis and initial applications
• Tensor numerical methods in quantum chemistry
• Tensor Regression Using Low-rank and Sparse Tucker Decompositions
• Tensor-Based Formulation and Nuclear Norm Regularization for Multienergy Computed Tomography
• Tensor-Based Reduced-Order Modeling for Optimization-Based Inverse Problems
• Tensor-on-Tensor Regression
• Tensor-train decomposition
• Theory of Inexact Krylov Subspace Methods and Applications to Scientific Computing
• TRIPs-Py: Techniques for Regularization of Inverse Problems in Python

This page was built for publication: Randomized Tucker-Sketched GMRES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284761)