Stochastic Diagonal Estimation Based on Matrix Quadratic Form Oracles

We study the problem of estimating the diagonal of an implicitly given matrix $\text{Ab}$. For such a matrix we have access to an oracle that allows us to evaluate the matrix quadratic form ${\text{ub}}^{\mathrm{\top }}\text{Ab}\text{ub}$. Based on this query oracle, we propose a stochastic diagonal estimation method with random variable $\text{ub}$ drawn from the standard Gaussian distribution. We provide the element-wise and norm-wise sample complexities of the proposed method. Our numerical experiments on different types and dimensions matrices demonstrate the effectiveness of our method and validate the tightness of theoretical results.