An estimator for the diagonal of a matrix

By C. Bekas, Effrosini Kokiopoulou, Y. Saad. 2007

246 citations recorded by the source corpus.

Subfields: Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics, Materials Chemistry

View Paper: https://www.semanticscholar.org/paper/bfdbe36894d3d02f061adf0df3da62cc55bc5d3c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Computational Theory and Mathematics

In Materials Chemistry

Citations in the corpus

Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, background): “[8] Costas Bekas, Effrosyni Kokiopoulou, and Yousef Saad.”
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix (2011, methodology): “Finding the rank of a projection matrix is useful for computing charge densities (in electronic structures calculations) without diagonalization [Bekas et al. 2007].”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, methodology): “It can be proved that the expectation of z (cid:12) ( H z ) converges to the Hessian diagonal with sufﬁciently many random samples [4].”
Adaptive norms for deep learning with regularized Newton methods (2019, background): “We thus consider the development of further ellipsoids that can potentially adapt even better to the loss landscape such as e.g. (block-) diagonal hessian approximations (e.g. Bekas et al. (2007)) or approximations of higher order derivatives as an interesting direction of future research.”
RMSProp and equilibrated adaptive learning rates for non-convex optimization (2015, unknown): “Bekas et al. (2007) show that the diagonal of a matrix can be recovered by the expression”
DECAY BOUNDS AND ( ) ALGORITHMS FOR APPROXIMATING FUNCTIONS OF SPARSE MATRICES (2007, methodology): “For instance, when f is analytic, f(A) can be defined by a power series expansion, or by a contour integral (using Cauchy’s Theorem).”
Estimating the Spectral Density of Large Implicit Matrices (2018, methodology): “If the Skilling-Hutchinson trace estimator is used sequentially, then the raw diagonal estimator sitting beneath it can be used to form a diagonal B , i.e., E [ x T A x ] = diag( A ) where is element-wise product (Bekas et al., 2007).”
Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations (2016, background): “Bekas et al. [6] and Malioutov et al. [33] consider the problem of computing the diagonal of a matrix or of the matrix inverse.”
Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature (2017, methodology): “It has since been shown that vectors from any other random distributions of zero mean and unit covariance also work [8, 5].”
A probing method for computing the diagonal of a matrix inverse (2012, methodology): “Later, Bekas et al. [26] extended this idea to develop an unbiased stochastic estimator for (cid:2) ( M ) ∈ C n , which is the diagonal of D ( M ), reshaped as a vector.”
Fast approximation of matrix coherence and statistical leverage (2011, methodology): “For example, in the former case, “heuristic” methods based on using Chebychev polynomials have been used in numerical linear algebra to compute the diagonal elements of the projector (Bekas et al., 2007).”
Pruning Convolutional Neural Networks for Resource Efficient Inference (2016, methodology): “Our implementation of Hessian diagonal computation was inspired by Dauphin et al. (2015) work, where the technique proposed by Bekas et al. (2007) was used to evaluate SGD preconditioned with the Jacobi preconditioner.”
The SURE-LET Approach to Image Denoising (2007, background): “In particular, for a 3Note that a similar result for the stochastic estimation of the trace or the diagonal of a matrix can be found in [115,116].”