Linear-size $\ell_1$ sparsifiers

Thomas Rothvoss; Victor Reis

REVIEW 3 major objections 5 minor 5 cited by

This paper proves that any ℓ1 norm on R^n, or equivalently any zonotope, has a (1±ε)-approximation using only O(n/ε² log(1/ε)) rows or segments, removing the logarithmic dependence on n.

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 · deepseek-v4-flash

2026-08-02 09:50 UTC pith:6O2HXGFE

load-bearing objection Genuine improvement over Talagrand's bound with a fresh proof mechanism, but the abstract overclaims and the key vector-balancing black-box needs verification. the 3 major comments →

arxiv 2606.28147 v2 pith:6O2HXGFE submitted 2026-06-26 math.MG cs.CGcs.DM

Linear-size ell₁ sparsifiers

Victor Reis , Thomas Rothvoss This is my paper

classification math.MG cs.CGcs.DM MSC 52A2046B07

keywords ℓ1 sparsificationzonotopeMinkowski subtractionsymmetrizerBanach–Mazur distanceconvex geometrydiscrepancy theoryspectral sparsifiers

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.

This paper proves that every ℓ1 norm defined by a matrix A ∈ R^{m×n} — equivalently, every zonotope, the Minkowski sum of segments — can be approximated, up to a multiplicative factor 1±ε, by a weighted subset of at most O(n/ε² log(1/ε)) of its original generating segments. This removes the factor of log n that had remained in the best previous bound since 1990 and, for fixed ε, makes the sparsifier linear in the dimension n. The same statement has two equivalent forms: any n-dimensional subspace of the Banach space ℓ1 is within Banach–Mazur distance 1+ε of a subspace of some finite-dimensional ℓ1^N with N = O(n/ε² log(1/ε)); and a zonotope can be sandwiched between (1−ε)Z and (1+ε)Z by one with few generators. The proof is geometric: random rescaling of generators preserves the norm with high probability, a symmetrizer volume bound guarantees a large set of sign changes, and a discrepancy theorem iteratively discards a constant fraction of the segments. The construction also yields an alternative proof of linear-size spectral sparsifiers.

Core claim

The central claim is that for any matrix A ∈ R^{m×n} and ε ∈ (0,1/2], there is a nonnegative diagonal matrix D with at most O(n/ε² log(1/ε)) nonzero entries that preserves the ℓ1 norm of Ax up to a factor 1±ε for every x. Because a matrix's rows generate a symmetric zonotope whose support function is the ℓ1 norm, the same result says every zonotope in R^n can be sandwiched between (1−ε)Z and (1+ε)Z by a zonotope with O(n/ε² log(1/ε)) segments. A third equivalent form embeds any n-dimensional subspace of ℓ1 into ℓ1^N with N = O(n/ε² log(1/ε)) at Banach–Mazur distance 1+ε, answering a 1986 question. The paper further derives a new proof of linear-size spectral sparsifiers by the same symmetriz

What carries the argument

The proof pivots on two facts. First, the volume of the Minkowski subtraction K ª Z_t — the set of shifts that keep a scaled zonotope inside K — is separately convex as a function of the segment lengths t; this lets the authors use Jensen's inequality to show that a random rescaling of the generators is contained in (1+ε)Z with probability at least (ε/2)^n. Second, a symmetrizer theorem (Theorem 16) asserts that if all coordinate sections of a convex body K in [−1,1]^m have volume at least p 2^{|S|}, then K ∩ −K has volume at least 2^{−5m}; the proof of this theorem is a delicate volume estimate (Lemma 18) that partitions coordinates by magnitude and uses a telescoping inequality. The large

Load-bearing premise

The entire proof rests on a technical volume bound saying that cutting a convex body with large coordinate sections by any halfspace still leaves volume at least p 2^{−2m}; if that bound is false, the symmetrizer estimate collapses and the iterative segment-reduction has no starting point.

What would settle it

Run a computational search over convex bodies K ⊂ [−1,1]^m that satisfy Vol_S(K_S) ≥ p 2^{|S|} for all subsets S (e.g., K a cube with one corner cut off and p = 1/2), and compute Vol(K ∩ {x : ⟨a,x⟩ ≤ λ‖a‖₁/√m}) for random vectors a. Any instance with volume below p 2^{−2m} for m ≈ 50 would falsify Lemma 18 and hence Theorem 16.

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

Share X Bluesky LinkedIn Reddit HN

If this is right

Every zonotope in R^n has a (1+ε)-approximation by a zonotope with O(n/ε² log(1/ε)) segments, improving the previous O(n/ε² log n).
Every n-dimensional subspace of ℓ1 is within Banach–Mazur distance 1+ε of ℓ1^N for N = O(n/ε² log(1/ε)), resolving a 1986 open question up to the log(1/ε) factor.
The proof gives a second route to linear-size spectral sparsifiers: the same symmetrizer machinery yields O(n/ε² log(1/ε)) nonnegative weights preserving the Loewner order up to 1±ε.
For any fixed ε, the construction is linear in n — O(n/ε²) segments — matching the qualitative behavior long known for Euclidean norms and graph cut sparsifiers.
Combined with the known cut-sparsifier lower bound, the result shows the sparsifier size is tight up to a log(1/ε) factor.

Where Pith is reading between the lines

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

The log(1/ε) factor appears as an artifact of the coordinate-partition argument in Lemma 18; if that lemma can be sharpened to Vol(K_a) ≥ p 2^{−m}, the whole iterative scheme would yield O(n/ε²) segments for all ε, matching the lower bound.
The symmetrizer technique is not obviously limited to ℓ1: the spectral analogue in the paper suggests the same 'random rescaling + symmetrizer + sign-flip' pattern could apply to other matrix-induced norms or to sums of convex functions, potentially giving a unified sparsification theory.
Because the separation oracle for the zonotope inclusion Q is the only non-polynomial step, replacing it with an approximate membership test could make the construction polynomial-time, which the paper explicitly does not provide.
The result suggests that the hard part of ℓ1 sparsification is not the norm's non-smoothness but the need to control both lower and upper inclusions; the proof's early focus on K ∩ −K may be the key insight for other Banach-space approximation problems.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

Genuine improvement over Talagrand's bound with a fresh proof mechanism, but the abstract overclaims and the key vector-balancing black-box needs verification.

read the letter

Bottom line: this is a genuine advance. They improve the best known bound for ℓ1 sparsification from O(n/ε² log n) to O(n/ε² log(1/ε)), which for fixed ε is linear in n, and they do it with a mechanism that is not just a re-run of known arguments. The Minkowski-subtraction convexity (Lemma 12) and the separate-convexity argument in Theorem 14 are clean; the symmetrizer volume bound (Theorem 16) is a substantial piece of work. The zonotope and Banach-Mazur consequences follow naturally, and the alternative proof of the BSS spectral sparsifier is a nice bonus.

The main soft spots: the abstract claims O(n/ε²) but Theorem 1 only proves O(n/ε² log(1/ε)); that mismatch should be fixed. More importantly, the proof relies on Theorem 7, a vector-balancing statement quoted from the authors' own [RR23] as a minor modification, with a one-line Gaussian-to-volume conversion. Theorem 20's iteration needs a constant s that works uniformly for every symmetric convex set of volume at least 2^{-5m}; if that black-box is wrong for this regime, the shrinking argument collapses. The stress-test note says Lemma 18, which I initially flagged as delicate, actually checks out; I agree — the proof is in the paper and the telescoping works. So the least secure load-bearing step is Theorem 7, not Lemma 18. The paper should either prove the needed statement in full or state it as a lemma with enough detail to verify the parameter dependence. There is also a small notational slip (B_1^m vs B_∞^m) in the proof of Theorem 16; it doesn't affect the argument.

I don't think the core is wrong. The logic from Theorem 15 to 16 to 19 to 20 is coherent, and the new volume-convexity idea is convincing. The reliance on a self-cited black box is a real concern, but it's the kind of thing peer review can fix. This paper deserves a serious referee. I'd send it to review with a request that the referee verify Theorem 7 and the abstract be corrected. If you work on convex geometry or sparsification, this is worth a close read.

Referee Report

3 major / 5 minor

Summary. The manuscript proves that for every A∈R^{m×n} and ε∈(0,1/2] there exists a nonnegative diagonal matrix D with at most O(n/ε² log(1/ε)) nonzero entries such that ‖DAx‖₁ approximates ‖Ax‖₁ within factor 1±ε for all x. This implies the stated approximation of any zonotope by a zonotope with O(n/ε² log(1/ε)) segments and a Banach–Mazur embedding statement. The proof combines a volume-based inclusion lemma for random zonotopes (via Minkowski subtraction and separate convexity), a symmetrizer volume theorem, and an iterative halving of the number of segments using a vector-balancing result from the authors' earlier work. Section 6 gives an analogous spectral sparsification result with the same O(n/ε² log(1/ε)) bound.

Significance. Should the proof be completed, the main theorem would be a genuine improvement over Talagrand's O(n/ε² log n) for every fixed ε, reducing the logarithmic term to log(1/ε), and would answer Schechtman's 1986 question in a near-optimal form. The volume lower bounds and the use of Minkowski subtraction are elegant and mostly elementary. The paper is not fully self-contained: the vector-balancing theorem (Theorem 7) is cited from [RR23] and is not reproduced, and the proof of Theorem 16 contains a ball-norm slip. These are local and likely repairable, but until fixed the claimed theorem should not be considered verified as written.

major comments (3)

[Theorem 7 (black box)] The iterative step in Theorem 20 applies Theorem 7 with c=2^{-5} to Qε_t. The theorem is asserted as a 'minor modification' of [RR23, Thm 9], with only the Gaussian/volume ratio in one sentence. Since Theorem 7's s(c) is essential for the iteration and is not stated in the cited theorem's original form, the paper should include a precise statement of [RR23, Thm 9] and a proof of the modification, or at least a complete derivation of the constants. Without this, an independent reader cannot verify the existence of a universal s(2^{-5}).
[Section 4, Claim I (Theorem 16)] The separating-hyperplane step is incorrect. It asserts max_{x∈rB_1^m} ⟨a,x⟩ = r‖a‖_1, but the correct value is r‖a‖_∞. With the stated ℓ1 ball, the inequality ⟨a,z⟩ > r‖a‖_1 for all z∈S does not follow, and the contradiction collapses. The natural fix is to state Claim I with rB_∞^m and conclude kz*‖∞≤r, which suffices for the final step since r≤ε. Please correct the statement and proof.
[Abstract / header] The abstract in the submission header states O(n/ε²), whereas Theorem 1 and the full-text abstract give O(n/ε² log(1/ε)). The log(1/ε) factor is essential in the proof (Corollary 19 and Theorem 20). The abstract must be corrected to match the theorem; the improvement over Talagrand is O(log n) → O(log(1/ε)), not removal of all log factors.

minor comments (5)

[Theorem 15] The reduction to full-dimensional Z ('adding [−δ,δ]^n as δ→0') is a one-line limiting argument. Please provide a few sentences explaining why the volume lower bound for K_S passes to the limit; alternatively work in the linear span of Z with n replaced by rank(Z).
[Theorem 16 proof] In the proof of Theorem 16, the initial inclusion should be εB_∞^m ⊂ K ⊂ B_∞^m rather than B_1^m; the current text has a notational slip.
[Section 6, Theorem 24] The phrase 'due to De Carli, Harvey and Sato [SHS15]' is confusing; the theorem is proved here, with [SHS15] being a related result. Please rephrase.
[Theorem 4] The statement of Theorem 4 says 'O(n/ε² log(1/ε))' while the text recalls that O(n/ε²) is known [BSS09,BSS12]; the new contribution is the alternative proof, and this should be stated clearly.
[Lemma 8 proof] In the proof of Lemma 8, the line 'taking t=3√λ/‖v‖₂' yields exp(−3λ/2); the subsequent inequality exp(−3λ/2)≤2^{−2λ} is correct but should be stated, since the displayed chain jumps slightly.

Circularity Check

0 steps flagged

No significant circularity: the sparsifier bound follows from a self-contained volume argument plus a published, non-equivalent vector-balancing theorem.

full rationale

The derivation chain is: Theorem 15 uses Theorem 14 (proved in full) to show that the set K of sign changes keeping the zonotope inside (1+ε)Z has large coordinate sections; Lemma 18 and Theorem 16 (proved in full) convert this into a large symmetrizer K∩−K; Corollary 19 packages this; and Theorem 20 iteratively shrinks the support by applying Theorem 7 to the symmetric convex body Q_εt. None of these steps assumes the target Theorem 1/2, and none defines a quantity in terms of the conclusion. The only external input is Theorem 7, quoted as "The following is a minor modification of [RR23, Theorem 9]". That theorem is a published vector-balancing statement in Gaussian measure whose assumptions do not include the existence of ℓ1 sparsifiers; the paper supplies the Gaussian-to-volume conversion via the density bound 'γm(K)/Volm(K) ∈ [(2πe)^{−m/2}, (2π)^{−m/2}]'. Thus it is independent support, not a self-citation chain forcing the result. The iterative product argument and constant choice C = Θ(s^4) are explicit. The abstract's first sentence states O(n/ε²) while Theorem 1 states O(n/ε² log(1/ε)); this is a consistency slip, not a circular reduction. There is no fitted parameter renamed as a prediction and no equation that reduces by construction to its own input. Therefore no circular step can be quoted with a specific reduction, and the score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central existence theorem is not built on fitted parameters or invented objects. It rests on three external or background theorems: Milman–Pajor, Brunn's concavity principle, and a vector-balancing theorem from the authors' own previous paper [RR23]. The last is the most consequential dependency: it is load-bearing in the iterative reduction and is self-cited, though it concerns a different problem.

axioms (3)

standard math Milman–Pajor theorem: for any convex body K⊂R^m with barycenter z, Vol((K−z)∩(−(K−z))) ≥ 2^{-m} Vol(K).
Invoked as Theorem 5 and used inside Proposition 17(A) to certify a large f_K(z*).
standard math Brunn's concavity principle: Vol(K∩(x+L))^{1/m} is concave.
Theorem 6, used in Proposition 17(C) to prove convexity of superlevel sets of f_K(z).
domain assumption Vector balancing theorem of Reis–Rothvoss (Theorem 7, modification of [RR23, Thm 9]): if a symmetric convex K⊂[−1,1]^m has volume ≥ c^m, then some x∈sK∩[−1,1]^m has at least m/2 coordinates equal to ±1, and such x can be found in randomized polynomial time given a separation oracle.
Load-bearing black box in the iterative reduction (Theorem 20); it is self-cited from the authors' earlier work and converted from Gaussian to uniform measure by standard density bounds.

pith-pipeline@v1.3.0-alltime-deepseek · 14865 in / 27704 out tokens · 210611 ms · 2026-08-02T09:50:21.115625+00:00 · methodology

0 comments

Cite this review

Pith. "Pith review of Linear-size $\ell_1$ sparsifiers." pith.science (2026). https://pith.science/paper/6O2HXGFE

@misc{pith2026260628147,
  author       = {Pith},
  title        = {Pith review of: Linear-size $\ell_1$ sparsifiers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6O2HXGFE}},
  note         = {Machine review of arXiv:2606.28147}
}

Share X Bluesky LinkedIn Reddit HN

read the original abstract

We prove that for any matrix $A \in \mathbb{R}^{m \times n}$ and any $\varepsilon > 0$ there is a diagonal matrix $D \in \mathbb{R}_{\geq 0}^{m \times m}$ with at most $O(\frac{n}{\varepsilon^2})$ 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})$ 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).

Review history (2 revisions) →

discussion (0)

Forward citations

Cited by 5 Pith papers

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

Optimal Embeddings of Constant-Dimensional Subspaces of $L^p$ into $\ell_p^N$
math.FA 2026-07 accept novelty 7.0

Every d-dimensional subspace of L^p embeds into ℓ_p^N with distortion 1+ε for N = Õ(ε^{-2(d-1)/(d+2p)}), which is optimal up to logs for every p that is not an even integer.
Optimal Embeddings of Constant-Dimensional Subspaces of $L^p$ into $\ell_p^N$
math.FA 2026-07 conditional novelty 7.0

For fixed d ≥ 2 and every p not an even integer, every d-dimensional subspace of L^p embeds into ℓ_p^N with distortion 1+ε for N ≍_{d,p} ε^{-2(d-1)/(d+2p)}, optimally in ε up to constants.
Optimal Embeddings of Constant-Dimensional Subspaces of $L^p$ into $\ell_p^N$
math.FA 2026-07 accept novelty 6.5

For fixed d≥2 and p≥1, N_p(d,ε) is Õ_{d,p}(ε^{-2(d-1)/(d+2p)}), optimal up to logs for non-even p.
Optimal Sparsifiers for Abelian Cayley Graphs
cs.DS 2026-07 accept novelty 6.5

Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.
Optimal Embeddings of Constant-Dimensional Subspaces of $L^p$ into $\ell_p^N$
math.FA 2026-07 unverdicted novelty 6.0

Every d-dimensional subspace of L^p embeds into ℓ_p^N with distortion 1+ε for N of order ε^{-2(d-1)/(d+2p)}, up to d,p-dependent logs.

Reference graph

Works this paper leans on

3 extracted references · cited by 2 Pith papers

[2000]

[Nao12] Assaf Naor

URL: https://www.sciencedirect.com/science/article/ pii/S0001870899919035, doi:10.1006/aima.1999.1903. [Nao12] Assaf Naor. Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]. In Séminaire Bour- baki Volume 2010/2011 Exposés 1027-1042, number 348 in Astérisque, pages 189–217. Société mathématique de France, ...

arXiv 1999
[2007]

Workshop held August 20–24, 2007, Palo Alto, Cali- fornia

Problem 4. Workshop held August 20–24, 2007, Palo Alto, Cali- fornia. [BK96] András A. Benczúr and David R. Karger. Approximating s-t mini- mum cuts in Õ(n2) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Comput- ing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 , pages 47–55. ACM, 1996. doi:10....

arXiv 2007
[2025]

[RR20] Victor Reis and Thomas Rothvoss

URL: https://sites.math.washington.edu/~rothvoss/ archive/lecturenotes/AsymptoticConvexGeometry.pdf. [RR20] Victor Reis and Thomas Rothvoss. Linear size sparsiﬁer and the geometry of the operator norm ball. In Proceedings of the Thirty- First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2337–2348. Society for Industrial and Applied Math...

doi:10.1137/1 2020

[1] [2000]

[Nao12] Assaf Naor

URL: https://www.sciencedirect.com/science/article/ pii/S0001870899919035, doi:10.1006/aima.1999.1903. [Nao12] Assaf Naor. Sparse quadratic forms and their geometric applications [following Baston, Spielman and Srivastava]. In Séminaire Bour- baki Volume 2010/2011 Exposés 1027-1042, number 348 in Astérisque, pages 189–217. Société mathématique de France, ...

arXiv 1999

[2] [2007]

Workshop held August 20–24, 2007, Palo Alto, Cali- fornia

Problem 4. Workshop held August 20–24, 2007, Palo Alto, Cali- fornia. [BK96] András A. Benczúr and David R. Karger. Approximating s-t mini- mum cuts in Õ(n2) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Comput- ing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 , pages 47–55. ACM, 1996. doi:10....

arXiv 2007

[3] [2025]

[RR20] Victor Reis and Thomas Rothvoss

URL: https://sites.math.washington.edu/~rothvoss/ archive/lecturenotes/AsymptoticConvexGeometry.pdf. [RR20] Victor Reis and Thomas Rothvoss. Linear size sparsiﬁer and the geometry of the operator norm ball. In Proceedings of the Thirty- First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2337–2348. Society for Industrial and Applied Math...

doi:10.1137/1 2020