Pith. sign in

REVIEW 2 minor 1 cited by

Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products

T0 review · 0 major / 2 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read The query complexity for near-optimal sparse approximation of an implicit matrix is governed exactly by the degeneracy of the target sparsity pattern.

desk verdict Degeneracy of the sparsity pattern gives nearly tight matvec query bounds for sparse approximation that unify prior measures and run in polynomial time. read the letter →

arxiv 2606.12179 v1 pith:SY7QLMOH submitted 2026-06-10 cs.DS cs.NAmath.NA

Christoper Musco , Indu Ramesh This is my paper · ORCID
classification cs.DScs.NAmath.NA
keywords sparsematrixapproximationmatrix-vectorqueriesdegeneracyquerycomplexitysparsitypatternimplicitmatricesgraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper shows that for any fixed sparsity pattern S, a near-optimal approximation to an unknown matrix A can be recovered using a number of matrix-vector product queries that is linear in the degeneracy of S, both from above and below. Degeneracy is obtained by repeatedly removing all rows and columns that contain at most k ones until the matrix is empty; the minimal such k is the degeneracy. This single parameter unifies and tightens earlier incomparable bounds that depended on total nonzeros, maximum degree, or chromatic number of a conflict graph, while also guaranteeing polynomial running time.

What carries the argument

The degeneracy degen(S), defined as the smallest integer k such that iteratively deleting every row and column containing at most k ones eventually empties the matrix.

What would settle it

An explicit sparsity pattern S together with a matrix A for which the minimal number of queries needed to achieve near-optimal approximation with support S deviates by more than a constant factor from degen(S).

Watch

Extended reading notes

Core claim

For every sparsity pattern S, Õ(degen(S)) matrix-vector queries are sufficient and Ω(degen(S)) queries are necessary to produce a near-optimal approximation to any matrix A using exactly the support of S; the algorithms achieving the upper bound run in polynomial time.

Load-bearing premise

That the combinatorial structure of the sparsity pattern alone determines how many matrix-vector queries are required, independently of the numerical values inside the matrix.

Editorial extensions

If this is right

  • Any prior algorithm whose complexity was expressed in terms of total nonzeros, maximum row/column sparsity, or conflict-graph coloring is now subsumed by the degeneracy bound.
  • Polynomial-time procedures replace the graph-coloring routines used in earlier work.
  • The same degeneracy parameter yields matching upper and lower bounds for every possible sparsity pattern, including diagonal, banded, and arrowhead forms.
  • The result holds uniformly for every matrix A, so the query count can be decided from S alone before any queries are made.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Degeneracy may serve as a practical design criterion when choosing which sparsity pattern to request from a black-box linear operator.
  • The same iterative deletion process could be applied to other query models, such as entrywise or row/column access, to obtain analogous tight bounds.
  • For patterns whose degeneracy is small, the new algorithms immediately give practical query-efficient sketches that earlier methods could not guarantee in polynomial time.
Share X Bluesky LinkedIn Reddit HN

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 studies the problem of learning a near-optimal approximation to an implicit matrix A (accessible only via matvec queries) with a prescribed sparsity pattern S. It defines the degeneracy degen(S) by iteratively deleting rows and columns with at most k ones until the matrix is empty, and claims that Õ(degen(S)) matvec queries suffice to produce a near-optimal S-sparse approximation while Ω(degen(S)) queries are necessary for any S. All algorithms are stated to run in polynomial time, unifying and tightening prior incomparable bounds based on the number of nonzeros, maximum row/column sparsity, or chromatic number of the conflict graph.

Significance. If the claims hold, the result is significant because it supplies a tight, instance-independent characterization of matvec query complexity for sparse approximation that depends only on a natural combinatorial parameter of S. It generalizes the standard graph degeneracy notion to the bipartite setting of the sparsity pattern, removes the need for graph coloring, and guarantees polynomial-time algorithms. The paper explicitly credits the tight upper and lower bounds together with the polynomial-time guarantee as the main technical contributions.

minor comments (2)
  1. [Abstract] Abstract: the claim that 'all of our methods run in polynomial time' would be strengthened by a brief parenthetical reference to the theorem or section establishing the degree of the polynomial.
  2. [Introduction] The definition of degen(S) is given only informally in the abstract; a formal inductive definition with a small example matrix would improve readability in the introduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. No major comments were provided in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper defines degen(S) independently via an iterative deletion process on the binary sparsity pattern S (generalizing graph degeneracy), then proves that matvec query complexity for near-optimal S-sparse approximation is tightly bounded by Θ(degen(S)) using polynomial-time algorithms. No step reduces a claimed prediction or result to a fitted parameter, self-referential definition, or load-bearing self-citation; the lower bound follows from the combinatorial definition of degen(S) itself, and the upper bound is established via explicit algorithmic constructions. The derivation is self-contained against external graph-theoretic benchmarks with no reduction to inputs by construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Abstract-only review; the setup relies on standard linear algebra but no free parameters, ad-hoc axioms, or invented entities are visible.

assumptions (1)
  • standard math Basic properties of matrix-vector product queries and binary sparsity patterns.
    The problem is posed in standard real linear algebra with matvec access.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products." pith.science (2026). https://pith.science/paper/SY7QLMOH

@misc{pith2026260612179,
  author       = {Pith},
  title        = {Pith review of: Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SY7QLMOH}},
  note         = {Machine review of arXiv:2606.12179}
}
abstract

A large body of work studies the problem of learning an approximation to an implicit matrix $A\in \mathbb{R}^{m\times n}$ that is only accessible implicitly via matrix-vector product queries (matvec queries) of the form ${x} \rightarrow {A}{x}$ or ${x} \rightarrow {A}^T{x}$. Of particular interest are methods that learn a near-optimal approximation with a fixed sparsity pattern. For example, we might want to learn a near-optimal diagonal, banded, or arrow-head approximation to an implicit matrix $A$. Naturally, the number of matvec queries required to solve this problem depends on the sparsity pattern, which can be encoded as a binary matrix ${S}\in \{0,1\}^{m\times n}$. The query complexity of previous algorithms scales with quantities like the total number of ones in ${S}$, its maximum column/row sparsity, or the chromatic number of a its "conflict graph". These quantities are incomparable: for a given ${S}$, parameterizing by one might yield lower query complexity than another. In this work, we unify and tighten these prior results by providing a nearly sharp characterization of the matvec query complexity of sparse matrix approximation. Generalizing a definition from graph algorithms, let the degeneracy, ${degen}({S})$, denote the smallest number $k$ so that, if we iteratively delete all rows and columns of ${S}$ with $\leq k$ ones, we are left with an empty matrix. We show that a near-optimal approximation to $A$ with sparsity pattern $S$ can be learned with $\tilde{O}({degen}({S}))$ matrix-vector product queries, and $\Omega({degen}({S}))$ queries are necessary, for any sparsity pattern ${S}$. Moreover, unlike prior work based on graph coloring, all of our methods run in polynomial time.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. A recursive butterfly factorization with optimality guarantees

    math.NA 2026-07 conditional novelty 7.0 of 10

    A recursive butterfly representation leads to entry-access and matrix-free butterfly approximations with provably near-optimal error guarantees.

Reference graph

Works this paper leans on

60 extracted references · cited by 1 Pith paper

  1. [1]

    and Beck, Leland L

    Matula, David W. and Beck, Leland L. , date-added =. Smallest-last ordering and clustering and graph coloring algorithms , volume =. J. ACM , number =

  2. [2]

    Eigenvalues and Condition Numbers of Random Matrices , volume =

    Edelman, Alan , date-added =. Eigenvalues and Condition Numbers of Random Matrices , volume =. SIAM Journal on Matrix Analysis and Applications , number =

  3. [3]

    The matrix-vector complexity of

    Micha. The matrix-vector complexity of

  4. [4]

    Sharper Bounds for Chebyshev Moment Matching, with Applications , year =

    Cameron Musco and Christopher Musco and Lucas Rosenblatt and Apoorv Vikram Singh , booktitle =. Sharper Bounds for Chebyshev Moment Matching, with Applications , year =

  5. [5]

    Woodruff and Guang Yang and Jialin Zhang , booktitle =

    Xiaoming Sun and David P. Woodruff and Guang Yang and Jialin Zhang , booktitle =. Querying a Matrix Through Matrix-Vector Products , year =

  6. [6]

    Query lower bounds for log-concave sampling , volume =

    Chewi, Sinho and de Dios Pont, Jaume and Li, Jerry and Lu, Chen and Narayanan, Shyam , date-added =. Query lower bounds for log-concave sampling , volume =. Journal of the ACM , number =

  7. [7]

    Analysis of stochastic

    Tyler Chen and Thomas Trogdon and Shashanka Ubaru , booktitle =. Analysis of stochastic

  8. [8]

    Meyer and Cameron Musco and Christopher Musco and David Woodruff , booktitle =

    Raphael A. Meyer and Cameron Musco and Christopher Musco and David Woodruff , booktitle =

Show all 60 references
  1. [9]

    Meyer and William Swartworth and David Woodruff , booktitle =

    Raphael A. Meyer and William Swartworth and David Woodruff , booktitle =. Understanding the

  2. [10]

    Optimal Query Complexities for Dynamic Trace Estimation , year =

    Woodruff, David and Zhang, Fred and Zhang, Richard , booktitle =. Optimal Query Complexities for Dynamic Trace Estimation , year =

  3. [11]

    Tight query complexity lower bounds for

    Simchowitz, Max and El Alaoui, Ahmed and Recht, Benjamin , booktitle =. Tight query complexity lower bounds for

  4. [12]

    The Gradient Complexity of Linear Regression , year =

    Mark Braverman and Elad Hazan and Max Simchowitz and Blake Woodworth , booktitle =. The Gradient Complexity of Linear Regression , year =

  5. [13]

    Sublinear Time Spectral Density Estimation , year =

    Vladimir Braverman and Aditya Krishnan and Christopher Musco , booktitle =. Sublinear Time Spectral Density Estimation , year =

  6. [14]

    and Thilikos, Dimitris M

    Kirousis, Lefteris M. and Thilikos, Dimitris M. , date-added =. The Linkage of a Graph , volume =. SIAM J. Comput. , number =

  7. [15]

    On chromatic number of graphs and set-systems , volume =

    Erd. On chromatic number of graphs and set-systems , volume =. Acta Mathematica Academiae Scientiarum Hungarica , number =

  8. [16]

    Powell, M. J. D. and Toint, Ph. L. , date-added =. On the Estimation of Sparse Hessian Matrices , volume =. SIAM Journal on Numerical Analysis , number =

  9. [17]

    Goldfarb and Ph

    D. Goldfarb and Ph. L. Toint , date-added =. Optimal Estimation of. Mathematics of Computation , number =

  10. [18]

    Thomas , date-added =

    Mccormick, S. Thomas , date-added =. Optimal approximation of sparse. Math. Program. , number =

  11. [19]

    ACM Trans

    Villa, Umberto and Petra, Noemi and Ghattas, Omar , date-added =. ACM Trans. Math. Softw. , number =. 2021 , bdsk-url-1 =

    2021

  12. [20]

    The Elements of Differentiable Programming , year =

    Mathieu Blondel and Vincent Roulet , date-added =. The Elements of Differentiable Programming , year =

  13. [21]

    Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions , volume =

    Frommer, Andreas and Schimmel, Claudia and Schweitzer, Marcel , date-added =. Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions , volume =. SIAM Journal on Matrix Analysis and Applications , number =

  14. [22]

    and Saad, Yousef , date-added =

    Tang, Jok M. and Saad, Yousef , date-added =. A probing method for computing the diagonal of a matrix inverse , volume =. Numerical Linear Algebra with Applications , number =

  15. [23]

    Eriksson, David and Dong, Kun and Lee, Eric and Bindel, David and Wilson, Andrew G , booktitle =. Scaling

  16. [24]

    Aster and Brian Borchers and Clifford H

    Richard C. Aster and Brian Borchers and Clifford H. Thurber , date-added =. Parameter estimation and inverse problems , year =

  17. [25]

    Full waveform inversion and the truncated Newton method: quantitative imaging of complex subsurface structures , volume =

    M. Full waveform inversion and the truncated Newton method: quantitative imaging of complex subsurface structures , volume =. Geophysical Prospecting , number =

  18. [26]

    , date-added =

    Dasarathy, Gautam and Shah, Parikshit and Bhaskar, Badri Narayan and Nowak, Robert D. , date-added =. Sketching Sparse Matrices, Covariances, and Graphs via Tensor Products , volume =. IEEE Transactions on Information Theory , number =

  19. [27]

    , date-added =

    Pearlmutter, Barak A. , date-added =. Fast exact multiplication by the. Neural computation , number =

  20. [28]

    and Vries, Harm de and Bengio, Yoshua , booktitle =

    Dauphin, Yann N. and Vries, Harm de and Bengio, Yoshua , booktitle =. Equilibrated adaptive learning rates for non-convex optimization , year =

  21. [29]

    Yao, Zhewei and Gholami, Amir and Shen, Sheng and Keutzer, Kurt and Mahoney, Michael W , booktitle =

  22. [30]

    Randomized Block

    Musco, Cameron and Musco, Christopher , booktitle =. Randomized Block

  23. [31]

    Communications in Mathematical Sciences , number =

    Lin Lin and Jianfeng Lu and Lexing Ying and Roberto Car and Weinan E , date-added =. Communications in Mathematical Sciences , number =

  24. [32]

    Fast construction of hierarchical matrix representation from matrix--vector multiplication , volume =

    Lin, Lin and Lu, Jianfeng and Ying, Lexing , date-added =. Fast construction of hierarchical matrix representation from matrix--vector multiplication , volume =. Journal of Computational Physics , number =

  25. [33]

    Butterfly Factorization Via Randomized Matrix-Vector Multiplications , volume =

    Liu, Yang and Xing, Xin and Guo, Han and Michielssen, Eric and Ghysels, Pieter and Li, Xiaoye Sherry , date-added =. Butterfly Factorization Via Randomized Matrix-Vector Multiplications , volume =. SIAM Journal on Scientific Computing , number =

  26. [34]

    Pearce and Anna Yesypenko and James Levitt and Per-Gunnar Martinsson , date-added =

    Katherine J. Pearce and Anna Yesypenko and James Levitt and Per-Gunnar Martinsson , date-added =. Randomized Rank-Structured Matrix Compression by Tagging , year =

  27. [35]

    Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices , volume =

    Levitt, James and Martinsson, Per-Gunnar , date-added =. Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices , volume =. SIAM Journal on Scientific Computing , number =

  28. [36]

    Journal of Computational and Applied Mathematics , title =

    Levitt, James and Martinsson, Per-Gunnar , date-added =. Journal of Computational and Applied Mathematics , title =

  29. [37]

    and Woodruff, David P

    Clarkson, Kenneth L. and Woodruff, David P. , booktitle =. Numerical linear algebra in the streaming model , year =

  30. [38]

    and Woodruff, David P

    Bakshi, Ainesh and Clarkson, Kenneth L. and Woodruff, David P. , booktitle =. Low-Rank Approximation with 1/ ^

  31. [39]

    Krylov Methods are (nearly) Optimal for Low-Rank Approximation , year =

    Bakshi, Ainesh and Narayanan, Shyam , booktitle =. Krylov Methods are (nearly) Optimal for Low-Rank Approximation , year =

  32. [40]

    A Tight Analysis of Hutchinson's Diagonal Estimator , year =

    Prathamesh Dharangutte and Christopher Musco , booktitle =. A Tight Analysis of Hutchinson's Diagonal Estimator , year =

  33. [41]

    Query Efficient Structured Matrix Learning , year =

    Noah Amsel and Pratyush Avi and Tyler Chen and Feyza Duman Keles and Chinmay Hegde and Cameron Musco and Christopher Musco and David Persson , booktitle =. Query Efficient Structured Matrix Learning , year =

  34. [42]

    Curtis, A. R. and Powell, M. J. D. and Reid, J. K. , date-added =. On the Estimation of Sparse. IMA Journal of Applied Mathematics , number =. 1974 , bdsk-url-1 =

    1974

  35. [43]

    and Cai, Jin-Yi , date-added =

    Coleman, Thomas F. and Cai, Jin-Yi , date-added =. The Cyclic Coloring Problem and Estimation of Sparse. SIAM Journal on Algebraic Discrete Methods , number =

  36. [44]

    Coleman, Thomas F. and Mor. Estimation of Sparse. SIAM Journal on Numerical Analysis , number =

  37. [45]

    Baston and Yuji Nakatsukasa , date-added =

    Robert A. Baston and Yuji Nakatsukasa , date-added =. Stochastic diagonal estimation: probabilistic bounds and an improved algorithm , year =

  38. [46]

    and Kokiopoulou, E

    Bekas, C. and Kokiopoulou, E. and Saad, Y. , date-added =. An estimator for the diagonal of a matrix , volume =. Applied Numerical Mathematics , number =

  39. [47]

    Structured Semidefinite Programming for Recovering Structured Preconditioners , year =

    Arun Jambulapati and Jerry Li and Christopher Musco and Aaron Sidford and Kevin Tian , booktitle =. Structured Semidefinite Programming for Recovering Structured Preconditioners , year =

  40. [48]

    Sparse Cholesky Factorization by Kullback--Leibler Minimization , volume =

    Sch\". Sparse Cholesky Factorization by Kullback--Leibler Minimization , volume =. SIAM Journal on Scientific Computing , number =

  41. [49]

    Sparse Recovery of Elliptic Solvers from Matrix-Vector Products , volume =

    Sch\". Sparse Recovery of Elliptic Solvers from Matrix-Vector Products , volume =. SIAM Journal on Scientific Computing , number =

  42. [50]

    and Kovachki, Nikola B

    de Hoop, Maarten V. and Kovachki, Nikola B. and Nelsen, Nicholas H. and Stuart, Andrew M. , date-added =. Convergence Rates for Learning Linear Operators from Noisy Data , volume =. SIAM/ASA Journal on Uncertainty Quantification , number =

  43. [51]

    Learning Elliptic Partial Differential Equations with Randomized Linear Algebra , volume =

    Boull. Learning Elliptic Partial Differential Equations with Randomized Linear Algebra , volume =. Foundations of Computational Mathematics , number =

  44. [52]

    SIAM Journal on Matrix Analysis and Applications , title =

    Noah Amsel and Tyler Chen and Feyza Duman Keles and Diana Halikias and Cameron Musco and Christopher Musco and David Persson , date-added =. SIAM Journal on Matrix Analysis and Applications , title =

  45. [53]

    Operator learning without the adjoint , volume =

    Nicolas Boull. Operator learning without the adjoint , volume =. Journal of Machine Learning Research , number =

  46. [54]

    Elliptic

    Boull. Elliptic. Proceedings of the National Academy of Sciences , number =

  47. [55]

    Near-optimal hierarchical matrix approximation from matrix-vector products , year =

    Tyler Chen and Feyza Duman Keles and Diana Halikias and Cameron Musco and Christopher Musco and David Persson , booktitle =. Near-optimal hierarchical matrix approximation from matrix-vector products , year =

  48. [56]

    Structured matrix recovery from matrix‐vector products , volume =

    Halikias, Diana and Townsend, Alex , date-added =. Structured matrix recovery from matrix‐vector products , volume =. Numerical Linear Algebra with Applications , number =

  49. [57]

    D. R. Lick and A. T. White , date-modified =. k-Degenerate Graphs , volume =. Canadian Journal of Mathematics , pages =

  50. [58]

    Coloring, register allocation,

    David Eppstein , date-modified =. Coloring, register allocation,

  51. [59]

    and Martinsson, P

    Halko, N. and Martinsson, P. G. and Tropp, J. A. , date-modified =. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions , volume =. SIAM Review , number =

  52. [60]

    SIAM Journal on Matrix Analysis and Applications , title =

    Noah Amsel and Tyler Chen and Feyza Duman Keles and Diana Halikias and Cameron Musco and Christopher Musco , date-modified =. SIAM Journal on Matrix Analysis and Applications , title =

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.