Source-linked AI summary
A Randomized Tensor Singular Value Decomposition based on the t-product
Jiani Zhang, Arvind K. Saibaba, Misha Kilmer, Shuchin Aeron
TL;DR
Large datasets challenge matrix-based analysis, and the paper asks how to extend randomized low-rank methods while retaining multidimensional tensor structure. It develops randomized t-SVD algorithms using the t-product; their expected errors are theoretically comparable to the best rank-k t-SVD approximation, with numerical support from facial recognition.
Problem
The paper asks how to generalize best low-rank approximation and randomized matrix techniques to tensor data while retaining its inherent multi-way structure.
Source: §1 · p. 2Method
The paper extends randomized SVD to third-order tensors through the t-product, with basic and subspace-iteration algorithms and implementations in spatial and Fourier domains.
Source: §1 · p. 3Results
The expected errors of both randomized t-SVD algorithms are theoretically comparable to the best rank-k approximation obtained by deterministic t-SVD, with numerical support from facial-recognition applications.
Source: §1 · p. 3, §5 · p. 17Takeaways & Limitations
The methods combine randomized dimensionality reduction with t-product tensor decompositions and are applied to facial recognition, including a parallel implementation.
Source: §1 · p. 3, §5 · p. 17Adding a new image or image set to the database requires recomputing the approximate factorization, which can be very expensive.
Source: §5 · p. 18
Abstract
from arXiv · showhide
The tensor Singular Value Decomposition (t-SVD) for third order tensors that was proposed by Kilmer and Martin~\cite{2011kilmer} has been applied successfully in many fields, such as computed tomography, facial recognition, and video completion. In this paper, we propose a method that extends a well-known randomized matrix method to the t-SVD. This method can produce a factorization with similar properties to the t-SVD, but is more computationally efficient on very large datasets. We present details of the algorithm, theoretical results, and provide numerical results that show the promise of our approach for compressing and analyzing datasets. We also present an improved analysis of the randomized subspace iteration for matrices, which may be of independent interest to the scientific community.
1 Introduction
Growing datasets challenge matrix-based analysis, while exact truncated SVD can be prohibitively expensive. The paper motivates randomized tensor factorization that retains multidimensional structure and extends randomized SVD through the t-product and t-SVD.
1 Introduction
- Petabyte-scale datasets and multidimensional data structures challenge matrix-based analysis and motivate low-rank methods that preserve tensor structure.Examples include hyperspectral images represented as slices and videos represented as higher-order tensors.Source: §1 · pp. 1–2
- Accurately computing truncated matrix SVD can be prohibitively expensive at very large scales, motivating cheaper low-rank approximations that relinquish optimality for near-optimal results.Randomized matrix methods use sampling or projection and are described as numerically robust, computationally efficient, and suited to varied architectures.Source: §1 · p. 2
- Tensor low-rank approximation depends on the chosen decomposition: CP rank-k approximation may not exist without extra assumptions, while truncating HOSVD does not yield the best Tucker approximation.Tucker3 factorization always exists, and its factor matrices can be chosen with orthonormal columns.Source: §1 · p. 2
- The t-SVD defines tensor factorization through the t-product, and truncating it gives a Frobenius-norm-optimal compressed result.The authors cite existing applications in which tensor decompositions improve on matrix-based counterparts, while noting that these methods are deterministic.Source: §1 · pp. 2–3
- The t-product motivates this extension through its theoretical and computational advantages, including a best k-term truncation, parallelizable t-SVD computations, and established tensor analogues of matrix operations.The introduction also notes prior t-SVD results reporting better compression characteristics than Tucker in some applications.Source: §1 · p. 3
- The paper extends randomized SVD to third-order tensors using the t-product and t-SVD, developing basic and subspace-iteration algorithms with error analysis and a facial-recognition application.The authors also report efficient implementations in spatial and Fourier domains, including a parallel implementation.Source: §1 · p. 3
2 Preliminaries
This section reviews randomized matrix SVD and the tensor operations underlying t-SVD. It also states their approximation properties and computational features that motivate randomized tensor methods.
2.1 The r-SVD
- The randomized matrix SVD forms a basis from random linear combinations of A's columns, then factors the projected matrix to estimate its singular values and vectors.When singular values decay gradually, subspace iteration may be preferred.Source: §2.1 · pp. 4–5
- The section presents a Frobenius-norm error analysis for randomized matrix subspace iteration, where prior analysis covered the spectral norm.The stated result assumes a small singular-value gap ratio τk.Source: §2.1 · p. 5
- The analysis states that k/(p − 1) decreases and subspace iteration achieves the optimal error of the SVD; at q = 0 it exactly obtains Theorem 2, sharpening a similar result in [19, Theorem 5.7].Source: §2.1 · p. 5
2.2 Tensors
- The t-product between tensors is defined using circular convolution of tube fibers and can be computed in the Fourier domain.A tensor's third-order structure is described using fibers and slices.Source: §2.2 · pp. 5–6
- The paper introduces Gaussian random tensors to use as few random samples as possible while retaining access to results for Gaussian random matrices.The definition places standard normal entries in the first frontal slice and zeros in the remaining slices.Source: §2.2 · p. 7
2.3 t-SVD
- Truncating the t-SVD gives the minimum Frobenius error among approximations expressible as a t-product with inner dimension k.This is a best tubal-rank k approximation, not necessarily a best rank-k outer-product or Tucker3 approximation.Source: §2.3 · p. 8
- A k-term truncated t-SVD costs O(n1n2n3k) flops and can parallelize over frontal slices, unlike typical truncated matrix SVD algorithms.The stated flop count matches that of a truncated SVD for a matrix of size n1n2 × n3.Source: §2.3 · p. 8
3 Randomized Tensor SVD
The rt-SVD extends randomized matrix SVD to third-order tensors under the t-product, producing approximate low-tubal-rank factorizations. The section develops slice-wise subspace-iteration variants and analyzes their error and computational cost.
3 Randomized Tensor SVD
- The rt-SVD forms a random projection, computes a t-QR basis, truncates the t-SVD of the compressed tensor, and uses the resulting factors to approximate A.The projection is Y = A ∗ W, the compressed tensor is B = Q^T ∗ A, and the approximation is (Q ∗ U) ∗ S_k ∗ V_k^T.Source: §3 · pp. 8–9
- In the Fourier domain, the method applies matrix randomized SVD results independently to each frontal slice.This implementation is presented to facilitate error analysis.Source: §3 · p. 9
- The expected-error bound matches the matrix-case optimality factor 1 + k/(p − 1), and its approximation quality depends on frontal-slice singular-value decay.Rapid decay yields a bound involving the largest (k + 1)th singular value across slices; gradual decay can leave that term large.Source: §3 · p. 10
- When the (k + 1)th singular value is large, subspace iteration can improve accuracy; assigning a separate iteration count to each slice avoids wasted work when decay rates differ.A shared iteration count is efficient when slice singular values decay at similar rates.Source: §3 · p. 10
- Choosing iteration counts using tolerance ϵ bounds the expected error by at most √(1 + ϵ) times the optimal result.The bound is stated for the probabilistic error under the strategy derived from Theorem 5.Source: §3 · p. 11
- The analysis also provides tail bounds for probabilistic error; for n2 = 100, k = 30, p = 20, and δ = 10^-16, Cδ ≈ 43.The theorem allows an arbitrarily small chance that its upper bound does not hold.Source: §3 · pp. 11–12
- The t-SVD costs O(n1n2n3 log n3) for the Fourier transform plus O(n1n2n3 min{n1, n2}) for decomposition, while rt-SVD costs O(kn1n2n3).The section states rt-SVD can be advantageous when k ≪ min{n1, n2}.Source: §3 · p. 12
4 Numerical Results
The numerical results compare randomized tensor approximations with theoretical error bounds and evaluate facial recognition accuracy and computation time on two datasets. They also examine how parallel execution affects runtime.
4 Numerical Results
- Two public face datasets are used: Cropped Yale B, with 1,140 images, and AT&T, with 400 images.Images are organized as lateral slices; test faces are recognized by projecting onto the training data and selecting the closest tensor coefficient.Source: §4 · p. 12, §4.2 · p. 13
4.1 Error Analysis
- With subspace iterations, the relative errors approach the theoretical minimum as iteration count increases; both randomized methods remain comparable in accuracy to truncated t-SVD.The comparison uses dataset B and target truncation terms k from 50 to 180.Source: §4.1 · p. 12, Figure 4.1.1 · p. 13
4.2.1 Cropped Yale Face B Dataset
- As truncation k increases on Cropped Yale B, recognition rate and computation time both increase, creating a tradeoff in choosing k.The reported k values range from 25 to 50.Source: §4.2.1 · p. 14, Table 2 · p. 14, Table 3 · p. 15
- About one-third the cost of full t-SVD, rt-SVD with subspace iterations matches its recognition rates in every Cropped Yale B fold.The randomized methods show almost no variation across realizations.Source: §4.2.1 · p. 16
4.2.2 AT&T Dataset
- The AT&T experiments report results for k = 15 and k = 25, and their numerical results are described as consistent with Cropped Yale B.The dataset contains images with different poses.Source: §4.2.2 · p. 16, Table 4 · p. 16, Table 5 · p. 17
4.3 Computation time for parallel implementation
- On Cropped Yale B with k = 50, runtime decreases on average as the number of processors increases, up to eight processors.The experiments compare parallel implementations of t-SVD, rt-SVD, and rt-SVD with subspace iterations.Source: §4.3 · p. 17
5 Conclusion and Future Work
The paper develops randomized tensor low-rank algorithms based on the t-product and reports theoretical and empirical support for their accuracy and efficiency. It identifies updating factorizations when images are added as a future direction.
Conclusion
- The paper introduces rt-SVD and rt-SVD with subspace iterations for third-order tensors, with theoretical error behavior comparable to the best rank-k t-SVD approximation.The algorithms can be parallelized, and the paper demonstrates parallel computation-time benefits.Source: §5 · p. 17
- Facial-recognition experiments on two publicly available datasets provide numerical support for the algorithms’ accuracy.The conclusion also reports parallelization benefits in computation time.Source: §5 · p. 17
Future Work
- The authors propose exploring randomized t-SVD II and structured random tensors based on subsampled Hadamard or Fourier transforms.They describe these as potential future research directions.Source: §5 · pp. 17–18
- Adding images can require recomputing the approximate factorization, which the authors note may be very expensive.They identify tensor updating or downdating as a possible future extension.Source: §5 · p. 18
A Randomized subspace iteration
This appendix develops matrix subspace-iteration error analysis used in the paper’s tensor results. It also compares the resulting bound with an earlier bound under specified parameter conditions.
A Randomized subspace iteration
- The subspace iteration is also expressed using a random starting guess, and the appendix proves Theorem 2 by applying the arguments of [21, Theorem 10.5] to Theorem 7.Source: A Randomized subspace iteration · pp. 18–19
- For full-column-rank V, the projection onto Range(V) is V(V^H V)^−1V^H; with orthonormal columns, it simplifies to VV^H.Source: A Randomized subspace iteration · p. 18
- The analysis presents an error characterization for a matrix approximation using Algorithm 2, assuming W_1 has full row rank.The stated result makes minimal assumptions about the sampling matrix W and applies to any distribution.Source: A Randomized subspace iteration · p. 18
- Theorem 2’s estimate is sharper than the bound from [19, Theorem 5.7] when ℓ = k + p and p ≥ 2; for other choices, the earlier bound may be sharper depending on singular-value decay.The stated condition places the singular-value gap between k and k + 1.Source: A Randomized subspace iteration · p. 19
B Proofs of Section 3
The appendix supplies proof steps for tensor error results by relating tensor norms to Fourier-domain frontal slices and applying matrix approximation bounds. It uses Gaussian rotation invariance in one probabilistic argument.
B Proofs of Section 3
- The appendix introduces a tensor lemma described as similar to Parseval’s theorem and uses it in the proofs of Theorems 4 and 5.Source: B Proofs of Section 3 · pp. 19–20
- Theorem 4’s proof bounds terms in a sum, substitutes the resulting inequality, and completes the argument using Hölder’s inequality.Source: B Proofs of Section 3 · p. 20
- Theorem 5’s proof applies Theorem 2 to each Fourier-domain frontal slice and then follows the remaining steps used for Theorem 4.Source: B Proofs of Section 3 · pp. 19–20
- The proof of Theorem 6 combines Lemma 1 and Theorem 7, then uses independence of the Gaussian-derived W_1 slices to apply Lemma 2.Source: B Proofs of Section 3 · p. 21