🔢 mathematics

Randomized block Krylov method for approximation of truncated tensor SVD

This paper proposes and evaluates a randomized block Krylov subspace method for approximating the truncated tensor SVD, demonstrating its theoretical validity and practical efficiency in data completion and compression tasks through experiments on both synthetic and real-world datasets.

Original authors: Malihe Nobakht Kooshkghazi, Salman Ahmadi-Asl, Andre L. F. de Almeida

Published 2026-03-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Malihe Nobakht Kooshkghazi, Salman Ahmadi-Asl, Andre L. F. de Almeida

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, multi-layered library of information. Instead of just books (2D pages) or single words (1D text), this library is made of tensors—think of them as 3D blocks of data, like a stack of photos, a video, or a hyperspectral image where every pixel holds a spectrum of colors.

The problem? These data blocks are huge. They take up too much space and are too slow to process. We want to shrink them down (compress them) or fill in the missing pieces (like a puzzle with 90% of the pieces gone) without losing the important details.

To do this, mathematicians use a tool called T-SVD (Tensor Singular Value Decomposition). Think of T-SVD as a way to break a complex 3D block down into its simplest, most essential "ingredients." If you keep only the top few ingredients, you get a smaller, simpler version that still looks and acts almost exactly like the original.

The Old Way: The "Guess and Check" Method

Traditionally, to find these essential ingredients, researchers used a method called Randomized Power Iteration.

The Analogy: Imagine you are trying to find the loudest voice in a crowded stadium. The old method is like shouting "Who's the loudest?" and listening to the echo. You do this a few times, and each time, the echo gets a bit clearer. But to get a really clear answer, you have to shout many, many times. It's slow, and if the voices are very similar in volume, it takes forever to tell them apart.

The New Way: The "Block Krylov" Method

This paper introduces a new, smarter technique called the Randomized Block Krylov Method.

The Analogy: Instead of just listening to the echo once and discarding it, this new method is like recording every echo you've ever heard and stacking them together to build a giant, crystal-clear soundboard.
- The "Block": Instead of asking about one voice at a time, it asks about a whole group of voices at once.
- The "Krylov": It doesn't just listen to the final echo; it keeps a record of every step of the conversation. It uses the history of the process to refine its guess much faster.

Why is this better?
In the old method, you might need 10 rounds of shouting to get a good answer. In this new method, you might only need 2 or 3 rounds, but because you are using all that extra information from the previous rounds, your answer is sharper, more accurate, and more detailed.

What Did They Do?

The authors of this paper took this powerful "soundboard" idea and applied it to 3D data blocks (tensors). They proved mathematically that it works and then tested it in the real world:

Image Compression: They took colorful photos (like "peppers" or "baboons") and shrunk them down. The new method kept the image looking crisp with less data than the old method.
Image Completion (The "Inpainting" Magic): They took photos and deleted 70% to 98% of the pixels (leaving huge holes). Then, they used their new algorithm to fill in the blanks.
- The Result: It was like a master painter looking at a few scattered dots and instantly knowing exactly what the rest of the picture should look like. It worked even better and faster than other popular methods used by scientists today.

The Bottom Line

This paper is about a smarter, faster way to simplify and repair complex 3D data.

Old Way: Slow, requires many attempts, and sometimes misses the fine details.
New Way: Uses a "memory" of every step to get a high-quality result much faster.

It's like upgrading from a basic flashlight to a high-tech laser scanner: you get the same job done, but with incredible precision and in a fraction of the time. This is great news for anyone dealing with big data, from streaming video services to medical imaging and artificial intelligence.

1. Problem Statement

The paper addresses the computational challenge of approximating the Truncated Tensor Singular Value Decomposition (T-SVD) for large-scale third-order tensors.

Context: Tensors are essential for representing high-dimensional data (e.g., color images, videos, hyperspectral data). The T-SVD, based on the T-product (a tensor-tensor multiplication defined in the Fourier domain), generalizes matrix SVD to tensors.
Challenge: Computing the exact T-SVD for large tensors is computationally expensive ( $O(n^3)$ or higher). While randomized algorithms (like classical randomized subspace methods with power iterations) exist to accelerate this, they often suffer from slow convergence when the singular values decay slowly or when the spectral gap is small.
Goal: To develop a more efficient and accurate randomized algorithm that captures the spectral range of the tensor better than classical methods, reducing the number of iterations required for high-precision approximations.

2. Methodology

The authors propose a Randomized Block Krylov Subspace Method tailored for T-SVD. The approach leverages the properties of the T-product and the Discrete Fourier Transform (DFT).

Core Concepts

T-Product: Defined as $X * Y = \text{fold}(\text{bcirc}(X) \cdot \text{unfold}(Y))$ . In the Fourier domain, this operation becomes standard matrix multiplication for each frontal slice of the tensor.
Block Krylov Subspace: Unlike classical randomized methods that only use the result of the final power iteration step ( $(X*X^\top)^q * X * B$ $(X * X^{⊤})^{q} * X * B$ ), the proposed method constructs a subspace using all intermediate iterations.
- Let $K_0 = X * B$ (where $B$ is a random tensor).
- The Krylov subspace is formed by the block tensor $K = [K_0, K_1, \dots, K_q]$ , where $K_i = (X * X^\top) * K_{i-1}$ .

The Proposed Algorithm (Algorithm 5)

Random Projection: Generate a random tensor $B$ and compute $K_0 = X * B$ .
Power Iteration & Block Construction: Iteratively compute $K_i = (X * X^\top) * K_{i-1}$ for $i=1 \dots q$ .
Subspace Formation: Concatenate all iterations into a block tensor $K = [K_0, K_1, \dots, K_q]$ .
Orthogonalization: Perform a T-QR decomposition on $K$ to obtain an orthogonal basis $Q$ .
Projection: Compute the projected tensor $C = Q^\top * X$ .
Truncated SVD: Compute the T-SVD of the smaller tensor $C$ to get $\tilde{U}, \tilde{S}, \tilde{V}$ .
Reconstruction: The final approximation is $\hat{X} = (Q * \tilde{U}_R) * \tilde{S}_R * \tilde{V}_R^\top$ .

Theoretical Analysis

The paper provides rigorous theoretical guarantees:

Error Bounds: The authors derive an upper bound for the spectral norm error $\|X - \hat{X}\|_2$ . The error is shown to depend on the $(2q+1)$ -th root of the singular values of a specific tensor constructed from the Krylov sequence.
Convergence: The analysis proves that by utilizing the entire block Krylov sequence rather than just the final power iteration, the method achieves super-linear convergence. This allows for high accuracy with fewer iterations ( $q$ ) compared to classical methods.
Key Lemmas: The proof relies on properties of T-orthogonal projections, the linearity of the bcirc operator, and the relationship between tensor norms and matrix norms in the Fourier domain.

3. Key Contributions

Novel Algorithm: Introduction of the first randomized block Krylov method specifically designed for Truncated T-SVD.
Theoretical Guarantees: Detailed theoretical analysis establishing error bounds and proving that the method captures a richer spectral range than classical randomized subspace methods.
Efficiency vs. Accuracy Trade-off: Demonstrates that while the per-iteration cost is slightly higher (due to orthogonalizing a larger block), the total computational cost to achieve a target accuracy is significantly lower because fewer iterations are needed.
Applications: Validated the method in two practical scenarios:
- Data Compression: Reducing the storage size of images while maintaining quality.
- Data Completion: Recovering missing pixels in images (inpainting) under random and structured missing patterns.

4. Experimental Results

The authors conducted experiments on synthetic data and real-world datasets (Kodak image dataset) using MATLAB.

Synthetic Data:
- Tested on tensors with varying singular value decay rates ( $1/m^5$ , $1/m^6$ , exponential).
- Result: The proposed algorithm (Algorithm 5) consistently achieved lower relative errors than the baseline classical randomized method (Algorithm 4) for the same number of iterations.
Image Compression:
- Applied to "peppers," "baboon," and "house" images ( $256 \times 256 \times 3$ ).
- Result: The proposed method yielded marginally better Peak Signal-to-Noise Ratio (PSNR) values. The running time was slightly higher per run but more efficient for high-precision requirements.
Image Completion (Inpainting):
- Tested on the Kodak dataset with missing pixel ratios ranging from 70% to 98%.
- Structured Patterns: Tested against various missing patterns (occlusion lines, circles, text masks).
- Comparison: Outperformed Bayesian CPD, Tensor Ring, and Tensor Train completions in terms of PSNR and robustness.
- Speed: The proposed method was comparable to Tensor Ring completion but 4-5 times faster than other baselines. It achieved similar PSNR to state-of-the-art randomized methods ([42]) but with slightly faster execution.
Parameter Sensitivity: The method was found to be robust to the choice of oversampling ( $P$ ) and power iteration ( $q$ ) parameters. Small values (e.g., $P=5-10$ , $q=2$ ) were often sufficient.

5. Significance and Conclusion

Paradigm Shift: The paper highlights the synergy between randomization (for cheap subspace guessing) and Krylov methods (for iterative refinement). This combination creates algorithms that are faster, more robust, and theoretically stronger than using either approach in isolation.
Practical Impact: The method offers a scalable solution for large-scale tensor data processing, which is critical in fields like computer vision, signal processing, and machine learning.
Future Work: The authors plan to extend this method to other tensor decompositions (e.g., Tucker, Tensor Train) and explore its application in enhancing the adversarial robustness of deep neural networks.

In summary, this paper successfully bridges the gap between theoretical randomized linear algebra and practical tensor analysis, providing a superior algorithm for low-rank tensor approximation that balances computational cost with high accuracy.