Pith. sign in

REVIEW 2 minor 1 cited by

An algorithm approximates the spectral density of a normal matrix to Earth Mover's distance O(1/m + log m / sqrt(n)) using m matrix-vector queries, with a matching Omega(1/eps) lower bound even for symmetric matrices.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-28 21:13 UTC pith:IIKHWKCY

load-bearing objection The paper shows spectral density estimation on normal matrices matches the symmetric query lower bound asymptotically via an m-query algorithm with EMD error O(1/m + log m/sqrt(n)).

arxiv 2605.31430 v1 pith:IIKHWKCY submitted 2026-05-29 math.NA cs.NA

Spectral density estimation for normal matrices

Cameron Musco , Christopher Musco , Rikhav Shah , John Urschel , Nicholas West This is my paper
classification math.NA cs.NA
keywords spectral density estimationnormal matricesmatrix-vector queriesEarth Mover's distanceeigenvalue distributionquery complexitylower bounds
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an algorithm for approximating the spectral density of an n by n normal matrix when the matrix is accessible only through matrix-vector products. With m such products the algorithm returns a probability measure whose Earth Mover's distance to the true density is at most O(1/m + log m / sqrt(n)) with high probability. A complementary lower bound shows that Omega(1/eps) queries are necessary to achieve eps-approximation in the worst case. The lower bound continues to hold when the input is restricted to real symmetric matrices, so the query complexity for normal matrices is essentially the same as for the symmetric case.

Core claim

The authors provide an algorithm that makes m matrix-vector queries to a normal matrix A and returns, with high probability, a measure within Earth Mover's distance O(1/m + log m / sqrt(n)) of the true spectral density of A. They also prove that any algorithm producing an eps-approximation must make Omega(1/eps) matrix-vector queries, and that this lower bound holds even when A is real symmetric. The combination shows that spectral density estimation is essentially no harder for complex normal matrices than for real symmetric matrices.

What carries the argument

The m-query algorithm that returns a probability measure approximating the uniform distribution on the eigenvalues of a normal matrix in Earth Mover's distance.

Load-bearing premise

The input matrix A must be normal and accessible only through matrix-vector product queries.

What would settle it

An explicit normal matrix together with a query algorithm that uses o(1/eps) matrix-vector products yet produces an eps-approximation in Earth Mover's distance would refute the lower bound.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • m matrix-vector queries suffice for spectral density approximation on any normal matrix of any size.
  • The dominant error term scales linearly with the number of queries, while the log m / sqrt(n) term vanishes for large n.
  • The Omega(1/eps) query lower bound applies directly to real symmetric matrices.
  • Spectral density estimation therefore has the same asymptotic query complexity for normal and symmetric inputs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same query model and distance could be used to compare other matrix access methods that also return linear combinations of eigenvectors.
  • The lower-bound construction for symmetric matrices supplies a concrete family of test cases for checking whether practical implementations meet the predicted query threshold.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper claims an algorithm that, given an n×n normal matrix A accessible only via matrix-vector products, uses m such queries to return (w.h.p.) a measure within Earth Mover's distance O(1/m + log m / √n) of the uniform distribution on the eigenvalues of A. It also proves a matching lower bound of Ω(1/ε) matrix-vector queries for any ε-approximation, which already holds for real symmetric matrices, implying that spectral density estimation is asymptotically no harder for complex normal matrices than for the symmetric case.

Significance. If the stated bounds and constructions hold, the result is significant for numerical linear algebra: it shows that the matrix-vector query complexity for spectral density estimation does not increase when moving from real symmetric to normal matrices, despite the latter having eigenvalues in the complex plane. The combination of an explicit algorithmic upper bound with an information-theoretic lower bound that is tight in the leading 1/ε term provides a clean characterization of the problem's difficulty in this model.

minor comments (2)
  1. [Abstract] Abstract, paragraph 2: the error term log m / √n is stated without an explicit regime relating m and n; a brief sentence clarifying when this term is negligible (e.g., m = o(√n)) would improve readability.
  2. The lower-bound argument is said to hold for 'large matrices'; specifying the minimal n required for the Ω(1/ε) statement would make the comparison with the upper bound fully precise.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. We appreciate the recognition that the upper and lower bounds together give a tight characterization of the matrix-vector query complexity for spectral density estimation.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central result is an explicit m-query algorithm for approximating the spectral density of a normal matrix in earth mover's distance, together with a matching Omega(1/epsilon) lower bound that already holds for real symmetric matrices. Both the upper and lower bounds are derived from standard matrix-vector query models, the spectral theorem, and information-theoretic arguments; they do not reduce to any fitted parameter, self-defined quantity, or self-citation chain inside the paper. The normality assumption is used only to place eigenvalues in the complex plane and is explicitly scoped; the query complexity is shown to be asymptotically no worse than the symmetric case. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard linear-algebra facts about normal matrices and the matrix-vector query model; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption A normal matrix satisfies A A^* = A^* A and therefore is unitarily diagonalizable.
    Invoked to define the spectral density as the uniform measure on eigenvalues.
  • domain assumption Access to the matrix is restricted to matrix-vector products.
    Defines the query model used for both upper and lower bounds.

pith-pipeline@v0.9.1-grok · 5712 in / 1209 out tokens · 25464 ms · 2026-06-28T21:13:45.679691+00:00 · methodology

0 comments
read the original abstract

The spectral density estimation problem asks for an algorithm that, given an $n\times 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/{\sqrt n})$ of the true spectral density of $A$. We provide a complementary lower bound that any algorithm producing an $\varepsilon$-approximation to the true spectral density for large matrices must make $\Omega(1/\varepsilon)$ 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.

Figures

Figures reproduced from arXiv: 2605.31430 by Cameron Musco, Christopher Musco, John Urschel, Nicholas West, Rikhav Shah.

Figure 1
Figure 1. Figure 1: Spectral density estimation for two example matrices. The leftmost column is a scatter plot of the eigenvalues of the matrices. The next columns left-to-right are the result of running Algorithm 3 for m = 16, 32, 64, and 128 respectively. The first row is with the 150,000×150,000 matrix where 100,000 eigenvalues are uniformly distributed in the disk, and 50,000 additional eigenvalues are uniformly distribu… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A non-asymptotic bound on the TV distance between a Wishart matrix and an appropriately scaled GOE matrix

    math.PR 2026-06 accept novelty 4.0

    For W ~ Wishart(n,k) and G ~ GOE(n), TV(W, √k G + k I) ≲ √(n³/k) whenever k ≳ n³.

Reference graph

Works this paper leans on

40 extracted references · 4 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Estimating the Spectral Density of Large Implicit Matrices

    Ryan Adams, Jeffrey Pennington, Matthew Johnson, Jamie Smith, Yaniv Ovadia, Brian Patton, and James Saunderson. Estimating the spectral density of large implicit matrices. arXiv:1802.03451 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  2. [2]

    Concentration and Gaussian Approximation for Randomized Sums

    Sergey Bobkov, Gennadiy Chistyakov, and Friedrich G\" o tze. Concentration and Gaussian Approximation for Randomized Sums . Springer Nature Switzerland, 2023

    2023

  3. [3]

    Testing for high-dimensional geometry in random graphs

    S \'e bastien Bubeck, Jian Ding, Ronen Eldan, and Mikl \'o s Z R \'a cz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms , 49(3), 2016

    2016

  4. [4]

    Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time

    Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava. Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time. Foundations of Computational Mathematics , 23(6):1959--2047, 2022

    1959

  5. [5]

    Operator learning without the adjoint

    Nicolas Boull \'e , Diana Halikias, Samuel E Otto, and Alex Townsend. Operator learning without the adjoint. Journal of Machine Learning Research , 25(364), 2024

    2024

  6. [6]

    Improved spectral density estimation via explicit and implicit deflation

    Rajarshi Bhattacharjee, Rajesh Jayaram, Cameron Musco, Christopher Musco, and Archan Ray. Improved spectral density estimation via explicit and implicit deflation. In 2025 , 2025

    2025

  7. [7]

    Sublinear time spectral density estimation

    Vladimir Braverman, Aditya Krishnan, and Christopher Musco. Sublinear time spectral density estimation. In 2022 , 2022

    2022

  8. [8]

    Krylov methods are (nearly) optimal for low-rank approximation

    Ainesh Bakshi and Shyam Narayanan. Krylov methods are (nearly) optimal for low-rank approximation. In 2023 , 2023

    2023

  9. [9]

    Download the datasaurus: Never trust summary statistics alone; always visualize your data

    Alberto Cairo. Download the datasaurus: Never trust summary statistics alone; always visualize your data. https://web.archive.org/web/20160901105257/http://www.thefunctionalart.com/2016/08/download-datasaurus-never-trust-summary.html, 2016

    work page arXiv 2016

  10. [10]

    Query lower bounds for log-concave sampling

    Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, and Shyam Narayanan. Query lower bounds for log-concave sampling. Journal of the ACM , 71(4), 2024

    2024

  11. [11]

    Analysis of stochastic L anczos quadrature for spectrum approximation

    Tyler Chen, Thomas Trogdon, and Shashanka Ubaru. Analysis of stochastic L anczos quadrature for spectrum approximation. In 2021 , 2021

    2021

  12. [12]

    Estimating the numerical range with a K rylov subspace

    Cecilia Chen and John Urschel. Estimating the numerical range with a K rylov subspace. arXiv:2411.19165 , 2024

    work page arXiv 2024

  13. [13]

    Unitary polynomials in normal matrix models and wave functions for the fractional quantum Hall effects

    Ling-Lie Chau and Yue Yu. Unitary polynomials in normal matrix models and wave functions for the fractional quantum Hall effects. Physics Letters A , 167(5-6), 1992

    1992

  14. [14]

    On the structure of correlation functions in the normal matrix model

    Ling-Lie Chau and Oleg Zaboronsky. On the structure of correlation functions in the normal matrix model. Communications in mathematical physics , 196(1), 1998

    1998

  15. [15]

    Derezi´ nski, E

    Michal Derezi \'n ski, Ethan N Epperly, and Raphael A Meyer. The matrix-vector complexity of Ax= b . arXiv:2602.04842 , 2026

    work page internal anchor Pith review arXiv 2026

  16. [16]

    An interpolation--regression approach for function approximation on the disk and its application to cubature formulas

    Francesco Dell'Accio, Francisco Marcell \'a n, and Federico Nudo. An interpolation--regression approach for function approximation on the disk and its application to cubature formulas. Advances in Computational Mathematics , 51(6), 2025

    2025

  17. [17]

    Imbedding conditions for Hermitian and normal matrices

    Ky Fan and Gordon Pall. Imbedding conditions for Hermitian and normal matrices. Canadian Journal of Mathematics , 9, 1957

    1957

  18. [18]

    An investigation into neural net optimization via H essian eigenvalue density

    Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via H essian eigenvalue density . In International Conference on Machine Learning , pages 2232--2241. PMLR, 2019

    2019

  19. [19]

    Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

    Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review , 53(2), 2011

    2011

  20. [20]

    On approximation by trigonometric sums and polynomials

    Dunham Jackson. On approximation by trigonometric sums and polynomials. Transactions of the American Mathematical society , 13(4), 1912

    1912

  21. [21]

    Approximation of rectangular beta- Laguerre ensembles and large deviations

    Tiefeng Jiang and Danning Li. Approximation of rectangular beta- Laguerre ensembles and large deviations. Journal of Theoretical Probability , 28(3), 2013

    2013

  22. [22]

    Lanczos method for the calculation of finite-temperature quantities in correlated systems

    Janez Jaklic and Peter Prelovsek. Lanczos method for the calculation of finite-temperature quantities in correlated systems. Physical Review B , 49(7), 1994

    1994

  23. [23]

    An iteration method for the solution of the eigenvalue problem of linear differential and integral operators

    Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards , 45(4), 1950

    1950

  24. [24]

    Approximating spectral densities of large matrices

    Lin Lin, Yousef Saad, and Chao Yang. Approximating spectral densities of large matrices. SIAM review , 58(1), 2016

    2016

  25. [25]

    The eigenvalues slicing library (EVSL) : Algorithms, implementation, and software

    Ruipeng Li, Yuanzhe Xi, Lucas Erlandson, and Yousef Saad. The eigenvalues slicing library (EVSL) : Algorithms, implementation, and software. SIAM Journal on Scientific Computing , 41(4), 2019

    2019

  26. [26]

    Same stats, different graphs: Generating datasets with varied appearance and identical statistics through simulated annealing

    Justin Matejka and George Fitzmaurice. Same stats, different graphs: Generating datasets with varied appearance and identical statistics through simulated annealing. In Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems , pages 1290--1294, 2017

    2017

  27. [27]

    Randomized block K rylov methods for stronger and faster approximate singular value decomposition

    Cameron Musco and Christopher Musco. Randomized block K rylov methods for stronger and faster approximate singular value decomposition. 2015 , 28, 2015

    2015

  28. [28]

    Meyer, Cameron Musco, Christopher Musco, and David P

    Raphael A. Meyer, Cameron Musco, Christopher Musco, and David P. Woodruff. Hutch++: Optimal stochastic trace estimation. In 2021 , 2021

    2021

  29. [29]

    Sharper bounds for C hebyshev moment matching, with applications

    Cameron Musco, Christopher Musco, Lucas Rosenblatt, and Apoorv Vikram Singh. Sharper bounds for C hebyshev moment matching, with applications. 2025 , 2025

    2025

  30. [30]

    D. J. Newman and H.S. Shapiro. Jackson's theorem in higher dimensions. In On Approximation Theory / \"U ber Approximationstheorie: Proceedings of the Conference held in the Mathematical Research Institute at Oberwolfach , pages 208--219, 1964

    1964

  31. [31]

    Raikov and Y.M

    I.O. Raikov and Y.M. Beltukov. The kernel polynomial method based on J acobi polynomials. Applied Mathematics and Computation , 490, 2025

    2025

  32. [32]

    Theodore J. Rivlin. An introduction to the approximation of functions . Courier Corporation, 1981

    1981

  33. [33]

    R \'a cz and Jacob Richey

    Mikl \'o s Z. R \'a cz and Jacob Richey. A smooth transition from Wishart to GOE . Journal of Theoretical Probability , 32(2), 2018

    2018

  34. [34]

    Combinatorial Mathematics

    Herbert Ryser. Combinatorial Mathematics . American Mathematical Society, 1963

    1963

  35. [35]

    Numerical methods for large eigenvalue problems: revised edition

    Yousef Saad. Numerical methods for large eigenvalue problems: revised edition . SIAM, 2011

    2011

  36. [36]

    Woodruff

    William Swartworth and David P. Woodruff. Optimal eigenvalue approximation via sketching. In 2023 , 2023

    2023

  37. [37]

    Aleksandr F. Timan. Theory of Approximation of Functions of a Real Variable . International Series of Monographs in Pure and Applied Mathematics. Pergamon Press, 1963

    1963

  38. [38]

    Woodruff

    David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science , 10(1-2), 2014

    2014

  39. [39]

    The kernel polynomial method

    Alexander Wei e, Gerhard Wellein, Andreas Alvermann, and Holger Fehske. The kernel polynomial method. Reviews of modern physics , 78(1), 2006

    2006

  40. [40]

    Woodruff, Fred Zhang, and Richard Zhang

    David P. Woodruff, Fred Zhang, and Richard Zhang. Optimal query complexities for dynamic trace estimation. In 2022 , 2022

    2022