# Sublinear Time Eigenvalue Approximation via Random Sampling

@article{Bhattacharjee2021SublinearTE, title={Sublinear Time Eigenvalue Approximation via Random Sampling}, author={Rajarshi Bhattacharjee and Cameron Musco and Archan Ray}, journal={ArXiv}, year={2021}, volume={abs/2109.07647} }

We study the problem of approximating the eigenspectrum of a symmetric matrix A ∈ Rn×n with bounded entries (i.e., ‖A‖∞ ≤ 1). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error ± n using those of a randomly sampled Õ( 1 4 )× Õ( 1 4 ) principal submatrix. Our result can be viewed as a concentration bound on the full eigenspectrum of a random principal submatrix. It significantly extends existing work which shows concentration of just the… Expand

#### References

SHOWING 1-10 OF 41 REFERENCES

Eigenvalues of a matrix in the streaming model

- Computer Science, Mathematics
- SODA
- 2013

What is shown can be seen as a form of a bi-linear dimensionality reduction: if the authors multiply an input matrix with projection matrices on both sides, the resulting matrix preserves the top eigenvalues and the residual Frobenius norm. Expand

Approximating Spectral Densities of Large Matrices

- Mathematics, Computer Science
- SIAM Rev.
- 2016

The problem of estimating the spectral density carefully is defined and how to measure the accuracy of an approximate spectral density is discussed, which is generally costly and wasteful, especially for matrices of large dimension. Expand

Fast matrix multiplication is stable

- Computer Science, Mathematics
- Numerische Mathematik
- 2007

It is shown that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms, and new group-theoretic algorithms proposed in Cohn and Umans, and Cohn et al. are all included in the class of algorithms to which the analysis applies. Expand

Fast and stable deterministic approximation of general symmetric kernel matrices in high dimensions

- Computer Science, Mathematics
- ArXiv
- 2021

This paper develops a unified theoretical framework for analyzing Nyström approximations, which is valid for both SPSD and indefinite kernels and is independent of the specific scheme for selecting landmark points, and proposes the anchor net method, which operates entirely on the dataset without requiring the access to K or its matrix-vector product. Expand

The Noisy Power Method: A Meta Algorithm with Applications

- Computer Science, Mathematics
- NIPS
- 2014

A new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that is called the noisy power method is provided and shows that the error dependence of the algorithm on the matrix dimension can be replaced by an essentially tight dependence on the coherence of the matrix. Expand

Improved testing of low rank matrices

- Mathematics, Computer Science
- KDD
- 2014

This work studies the problem of quickly estimating the rank or stable rank of A, the latter often providing a more robust measure of the rank, and proves an Ω(d/ε) lower bound on the number of rows that need to be read, even for adaptive algorithms. Expand

On approximating functions of the singular values in a stream

- Mathematics, Computer Science
- STOC
- 2016

The results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices A and obtain similar near-linear lower bounds for Ky-Fan norms, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to this work. Expand

Fast Monte-Carlo algorithms for approximate matrix multiplication

- Computer Science
- Proceedings 2001 IEEE International Conference on Cluster Computing
- 2001

Given an m ? n matrix A and an n ? p matrix B, we present 2 simple and intuitive algorithms to compute an approximation P to the product A ? B, with provable bounds for the norm of the "error matrix"… Expand

DENSITIES OF STATES OF MEGA-DIMENSIONAL HAMILTONIAN MATRICES

- Mathematics
- 1994

We propose a statistical method to estimate densities of states (DOS) and thermodynamic functions of very large Hamiltonian matrices. Orthogonal polynomials are defined on the interval between lower… Expand

Norms of Random Submatrices and Sparse Approximation

- Mathematics
- 2008

Many problems in the theory of sparse approximation require bounds on operator norms of a random submatrix drawn from a fixed matrix. The purpose of this Note is to collect estimates for several… Expand