On The Variance of Schatten p-Norm Estimation with Gaussian Sketching Matrices

2024/10/21 by Horesh, Lior, Kalantzis, Vasileios, Lu, Yingdong +1
#60-08 #65C05 #65F35 #FOS: Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2410.16455

Abstract

Monte Carlo matrix trace estimation is a popular randomized technique to estimate the trace of implicitly-defined matrices via averaging quadratic forms across several observations of a random vector. The most common approach to analyze the quality of such estimators is to consider the variance over the total number of observations. In this paper we present a procedure to compute the variance of the estimator proposed by Kong and Valiant [Ann. Statist. 45 (5), pp. 2218 - 2247] for the case of Gaussian random vectors and provide a sharper bound than previously available.

Related

• Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
• A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
• Performance Bounds for Sparse Parametric Covariance Estimation in\n Gaussian Models
• Stochastic Trace Optimization of Parameter Dependent Matrices Based on Statistical Learning Theory
• Norm and trace estimation with random rank-one vectors