Stochastic Diagonal Estimation Based on Matrix Quadratic Form Oracles

We study the problem of estimating the diagonal of an implicitly given matrix . For such a matrix we have access to an oracle that allows us to evaluate the matrix quadratic form ^. Based on this query oracle, we propose a stochastic diagonal estimation method with random variable 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.