Stochastic Trace and Diagonal Estimator for Tensors

2025/10/25 by Verma, Bhisham Dev, Pratap, Rameshwar, Kang, Keegan
#FOS: Mathematics #Numerical Analysis (math.NA) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2510.22157

Abstract

We consider the problem of estimating the trace and diagonal entries of an N-order tensor (where N ≥ 2) under the framework where the tensor can only be accessed through tensor-vector multiplication. The aim is to estimate the tensor's diagonal entries and trace by minimizing the number of tensor-vector queries. The seminal work of Hutchinson and its extended version due to Bekas et al. give unbiased estimates of the trace and diagonal elements of a given matrix, respectively, using matrix-vector queries. However, to the best of our knowledge, no analogous results are known for estimating the trace and diagonal entries of higher-order tensors using tensor-vector queries. This paper addresses this gap and presents unbiased estimators for the trace and diagonal entries of a tensor under this model. Our proposed methods can be seen as generalizations of Hutchinson's and Bekas et al.'s estimators and reduce to their estimators when N = 2. We provide a rigorous theoretical analysis of our proposals and complement it with supporting simulations.

Citations

• Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation
• MG-MLMC++ as a Variance Reduction Method for Estimating the Trace of a Matrix Inverse
• A Tight Analysis of Hutchinson's Diagonal Estimator
• Stochastic diagonal estimation: probabilistic bounds and an improved algorithm
• Dynamic Trace Estimation
• Improved variants of the Hutch++ algorithm for trace estimation
• A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
• Estrada index and subgraph centrality of hypergraphs via tensors
• A Tensor-Based Formulation of Hetero-functional Graph Theory
• A Modern Analysis of Hutchinson's Trace Estimator
• Hutch++: Optimal Stochastic Trace Estimation
• On randomized trace estimates for indefinite matrices with an\n application to determinants
• Norm and trace estimation with random rank-one vectors
• Tensorized Random Projections
• Predicting many properties of a quantum system from very few measurements
• Estimating the Spectral Density of Large Implicit Matrices
• Introduction to Tensor Decompositions and their Applications in Machine Learning
• Tensor Decomposition for Signal Processing and Machine Learning
• Equilibrated adaptive learning rates for non-convex optimization
• Learning the Parameters of Determinantal Point Process Kernels
• Some new trace formulas of tensors with applications in spectral hypergraph theory
• Concentration and Moment Inequalities for Polynomials of Independent Random Variables
• Tensor Decompositions and Applications
• Random phase vector for calculating the trace of a large matrix

Related

• Tensor Completion with Nearly Linear Samples Given Weak Side Information
• Spectral algorithms for tensor completion
• Statistical Limits for Finite-Rank Tensor Estimation
• Tensor models from the viewpoint of matrix models: the case of the Gaussian distribution
• Statistical Inference for Low-Rank Tensors: Heteroskedasticity, Subgaussianity, and Applications