Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration Journal: Journal of computational and applied mathematics

A. Badahmane · 2026

Read Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration Journal: Journal of computational and applied mathematics by A. Badahmane (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00839.txt.

Introduction

Badahmane extends tensor Krylov subspace methods with a random Einstein product approach for large multi-way image and video systems. Older tensor global GMRES uses Frobenius inner products, which grow costly at large sizes. He adds a sketched Einstein inner product from per-mode random sketches and a randomized Arnoldi process. The new RTG-GMRES method cuts that cost while keeping convergence under subspace embedding rules. Error bounds, perturbation study, and projected Tikhonov smoothing follow, giving an efficient method for ill posed image and video restoration.

Catalog record

CREATORA. Badahmane
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31684
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2603.00839

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration Journal: Journal of computational and applied mathematics A. Badahmane Abstract We develop a randomized extension of tensor Krylov subspace methods based on the Einstein product for solving large-scale multilinear systems arising in image and video restoration. The classical tensor global GMRES method relies on Frobenius inner products and full tensor orthogonalization, which become computationally expensive for high-dimensional problems. We introduce a sketched Einstein inner product constructed via mode-wise random projections and develop a randomized tensor global Arnoldi process. The resulting Randomized Tensor Global GMRES (RTG-GMRES) method significantly reduces orthogonalization cost while preserving convergence properties under tensor subspace embedding assumptions. Residual bounds, perturbation analysis and projected Tikhonov regularization are derived. The proposed method provides an efficient framework for solving ill-posed multidimensional problems arising in color image and video restoration. 1 Introduction We consider multilinear systems of the form \Phi(\mathcal{X})=\mathcal{C}, where \Phi is a linear tensor mapping defined through the Einstein product: \Phi(\mathcal{X})=\mathcal{A}*_{N}\mathcal{X}\quad\text{or}\quad\Phi(\mathcal{X})=\mathcal{A}*_{N}\mathcal{X}*_{M}\mathcal{B}. Such problems arise in color image restoration, video deblurring, hyperspectral imaging, and high-dimensional PDE discretizations. Tensor Krylov subspace methods based on the Einstein product allow us to preserve multidimensional structure without vectorization. Classical tensor global GMRES methods construct orthonormal bases using Frobenius inner products. However, for high-order tensors with dimension n=\prod_{k=1}^{N}I_{k}\prod_{l=1}^{M}J_{l}, the orthogonalization cost becomes prohibitive. To overcome this limitation, we introduce a randomized framework based on a sketched Einstein inner product. The proposed method reduces orthogonalization complexity while maintaining convergence behavior. High-dimensional data, such as color images, hyperspectral images, and video sequences, are ubiquitous in modern scientific and engineering applications. Traditional matrix-based methods often require vectorization, which destroys the intrinsic multidimensional structure of the data and leads to large, memory-intensive problems. To overcome these challenges, tensor-based approaches preserve the multilinear structure, enabling both computational efficiency and more accurate modeling of complex data dependencies. In this paper, we consider linear tensor equations of the form: \min\|\Phi(\mathcal{X})-\mathcal{C}\|_{F}, (1) where \mathcal{X}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}\times J_{1}\times\cdots\times J_{M}} is the unknown tensor, \mathcal{C} is a given observed tensor, and \Phi is a linear tensor operator modeling transformations such as blurring, degradation, or subsampling. In particular, \Phi may take the forms: \Phi(\mathcal{X})=\mathcal{A}*_{N}\mathcal{X},\quad\text{or}\quad\Phi(\mathcal{X})=\mathcal{A}*_{N}\mathcal{X}*_{M}\mathcal{B}, (2) where *_{N},*_{M} denote Einstein products along specified modes. The Einstein product generalizes matrix multiplication to higher-order tensors while preserving multidimensional correlations, making it especially suitable for multichannel image and video processing. Many real-world applications, including image and video restoration, signal processing, and multidimensional PDEs, naturally lead to tensor equations. While classical Krylov subspace methods such as GMRES or Golub–Kahan work well for grayscale or low-dimensional problems, high-dimensional multichannel problems demand tensor-based iterative methods to maintain both efficiency and accuracy. Here, we introduce a novel approach: Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product. The core idea is to combine the Einstein product with randomized sketching to reduce computational cost and memory usage while preserving essential information. Specifically: 1. Tensor Krylov Subspaces allow iterative solution of high-dimensional tensor equations while preserving their natural structure. 2. Randomized sketching projects large tensors into smaller subspaces, enabling faster computation of tensor-tensor products without significantly sacrificing accuracy. 3. Tikhonov regularization is incorporated to stabilize solutions of ill-posed problems, such as restoring blurred and noisy images and videos. The combination of sketched Einstein products with Krylov subspace methods offers a powerful and efficient framework for solving large-scale, high-dimensional tensor equations. This approach reduces computational complexity, maintains the low-bandwidth structure of point spread function (PSF) tensors, and enables practical application to real-world high-resolution imaging problems. The remainder of the paper is organized as follows: 1. Section 2 introduces tensor notations, Einstein products, and algebraic preliminaries. 2. Section 3 presents Tikhonov regularization and extends global GMRES and Golub–Kahan methods to the sketched Einstein product framework. 3. Section 4 develops block tensor formulations of the algorithms and analyzes their theoretical properties. 4. Section 5 demonstrates numerical results on restoring blurred and noisy color images and videos. 5. Section 6 concludes with discussions on future extensions and applications. 2 Preliminaries 2.1 Einstein Product Let \mathcal{A}\in\mathbb{R}^{I_{1}\times\dots\times I_{L}\times K_{1}\times\dots\times K_{N}},\quad\mathcal{B}\in\mathbb{R}^{K_{1}\times\dots\times K_{N}\times J_{1}\times\dots\times J_{M}}. The Einstein product over N modes is defined by (\mathcal{A}*_{N}\mathcal{B})_{i_{1}\dots i_{L}j_{1}\dots j_{M}}=\sum_{k_{1}=1}^{K_{1}}\dots\sum_{k_{N}=1}^{K_{N}}a_{i_{1}\dots i_{L}k_{1}\dots k_{N}}b_{k_{1}\dots k_{N}j_{1}\dots j_{M}}. The resulting tensor belongs to \mathbb{R}^{I_{1}\times\dots\times I_{L}\times J_{1}\times\dots\times J_{M}}. This operation generalizes the matrix product to higher–order tensors. 2.2 Frobenius Inner Product For tensors \mathcal{X},\mathcal{Y}\in\mathbb{R}^{I_{1}\times\dots\times I_{L}\times J_{1}\times\dots\times J_{M}}, the Frobenius inner product is defined by \langle\mathcal{X},\mathcal{Y}\rangle_{F}=\sum_{i_{1}=1}^{I_{1}}\dots\sum_{i_{L}=1}^{I_{L}}\sum_{j_{1}=1}^{J_{1}}\dots\sum_{j_{M}=1}^{J_{M}}x_{i_{1}\dots i_{L}j_{1}\dots j_{M}}y_{i_{1}\dots i_{L}j_{1}\dots j_{M}}. The induced norm is \|\mathcal{X}\|_{F}^{2}=\langle\mathcal{X},\mathcal{X}\rangle_{F}. 3 Sketched Einstein Inner Product Let \Theta_{k}\in\mathbb{R}^{\ell_{k}\times I_{k}},\quad k=1,\dots,L, and \Psi_{l}\in\mathbb{R}^{\tilde{\ell}_{l}\times J_{l}},\quad l=1,\dots,M, be independent random projection matrices satisfying a subspace embedding property. 3.1 Compressed Tensor Define the compressed tensor by successive mode products \mathcal{X}_{\Theta}=\mathcal{X}\times_{1}\Theta_{1}\times_{2}\Theta_{2}\dots\times_{L}\Theta_{L}\times_{L+1}\Psi_{1}\dots\times_{L+M}\Psi_{M}. Then \mathcal{X}_{\Theta}\in\mathbb{R}^{\ell_{1}\times\dots\times\ell_{L}\times\tilde{\ell}_{1}\times\dots\times\tilde{\ell}_{M}}. Definition 3.1 . The sketched Einstein inner product is defined by \langle\mathcal{X},\mathcal{Y}\rangle_{\Theta}=\langle\mathcal{X}_{\Theta},\mathcal{Y}_{\Theta}\rangle_{F}. Equivalently, \langle\mathcal{X},\mathcal{Y}\rangle_{\Theta}=\sum(\mathcal{X}_{\Theta})_{\alpha_{1}\dots\alpha_{L}\beta_{1}\dots\beta_{M}}(\mathcal{Y}_{\Theta})_{\alpha_{1}\dots\alpha_{L}\beta_{1}\dots\beta_{M}}. Let \mathcal{X}\in\mathbb{R}^{I_{1}\times\dots\times I_{d}}, and let \Theta_{k}\in\mathbb{R}^{\ell_{k}\times I_{k}},\quad k=1,\dots,d, with \ell_{k}\ll I_{k} , be sketching matrices. Define the global tensor sketching operator \mathcal{S}(\mathcal{X})=\mathcal{X}\times_{1}\Theta_{1}\times_{2}\Theta_{2}\dots\times_{d}\Theta_{d}. This operator embeds tensor subspaces of \mathbb{R}^{I_{1}\times\dots\times I_{d}} into lower-dimensional tensor spaces \mathbb{R}^{\ell_{1}\times\dots\times\ell_{d}}. The Frobenius inner product between tensors is approximated by \langle\mathcal{X},\mathcal{Y}\rangle_{F}\;\approx\;\langle\mathcal{S}(\mathcal{X}),\mathcal{S}(\mathcal{Y})\rangle_{F}. 3.1.1 Tensor Subspace Embedding Let \mathcal{V} be a finite-dimensional tensor subspace of \mathbb{R}^{I_{1}\times\dots\times I_{d}}. Definition 3.2 (Tensor \varepsilon -Subspace Embedding) . Let \varepsilon<1 . The collection of sketching matrices \{\Theta_{k}\}_{k=1}^{d} defines an \varepsilon -subspace embedding for \mathcal{V} if \forall\mathcal{X},\mathcal{Y}\in\mathcal{V},\qquad\big|\langle\mathcal{X},\mathcal{Y}\rangle_{F}-\langle\mathcal{S}(\mathcal{X}),\mathcal{S}(\mathcal{Y})\rangle_{F}\big|\leq\varepsilon\|\mathcal{X}\|_{F}\|\mathcal{Y}\|_{F}. (3) 3.1.2 Equivalent Vectorized Form Using vectorization, we have \mathrm{vec}(\mathcal{S}(\mathcal{X}))=\left(\Theta_{d}\otimes\dots\otimes\Theta_{1}\right)\mathrm{vec}(\mathcal{X}). Thus the tensor embedding reduces to a classical \ell_{2} -subspace embedding in \mathbb{R}^{I_{1}\cdots I_{d}}. 3.2 Tensor Matrix Subspace Embedding Let \mathcal{V} admit a basis \{\mathcal{V}_{1},\dots,\mathcal{V}_{r}\}, and define the tensor subspace \mathcal{U}=\left\{\sum_{i=1}^{r}\mathcal{V}_{i}\alpha_{i}\;:\;\alpha_{i}\in\mathbb{R}\right\}. Definition 3.3 (Tensor Subspace Embedding – Norm Form) . The sketching operator \mathcal{S} is called an \varepsilon -subspace embedding for \mathcal{U} if (1-\varepsilon)\|\mathcal{X}\|_{F}^{2}\leq\|\mathcal{S}(\mathcal{X})\|_{F}^{2}\leq(1+\varepsilon)\|\mathcal{X}\|_{F}^{2},\quad\forall\mathcal{X}\in\mathcal{U}. (4) 3.3 Tensor Singular-Value Bounds Let \mathcal{V} be represented in matricized form along any mode k : V_{(k)}\in\mathbb{R}^{I_{k}\times r_{k}}. Let \Theta_{k}V_{(k)} be the sketched unfolding. Proposition 1 (Tensor Singular-Value Bounds) . If \mathcal{S} is an \varepsilon -subspace embedding for \mathcal{U} , then for every unfolding V_{(k)} , (1+\varepsilon)^{-1/2}\sigma_{\min}(\Theta_{k}V_{(k)})\leq\sigma_{\min}(V_{(k)})\leq\sigma_{\max}(V_{(k)})\leq(1-\varepsilon)^{-1/2}\sigma_{\max}(\Theta_{k}V_{(k)}). (5) Proof. By vectorization, \mathrm{vec}(\mathcal{S}(\mathcal{X}))=\mathbf{\Theta}\mathrm{vec}(\mathcal{X}),\quad\mathbf{\Theta}=\Theta_{d}\otimes\dots\otimes\Theta_{1}. Since \mathbf{\Theta} is an \varepsilon -embedding for \mathrm{vec}(\mathcal{U}) , classical singular-value perturbation bounds for subspace embeddings yield (1-\varepsilon)\|\mathcal{X}\|_{F}^{2}\leq\|\mathcal{S}(\mathcal{X})\|_{F}^{2}\leq(1+\varepsilon)\|\mathcal{X}\|_{F}^{2}. Applying this to rank-one tensors generated by singular vectors of the unfoldings gives the desired bounds. ∎ Krylov subspace methods via Sketched Einstein product and Tikhonov regularization In this section, we extend the tensor global Arnoldi process by incorporating a randomized sketching operator within the Einstein product framework. This allows the construction of reduced tensor Krylov subspaces while preserving the algebraic structure induced by the Einstein product. The proposed methods maintain the same theoretical properties as the classical tensor global GMRES and GGKB schemes, but with reduced computational complexity. Tikhonov regularization We consider the ill-posed tensor equation \Phi(\mathcal{X})=\mathcal{C}+\mathcal{E}, (4) where \mathcal{E} denotes the noise tensor. To stabilize the inversion process, we consider the Tikhonov regularization problem \mathcal{X}_{\mu}=\arg\min_{\mathcal{X}}\left(\|\Phi(\mathcal{X})-\mathcal{C}\|_{F}^{2}+\mu\|\mathcal{X}\|_{F}^{2}\right), (5) where \mu>0 is the regularization parameter. Sketched tensor Krylov subspace Let \mathcal{S} be a linear sketching operator acting on \mathbb{R}^{I_{1}\times\cdots\times I_{N}\times J_{1}\times\cdots\times J_{M}} such that it approximately preserves inner products induced by the Einstein product. We define the sketched operator \Phi_{S}(\mathcal{X})=\mathcal{S}\big(\Phi(\mathcal{X})\big). The m -th sketched tensor Krylov subspace generated by \Phi and \mathcal{V} is defined by \mathcal{K}_{m}^{S}(\Phi,\mathcal{V})=\operatorname{span}\left\{\mathcal{V},\Phi_{S}(\mathcal{V}),\Phi_{S}^{2}(\mathcal{V}),\ldots,\Phi_{S}^{m-1}(\mathcal{V})\right\}. (6S) This definition preserves the recursive tensor structure while reducing the dimensional complexity at each application of \Phi .

Read the complete text