Dimension-Free -Sampling Algorithms for Eigenvalue EstimationResearch Paper
Computing the eigenvalues of a symmetric matrix is a basic primitive of numerical linear algebra, data analysis and spectral algorithms. Classical methods read every entry, which costs for a dense matrix. Bhattacharjee, Dexter, Drineas, Musco and Ray ([BDD+24], Algorithmica 2024) asked whether a sublinear number of entry queries…