Spectral density estimation for normal matrices
Abstract
The spectral density estimation problem asks for an algorithm that, given an n× n matrix A, outputs a probability measure that is a good approximation to the uniform distribution on the eigenvalues of A, called the spectral density of A. This paper considers the setting where A is a large normal matrix that is accessible only through matrix-vector product queries. We provide an algorithm that makes just m matrix-vector queries to A and returns, with high probability, a measure within earth mover's distance O(1/m+log m/√n) of the true spectral density of A. We provide a complementary lower bound that any algorithm producing an ε-approximation to the true spectral density for large matrices must make Ω(1/ε) matrix-vector queries. The lower bound holds even for the more restricted case of real symmetric input matrices. In combination with our upper bound, it shows that spectral density estimation is essentially no harder for complex normal matrices than for real symmetric matrices.
Related
- A Truncated Singular-Value Bound for Spectral Variation of Normal Matrices
- Is Spectral Self-Supervised Learning a Minimax Optimal Method of Density Ratio Estimation?
- Beyond normal fluctuations in local laws for Wigner matrices
- Matrix equivalence to Smith normal form: new theoretical results for multivariate polynomial matrices
- Rayleigh-Residual Flow I: Normal Matrices
BibTeX
@misc{musco2026spectral,
title = {{Spectral density estimation for normal matrices}},
author = {Cameron Musco and Christopher Musco and Rikhav Shah and John Urschel and Nicholas West},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.31430},
eprint = {2605.31430},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.31430},
}
RIS
TY - UNPB
TI - Spectral density estimation for normal matrices
AU - Cameron Musco
AU - Christopher Musco
AU - Rikhav Shah
AU - John Urschel
AU - Nicholas West
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2605.31430
UR - https://arxiv.org/abs/2605.31430
AB - The spectral density estimation problem asks for an algorithm that, given an n× n matrix A, outputs a probability measure that is a good approximation to the uniform distribution on the eigenvalues of A, called the spectral density of A. This paper considers the setting where A is a large normal matrix that is accessible only through matrix-vector product queries. We provide an algorithm that makes just m matrix-vector queries to A and returns, with high probability, a measure within earth mover's distance O(1/m+log m/√n) of the true spectral density of A. We provide a complementary lower bound that any algorithm producing an ε-approximation to the true spectral density for large matrices must make Ω(1/ε) matrix-vector queries. The lower bound holds even for the more restricted case of real symmetric input matrices. In combination with our upper bound, it shows that spectral density estimation is essentially no harder for complex normal matrices than for real symmetric matrices.
ER -