Pith. sign in

REVIEW 2 major objections 3 minor 30 references

Level-set entropy and sparse randomized embeddings

T0 review · 2 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a k×n sparse random matrix with Bernoulli entries of mean p≈(log k)/k has spectral norm O(√kp) on every fixed r-dimensional subspace, for any k≥C r(log log r)^2.

desk verdict Genuine advance in sparse OSE upper bounds; the n-independent part needs referee verification of an external black box. read the letter →

arxiv 2607.23017 v1 pith:TOFU5ILF submitted 2026-07-25 math.PR cs.DMcs.DS

Konstantin Tikhomirov This is my paper
classification math.PRcs.DMcs.DS MSC 60B2068W20
keywords sparserandommatricesoblivioussubspaceembeddingspectralnormlevel-setentropyKahn–Szemerédiargumentrandomizeddimensionreductionnegativeassociationmatrixuniversality
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 establishes that very sparse random matrices can act as oblivious subspace embeddings with almost minimal row count: for a fixed r-dimensional subspace V and a k×n matrix with independent Bernoulli-sparse centered entries of density p≥(log k)/k, the spectral norm of Π restricted to V is O(√kp) with high probability once k≥C r(log log r)^2. Previously, upper bounds at logarithmic column sparsity required k of order r log r or a slowly growing extra factor; this result leaves only a (log log r)^2 gap from the conjectured optimal k=Ω(r). The proof introduces a new quantitative tool: an entropy bound for the coordinate level sets of unit vectors in V that is independent of ambient dimension n. This repairs the missing row-degree estimate in the classical Kahn–Szemerédi argument, and a Tall–Flat decomposition isolates the heavy-row interactions that entropy alone cannot control. Matching results are proved for fixed-column-degree and SparseStack^T models, and, for the i.i.d. model, for arbitrary n.

What carries the argument

The load-bearing object is the level-set entropy family F_V(β,s), together with the exact entropy bound |F_V(β,s)|≤(β^{−2s}/s!)·binom(r+s−1,s). Counting is reduced to Bombieri–Weyl norms of the polynomials p_I(y)=∏_{i∈I}⟨y,P_V e_i⟩; the Parseval identity closes the count. The second mechanism is the canonical Tall–Flat decomposition: for each vector x, dyadic coordinate levels I_j(x) are assigned row-degree cutoffs K_j=L max{pr_*, p|I_j(x)|}; entries in rows whose mask-degree on a level exceeds K_j are moved to a Flat matrix whose ℓ₂ norm is bounded by a leaf square function of a two-level partition. The Tall matrix is handled by a modified Kahn–Szemerédi envelope summation in which entropy

What would settle it

Check whether the cited matrix universality theorem's hypotheses are satisfied in Proposition 7.7: for q=⌈c_0 log(ek)⌉, verify the moment comparison (49) for sums of Hermitized rank-two matrices with covariance v(I_k⊗U^*P_{H^c}U) and the stated Gaussian target. A concrete numerical check: take n≫r^10, choose V spanned by a random isometry, set k=C r(log log r)^2 and p=(log k)/k, and examine the distribution of ||ΠU_V||/(√kp); consistent values above, say, 10 with non-negligible frequency would contradict Corollary 1.6.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the spectral norm of a sparse random map on a fixed low-dimensional subspace is governed by the number of coordinate patterns that unit vectors in that subspace can actually realize, not by the ambient dimension. Lemma 3.1 bounds the family F_V(β,s) of s-element subsets lying in a β-level set of some unit vector in V by (C(r+s)/(β²s²))^s, via the Parseval identity ∑ᵢ P_V e_i ⊗ P_V e_i = I_V. Combined with a Kahn–Szemerédi light/heavy decomposition, a Tall–Flat partition that zeroes rows that are too heavy on each dyadic level, and an entropy–probability balance for the Flat majorant, this yields Theorem 1.4: under n≤r^10, k≥r log²(en/r)

Load-bearing premise

The load-bearing premise is that the external matrix-universality inequality used in Proposition 7.7 remains valid with moment parameter q≈log k and the Gaussian comparator constructed there; if that black box fails at these parameters, the n-independent form of the main result no longer follows by this proof, though the n≤r^10 bound survives.

Editorial extensions

If this is right

  • If correct, Corollary 1.6 gives the first upper spectral bound O(√kp) for Bernoulli-sparse embeddings at average column sparsity log k and k only a (log log r)^2 factor above the conjectured optimal k=Ω(r).
  • For Rademacher entries, combining with the known lower-edge estimate yields a constant-distortion oblivious subspace embedding at p≍(log k)/k and k≍r(log log r)^2, a direct step toward the fixed-distortion form of the Nelson–Nguyen conjecture.
  • The entropy method replaces trace/Gaussian comparison tools for the upper edge and extends to any support mask that is negatively associated, including fixed-column-degree and SparseStack^T models.
  • For fixed-column-degree and unnormalized SparseStack^T models, Corollary 7.6 gives ||ΠU_V||≤C√d (resp. C√s) with failure probability k^{−B}, so the bound transfers to deterministic column sparsity.

Reading between the lines

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

  • The weakest point of the paper is not the entropy method but the passage from n≤r^10 to arbitrary n: Corollary 1.6 absorbs an external matrix universality theorem at moment parameter q≈log k, whose full hypotheses are not reproduced in the text. A direct verification of that theorem's applicability is the step to scrutinize.
  • The entropy bound is dimension-free and does not rely on negative association; the same level-set counting should control other rectangular random designs as long as the row-degree cutoffs can be defined, such as deterministic column sparsity or matrices with dependent amplitudes.
  • A sharpening of the entropy–probability balance to remove the (log log r)^2 factor would resolve the upper-bound side of the fixed-distortion Nelson–Nguyen problem; the apparent obstruction lies in the Flat-majorant summation over leaf widths.
  • A concrete numerical consequence of the claimed dimension independence: for n≫r^10 and a random r-subspace, the empirical distribution of ||ΠU_V||/(√kp) should concentrate below a universal constant when k=C r(log log r)^2 and p=(log k)/k.
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

2 major / 3 minor

Summary. The paper develops an entropy-based method to bound the spectral norm of a sparse random matrix restricted to a fixed r-dimensional subspace. For an admissible sparse-entry model with a negatively associated support mask and centered entries bounded by one, it proves (Theorem 1.4) that if n≤r^10, k≥r log^2(en/r), and p≥log k/k, then ||ΠU_V||≤C sqrt(kp) with probability at least 1−k^{−B}. The proof combines a new level-set entropy estimate (Lemma 3.1), a Tall–Flat decomposition, a Kahn–Szemerédi envelope for the Tall part, and a leaf-square-function analysis for the Flat part. For the three concrete models (i.i.d., fixed-column-degree, SparseStack^T), a hybrid leverage-score argument (Corollary 1.6) removes the n≤r^10 restriction at the cost of k≥C r(log log r)^2, using a matrix universality theorem of Brailovskaya–van Handel.

Significance. If correct, the n-independent statement gives the first O(sqrt(kp)) upper spectral bound at near-logarithmic sparsity with k superlinear in r by only a (log log r)^2 factor, improving on prior proportional-dimension results. The level-set entropy bound is genuinely novel and dimension-free, and the main theorem's proof is largely self-contained: constants are existential or universal, there is no fitted-parameter circularity, and the central estimates are derived from first principles plus standard concentration lemmas. The main vulnerability is the black-box use of [6] in Proposition 7.7, on which the entire n-independent Corollary 1.6 rests.

major comments (2)
  1. [§7.4, Proposition 7.7 and Corollary 1.6] The n-independent conclusion depends on (49), an application of [6, Theorem 2.9] with q=ceil(c0 log(ek)), q_BvH=2q, and tau=q^{-4}. The hypotheses of [6, Theorem 2.9] are not reproduced, and the proof does not verify them for the specific Hermitian dilations Z_i at these parameters: the definition of R_BvH_{2q}(X), the allowed range of moment parameters, and the exact form of the additive q-dependent term are all taken on faith. The cancellation q^2 sqrt(tau)=1 and the estimate (53) fail if the additive term has a different q-power or if p_BvH=q is outside the theorem's range. Since this is the only step that removes n≤r^10, the authors must state the theorem and check its hypotheses explicitly. This is a load-bearing point, not a matter of presentation.
  2. [§7.4, proof of Corollary 1.6, parameter verification (50)] The verification of (50) is too compressed. The chain N≤k q^4 and the bound (k q^4)^{1/10} log^2(ek q^4) ≤ k are asserted without proof. For k below an absolute threshold the displayed inequality is false; the phrase 'after increasing the universal constant' can absorb this only if the small-k cases are explicitly discharged, e.g., by making the corollary's assumption empty for k below that threshold. Please make this quantitative or state that finitely many small k,r are handled by enlarging the final constant.
minor comments (3)
  1. [Title] The title page shows 'SP ARSE' with an extra space; it should read 'SPARSE'.
  2. [§7.4] In Corollary 1.6, 'R:=max{r, ceil(N^{1/10})}' is typeset with OCR artifacts ('l N 1/10 m'); restore the mathematical notation.
  3. [§7.3, Definition 7.4] The notation SparseStack^T appears both as 'SparseStack^T' and 'SparseStack T' in different places; unify the notation for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main spectral bound is derived from internal entropy and Kahn–Szemerédi arguments plus external published theorems; the only self-citation is not load-bearing.

full rationale

The derivation chain is self-contained with respect to the claimed results. Theorem 1.4 is proved through the Tall–Flat decomposition (Definitions 1.9–1.13), the level-set entropy estimate Lemma 3.1, the subspace-sensitive edge-count Lemma 3.3, and internal Kahn–Szemerédi envelope arguments; none of these inputs assume the target O(sqrt{kp}) bound. Proposition 4.1 handles the Tall term and Section 6 handles the Flat term internally. Corollary 1.6 removes the n≤r^10 restriction by a leverage-score split: the large-leverage part re-applies Theorem 1.4 after extending the subspace to dimension R, while the small-leverage part invokes the external matrix universality theorem [6, Theorem 2.9] in Proposition 7.7, with q and τ chosen so that the q^2√τ factor cancels. The moment hypothesis (52) is derived from the actual column distribution via a binomial bound, not postulated as the desired spectral estimate. The cited universality theorem is external published work, not a self-citation. The only self-citation is [19], used in Definition 7.4 only to identify the unnormalized SparseStack^T model; the admissibility of that model is proved independently in Proposition 7.5, and [19] plays no role in the proof of the spectral bound. No fitted parameters, no renamed empirical pattern, and no imported uniqueness theorem appear. The possible unverified hypotheses of [6, Theorem 2.9] are a correctness or verification concern about an external black box, not evidence of circular dependence of the paper's conclusion on its own inputs.

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

No fitted parameters or postulated physical entities. The 'Tall', 'Flat', 'two-level partition', and 'leaf square function' are mathematical constructions inside the proof, not entities requiring independent evidence. The ledger is dominated by standard concentration tools, the new entropy lemma, and one imported universality theorem.

assumptions (7)
  • standard math Negative-association decoupling: products of nonnegative non-decreasing functions on disjoint blocks factor (Lemma 2.7, eq. (7)).
    Used throughout for row-degree and heavy-row estimates; holds for Bernoulli, sampling-without-replacement, and SparseStack masks.
  • standard math Bombieri-norm estimate |p(y)|≤||p||_* ||y||_2^s and the Parseval identity ∑_i P_V e_i ⊗ P_V e_i = I_V (Lemma 3.1).
    Core of the level-set entropy bound; converts counting of coordinate level sets into a polynomial norm identity.
  • standard math Chernoff and Bernstein concentration for negatively associated 0-1 variables (Lemma 2.7, eqs. (9)–(10)).
    Provides all tail estimates for row degrees and rectangle support-edge counts.
  • domain assumption Brailovskaya–van Handel matrix universality comparison inequality [6, Theorem 2.9] applies at q=⌈c0 log(ek)⌉.
    Imported published theorem used in Proposition 7.7 to remove n≤r^10; the paper states the parameters and comparator but does not reproduce the proof.
  • standard math Gaussian concentration and Gordon-type norm bounds for GB_I via [18, Props. 10.1, 10.3].
    Used to bound the Gaussian comparator in Proposition 7.7.
  • domain assumption Stated hypotheses: p≥(log k)/k, |ξ|≤1, Eξ=0, n≤r^{10}, k≥r log^2(en/r) for Theorem 1.4; Corollary 1.6 removes the n-restriction.
    These are the parameter regimes of the main theorems; p≥(log k)/k is identified as optimal for k polynomial in r.
  • domain assumption Lower-edge estimates of Tropp [28] for the constant-distortion OSE conclusion in Remark 7.8.
    Used only in the final OSE remark, not in the proof of the upper spectral bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Level-set entropy and sparse randomized embeddings." pith.science (2026). https://pith.science/paper/TOFU5ILF

@misc{pith2026260723017,
  author       = {Pith},
  title        = {Pith review of: Level-set entropy and sparse randomized embeddings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TOFU5ILF}},
  note         = {Machine review of arXiv:2607.23017}
}
abstract

Let $\Pi$ be a $k\times n$ sparse random matrix. For a fixed $r$-dimensional subspace $V\subset{\mathbb R}^n$, let $U_V:{\mathbb R}^r\to{\mathbb R}^n$ denote an isometry from ${\mathbb R}^r$ onto $V$. The product $\Pi U_V$ is a central model in randomized dimension reduction and has been studied primarily through trace and Gaussian comparison inequalities. In this work, we develop an approach to the spectral norm of the matrix product $\Pi U_V$, based on entropy estimates for level sets of vectors $x\in V$. Combining the method with existing estimates, we show the following. Assume that \[ k\ge C\,r(\log\log r)^2,\qquad p\ge (\log k)/k. \] Let $\Pi$ be a $k\times n$ matrix with i.i.d. entries equidistributed with the product $b\,\xi$, where $b$ is a Bernoulli($p$) random variable and $\xi$ is mean-zero, independent of $b$, and satisfies $|\xi|\le1$ almost surely. Then with high probability \[ \|\Pi U_V\|\le C\sqrt{kp}. \] Matching results hold for other random models with negatively associated entries.

Figures

Figures reproduced from arXiv: 2607.23017 by the authors.

Figure 1
Figure 1. A canonical Tall–Flat partition for a fixed vector and matrix realiza￾tion. Here k = 6, n = 15, r = 3, p = (log k)/k = (log 6)/6, L = 1, and x = 75−1/2 (4, 4, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1). Thus r∗ = 6 and the integer row￾degree cutoffs for I2(x), I3(x), I4(x) are, respectively, 2, 2, 3. A nonzero entry is orange precisely when its row meets the cutoff on the corresponding level; these entries form the Flat… view at source ↗
Figure 2
Figure 2. High-level organization of the proof. The bound on the supremum of ∥Πx∥2 over the net is obtained via the Tall–Flat canonical decomposition, followed by the modified Kahn–Szemeredi argument for the Tall contribution, relying on the level set entropy bounds. Here J (x) = {i ≤ n : |xi | > r−1/2 ∗ } and ρ = p p/k. We next argue why the first term in (4) is accessible to the Kahn–Szemeredi method. Let J (x) := {i ∈ [n] … view at source ↗
Figure 3
Figure 3. Construction of the canonical Flat row profile and majorant for the Flat matrix in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The entropy–probability balance illustration. The blue band is a co￾ordinate level I ∈ FV (12−1/2 , 12) for an r = 3 dimensional subspace V ⊂ R 100 . The first 16 columns and the final three columns of Π are displayed, while the dots represent columns 17, . . . , 97. T…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 3 linked inside Pith

  1. [12]

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

    2016

  2. [9]

    Chenakkod, M

    S. Chenakkod, M. Derezi´ nski, and X. Dong, Optimal subspace embeddings: Resolving Nelson–Nguyen conjecture up to sub-polylogarithmic factors, preprint, arXiv:2508.14234, 2025

    arXiv 2025

  3. [19]

    Huang, M

    H. Huang, M. Rudelson, and K. Tikhomirov, Well-invertible column subsets of sparse matrices are rare, preprint, arXiv:2607.05384, 2026

    arXiv 2026

  4. [6]

    Brailovskaya and R

    T. Brailovskaya and R. van Handel, Universality and sharp matrix concentration inequalities,Geom. Funct. Anal.34 (2024), no. 6, 1734–1838

    2024

  5. [1]

    Achlioptas, Database-friendly random projections: Johnson–Lindenstrauss with binary coins,J

    D. Achlioptas, Database-friendly random projections: Johnson–Lindenstrauss with binary coins,J. Comput. System Sci.66 (2003), no. 4, 671–687

    2003

  6. [2]

    Ailon and B

    N. Ailon and B. Chazelle, The fast Johnson–Lindenstrauss transform and approximate nearest neighbors,SIAM J. Comput.39 (2009), no. 1, 302–322

    2009

  7. [3]

    Beauzamy, E

    B. Beauzamy, E. Bombieri, P. Enflo, and H. L. Montgomery, Products of polynomials in many variables,J. Number Theory36 (1990), no. 2, 219–245

    1990

  8. [4]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart,Concentration inequalities: A nonasymptotic theory of independence, Oxford University Press, Oxford, 2013

    2013

Show all 30 references
  1. [5]

    Bourgain, S

    J. Bourgain, S. Dirksen, and J. Nelson, Toward a unified theory of sparse dimensionality reduction in Euclidean space,Geom. Funct. Anal.25 (2015), no. 4, 1009–1088

    2015

  2. [7]

    Cama˜ no, E

    C. Cama˜ no, E. N. Epperly, R. A. Meyer, and J. A. Tropp, Faster linear algebra algorithms with structured random matrices, preprint, arXiv:2508.21189, 2025

    2025 arXiv

  3. [8]

    Chenakkod, M

    S. Chenakkod, M. Derezi´ nski, and X. Dong, Optimal oblivious subspace embeddings with near-optimal sparsity, in52nd International Colloquium on Automata, Languages, and Programming, LIPIcs 334, Schloss Dagstuhl– Leibniz-Zentrum f¨ ur Informatik, 2025, Art. 55, 55:1–55:20

    2025

  4. [10]

    Chenakkod, M

    S. Chenakkod, M. Derezi´ nski, X. Dong, and M. Rudelson, Optimal embedding dimension for sparse subspace embeddings, inProceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024, 1106–1117

    2024

  5. [11]

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

    2013

  6. [13]

    Dasgupta, R

    A. Dasgupta, R. Kumar, and T. Sarl´ os, A sparse Johnson–Lindenstrauss transform, inProceedings of the 42nd ACM Symposium on Theory of Computing, 2010, 341–350

    2010

  7. [14]

    Dubhashi and D

    D. Dubhashi and D. Ranjan, Balls and bins: A study in negative dependence,Random Structures Algorithms 13 (1998), no. 2, 99–124

    1998

  8. [15]

    Feige and E

    U. Feige and E. Ofek, Spectral techniques applied to sparse random graphs,Random Structures Algorithms27 (2005), no. 2, 251–275

    2005

  9. [16]

    Friedman, J

    J. Friedman, J. Kahn, and E. Szemer´ edi, On the second eigenvalue of random regular graphs, inProceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, 587–598

    1989

  10. [17]

    Gordon, Some inequalities for Gaussian processes and applications,Israel J

    Y. Gordon, Some inequalities for Gaussian processes and applications,Israel J. Math.50 (1985), 265–289. LEVEL-SET ENTROPY AND SPARSE EMBEDDINGS 53

    1985

  11. [18]

    Halko, P.-G

    N. Halko, P.-G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,SIAM Rev.53 (2011), no. 2, 217–288

    2011

  12. [20]

    Joag-Dev and F

    K. Joag-Dev and F. Proschan, Negative association of random variables with applications,Ann. Statist.11 (1983), no. 1, 286–295

    1983

  13. [21]

    D. M. Kane and J. Nelson, Sparser Johnson–Lindenstrauss transforms,J. ACM61 (2014), no. 1, article 4, 23 pp

    2014

  14. [22]

    R. H. Keshavan, A. Montanari, and S. Oh, Matrix completion from a few entries,IEEE Trans. Inform. Theory 56 (2010), no. 6, 2980–2998

    2010

  15. [23]

    Martinsson and J

    P.-G. Martinsson and J. A. Tropp, Randomized numerical linear algebra: Foundations and algorithms,Acta Numer.29 (2020), 403–572

    2020

  16. [24]

    Nelson and H

    J. Nelson and H. L. Nguyen, OSNAP: Faster numerical linear algebra algorithms via sparser subspace embed- dings, inProceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013, 117–126

    2013

  17. [25]

    Nelson and H

    J. Nelson and H. L. Nguyen, Lower bounds for oblivious subspace embeddings, inAutomata, Languages, and Programming, Lecture Notes in Comput. Sci. 8572, Springer, 2014, 883–894

    2014

  18. [26]

    Oymak and J

    S. Oymak and J. A. Tropp, Universality laws for randomized dimension reduction, with applications,Inf. Infer- ence7 (2018), no. 3, 337–446

    2018

  19. [27]

    T. Sarl´ os, Improved approximation algorithms for large matrices via random projections, inProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, 143–152

    2006

  20. [28]

    J. A. Tropp, Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix,Comm. Amer. Math. Soc., to appear; arXiv:2501.16578, 2026

    2026 arXiv

  21. [29]

    J. A. Tropp, Subspace injections, lecture at the Institute for Computational and Experimental Research in Mathematics (ICERM), Providence, RI, February 4, 2026, slides

    2026

  22. [30]

    D. P. Woodruff, Sketching as a tool for numerical linear algebra,Found. Trends Theor. Comput. Sci.10 (2014), no. 1–2, 1–157. AppendixA.Proof of the standard envelope summation lemma We briefly recall the setup of Lemma 4.10. The parametersk≥d≥3 and 0< p≤1 determine the cutoffρ...

    2014

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.