Randomized Estimation of T-Eigenvalues of T-SPD Tensors: A Two-Sided Bracket
For researchers working with large third-order tensors, this work provides practical randomized eigenvalue estimation that complements existing deterministic bounds, though the methods are incremental adaptations of known randomized techniques.
This paper develops randomized estimators for extreme T-eigenvalues of T-SPD tensors, adapting the Halko–Martinsson–Tropp framework to the T-product setting. The two-sided bracket combining randomized lower bounds with deterministic upper bounds provides rigorous eigenvalue intervals, with the randomized power method achieving exponential convergence.
In earlier work \cite{sharma2025} we developed deterministic analytical bounds on the T-eigenvalues of symmetric positive definite (SPD) third-order tensors under the Kilmer--Martin T-product: the trace--determinant (TDet) bounds via the AM--GM inequality, and the trace-dependent (TDep) bounds generalizing Samuelson's inequality. While these bounds are cheap and guaranteed-valid, their relative gap grows as $\sqrt{d-1}$ in the tensor dimension $d = np$, limiting their usefulness for large tensors. This paper develops randomized estimators for the extreme T-eigenvalues of T-SPD tensors that complement the deterministic bounds. We adapt the Halko--Martinsson--Tropp framework \cite{halko2011} to the T-product setting and introduce four methods: (i) a randomized power method that produces a lower bound on $λ_1$ with exponential convergence; (ii) a randomized subspace iteration with a tensor-analogue HMT error bound; (iii) a two-sided rigorous bracket combining the randomized lower bound with the deterministic TDep upper bound; and (iv) a Hutchinson-based fully randomized TDep bound for matvec-only settings.