Randomized Estimation of T-Eigenvalues of T-SPD Tensors: A Two-Sided Bracket

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 ${\lambda }_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.