pith. sign in

arxiv: 2604.06439 · v2 · pith:L7VCRMSKnew · submitted 2026-04-07 · 🧮 math.FA

Greedy sparsifications of sums of positive semidefinite matrices

Grigory Ivanov This is my paper

Pith reviewed 2026-05-22 11:09 UTC · model grok-4.3

classification 🧮 math.FA
keywords deterministic samplingpositive semidefinite matricesoperator norm approximationmatrix sparsificationRudelson theoremgreedy selection
0
0 comments X

The pith

There exists a deterministic sequence of positive semidefinite matrices whose average approximates the identity with error at most 3 sqrt(M ln(2d)/k) for large k.

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

The paper establishes that for positive semidefinite matrices whose convex combination equals the identity, with each having operator norm at most M, a deterministic sequence of selections exists such that the running average stays close to the identity in operator norm. The error bound is piecewise: linear decay for small k and square-root decay for larger k. This matters because it replaces random sampling with an explicit construction that works for every prefix of the sequence, giving a reliable way to sparsify matrix sums without probability.

Core claim

Under the conditions that the lambda_i are non-negative numbers summing to 1, the weighted sum of A_i equals the d by d identity, and each A_i has operator norm at most M, there exists a deterministic sequence of indices i_r such that for every k the operator norm of (1/k sum first k A_ir minus identity) is at most 2M ln(2d)/k when k is small and 3 sqrt(M ln(2d)/k) when k is larger. This implies that with N at least 9M ln(2d) / eps^2 one can achieve error at most eps.

What carries the argument

The deterministic sequence of indices chosen so that the running average stays within the stated operator norm bound of the identity.

If this is right

  • With N at least 9M ln(2d) eps^{-2} selections the average is within eps of the identity in operator norm.
  • The bound applies uniformly for every k, giving the full rate of convergence.
  • The construction yields a deterministic sparsifier with O(M ln d / eps^2) terms.
  • The result holds for any dimension d and any finite collection of such matrices.

Where Pith is reading between the lines

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

  • The construction may admit an efficient greedy algorithm to compute the sequence in practice.
  • Similar deterministic bounds could apply to other matrix ensembles or to Schatten norms.
  • The explicit constants allow direct comparison with random sampling rates in applications.

Load-bearing premise

The matrices are positive semidefinite, their convex combination with weights summing to one equals the identity, and they are uniformly bounded in operator norm by M.

What would settle it

A specific collection of matrices satisfying the weight and bound conditions where for some k the minimal possible deviation of any average of k matrices exceeds the given bound.

read the original abstract

We prove a deterministic analogue of Rudelson's sampling theorem for sums of positive semidefinite matrices. Let $A_1,\dots,A_m$ be positive semidefinite \(d\times d\) matrices, and let $\lambda_1,\dots,\lambda_m \ge 0$ satisfy \[ \sum_{i=1}^m \lambda_i = 1, \qquad \sum_{i=1}^m \lambda_i A_i = I_d, \qquad \|A_i\| \le M \quad\text{for all } i=1,\dots,m. \] We show that there exists a deterministic sequence of indices $i_1,i_2,\dots \in \{1,\dots,m\}$ such that for every integer $k \ge 1$, \[ \left\| \frac{1}{k}\sum_{r=1}^k A_{i_r} - I_d \right\| \le \begin{cases} \displaystyle \frac{2M\ln(2d)}{k}, & \text{if } k \le M\ln(2d),\\[2ex] \displaystyle 3\sqrt{\frac{M\ln(2d)}{k}}, & \text{if } k > M\ln(2d). \end{cases} \] In particular, if $0<\varepsilon\le 1$ and $N \ge 9M\ln(2d)\varepsilon^{-2}$, then one can choose indices $i_1,\dots,i_N \in \{1,\dots,m\}$ such that \[ \left\| \frac{1}{N}\sum_{r=1}^N A_{i_r} - I_d \right\| \le \varepsilon. \]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves a deterministic analogue of Rudelson's sampling theorem for sums of positive semidefinite matrices. It shows that under the assumptions sum λ_i =1, sum λ_i A_i = I_d, and ||A_i|| ≤ M, there exists a sequence of indices i1, i2, ... such that the operator norm of the average minus I_d is bounded by 2M ln(2d)/k if k ≤ M ln(2d), and 3 sqrt(M ln(2d)/k) otherwise. Consequently, N ≥ 9M ln(2d) ε^{-2} suffices for an ε-approximation in operator norm.

Significance. This result is significant for providing a fully deterministic and constructive method for sparsifying or sampling from a convex combination of PSD matrices to approximate the identity. The potential function approach, based on the trace of a matrix exponential with two temperature regimes, allows for a clean proof with explicit constants derived from standard integral estimates and union bounds. This strengthens the literature on derandomized algorithms in linear algebra.

minor comments (2)
  1. [Abstract] Abstract: the motivation for switching regimes at k = M ln(2d) and the origin of the constant 9 in the sample complexity bound could be noted briefly for readers.
  2. [Section 3] Section 3 (proof): the exact definition of the potential function Φ and the two temperature parameters should be stated before the decrease analysis to improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and for recommending minor revision. The referee's summary correctly describes the main theorem and its consequences for deterministic sparsification of PSD matrix sums.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a direct existence proof for the sequence via a potential-function argument that maintains an invariant on a matrix-exponential or softmax-based quantity. At each step the choice of index is shown to exist by averaging the given weights lambda_i against the hypothesis sum lambda_i A_i = I_d and the bound ||A_i|| <= M; the piecewise rate follows from running the same potential at two temperatures and standard integral/union-bound estimates on the eigenvalues. No equation reduces to a fitted parameter, no self-citation is load-bearing, and the derivation is self-contained under the stated hypotheses without importing uniqueness or ansatzes from prior work by the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard linear-algebra facts about positive-semidefinite matrices, operator norms, and convex combinations; no free parameters, ad-hoc axioms, or new entities are introduced in the given statement.

axioms (1)
  • standard math Basic properties of positive semidefinite matrices, operator norm, and convex combinations of matrices
    Invoked in the theorem hypothesis to define the weighted sum equaling the identity.

pith-pipeline@v0.9.0 · 5846 in / 1253 out tokens · 51017 ms · 2026-05-22T11:09:34.871095+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Asymptotic geometric analysis, P art I I , volume 261

    Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D Milman. Asymptotic geometric analysis, P art I I , volume 261. American Mathematical Society, 2021

    work page 2021

  2. [2]

    Quantitative H elly-type theorems via sparse approximation

    V \' ctor Hugo Almendra-Hern \'a ndez, Gergely Ambrus, and Matthew Kendall. Quantitative H elly-type theorems via sparse approximation. Discrete & Computational Geometry , pages 1--8, 2022

    work page 2022

  3. [3]

    Spielman, and Nikhil Srivastava

    Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice- R amanujan sparsifiers. SIAM Rev. , 56(2):315--334, 2014

    work page 2014

  4. [4]

    Sparse sums of positive semidefinite matrices

    Marcel Kenji de Carli Silva, Nicholas JA Harvey, and Cristiane M Sato. Sparse sums of positive semidefinite matrices. ACM Trans. Algorithms , 12(1):9--1, 2016

    work page 2016

  5. [5]

    Integral norm discretization and related problems

    Feng Dai, Andriy Prymak, Vladimir Nikolaevich Temlyakov, and S Yu Tikhonov. Integral norm discretization and related problems. Russian Mathematical Surveys , 74(4):579--630, 2019

    work page 2019

  6. [6]

    Dvoretzky and C

    A. Dvoretzky and C. A. Rogers. Absolute and unconditional convergence in normed linear spaces. Proceedings of the National Academy of Sciences , 36(3):192--197, March 1950

    work page 1950

  7. [7]

    Approximating matrices and convex bodies

    Omer Friedland and Pierre Youssef. Approximating matrices and convex bodies. International Mathematics Research Notices , 2019(8):2519--2537, September 2017

    work page 2019

  8. [8]

    A quantitative H elly-type theorem: containment in a homothet

    Grigory Ivanov and M \'a rton Nasz \'o di. A quantitative H elly-type theorem: containment in a homothet. SIAM Journal on Discrete Mathematics , 36(2):951--957, 2022

    work page 2022

  9. [9]

    Quantitative S teinitz theorem: A polynomial bound

    Grigory Ivanov and Márton Naszódi. Quantitative S teinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society , 56(2):796--802, 2024

    work page 2024

  10. [10]

    Approximation of the average of some random matrices

    Grigory Ivanov, Márton Naszódi, and Alexandr Polyanskii. Approximation of the average of some random matrices. Journal of Functional Analysis , 279(7):108684, 2020

    work page 2020

  11. [11]

    Approximate C arath \'e odory’s theorem in uniformly smooth B anach spaces

    Grigory Ivanov. Approximate C arath \'e odory’s theorem in uniformly smooth B anach spaces. Discrete & Computational Geometry , 66(1):273--280, 2021

    work page 2021

  12. [12]

    No-dimensional results of combinatorial convexity

    Grigory Ivanov. No-dimensional results of combinatorial convexity. D imension strikes back. arXiv preprint arXiv:2602.20035, 2026

    work page arXiv 2026

  13. [13]

    Sampling discretization and related problems

    Boris Kashin, Egor Kosov, Irina Limonova, and Vladimir Temlyakov. Sampling discretization and related problems. Journal of Complexity , 71:101653, 2022

    work page 2022

  14. [14]

    In\' e galit\' e s de K hintchine dans C_p\;(1<p< )

    Fran c oise Lust-Piquard. In\' e galit\' e s de K hintchine dans C_p\;(1<p< ) . C. R. Acad. Sci. Paris S\' e r. I Math. , 303(7):289--292, 1986

    work page 1986

  15. [15]

    Noncommutative K hintchine and P aley inequalities

    Fran c oise Lust-Piquard and Gilles Pisier. Noncommutative K hintchine and P aley inequalities. Ark. Mat. , 29(2):241--260, 1991

    work page 1991

  16. [16]

    Interlacing families II : M ixed characteristic polynomials and the K adison-- S inger problem

    Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Interlacing families II : M ixed characteristic polynomials and the K adison-- S inger problem. Annals of Mathematics , pages 327--350, July 2015

    work page 2015

  17. [17]

    Proof of a conjecture of B \'a r \'a ny, K atchalski and P ach

    M \'a rton Nasz \'o di. Proof of a conjecture of B \'a r \'a ny, K atchalski and P ach. Discrete & Computational Geometry , 55(1):243--248, 2016

    work page 2016

  18. [18]

    Sums of random hermitian matrices and an inequality by rudelson

    Roberto Oliveira. Sums of random hermitian matrices and an inequality by rudelson. Electronic Communications in Probability , 15, 04 2010

    work page 2010

  19. [19]

    Maurey-Schwartz

    Gilles Pisier. Remarques sur un r \'e sultat non publi \'e de B . M aurey. S \'e minaire Analyse fonctionnelle (dit" Maurey-Schwartz") , pages 1--12, 1980

    work page 1980

  20. [20]

    Linear size sparsifier and the geometry of the operator norm ball

    Victor Reis and Thomas Rothvoss. Linear size sparsifier and the geometry of the operator norm ball. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2337--2348. SIAM, 2020

    work page 2020

  21. [21]

    Random vectors in the isotropic position

    Mark Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis , 164(1):60--72, 1999

    work page 1999

  22. [22]

    Thompson

    Colin J. Thompson. Inequality with applications in statistical mechanics. Journal of Mathematical Physics , 6(11):1812--1813, 1965

    work page 1965

  23. [23]

    Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and trends in machine learning , 8(1-2):1--230, 2015

    work page 2015

  24. [24]

    High-dimensional probability: An introduction with applications in data science , volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science , volume 47. Cambridge university press, 2018

    work page 2018