pith. sign in

arxiv: 2606.28147 · v1 · pith:6O2HXGFEnew · submitted 2026-06-26 · 🧮 math.MG · cs.DM

Linear-size ell₁ sparsifiers

Victor Reis , Thomas Rothvoss This is my paper

Pith reviewed 2026-06-29 01:39 UTC · model grok-4.3

classification 🧮 math.MG cs.DM
keywords l1 sparsifiersmatrix sparsificationzonotopesnorm preservationdiagonal reweightinglinear sizeapproximation
0
0 comments X

The pith

Any matrix A admits a diagonal ℓ1 sparsifier D with O(n/ε² log(1/ε)) nonzeros that (1±ε)-preserves ||Ax||1 for all x.

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

The paper proves existence of a diagonal reweighting matrix D with only linearly many nonzeros in the column dimension n that approximates the ℓ1 norm of every linear image Ax to relative error ε. This replaces an earlier bound that carried an extra log n factor with one whose only extra logarithmic term depends on the approximation quality 1/ε. A reader cares because the construction immediately yields linear-size zonotope approximations and removes a dimension-dependent overhead that had persisted since 1990. The guarantee holds uniformly over the whole space of directions x.

Core claim

For any matrix A ∈ R^{m×n} and ε ∈ (0,1/2], there exists a nonnegative diagonal matrix D with at most O(n/ε² log(1/ε)) nonzero entries satisfying (1−ε)∥Ax∥1 ≤ ∥DAx∥1 ≤ (1+ε)∥Ax∥1 for every x ∈ R^n. Equivalently, every zonotope generated by m segments in R^n can be sandwiched between two zonotopes each generated by O(n/ε² log(1/ε)) segments.

What carries the argument

A sparse nonnegative diagonal matrix D whose nonzero entries reweight a linear number of rows of A to preserve the ℓ1 norm uniformly over all directions.

If this is right

  • Every zonotope in R^n admits a (1±ε)-sandwiching zonotope generated by O(n/ε² log(1/ε)) segments.
  • The long-standing O(n/ε² log n) row bound for ℓ1 sparsifiers is improved by substituting log(1/ε) for log n.
  • The same size bound holds for every matrix without further dependence on the number of rows m.
  • The sparsifier works simultaneously for the entire unit sphere in the ℓ1 sense.

Where Pith is reading between the lines

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

  • The construction may yield faster preprocessing routines for ℓ1-based linear programs or geometric queries whose running time scales with the number of rows.
  • Analogous linear-size sparsifiers could exist for other norms once the right selection mechanism is identified.
  • The disappearance of the log n term suggests that earlier proofs carried an avoidable dimension-dependent overhead rather than an intrinsic barrier.
  • Discrepancy or sampling algorithms that rely on row selection might inherit the improved size bound.

Load-bearing premise

It is possible to pick which rows to keep and what weights to assign so that the (1±ε) bound holds for every direction without an extra logarithmic factor in the ambient dimension n.

What would settle it

An explicit matrix A and ε>0 for which every diagonal D with fewer than c n/ε² log(1/ε) nonzeros (some fixed c>0) violates the (1±ε) inequality for at least one vector x.

read the original abstract

We prove that for any matrix $A \in \mathbb{R}^{m \times n}$ and any $\varepsilon \in (0, 1/2]$ there is a diagonal matrix $D \in \mathbb{R}_{\geq 0}^{m \times m}$ with at most $O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))$ nonzero entries so that \[(1-\varepsilon) \|Ax\|_1 \leq \|DAx\|_1 \leq (1+\varepsilon)\|Ax\|_1 \quad \forall x \in \mathbb{R}^n.\]In particular, for any zonotope $Z \subseteq \mathbb{R}^{n}$ there exists a zonotope $Z' \subseteq \mathbb{R}^{n}$ generated by at most $O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))$ segments so that $(1-\varepsilon) Z \subseteq Z' \subseteq (1+\varepsilon) Z$. Previously, the best known bound was $O(\frac{n}{\varepsilon^2} \log n)$ due to Talagrand (1990).

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 / 3 minor

Summary. The paper proves that for any matrix A ∈ R^{m×n} and ε ∈ (0,1/2], there exists a nonnegative diagonal matrix D with at most O(n/ε² log(1/ε)) nonzero entries satisfying (1−ε)‖Ax‖₁ ≤ ‖DAx‖₁ ≤ (1+ε)‖Ax‖₁ for all x ∈ R^n. This improves Talagrand's 1990 bound of O(n/ε² log n). The result is also phrased in terms of approximating any zonotope Z by a zonotope Z' generated by O(n/ε² log(1/ε)) segments with (1−ε)Z ⊆ Z' ⊆ (1+ε)Z.

Significance. If the proof is correct, the result removes the ambient-dimension dependence from the logarithmic term in ℓ₁-sparsifier size, which is a concrete advance over the prior state of the art. The manuscript supplies a parameter-free existence statement whose central claim is an improvement on a classical result in geometric functional analysis.

minor comments (3)
  1. [Theorem statement] The statement of the main theorem (presumably Theorem 1.1 or equivalent) should explicitly record whether the hidden constant in the O-notation depends on ε or is absolute.
  2. [Introduction] The introduction should clarify the precise relationship between the matrix sparsifier and the zonotope statement; a short paragraph deriving one from the other would help readers.
  3. Notation for the support size of D is used without a dedicated symbol; introducing s(D) or similar would improve readability when the size bound is invoked repeatedly.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main result, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is a self-contained mathematical existence proof establishing an improved bound on the size of ℓ1 sparsifiers for any matrix A, reducing the log n factor from Talagrand (1990) to log(1/ε). No load-bearing steps reduce by construction to fitted inputs, self-definitions, or self-citation chains; the result is derived via direct probabilistic or combinatorial arguments on the unit sphere without renaming known patterns or smuggling ansatzes. The central claim remains an independent theorem whose soundness rests on external verification rather than internal redefinition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract presents a pure existence theorem in linear algebra without introducing new parameters, entities, or non-standard axioms.

axioms (1)
  • standard math The vector space is over the real numbers with the standard l1 norm.
    The statement is formulated for real matrices and the l1 norm.

pith-pipeline@v0.9.1-grok · 5730 in / 1358 out tokens · 82614 ms · 2026-06-29T01:39:28.175214+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

34 extracted references · 19 canonical work pages

  1. [1]

    Figiel and J

    T. Figiel and J. Lindenstrauss and V. D. Milman , title =. Acta Mathematica , volume =. 1977 , doi =

    1977

  2. [2]

    Lee and Yang P

    Arun Jambulapati and James R. Lee and Yang P. Liu and Aaron Sidford , title =. Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =. 2023 , publisher =

    2023

  3. [3]

    Lee and Yang P

    Arun Jambulapati and James R. Lee and Yang P. Liu and Aaron Sidford , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2024 , publisher =

    2024

  4. [4]

    Proceedings of the Thirty-First Annual

    Victor Reis and Thomas Rothvoss , title =. Proceedings of the Thirty-First Annual. 2020 , pages =. doi:10.1137/1.9781611975994.143 , url =

    work page doi:10.1137/1.9781611975994.143 2020

  5. [5]

    Proceedings of the 2024 Symposium on Simplicity in Algorithms (SOSA) , year =

    Phevos Paschalidis and Ashley Zhuang , title =. Proceedings of the 2024 Symposium on Simplicity in Algorithms (SOSA) , year =. doi:10.1137/1.9781611977936.2 , url =

    work page doi:10.1137/1.9781611977936.2 2024

  6. [6]

    L. S. Pontryagin , title =. Soviet Mathematics Doklady , volume =. 1967 , pages =

    1967

  7. [7]

    Talagrand, Michel , TITLE =. Proc. Amer. Math. Soc. , FJOURNAL =. 1990 , NUMBER =. doi:10.2307/2048283 , URL =

    work page doi:10.2307/2048283 1990

  8. [8]

    and Lindenstrauss, J

    Bourgain, J. and Lindenstrauss, J. and Milman, V. , TITLE =. Acta Math. , FJOURNAL =. 1989 , NUMBER =. doi:10.1007/BF02392835 , URL =

    work page doi:10.1007/bf02392835 1989

  9. [9]

    Compositio Math

    Schechtman, Gideon , TITLE =. Compositio Math. , FJOURNAL =. 1987 , NUMBER =

    1987

  10. [10]

    and Srivastava, Nikhil , TITLE =

    Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil , TITLE =. SIAM J. Comput. , FJOURNAL =. 2012 , NUMBER =. doi:10.1137/090772873 , URL =

    work page doi:10.1137/090772873 2012

  11. [11]

    and Spielman, Daniel A

    Batson, Joshua D. and Spielman, Daniel A. and Srivastava, Nikhil , TITLE =. S. 2009 , ISBN =

    2009

  12. [12]

    Milman and A

    V.D. Milman and A. Pajor , abstract =. Entropy and Asymptotic Geometry of Non-Symmetric Convex Bodies , journal =. 2000 , issn =. doi:https://doi.org/10.1006/aima.1999.1903 , url =

    work page doi:10.1006/aima.1999.1903 2000

  13. [13]

    , TITLE =

    Giannopoulos, Apostolos A. , TITLE =. Studia Math. , FJOURNAL =. 1997 , NUMBER =. doi:10.4064/sm-122-3-225-234 , URL =

    work page doi:10.4064/sm-122-3-225-234 1997

  14. [14]

    Random Struct

    Victor Reis and Thomas Rothvoss , title =. Random Struct. Algorithms , volume =. 2023 , url =. doi:10.1002/RSA.21113 , timestamp =

    work page doi:10.1002/rsa.21113 2023

  15. [15]

    , TITLE =

    Hadwiger, H. , TITLE =. Math. Z. , FJOURNAL =. 1950 , PAGES =. doi:10.1007/BF01175656 , URL =

    work page doi:10.1007/bf01175656 1950

  16. [16]

    , TITLE =

    Pontrjagin, L. , TITLE =. Dokl. Akad. Nauk SSSR , FJOURNAL =. 1967 , PAGES =

    1967

  17. [17]

    Approximating

    Andr. Approximating. Proceedings of the Twenty-Eighth Annual. 1996 , url =. doi:10.1145/237814.237827 , timestamp =

    work page doi:10.1145/237814.237827 1996

  18. [18]

    Spielman and Shang

    Daniel A. Spielman and Shang. Spectral Sparsification of Graphs , journal =. 2011 , url =. doi:10.1137/08074489X , timestamp =

    work page doi:10.1137/08074489x 2011

  19. [19]

    Spielman and Nikhil Srivastava , title =

    Daniel A. Spielman and Nikhil Srivastava , title =. 2011 , url =. doi:10.1137/080734029 , timestamp =

    work page doi:10.1137/080734029 2011

  20. [20]

    Johnson and Joram Lindenstrauss , journal=

    William B. Johnson and Joram Lindenstrauss , journal=. Extensions of. 1984 , volume=

    1984

  21. [21]

    2007 , month = aug, howpublished =

    Problems from the. 2007 , month = aug, howpublished =

    2007

  22. [22]

    S\'eminaire Bourbaki Volume 2010/2011 Expos\'es 1027-1042 , series =

    Naor, Assaf , title =. S\'eminaire Bourbaki Volume 2010/2011 Expos\'es 1027-1042 , series =. 2012 , publisher =

    2010

  23. [23]

    Kane and Jelani Nelson , title =

    Daniel M. Kane and Jelani Nelson , title =. J. 2014 , url =. doi:10.1145/2559902 , timestamp =

    work page doi:10.1145/2559902 2014

  24. [24]

    A sparse

    Dasgupta, Anirban and Kumar, Ravi and Sarlos, Tam\'. A sparse. Proceedings of the Forty-Second ACM Symposium on Theory of Computing , pages =. 2010 , isbn =. doi:10.1145/1806689.1806737 , abstract =

    work page doi:10.1145/1806689.1806737 2010

  25. [25]

    and Peng, Richard , title =

    Cohen, Michael B. and Peng, Richard , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing , pages =. 2015 , isbn =. doi:10.1145/2746539.2746567 , abstract =

    work page doi:10.1145/2746539.2746567 2015

  26. [26]

    Adrian Kulmburg and Matthias Althoff , keywords =. On the. European Journal of Control , volume =. 2021 , note =. doi:https://doi.org/10.1016/j.ejcon.2021.06.028 , url =

    work page doi:10.1016/j.ejcon.2021.06.028 2021

  27. [27]

    Israel J

    Gordon, Yehoram , TITLE =. Israel J. Math. , FJOURNAL =. 1985 , NUMBER =. doi:10.1007/BF02759761 , URL =

    work page doi:10.1007/bf02759761 1985

  28. [28]

    Convex Bodies: The Brunn–

    Schneider, Rolf , year=. Convex Bodies: The Brunn–

  29. [29]

    , TITLE =

    Matheron, G. , TITLE =. 1975 , PAGES =

    1975

  30. [30]

    , TITLE =

    Artstein-Avidan, Shiri and Giannopoulos, Apostolos and Milman, Vitali D. , TITLE =. 2015 , PAGES =. doi:10.1090/surv/202 , URL =

    work page doi:10.1090/surv/202 2015

  31. [31]

    2021 , howpublished =

    Rothvoss, Thomas , title =. 2021 , howpublished =

    2021

  32. [32]

    Woodruff , title =

    Alexandr Andoni and Robert Krauthgamer and David P. Woodruff , title =. CoRR , volume =. 2014 , url =. 1403.7058 , timestamp =

    Pith/arXiv arXiv 2014

  33. [33]

    Geometric Algorithms and Combinatorial Optimization

    Martin Gr \"o tschel and L \'a szlo Lov \'a sz and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. 1988

    1988

  34. [34]

    De Carli and Harvey, Nicholas J

    Silva, Marcel K. De Carli and Harvey, Nicholas J. A. and Sato, Cristiane M. , title =. ACM Trans. Algorithms , month = dec, articleno =. 2015 , issue_date =. doi:10.1145/2746241 , abstract =

    work page doi:10.1145/2746241 2015