Norming Sets for Tensor and Polynomial Sketching

Joe Kileel; Yifan Zhang

REVIEW 3 major objections 6 minor 36 references

Norming Sets for Tensor and Polynomial Sketching

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Norming sets make any sketch operator embed algebraic varieties with near-optimal measurement counts.

desk verdict Genuinely new transfer from norming sets to sketching plus a clever median sketch; Section 4.1 is underproved but the main ideas are sound — send it to referees. read the letter →

arxiv 2506.05174 v1 pith:E5VW5FCP submitted 2025-06-05 math.NA cs.ITcs.NAmath.AGmath.IT

Yifan Zhang , Joe Kileel This is my paper

classification math.NAcs.ITcs.NAmath.AGmath.IT MSC 68W2068R1214P0515A6914Q2068Q87

keywords randomizedsketchingdimensionreductionJohnson-Lindenstrausstransformrealalgebraicvarietypolynomialimagetensornormingsetmedianofmeans

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

This paper establishes that norming sets—finite point sets that control polynomial behavior on a set—give a general route to sketching dimensions for real algebraic varieties and images of polynomial maps. It proves that any sketching operator with a known single-vector concentration guarantee embeds such a set once the sketch dimension satisfies a threshold expressed through the variety's dimension and degree, covering tensor-structured and sparse operators that earlier covering-number theory could not handle. It then introduces the median sketch, an odd-sized committee of independent sketches whose median norm is the output, and shows it embeds any such set with total measurement count $C\varepsilon^{-2}(n\log(N/\varepsilon)+\log(1/\delta))$, within logarithmic factors of the lower bound for linear subspaces. This matters because low-rank tensor sets, tensor networks, and other polynomial images arise throughout numerical linear algebra and data science, where fast structured sketches are needed rather than dense Gaussian matrices.

What carries the argument

The central object is the $(d,\omega)$-norming set: a finite subset $Q$ of a bounded set $V$ such that every polynomial of degree at most $d$ satisfies $\sup_V |p| \leq \omega \sup_Q |p|$. For equi-dimensional varieties of degree $D$ and dimension $n$, a bound from Theorem 2.3 guarantees such a set exists with log-cardinality at most $C_1\log D + C_1 n(\log(C_2 n d) - \log\log\omega)$; the paper proves both main theorems by applying this bound to the degree-4 polynomial $p(x) = (\|Sx\|^2-1)^2$ on the spherically normalized variety, whose dimension and degree are controlled by a double-cover argument. The median-sketch proof additionally uses Bernstein's polynomial approximation of the counting function to transfer control from the norming set to the median of the committee.

What would settle it

Compute the minimal $(4,2)$-norming set size for the unit sphere in $\mathbb{R}^N$: if the smallest such set grows faster than $C N\log N$ for fixed $\omega=2$, the cardinality bound behind Theorem 2.7 would be contradicted; alternatively, numerically test the median sketch on the set of $n\times n\times n$ tensors of CP rank 1 with a Kronecker sketch and check whether the total measurement count needed for $(1\pm 0.1)$-norm preservation with failure probability 0.01 stays within $C\varepsilon^{-2} n\log n$ for large $n$.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that a finite norming set stands between single-vector concentration and global embedding: to make a sketch an isometry on an entire variety or polynomial image, it is enough to check the squared norms at the points of a norming set and then apply a union bound. Concretely, Theorem 2.7 states that if the sketch ensemble satisfies the exponential restricted isometry property with tail function $\varphi$, then $\varphi(m,\varepsilon/\sqrt{2}) \geq C_1 \log D + C_1 n\log(C_2 n) + \log(1/\delta)$ suffices for an $(\varepsilon,\delta)$ JLT on a subset of a variety of dimension $n$ and degree $D$, with $\log D$ replaced by $n\log d$ for a polynomial image. For the proposed median sketch, Theorem 3.2 states that a committee of $2k+1$ independent sketches, each bounded on the unit sphere and each succeeding on a fixed vector with failure probability at most $e^{-\theta}$, $\theta > \log 4$, embeds the whole set with high probability once $k \approx C_4(n\log(M/\varepsilon)+\log(1/\delta))$; with each sketch costing $m = O(\varepsilon^{-2})$ measurements, the total is $C\varepsilon^{-2}(n\log(N/\varepsilon)+\log(1/\delta))$, near the $\Omega(\varepsilon^{-2}(n+\log(1/\delta)))$ lower bound for Gaussian embeddings of linear subspaces.

Load-bearing premise

The whole argument rests on the existence of small norming sets for varieties—specifically, the bound that a variety of dimension $n$ and degree $D$ has a norming set of log-size $O(\log D + n\log n)$—and on the accompanying claim that the spherical normalization of the variety has dimension at most $n$ and degree at most $2D$; if either fails, the near-optimal measurement counts in both main theorems fail.

Editorial extensions

If this is right

Sub-Gaussian and fast JL sketches of polynomial images in $n$ variables with degree-$d$ coordinates need only $\widetilde{O}(n\log(nd))$ measurements, improving the earlier $\widetilde{O}(nd\log n)$ covering-number bound.
Tensor-structured and sparse sketch operators, previously lacking variety-embedding guarantees, now inherit near-optimal measurement bounds for low-rank tensor sets and tensor networks.
The median sketch, although nonlinear, is homogeneous and can produce all pairwise distances in a dataset $V$ in $O(kmP^2)$ time after a one-time sketch profile, enabling fast distance queries in optimization.
Any future sketch ensemble with verified single-vector concentration (eRIP) automatically gets a variety-embedding theorem through Theorem 2.7, decoupling sketch design from geometry.

Reading between the lines

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

The norming-set reduction is likely to extend beyond irreducible varieties to semialgebraic sets by partitioning into algebraic strata, which would give structured-sketch guarantees for a much broader class of feasible sets.
The median-of-means mechanism suggests that other robust aggregators (trimmed mean, geometric median) would work as well; the only ingredient needed is a polynomial certificate bounding the number of failed committee members.
The worst-case Bezout degree bound $\log D = n\log d$ may be loose for structured polynomial images such as tensor networks of bounded treewidth, so tighter degree estimates could reduce the measurement count further for specific applications.
Condition (i) in Theorem 3.2 could be enforced in practice by clipping sketch outputs or using subexponential sketches as hinted in Remark 4.5, making the theorem directly implementable with bounded-memory sketches.

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.

Desk Editor's Note

read the letter

Best read as a theoretical contribution to randomized sketching for structured sets. The core is Theorem 2.7: if a sketch ensemble has single-vector eRIP, then a union bound over a degree-4 norming set gives a JLT on an irreducible variety or polynomial image, with the norming-set size doing the work. That connection is new, as far as I know, and it lets you use tensor-structured or sparse operators that old covering-number arguments couldn't handle. The application to sub-Gaussian sketches improves the earlier bound from O(nd log n) to O(n log(nd)), and the comparison with [35], [1], [22] is honest.

The median sketch (Theorem 3.2) is the more substantial piece. The construction — a committee of 2k+1 independent sketches, pick the one with median norm — is simple, and the proof via polynomial approximation of the counting function on a norming set is effective. I checked the key inequalities: η ≤ 1/(3(k+1)) in Lemma 4.3 keeps the count below k+1, θ > log 4 is what the median exponent needs, and M ≥ n_v absorbs the n_v log k term. The total measurement count Õ(ε^{-2} dim V) for structured sketches is close to the subspace lower bound. That's a real result.

Now the soft spots, in proportion. Section 4.1 is the load-bearing geometry and it is underproved. The sentence 'By assumption ψ|W is generically finite-to-1' is wrong as written — no such assumption appears in the theorem. The fact is probably true for irreducible non-cone varieties (the directions of lines contained in V0 form a proper Zariski closed set), but it needs an argument. The degree bound for the spherical normalization and the D=d^n bound for polynomial images are likewise one-line references to Bézout/projective degree; a referee should demand a full proof or a specific citation. These are gaps in exposition, not necessarily flaws — nothing I saw suggests the central claim fails. The degree mismatch in Lemma 4.3 (P has degree 2CM/(εη) while Q's norming degree is CM/(εη)) is a constant-only nuisance. The paper has no experiments, which is fine for a theory paper, but the practical claims about fast low-rank tensor distance evaluation remain unvalidated. And the constants C_d from tensor-moment bounds can be severe, as the paper itself notes in Section 3.1; the near-optimality is up to those constants.

Verdict: this deserves a serious referee. The novel mechanism and the median-sketch result are worth publication if Section 4.1 gets rigor.

Referee Report

3 major / 6 minor

Summary. The paper develops a framework for sketching real algebraic varieties and images of polynomial maps using any random linear sketch operator that satisfies a one-vector concentration (eRIP) condition. The key idea is to replace covering-number arguments with norming sets: Theorem 2.7 reduces the JLT property on a variety or polynomial image to a union bound over a norming set of controlled size, and Theorem 3.2 introduces a median sketch, formed from a committee of 2k+1 independent sketches, that preserves norms on such sets with near-optimal total measurement complexity. Applications to low-rank tensor sets and structured sketches are discussed, and explicit bounds are given for sub-Gaussian, FJLT, and tensor-structured operators.

Significance. If the main results hold, the paper provides a genuinely general and powerful framework: it extends Johnson-Lindenstrauss-type embeddings to infinite nonlinear algebraic sets while allowing structured sketches, and it gives near-linear-in-dimension measurement bounds (up to logarithms) that match the linear-subspace lower bound. The median-sketch construction is elegant, and the strategy of leveraging Altschuler-Parrilo's norming-set theorem to avoid covering numbers is a promising new connection. The proof architecture is largely transparent, and the key probabilistic inequalities (Lemmas 4.3 and 4.4) are checkable and sound. The dependence on the external norming-set bound is explicit and not circular; the authors' previous work appears mainly for comparison. The main weakness is a set of under-proved algebraic-geometry claims in Section 4.1 that are load-bearing for both main theorems.

major comments (3)

[Section 4.1 (proof of Theorem 2.7)] The proof states 'By assumption ψ|W is generically finite-to-1', but no such assumption appears in Theorem 2.7 or its hypotheses. This generic finiteness must be proved for a non-cone irreducible variety V0, and the proof must address directions y for which the line through the origin in direction y is contained in V0, as well as the behavior at λ=0. Since Theorem 2.3 is applied to the Zariski closure π°(V0)^z, the equi-dimensionality claim is load-bearing: if π°(V0)^z is not equi-dimensional, the norming set cardinality bound (3) is not available, and the conclusions of both Theorem 2.7 and Theorem 3.2 lose their support.
[Section 4.1 (degree bound for π°(V0)^z)] The one-sentence argument 'pull back the intersection ... via ψ to W and use that the coordinate functions of ψ are quotients of degree 1 functions' is not a proof of deg(π°(V0)^z) ≤ 2D. The rational map ψ(x,λ)=x/λ is not regular at λ=0, and the degree of the image of a variety under a rational map depends on the base locus and the chosen compactification. A rigorous projective construction (e.g., homogenizing W ⊂ P^{N+1} and realizing ψ as a linear projection) is needed to justify the degree bound used in the norming set count in Eq. (6).
[Section 4.1 (polynomial-image case)] The assertion 'by Bézout's theorem the degree is bounded by log D = n log d' is unjustified. The Zariski closure of p(R^n) is the projection of the graph of p, not the intersection of N hypersurfaces of degree d, so a direct Bezout bound would give D ≤ d^N, which would replace the desired n_v log d by N log d and destroy the near-optimal measurement count in both theorems. The proof must homogenize the map P^n → P^N and invoke a standard bound on the degree of the image of a rational map (e.g., D ≤ d^n) or give an equivalent argument.

minor comments (6)

[Section 4.2 (proof of Theorem 3.2)] In the last displayed paragraph of the proof, 'M ≥ d_v' is a typo; it should read 'M ≥ n_v'.
[Lemma 4.3] The implication 'Since ‖S_i x‖² ≤ M on Q, ‖S_i x‖² ≤ 2M on π°(V)' should explicitly use that Q is a norming set for polynomials up to the degree of p, in particular for the quadratic polynomials ‖S_i x‖²; as written the step is not self-evident.
[Lemma 4.3 and proof of Theorem 3.2] The proof uses a norming set of degree CM/(εη), but the constructed polynomial P has degree 2CM/(εη), so the norming set degree should be doubled. Additionally, the displayed simplification log|Q| ≤ C log D + C n_v log(n_v Mk/ε) appears to drop a log k factor coming from the -log log(1+η) term when η=1/(3(k+1)); the correct expression is log(n_v Mk²/ε) up to constants. These are constant-factor issues that do not change the qualitative statement, but the expressions should be corrected.
[Section 4.1 and Theorem 2.3] Theorem 2.3 assumes compactness, but π°(V) is only bounded in general; the proof of Theorem 2.7 should state that one passes to the Euclidean closure of π°(V), which is compact and contained in π°(V0)^z, so that the sup norms are unchanged.
[Section 1.3] The degree of a real algebraic variety is used throughout (e.g., Theorem 2.3) without a definition; a brief definition or a precise reference to [3] would improve readability.
[Section 1, pairwise-distance discussion] The introduction's claim that pairwise distances can be preserved by replacing V by V−V should be qualified: the theorems are proved for subsets of varieties/polynomial images, and V−V is generally semialgebraic; the paper should either state assumptions under which V−V fits the framework or restrict the pairwise-distance discussion to translates such as the model problem.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorems reduce to the external Altschuler–Parrilo norming-set bound and standard concentration arguments; the authors' self-citations are comparisons, not premises.

full rationale

The paper's central results, Theorem 2.7 and Theorem 3.2, derive measurement-count bounds by combining the external norming-set cardinality theorem of Altschuler and Parrilo (Theorem 2.3) with union bounds, exponential concentration assumptions on the sketch ensemble, and classical polynomial approximation (Bernstein's lemma). The proof of Theorem 2.7 introduces the degree-4 polynomial p(x) = (||Sx||^2 - 1)^2 and uses Theorem 2.3 to pass from a norming set to all of pi^circ(V); this is a standard norming-set reduction, not a recycling of the desired conclusion. Theorem 3.2 similarly uses Theorem 2.3 and a median-of-means concentration lemma, with no fitted parameter being renamed as a prediction. The authors' self-citations, chiefly [35], [36], and [28], appear in comparisons, motivation, or application contexts; none of these is used as a load-bearing premise in the proofs. The degree and dimension bounds for the spherical normalization in Section 4.1 are internal algebraic-geometry arguments, and the polynomial-image estimate log D = n log d is justified as a Bezout bound; even where these arguments are terse, they are not circular. The derivation chain therefore terminates in external, published inputs and standard inequalities rather than in the paper's own claims, so no significant circularity is present.

Assumptions & free parameters 4 free parameters · 6 assumptions · 1 invented entities

Everything load-bearing traces to either the external norming set bound (Theorem 2.3 of [3]), classical concentration inequalities, or two terse in-paper geometric claims (spherical normalization degree and dimension, polynomial-image degree d^n). The sketch-dependent constants M, theta, and C_d are supplied by the user or the sketch family and are not tracked in the headline eO(dim V) count; omega = 2 and eta = 1/(3(k+1)) are slack choices. There are no fitted parameters and no invented physical entities; the median sketch is a new algorithm whose only evidence is the in-paper theorems.

free parameters (4)

M, bounded sketch output norm = O(N) for KFJLT/KR sketches (Remark 3.3); general case user-supplied
Theorem 3.2 condition (i); the final bound carries log(M/epsilon), so M is a supplied constant, not fitted to data.
theta, single-vector failure exponent = any theta > log 4; corollary takes theta = 1 + log 4
Condition (11) in Theorem 3.2; affects the committee size k via the factor (theta - log 4)^-1; a design choice, not fitted.
C_d, tensor sketch moment constant = unspecified; depends on tensor order d
Equation (9) in Example 3.1; enters the per-sketch dimension m = O(C_d epsilon^-2) and hence the total count; the paper does not bound C_d, a gap between the quote and the headline eO(dim V).
omega and eta, norming set slack choices = omega = 2; eta = 1/(3(k+1))
Theorem 2.7 and Lemma 4.3; any omega > 1 and eta <= 1/(3(k+1)) work, affecting only universal constants.

assumptions (6)

domain assumption Norming set cardinality bound for compact subsets of equi-dimensional varieties (Theorem 2.3 of [3]): log|Q| <= C_1 log D + C_1 n(log(C_2 n d) - log log omega)
Quoted as a black box from Altschuler-Parrilo; both main theorems depend on it for the log-size of the test set Q.
domain assumption The spherical normalization of V0 is an equi-dimensional variety of dimension at most n and degree at most 2D
Section 4.1; argued via the double cover W = {(x, lambda): x in V0, lambda^2 = ||x||^2} and generic finiteness of psi(x, lambda) = x/lambda. If false, Theorem 2.3 could not be applied to the sphere projection.
domain assumption For a polynomial map with coordinate degrees at most d from R^n, the Zariski closure of the image has degree at most d^n (log D = n log d)
Stated in Section 4.1 with a one-line Bezout justification; standard result, but the graph-projection argument is omitted and the naive Bezout count on the graph gives d^N.
standard math Bernstein polynomial approximation of ReLU at rate O(1/d) on [-1,1] (Lemma 4.1)
Used to construct the counting polynomials in Lemma 4.2; stated without proof or citation.
domain assumption Single-vector concentration bounds (eRIP) for the sketch ensembles: Bernstein for sub-Gaussian, [14] for FJLT, moment bounds (9) for tensor sketches
Examples 2.9, 2.10, and 3.1; the framework takes such bounds as inputs and their constants enter the final measurement counts.
standard math Median-of-means concentration bound (Lemma 4.4) with binomial coefficient bound via Catalan numbers
Proved in the paper; boosts per-point success probability from constant to 1 - delta across the norming set.

invented entities (1)

median sketch (committee of 2k+1 independent sketches, output is the sketch with median norm)
purpose: Achieving near-optimal total measurement count eO(dim V) for tensor-structured and sparse sketches on varieties and polynomial images, bypassing the Omega(log^d P) barrier for order-d tensor sketches
Not a physical entity; it is the paper's new algorithm. No numerical experiments or external implementations validate it; the only evidence is the in-paper theorems. Marked false because no falsifiable handle outside the paper is provided, though the bounds themselves are testable.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Norming Sets for Tensor and Polynomial Sketching." pith.science (2026). https://pith.science/paper/E5VW5FCP

@misc{pith2026250605174,
  author       = {Pith},
  title        = {Pith review of: Norming Sets for Tensor and Polynomial Sketching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E5VW5FCP}},
  note         = {Machine review of arXiv:2506.05174}
}

abstract

This paper develops the sketching (i.e., randomized dimension reduction) theory for real algebraic varieties and images of polynomial maps, including, e.g., the set of low rank tensors and tensor networks. Through the lens of norming sets, we provide a framework for controlling the sketching dimension for \textit{any} sketch operator used to embed said sets, including sub-Gaussian, fast Johnson-Lindenstrauss, and tensor structured sketch operators. Leveraging norming set theory, we propose a new sketching method called the median sketch. It embeds such a set $V$ using only $\widetilde{\mathcal{O}}(\dim V)$ tensor structured or sparse linear measurements.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 31 canonical work pages

[35]

Covering number of real algebraic varieties and beyond: Improved bounds and applications

Yifan Zhang and Joe Kileel. “Covering number of real algebraic varieties and beyond: Improved bounds and applications”. In:arXiv preprint arXiv:2311.05116(2023)

arXiv 2023
[1]

Oblivious sketching of high-degree polynomial kernels

Thomas D. Ahle, Michael Kapralov, Jakob B.T. Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, and Amir Zandieh. “Oblivious sketching of high-degree polynomial kernels”. In:Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2020, pp. 141–160. 14

work page 2020
[22]

Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs

Linjian Ma and Edgar Solomonik. “Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs”. In:Advances in Neural Information Processing Systems35 (2022), pp. 38980–38993

work page 2022
[2]

Approximate nearest neighbors and the fast Johnson- Lindenstrauss transform

Nir Ailon and Bernard Chazelle. “Approximate nearest neighbors and the fast Johnson- Lindenstrauss transform”. In:Proceedings of the Thirty-Eighth annual ACM Symposium on Theory of Computing. 2006, pp. 557–563

work page 2006
[3]

Kernel approximation on algebraic varieties

Jason M. Altschuler and Pablo A. Parrilo. “Kernel approximation on algebraic varieties”. In:SIAM Journal on Applied Algebra and Geometry7.1 (2023), pp. 1–28

work page 2023
[4]

Johnson–Lindenstrauss embeddings with Kronecker structure

Stefan Bamberger, Felix Krahmer, and Rachel Ward. “Johnson–Lindenstrauss embeddings with Kronecker structure”. In:SIAM Journal on Matrix Analysis and Applications43.4 (2022), pp. 1806–1850

work page 2022
[5]

Springer-Verlag, 2006

Saugata Basu, Richard Pollack, and Marie-Fran¸ coise Roy.Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag, 2006

work page 2006
[6]

Jacek Bochnak, Michel Coste, and Marie-Fran¸ coise Roy.Real Algebraic Geometry. Vol. 36. Springer Science & Business Media, 2013

work page 2013

Show all 36 references

[7]

Tight concentration inequality for sub- weibull random variables with generalized Bernstein Orlicz norm

Heejong Bong and Arun Kumar Kuchibhotla. “Tight concentration inequality for sub- weibull random variables with generalized Bernstein Orlicz norm”. In:arXiv preprint arXiv:2302.03850(2023)

2023 arXiv
[8]

Fekete points as norming sets

Len Bos. “Fekete points as norming sets”. In:Dolomites Research Notes on Approximation 11.DRNA Volume 11.4 (2018), pp. 26–34

2018
[9]

Subspace em- bedding with random Khatri-Rao products and its application to eigensolvers

Zvonimir Bujanovi´ c, Luka Grubiˇ si´ c, Daniel Kressner, and Hei Yin Lam. “Subspace em- bedding with random Khatri-Rao products and its application to eigensolvers”. In:arXiv preprint arXiv:2405.11962(2024)

2024 arXiv
[10]

Optimal approximate matrix product in terms of stable rank

Michael B. Cohen, Jelani Nelson, and David P. Woodruff. “Optimal approximate matrix product in terms of stable rank”. In:arXiv preprint arXiv:1507.02268(2015)

2015 arXiv
[11]

Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions

Alperen A. Erg¨ ur, Grigoris Paouris, and J. Maurice Rojas. “Probabilistic condition number estimates for real polynomial systems I: A broader family of distributions”. In:Foundations of Computational Mathematics19.1 (2019), pp. 131–157

2019
[12]

Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery

Cullen A. Haselby, Mark A. Iwen, Deanna Needell, Michael Perlmutter, and Elizaveta Re- brova. “Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery”. In:Applied and Computational Harmonic Analysis66 (2023), pp. 161–192

2023
[13]

Generative modeling via tensor train sketching

Yoonhaeng Hur, Jeremy G. Hoskins, Michael Lindsey, Edwin M. Stoudenmire, and Yuehaw Khoo. “Generative modeling via tensor train sketching”. In:Applied and Computational Harmonic Analysis67 (2023), p. 101575

2023
[14]

On fast Johnson–Lindenstrauss embeddings of compact submanifolds ofR N with boundary

Mark A. Iwen, Benjamin Schmidt, and Arman Tavakoli. “On fast Johnson–Lindenstrauss embeddings of compact submanifolds ofR N with boundary”. In:Discrete & Computational Geometry(2022), pp. 1–58

2022
[15]

Scalable symmetric Tucker tensor decomposition

Ruhui Jin, Joe Kileel, Tamara G. Kolda, and Rachel Ward. “Scalable symmetric Tucker tensor decomposition”. In:SIAM Journal on Matrix Analysis and Applications45.4 (2024), pp. 1746–1781

2024
[16]

Faster Johnson–Lindenstrauss transforms via Kronecker products

Ruhui Jin, Tamara G. Kolda, and Rachel Ward. “Faster Johnson–Lindenstrauss transforms via Kronecker products”. In:Information and Inference: A Journal of the IMA10.4 (2021), pp. 1533–1562

2021
[17]

Extensions of Lipschitz mappings into a Hilbert space

William B. Johnson, Joram Lindenstrauss, et al. “Extensions of Lipschitz mappings into a Hilbert space”. In:Contemporary Mathematics26.189-206 (1984), p. 1

1984
[18]

PolySketchFormer: Fast trans- formers via sketching polynomial kernels

Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. “PolySketchFormer: Fast trans- formers via sketching polynomial kernels”. In:arXiv preprint arXiv:2310.01655(2023)

2023 arXiv
[19]

Tensor decompositions and applications

Tamara G. Kolda and Brett W. Bader. “Tensor decompositions and applications”. In: SIAM Review51.3 (2009), pp. 455–500. 15

2009
[20]

Estimation of moments of sums of independent real random variables

Rafal Latala. “Estimation of moments of sums of independent real random variables”. In: The Annals of Probability25.3 (1997), pp. 1502–1513

1997
[21]

Near optimal sketching of low-rank tensor regression

Xingguo Li, Jarvis Haupt, and David P. Woodruff. “Near optimal sketching of low-rank tensor regression”. In:Advances in Neural Information Processing Systems30 (2017)

2017
[23]

Guarantees for the Kronecker fast Johnson– Lindenstrauss transform using a coherence and sampling argument

Osman Asif Malik and Stephen Becker. “Guarantees for the Kronecker fast Johnson– Lindenstrauss transform using a coherence and sampling argument”. In:Linear Algebra and its Applications602 (2020), pp. 120–137

2020
[24]

Randomized numerical linear algebra: Foun- dations and algorithms

Per-Gunnar Martinsson and Joel A. Tropp. “Randomized numerical linear algebra: Foun- dations and algorithms”. In:Acta Numerica29 (2020), pp. 403–572

2020
[25]

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Jelani Nelson and Huy L. Nguyen. “OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings”. In:2013 IEEE 54th Annual Symposium on Foundations of Computer Science. 2013, pp. 117–126

2013
[26]

Isometric sketching of any set via the restricted isometry property

Samet Oymak, Benjamin Recht, and Mahdi Soltanolkotabi. “Isometric sketching of any set via the restricted isometry property”. In:Information and Inference: A Journal of the IMA7.4 (2018), pp. 707–726

2018
[27]

Compressed matrix multiplication

Rasmus Pagh. “Compressed matrix multiplication”. In:ACM Transactions on Computa- tion Theory5.3 (2013), pp. 1–17

2013
[28]

Tensor moments of Gaussian mixture models: Theory and applications

Jo˜ ao M. Pereira, Joe Kileel, and Tamara G. Kolda. “Tensor moments of Gaussian mixture models: Theory and applications”. In:arXiv preprint arXiv:2202.06930(2022)

2022 arXiv
[29]

Fast and scalable polynomial kernels via explicit feature maps

Ninh Pham and Rasmus Pagh. “Fast and scalable polynomial kernels via explicit feature maps”. In:Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2013, pp. 239–247

2013
[30]

Estimating higher-order moments using sym- metric tensor decomposition

Samantha Sherman and Tamara G. Kolda. “Estimating higher-order moments using sym- metric tensor decomposition”. In:SIAM Journal on Matrix Analysis and Applications41.3 (2020), pp. 1369–1387

2020
[31]

Sharp bounds on the approximation rates, metric entropy, andn-widths of shallow neural networks

Jonathan W. Siegel and Jinchao Xu. “Sharp bounds on the approximation rates, metric entropy, andn-widths of shallow neural networks”. In:Foundations of Computational Mathematics(2022)

2022
[32]

Roman Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Vol. 47. Cambridge University Press, 2018

2018
[33]

Sketching as a tool for numerical linear algebra

David P. Woodruff. “Sketching as a tool for numerical linear algebra”. In:Foundations and Trends®in Theoretical Computer Science10.1-2 (2014), pp. 1–157

2014
[34]

Stable manifold embed- dings with structured random matrices

Han Lun Yap, Michael B. Wakin, and Christopher J. Rozell. “Stable manifold embed- dings with structured random matrices”. In:IEEE Journal of Selected Topics in Signal Processing7.4 (2013), pp. 720–730

2013
[36]

Moment estimation for nonparametric mixture models through implicit tensor decomposition

Yifan Zhang and Joe Kileel. “Moment estimation for nonparametric mixture models through implicit tensor decomposition”. In:SIAM Journal on Mathematics of Data Sci- ence5.4 (2023), pp. 1130–1159. 16

2023

Pith tools

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

[1] [35]

Covering number of real algebraic varieties and beyond: Improved bounds and applications

Yifan Zhang and Joe Kileel. “Covering number of real algebraic varieties and beyond: Improved bounds and applications”. In:arXiv preprint arXiv:2311.05116(2023)

arXiv 2023

[2] [1]

Oblivious sketching of high-degree polynomial kernels

Thomas D. Ahle, Michael Kapralov, Jakob B.T. Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, and Amir Zandieh. “Oblivious sketching of high-degree polynomial kernels”. In:Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2020, pp. 141–160. 14

work page 2020

[3] [22]

Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs

Linjian Ma and Edgar Solomonik. “Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs”. In:Advances in Neural Information Processing Systems35 (2022), pp. 38980–38993

work page 2022

[4] [2]

Approximate nearest neighbors and the fast Johnson- Lindenstrauss transform

Nir Ailon and Bernard Chazelle. “Approximate nearest neighbors and the fast Johnson- Lindenstrauss transform”. In:Proceedings of the Thirty-Eighth annual ACM Symposium on Theory of Computing. 2006, pp. 557–563

work page 2006

[5] [3]

Kernel approximation on algebraic varieties

Jason M. Altschuler and Pablo A. Parrilo. “Kernel approximation on algebraic varieties”. In:SIAM Journal on Applied Algebra and Geometry7.1 (2023), pp. 1–28

work page 2023

[6] [4]

Johnson–Lindenstrauss embeddings with Kronecker structure

Stefan Bamberger, Felix Krahmer, and Rachel Ward. “Johnson–Lindenstrauss embeddings with Kronecker structure”. In:SIAM Journal on Matrix Analysis and Applications43.4 (2022), pp. 1806–1850

work page 2022

[7] [5]

Springer-Verlag, 2006

Saugata Basu, Richard Pollack, and Marie-Fran¸ coise Roy.Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Springer-Verlag, 2006

work page 2006

[8] [6]

Jacek Bochnak, Michel Coste, and Marie-Fran¸ coise Roy.Real Algebraic Geometry. Vol. 36. Springer Science & Business Media, 2013

work page 2013