Optimal query complexity for estimating the trace of a matrix

DOI10.1007/978-3-662-43948-7_87MaRDI QIDQ5167814zbMATH OpenOpenAlexFDO

Authors Karl Wimmer, Yi Wu, Peng Zhang

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.7112

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Abstract: Given an implicit $nimesn$ matrix $A$ with oracle access $x^{T}Ax$ for any $xinmathbb{R}^n$, we study the query complexity of randomized algorithms for estimating the trace of the matrix. This problem has many applications in quantum physics, machine learning, and pattern matching. Two metrics are commonly used for evaluating the estimators: i) variance; ii) a high probability multiplicative-approximation guarantee. Almost all the known estimators are of the form $frac1ksu{m}_{i=1}^k{x}_i^{T}A{x}_i$ for $x_{i}inmathbb{R}^n$ being i.i.d. for some special distribution. Our main results are summarized as follows. We give an exact characterization of the minimum variance unbiased estimator in the broad class of linear nonadaptive estimators (which subsumes all the existing known estimators). We also consider the query complexity lower bounds for any (possibly nonlinear and adaptive) estimators: (1) We show that any estimator requires $Omega(1/epsilon)$ queries to have a guarantee of variance at most $epsilon$. (2) We show that any estimator requires $Omega(frac1epsilo{n}^{2}logfrac1delta)$ queries to achieve a $(1pmepsilon)$-multiplicative approximation guarantee with probability at least $1-delta$. Both above lower bounds are asymptotically tight. As a corollary, we also resolve a conjecture in the seminal work of Avron and Toledo (Journal of the ACM 2011) regarding the sample complexity of the Gaussian Estimator.

Recommendations

• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Improved bounds on sample size for implicit matrix trace estimators
• Randomized matrix-free trace and log-determinant estimators
• How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?
• Improved Variants of the Hutch++ Algorithm for Trace Estimation

Cited in

(9)

• On randomized trace estimates for indefinite matrices with an application to determinants
• How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
• Faster randomized partial trace estimation
• Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices
• Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
• Query lower bounds for log-concave sampling
• Improved bounds on sample size for implicit matrix trace estimators

This page was built for publication: Optimal query complexity for estimating the trace of a matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167814)