Pith. sign in

REVIEW 5 minor 1 cited by

Well-invertible column subsets of sparse matrices are rare

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read Constant-sparsity sketch matrices cannot injectively embed proportional-dimensional subspaces with constant injectivity.

desk verdict Clean negative answer to the constant-sparsity OSI question, via a dual rarity statement to Bourgain–Tzafriri that is new and carefully proved. read the letter →

arxiv 2607.05384 v2 pith:V2BXUWNG submitted 2026-07-06 math.PR math.FA

Han Huang , Mark Rudelson , Konstantin Tikhomirov This is my paper
classification math.PRmath.FA MSC 60B2015B5268W20
keywords oblivioussubspaceinjectionrestrictedinvertibilitysparsesketchingsmallestsingularvalueC4-freebipartitegraphsmatchingrootedtreesStackcolumnsubsets
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

Randomized sketching compresses high-dimensional data with sparse random matrices, and oblivious subspace injections (OSI) only require one-sided injectivity rather than full isometry. This paper proves that no constant-row-sparsity matrix can be an OSI when the target subspace dimension is a constant fraction of the sketch width and the injectivity factor stays bounded away from zero. The failure is deterministic: under mild average-sparsity and mild double-overlap assumptions, almost every proportional-size column submatrix of a sparse matrix has vanishingly small least singular value. The well-invertible column subsets guaranteed by classical restricted-invertibility theorems therefore exist but form a vanishing fraction of all possible subsets. The result immediately rules out constant-sparsity SparseStack matrices as OSI maps for proportional dimensions.

What carries the argument

Weight-compatible m-matching rooted trees (m o∞) inside C4-free support subgraphs: an explicit test vector supported on the tree cancels on the first left layer and leaves only a small outer residual, forcing s_min o0. The trees are harvested by intermediate sampling that produces large C4-free pieces, then by a witness-block capture argument.

What would settle it

Exhibit a deterministic sequence of constant-sparsity k imes n_k matrices (n_k/k o∞) whose double-overlap count is o(n_k^{2}/k) yet a positive fraction of random ⌊εk⌋-column submatrices keep least singular value bounded below by a fixed positive constant.

Watch

Extended reading notes

Core claim

Under average column support O(1), average nonzero magnitude O(1), and o(n_k^{2}/k) pairs of columns that overlap on two or more indices, a uniformly random set of ⌊εk⌋ columns of a k imes n_k matrix has smallest singular value o(1) with probability 1-o(1) as n_k/k o∞. Consequently constant-sparsity SparseStack matrices fail to be (εk,α)-OSI for every fixed ε,α>0.

Load-bearing premise

Typical columns share support with only a vanishing fraction of other columns on two or more rows; if many columns double-overlap, the whole reduction to tree-free singular patterns collapses.

Editorial extensions

If this is right

  • Constant-sparsity SparseStack (any fixed number of nonzeros per row) is never (r,α)-OSI for r=Ω(k) and α=Ω(1).
  • The same scarcity holds for combinatorial random matrices with fixed row support size and for matrices with prescribed constant row and column degrees.
  • Restricted-invertibility theorems guarantee existence of well-invertible column subsets, yet those subsets form a vanishing proportion of all proportional-size subsets of sparse matrices.
  • Any sketch matrix that hopes to be OSI at proportional dimension must either grow its row sparsity or abandon the mild double-overlap condition.
  • The obstruction already appears for coordinate subspaces, so injectivity fails even without testing arbitrary subspaces.

Reading between the lines

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

  • If the double-overlap hypothesis can be removed (as the authors conjecture), the same rarity would hold for every deterministic constant-sparsity matrix, closing the last combinatorial loophole for sparse OSI maps.
  • The critical sparsity for random constant-support matrices to regain constant least singular value on random proportional submatrices is expected to sit at a polylogarithmic threshold; settling the exact exponent would give the optimal OSI sparsity.
  • The tree-based cancellation pattern suggests that other local combinatorial motifs (higher-girth trees, expanders of controlled depth) may likewise force singular-value collapse once they appear with high probability in random samples.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper proves that well-invertible proportional column subsets of sparse matrices are rare. Theorem 1.3 states that if M^(k) is a deterministic k imes n_k sequence with n_k/k o∞, average column support O(1), average nonzero magnitude O(1), and o(n_k^{2}/k) pairs of columns overlapping on ≥2 indices, then a uniform random column subset of size ⌊εk⌋ has s_min=o(1) with probability 1−o(1). The argument reduces the matrix problem to weighted bipartite graphs, upgrades local four-cycle sparsity to a large C4-free intermediate subgraph (Prop. 4.4), extracts a weight-compatible m-matching rooted tree via witness blocks and heavy reservoirs (Thm. 3.15, Prop. 4.5), and produces an explicit test vector (Prop. 2.5) forcing s_min=O(1/√m) with m→∞. As a corollary, constant-sparsity SparseStack matrices fail to be (εk,α)-OSI for any fixed ε,α>0 (Cor. 1.6), answering a question of Camaño–Epperly–Meyer–Tropp in a strong form.

Significance. The result is a clean negative answer to the constant-sparsity OSI question and a dual to classical restricted invertibility: Bourgain–Tzafriri guarantees existence of well-invertible submatrices, while the paper shows that under mild sparsity and overlap hypotheses those submatrices form a vanishing fraction of all proportional subsets. The reduction of a probabilistic sketching question to a deterministic combinatorial phenomenon is valuable, and the modular chain (average-degree trichotomy → C4-free sampling → weight-compatible tree → test vector) is reusable. The SparseStack application is immediate and covers the models of primary interest. Open problems (Conj. 7.1, Problem 7.2) correctly flag the remaining unrestricted and optimal-sparsity questions. Strengths include explicit constructions, finite combinatorial lemmas, and transparent asymptotic bookkeeping.

minor comments (5)
  1. [Abstract / §1.2] Abstract and Theorem 1.3: the abstract phrases the matrix as n_k×k with row sparsity, while Theorem 1.3 works with k×n_k and column sparsity (M = S^⊤). A single clarifying sentence early in §1.2 would prevent orientation confusion for readers coming from the OSI literature.
  2. [§3.2] Definition 3.6 and Corollary 3.8: the heavy-neighbor fraction 1/(32d) is a convenient but arbitrary constant. A short remark that any sufficiently small positive fraction works (with adjusted absolute constants) would make the parameter choices less opaque.
  3. [§5–6] Remark 5.1 and Proposition 6.2: the polylogarithmic sparsity extension is stated but left to the reader. A one-paragraph sketch of how d_k ≪ (log L_k)^{1/4−δ} enters the m_k lower bound would strengthen the quantitative claims without lengthening the paper much.
  4. [§1.3 / §2] Figures 1–3 are helpful; ensuring that the caption of Figure 2 explicitly identifies the cancellation rows versus the outer-layer rows would improve readability for non-specialists.
  5. [§3.4 / §4.1] A few absolute constants (C_{3.15}, c_{4.4}) appear without numerical values. Stating that they are absolute and can be taken large enough is fine, but a parenthetical “e.g., C_{3.15}=10^3 suffices” would aid verification.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: vanishing s_min is derived from external structural hypotheses via an independent combinatorial obstruction, not by definition or self-fit.

full rationale

Theorem 1.3 and Corollary 1.6 are conditional negative results: under stated external hypotheses (average column support O(1), average nonzero magnitude O(1), and o(n_k^{2}/k) double-overlap pairs / local sparse four-cycle incidence), a uniform proportional column subset has s_min=o(1) w.h.p. The derivation chain is modular and non-circular: (i) average-degree trichotomy (Prop. 4.5) reduces to isolated/degree-one collisions or a C4-free bounded-degree subgraph; (ii) C4-free sampling (Thm. 3.15) extracts a weight-compatible m-matching rooted tree with m→∞; (iii) Prop. 2.5 supplies an explicit test vector forcing s_min ≤ O(d_av^{2}/√m)=o(1). None of these objects is defined in terms of the target singular-value conclusion. SparseStack is handled by verifying the overlap hypothesis w.h.p. (Prop. 6.1), not by fitting. Citations to Bourgain–Tzafriri, Vershynin, and Camaño–Epperly–Meyer–Tropp are classical/external background (existence of good subsets; OSI definition and open question); they do not load-bear the scarcity proof. Conjecture 7.1 openly flags that the overlap hypothesis may be removable, confirming it is an assumption rather than a circular redefinition. No fitted parameters, no uniqueness imported from the authors’ prior work, and no renaming of a known empirical pattern. Honest non-finding: score 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

Load-bearing content is standard asymptotic probability and graph combinatorics plus three structural hypotheses on the input matrix sequence (average support, average magnitude, double-overlap count). No free parameters are fitted to data. Invented combinatorial objects (matching rooted trees, witness blocks, heavy reservoirs) are definitional tools with explicit falsifiable roles inside the proof, not physical entities.

assumptions (5)
  • standard math Bourgain–Tzafriri restricted invertibility and Vershynin’s stable-rank extension guarantee existence of well-invertible column subsets under spectral assumptions (used only as contrast, not as a lemma inside the proof).
    Cited in §1.2 as background; the paper proves a dual rarity statement rather than relying on BT for the main bound.
  • domain assumption Average column support size O(1), average nonzero magnitude O(1), and o(n_k²/k) double-overlap pairs (Theorem 1.3 assumptions (1)–(3)).
    Structural hypotheses on the matrix sequence; verified for SparseStack and combinatorial models in §6, but essential for the deterministic theorem.
  • domain assumption n_k/k → ∞ and sample size |Ω_k|=⌊εk⌋ for fixed ε>0.
    Asymptotic regime in which the o(1) singular-value claim is stated.
  • standard math Hall’s marriage theorem / multi-matching criterion for constructing disjoint heavy reservoirs (used in Proposition 3.12 Step 2).
    Classical combinatorial fact; applied after degree lower bounds from C4-freeness.
  • standard math Hoeffding comparison for sampling without replacement and standard Chernoff/Markov/Chebyshev tail bounds.
    Used throughout §§3–4 for hypergeometric concentration.
invented entities (2)
  • weight-compatible m-matching rooted tree
    purpose: Local combinatorial pattern that produces an explicit test vector with ||Mv||₂ = O(1/√m), forcing small s_min.
    Definition 2.2–2.4 and Proposition 2.5; purely combinatorial/analytic device, not an external physical postulate.
  • L-witness block / heavy reservoirs / light roots
    purpose: Intermediate objects that make capture of a matching tree by uniform sampling analyzable under C4-freeness.
    Definitions 3.1 and 3.6; tools internal to the sampling argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Well-invertible column subsets of sparse matrices are rare." pith.science (2026). https://pith.science/paper/V2BXUWNG

@misc{pith2026260705384,
  author       = {Pith},
  title        = {Pith review of: Well-invertible column subsets of sparse matrices are rare},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V2BXUWNG}},
  note         = {Machine review of arXiv:2607.05384}
}
abstract

A random $n\times k$ matrix $S$ is an \emph{$(r,\alpha)$-oblivious subspace injection} (OSI) if $\mathbb{E}\|S^\top x\|_2^2=\|x\|_2^2$ for every $x\in\mathbb{R}^n$, and for every fixed $r$-dimensional subspace $V\subset\mathbb{R}^n$, with probability close to one, one has $\alpha\|x\|_2^2\le\|S^\top x\|_2^2$ for all $x\in V$. In this work, we show that in the regime $r=\Omega(k)$ and $\alpha=\Omega(1)$, and under a mild additional structural assumption, no constant-row-sparsity matrix $S$ is OSI, thereby answering, in a strong form, a question raised by Cama\~no, Epperly, Meyer, and Tropp. We show that the failure of the OSI property for sparse random matrices stems from a general deterministic phenomenon, thereby reducing a probabilistic problem to a non-probabilistic one. This phenomenon is related to the restricted invertibility principle introduced in the seminal work of Bourgain--Tzafriri. Let $(n_k)_{k\in\mathbb{N}}$ be a sequence of integers satisfying $\frac{n_k}{k}\to\infty$. For each $k$, let $S^{(k)}$ be a $n_k\times k$ non-random matrix with $O(1)$ nonzero entries per row, whose nonzero entries have average magnitude $O(1)$, and such that the total number of pairs of rows with supports overlapping at two or more indices is $o({n_k}^2/k)$. We prove that for every constant $\varepsilon>0$, as $k\to\infty$, the overwhelming majority of $k\times \lfloor\varepsilon k\rfloor$ submatrices of $(S^{(k)})^\top$ have the smallest singular value $o(1)$. Thus, the well-invertible submatrices whose existence is guaranteed by the Bourgain--Tzafriri theorem are rare. The proof is itself based on probabilistic tools.

Figures

Figures reproduced from arXiv: 2607.05384 by the authors.

Figure 1
Figure 1. A m-matching rooted tree, shown for right degree d = 3 and width m = 5. The four tree layers have 1, 3, 15, and 30 vertices, respectively. This pattern gives an explicit test vector v supported on the right vertices of T. Put vj⋆ = 1, and choose the coefficients vcℓ,a with |vcℓ,a | = 1/m so that the contribution of the root column cancels on the rows i1, . . . , id. The only remaining nonzero coordinates of MΩv lie … view at source ↗
Figure 2
Figure 2. The support-pattern matrix associated with the tree in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Reservoir pruning around a root for d = 3 and m = 5. Each left neighbor of the root has a reservoir of size m(1 + (d − 1)2 ) = 25. The pruning lemma selects five blue vertices from each reservoir and avoids candidates whose outer left neighborhoods collide with previously selected vertices. Proof. Because G is C4-free, every j ∈ Ri satisfies NG(j) ∩ I⋆ = {i}. Otherwise j and j⋆ would have two common left neighbors. … view at source ↗

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Level-set entropy and sparse randomized embeddings

    math.PR 2026-07 accept novelty 8.0 of 10

    A sparse random k×n matrix with k≈r(log log r)^2 and p≈(log k)/k has O(√(kp)) spectral norm on every fixed r-dimensional subspace, with high probability.

Reference graph

Works this paper leans on

29 extracted references · 7 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Bourgain and L

    J. Bourgain and L. Tzafriri,Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis, Israel J. Math.57(1987), no. 2, 137–224

    1987

  2. [2]

    Bourgain and L

    J. Bourgain and L. Tzafriri,Restricted invertibility of matrices and applications, inAnalysis at Urbana, Vol. II (Urbana, IL, 1986–1987), London Math. Soc. Lecture Note Ser., vol. 138, Cambridge Univ. Press, Cambridge, 1989, pp. 61–107

    1986

  3. [3]

    Bourgain and L

    J. Bourgain and L. Tzafriri,On a problem of Kadison and Singer, J. Reine Angew. Math.420(1991), 1–43

    1991

  4. [4]

    St´ ephane Boucheron, G´ abor Lugosi, and Pascal Massart,Concentration Inequalities: A Nonasymptotic Theory of Inde- pendence, Oxford University Press, Oxford, 2013

    2013

  5. [5]

    Epperly, Raphael A

    Chris Cama˜ no, Ethan N. Epperly, Raphael A. Meyer, and Joel A. Tropp,Faster linear algebra algorithms with structured random matrices, arXiv:2508.21189, revised August 28, 2025

    arXiv 2025

  6. [6]

    Shabarish Chenakkod, Micha l Derezi´ nski, Xiaoyu Dong, and Mark Rudelson,Optimal embedding dimension for sparse subspace embeddings, inProceedings of the 56th ACM Symposium on Theory of Computing, 2024

    2024

  7. [7]

    Shabarish Chenakkod, Micha l Derezi´ nski, and Xiaoyu Dong,Optimal oblivious subspace embeddings with near-optimal sparsity, arXiv:2411.08773, 2024

    arXiv 2024

  8. [8]

    4501–4559

    Shabarish Chenakkod, Micha l Derezi´ nski, and Xiaoyu Dong,Optimal subspace embeddings: Resolving Nelson–Nguyen conjecture up to sub-polylogarithmic factors, inProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026, pp. 4501–4559

    2026

Show all 29 references
  1. [9]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff,Low-rank approximation and regression in input sparsity time, inProceedings of the 45th ACM Symposium on Theory of Computing, 2013, pp. 81–90

    2013

  2. [10]

    Cohen,Nearly tight oblivious subspace embeddings by trace inequalities, inProceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, pp

    Michael B. Cohen,Nearly tight oblivious subspace embeddings by trace inequalities, inProceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, pp. 278–287

    2016

  3. [11]

    Halmos and Herbert E

    Paul R. Halmos and Herbert E. Vaughan,The marriage problem, Amer. J. Math.72(1950), 214–215

    1950

  4. [12]

    G. H. Hardy, J. E. Littlewood, and G. P´ olya,Inequalities, 2nd ed., Cambridge University Press, Cambridge, 1952

    1952

  5. [13]

    301, 13–30

    Wassily Hoeffding,Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association58(1963), no. 301, 13–30

    1963

  6. [14]

    Kane and Jelani Nelson,Sparser Johnson–Lindenstrauss transforms, Journal of the ACM61(2014), no

    Daniel M. Kane and Jelani Nelson,Sparser Johnson–Lindenstrauss transforms, Journal of the ACM61(2014), no. 1, Article 4

    2014

  7. [15]

    Mahoney,Randomized algorithms for matrices and data, Foundations and Trends in Machine Learning3 (2011), no

    Michael W. Mahoney,Randomized algorithms for matrices and data, Foundations and Trends in Machine Learning3 (2011), no. 2, 123–224

    2011

  8. [16]

    Marcus, Daniel A

    Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava,Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem, Ann. of Math. (2)182(2015), no. 1, 327–350

    2015

  9. [17]

    Marcus, Daniel A

    Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava,Interlacing families III: Sharper restricted invertibility estimates, arXiv:1712.07766, 2017

    2017 arXiv

  10. [18]

    Tropp,Randomized numerical linear algebra: Foundations and algorithms, Acta Numerica29(2020), 403–572

    Per-Gunnar Martinsson and Joel A. Tropp,Randomized numerical linear algebra: Foundations and algorithms, Acta Numerica29(2020), 403–572

    2020

  11. [19]

    Xiangrui Meng and Michael W. Mahoney,Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression, inProceedings of the 45th ACM Symposium on Theory of Computing, 2013, pp. 91–100

    2013

  12. [20]

    Assaf Naor and Pierre Youssef,Restricted invertibility revisited, inA Journey Through Discrete Mathematics, Springer, Cham, 2017, pp. 657–691

    2017

  13. [21]

    Nguyen,Lower bounds for oblivious subspace embeddings, arXiv:1308.3280, 2013

    Jelani Nelson and Huy L. Nguyen,Lower bounds for oblivious subspace embeddings, arXiv:1308.3280, 2013

    2013 arXiv

  14. [22]

    Nguyen,OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, arXiv:1211.1002, 2012

    Jelani Nelson and Huy L. Nguyen,OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, arXiv:1211.1002, 2012

    2012 arXiv

  15. [23]

    24, Springer-Verlag, Berlin, 2003

    Alexander Schrijver,Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003

    2003

  16. [24]

    Spielman and Nikhil Srivastava,An elementary proof of the restricted invertibility theorem, Israel J

    Daniel A. Spielman and Nikhil Srivastava,An elementary proof of the restricted invertibility theorem, Israel J. Math.190 (2012), 83–91

    2012

  17. [25]

    Alex Townsend and Chris Wang,Oblivious subspace injection is not enough for relative error, arXiv:2604.10215, 2026

    2026 arXiv

  18. [26]

    Tropp,Comparison theorems for the extreme eigenvalues of a random symmetric matrix, arXiv:2603.04365, 2026

    Joel A. Tropp,Comparison theorems for the extreme eigenvalues of a random symmetric matrix, arXiv:2603.04365, 2026

    2026 arXiv

  19. [27]

    Vershynin,John’s decompositions: selecting a large part, Israel J

    R. Vershynin,John’s decompositions: selecting a large part, Israel J. Math.122(2001), 253–277. 31

    2001

  20. [28]

    Woodruff,Sketching as a tool for numerical linear algebra, Foundations and Trends in Theoretical Computer Science10(2014), no

    David P. Woodruff,Sketching as a tool for numerical linear algebra, Foundations and Trends in Theoretical Computer Science10(2014), no. 1–2, 1–157

    2014

  21. [29]

    1, 201–218

    Pierre Youssef,Restricted invertibility and the Banach–Mazur distance to the cube, Mathematika60(2014), no. 1, 201–218. Department of Mathematics, University of Missouri, Columbia Email address:hhuang@missouri.edu Department of Mathematics, University of Michigan Email address...

    2014

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.