Pith. sign in

REVIEW 2 major objections 4 minor 9 cited by

Faster Linear Algebra Algorithms with Structured Random Matrices

T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read A weaker random-matrix condition than full subspace embeddings still guarantees fast, accurate sketching algorithms for low-rank approximation and least-squares regression.

desk verdict OSI is a genuinely useful abstraction that explains why structured sketches match Gaussians; the paper is sound and worth refereeing, with the caveat that some construction-side proofs rest on the authors' own prior results. read the letter →

arxiv 2508.21189 v1 pith:PUSVUI4A submitted 2025-08-28 cs.DS cs.NAmath.NA

Chris Camaño , Ethan N. Epperly , Raphael A. Meyer , Joel A. Tropp This is my paper
classification cs.DScs.NAmath.NA MSC 65F5560B2068W20
keywords oblivioussubspaceinjectionrandomizedlinearalgebrastructuredrandommatriceslow-rankapproximationsketch-and-solvesparseembeddingsKhatri-Raoproductstrigonometrictransforms
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 tries to establish that core randomized linear algebra algorithms work with any random test matrix satisfying a weak condition it calls the oblivious subspace injection (OSI) property, rather than the stronger oblivious subspace embedding (OSE) property usually assumed. An OSI needs only to preserve vector lengths on average and, with high probability, not annihilate any vector in a fixed low-dimensional subspace. Because the condition is weaker, it holds for sparser and more structured random matrices, and the paper proves OSI guarantees for sparse stacks, randomized trigonometric transforms, and tensor-structured Khatri–Rao matrices. The payoff is near-optimal runtimes for several fundamental tasks, with approximation errors within a constant factor of the best possible. The paper also gives implementation guidance and empirical evidence that structured sketches match Gaussian accuracy on a large matrix testbed and in two scientific computing applications.

What carries the argument

The OSI property itself is the central object: a random matrix Omega in F^{d x k} is an (r, alpha)-OSI if it is isotropic, meaning E||Omega^* x||^2 = ||x||^2 for every vector x, and injective, meaning for every fixed r-dimensional subspace V, with probability at least 19/20, alpha ||x||^2 <= ||Omega^* x||^2 for all x in V. It is weaker than an OSE because there is no uniform upper dilation bound. The technical engine is Lemma 2.1, which shows that OSIs respect orthogonality: the norm of the sketched residual B(Q_perp^* Omega)(Q^* Omega)^dagger is bounded by (C/alpha)||B||_F. This single lemma transfers the OSI guarantee to RSVD, Nystrom, generalized Nystrom, and sketch-and-solve analysis. Th

What would settle it

Compute sigma_min^2(Omega^* Q) for a SparseStack matrix with row sparsity zeta = C log r and embedding dimension k = C r applied to the adversarial orthonormal matrix Q = [e_1 ... e_r], across growing r. If, with probability exceeding 1/20, this minimal singular value falls below 1/2, the imported SparseStack OSI guarantee and the runtimes derived from it fail.

Watch

Extended reading notes

Core claim

The central claim is that OSIs suffice for randomized matrix computations. If the test matrix Omega is an (r, alpha)-OSI, then the randomized SVD returns a rank-k approximation whose Frobenius error is at most (C/alpha) times the best rank-r error; Nystrom and generalized Nystrom approximations satisfy analogous nuclear-norm and squared-error bounds; and sketch-and-solve least-squares returns a residual at most (C/alpha) times optimal. The paper then shows that several structured test matrices are OSIs: SparseStack matrices with embedding dimension k = O(r) and row sparsity zeta = O(log r) serve as (r, 1/2)-OSIs; SparseRTT transforms achieve the minimal embedding dimension and minimal sketch

Load-bearing premise

The near-optimal runtime claims rest on two imported probability results—the Gaussian comparison bound for sparse matrices and the coherence bound for randomized trigonometric transforms—holding in exactly the parameter regimes used; the paper cites these results rather than reproving them, so any hidden hypothesis failure would break the stated OSI parameters and runtimes.

Editorial extensions

If this is right

  • Randomized SVD, Nystrom, generalized Nystrom, and sketch-and-solve all produce constant-factor-accurate outputs with any (r, alpha)-OSI, so structured matrices with OSI guarantees can replace Gaussian test matrices without losing approximation quality.
  • SparseStack test matrices with row sparsity O(log r) and embedding dimension O(r) give near-optimal sketching times, including O(nnz(A) log r) sketching for low-rank approximation and improved least-squares runtimes.
  • SparseRTT achieves the minimal embedding dimension and minimal sketching cost among trigonometric-transform test matrices, providing a strong option when sparse linear algebra libraries are unavailable.
  • Khatri–Rao test matrices with spherical base distributions are OSIs; in settings with small tensor order they yield near-optimal low-rank approximations, and bilinear-query structured matrix recovery can be done with O(d) queries.
  • Empirically, SparseStack with constant row sparsity zeta = 4 and embedding dimension k = 2r behaves as an OSI; if the paper's conjecture on constant sparsity is proved, sparse sketching would achieve optimal runtimes for several linear algebra tasks.

Reading between the lines

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

  • The OSI-versus-OSE split suggests re-examining other randomized linear algebra algorithms currently analyzed under OSE assumptions, such as sketch-and-precondition least squares, to see whether injectivity alone suffices; the paper does not make this claim.
  • The exponential dependence on tensor order in the worst-case Khatri–Rao OSI parameters is driven by overwhelming orthogonality; adaptive or coherence-aware base distributions could sidestep worst-case subspaces in practical tensor computations.
  • A proof of the constant-sparsity SparseStack conjecture would convert extensive empirical evidence into an unconditional near-optimal runtime guarantee; until then, the formal runtime claims require zeta = O(log r).
  • The bilinear-query recovery algorithm provides a template: any structured matrix family whose vectorization lies in a d-dimensional span can be approximated with O(d) queries, and concrete next experiments could measure its sample complexity on Toeplitz or bandwidth-limited families.
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 / 4 minor

Summary. The paper introduces the oblivious subspace injection (OSI) property, a weakening of the standard oblivious subspace embedding (OSE) that requires only isotropy and a lower (injectivity) bound on a fixed low-dimensional subspace. It proves that several core randomized linear algebra algorithms—RSVD, Nyström, generalized Nyström, and sketch-and-solve least squares—achieve constant-factor approximations when driven by any OSI with suitable parameters (Section 2, Theorems 1.3 and 1.4). The paper then constructs OSIs from three families of structured random matrices: SparseStack (sparse matrices), SparseRTT (randomized trigonometric transforms), and Khatri–Rao tensor-product test matrices. For SparseStack and SparseRTT this yields improved or near-optimal runtimes for low-rank approximation and least squares; for Khatri–Rao it gives the first OSI-type guarantees, including an optimal query complexity result for approximate matrix recovery from bilinear queries. The paper also contains extensive numerical experiments and two scientific applications (POD compression of a Bose–Einstein condensate simulation and partition-function estimation for a quantum system).

Significance. If the results hold up, this is a valuable conceptual contribution: it isolates a genuinely weaker condition than OSE that still suffices for several flagship randomized linear algebra algorithms, and it provides a clean two-part proof architecture. The algorithm-side results in Section 2 are self-contained and concise, and the empirical validation (Figures 1–10) is unusually thorough, with code publicly available. The construction-side results for Khatri–Rao matrices are new and address a poorly understood area. The main caveat is that some load-bearing construction-side guarantees are imported from the authors' own prior work ([111], [115], [79], [59]), with proofs only sketched or deferred; however, the paper transparently labels these imports and, in the case of SparseStack, provides a full derivation in Appendix B modulo the Gaussian comparison theorem. The central claim—that OSIs suffice for the named algorithms—is supported by direct proofs and does not appear circular.

major comments (2)
  1. [§4.5 / Imported Theorem 4.3] The OSI guarantee for SparseRTT (Theorem 4.2, and hence the runtime claims in Table 4) rests on Imported Theorem 4.3, a coherence bound stated in [111] for the Walsh–Hadamard transform with real Rademacher diagonal. The paper asserts that the result extends to DCT/DFT and to complex Rademacher/Steinhaus entries 'without any additional insight,' but no proof or precise statement is given. Since this is a load-bearing step for the central runtime claims, please provide the extension proof or a precise reference with hypotheses, and verify that the bounded-entry property of DCT/DFT suffices in the complex case.
  2. [§7.3.2, proof of Theorem 4.4] The displayed parameter choice for the column sparsity is inverted. The text reads 'ξ = O(k/(d μ(Q)) log(r/δ))', but the preceding lower bound on λmin contains terms of the form sqrt(d μ(Q)/(kξ) log r) and d μ(Q)/(kξ); to make these small one needs ξ = Ω((d μ(Q)/k) log(r/δ)), not the displayed expression. The theorem statement itself (ξ = O(d μ(Q)/r log r) when k=O(r)) is correct, so this appears to be a typo in the proof, but it should be fixed because it is directly used in the derivation.
minor comments (4)
  1. [§7.3 vs Appendix C] Theorem 7.3 states k ≥ max{3r,131} for real and k ≥ max{18r,169} for complex, while Theorem C.3 in Appendix C gives k ≥ max{4r,10 log(1/δ)} and k ≥ max{18r,57 log(1/δ)}. With δ=1/20 these do not match (e.g., 10 log 20 ≈ 30 vs 131). Please reconcile the constants or clarify that Theorem C.3 is a coarser high-probability statement.
  2. [Figure 1 caption] Typo: 'SparseSuite' should be 'SuiteSparse'.
  3. [§7.3.2, line after Eq. for ξ] Even after correcting the inversion, the choice of log factor inside ξ in the proof text ('log(r/δ)' vs 'log(2d/δ)' in the weak-variance term) should be aligned with the final high-probability statement.
  4. [§1.5.2 / Table 4] The claim that the SparseCol matrix S has 'the minimum possible sparsity' for the class (1.4) is stated as a consequence of [111, Sec. 3.3]. The lower bound in that reference is formulated for subsampled transforms; please clarify the precise class of S to which the lower bound applies and how it rules out sparser S within the general form (1.4).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: OSI is defined independently and the main theorems are proved from that definition using standard decompositions; construction proofs rely on independent published results.

full rationale

The paper's central derivation is not circular. The OSI property (Definition 1.2) is defined independently via isotropy and injectivity, with no reference to low-rank approximation or least-squares error bounds. Section 2 proves Lemma 2.1 and then derives the RSVD, Nyström, generalized Nyström, and sketch-and-solve guarantees (Theorems 2.2, 2.7, Corollaries 2.5 and 2.8) using only this definition plus standard prior error decompositions (Imported Theorem 2.3, Gram correspondence, Lemma 2.6). These imported decompositions are general statements about the algorithms and do not assume the target OSI-based bounds. The construction-side results are also non-circular. The SparseStack OSI guarantee (Imported Theorem 1.8) is actually proved in Appendix B via explicit moment computations for CountSketch and a Gaussian comparison theorem; the proof is given in the paper, not merely cited. The SparseRTT OSI guarantee (Theorem 4.2) is proved in Section 4.5 using an incoherence bound from Tropp [111], which is a prior published theorem about randomized trigonometric transforms with stated assumptions that do not include the OSI conclusion. The Khatri–Rao OSI results (Theorems 5.1 and 5.2) follow from fourth-moment bounds (Oliveira / Tropp) and small-ball methods (Hu–Paouris), again without assuming the OSI parameters being derived. Some imported theorems are authored by members of the same research group ([115], [111], [79]), and they are load-bearing for the construction proofs. However, these are independent published theorems with explicit assumptions and proofs; they are not restatements of the paper's conclusions, not fitted to the paper's data, and not used as a uniqueness argument to forbid alternatives. Under the review rules, such self-citation is normal and does not constitute circularity. No fitted parameter is renamed as a prediction, and no definition reduces to the target result by construction. The only noteworthy caveat is that the extension of the coherence bound to DCT/DFT and complex Rademacher entries is asserted rather than fully reproved; that is a verification/correctness risk, not circularity.

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

The paper's central algorithm-side results rely on the OSI definition and standard linear algebra. The construction-side results depend on imported probabilistic theorems (Oliveira, Tropp, Hu-Paouris, Meyer-Avron) that are not reproved in full in this paper. These are published results from the authors' group or collaborators, so they are reasonable but should be audited for scope and assumptions.

assumptions (5)
  • standard math Tropp's Gaussian comparison theorem [115, Thm. 2.3]
    Used to prove OSI for SparseStack (Appendix B) and SparseCol (Section 7.3.2).
  • standard math Oliveira's fourth-moment bound [92, Thm. 1.1]
    Used to prove Khatri-Rao OSI for constant injectivity (Section 7.1).
  • standard math Hu-Paouris small-ball bound for random tensors [59, Thms. 1.1 and 1.4]
    Used to prove Khatri-Rao OSI with proportional embedding dimension (Section 7.2.1).
  • standard math Meyer-Avron fourth-moment bounds for Kronecker products [79, Thm. 4]
    Provides the moment constants Cν used in Theorem 5.1 (Section 7.1.1).
  • standard math Incoherence bound for randomized trigonometric transforms [111, Lem. 3.3]
    Used in the proof of Theorem 4.2 (SparseRTT) to show the transformed matrix is incoherent.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Linear Algebra Algorithms with Structured Random Matrices." pith.science (2026). https://pith.science/paper/PUSVUI4A

@misc{pith2026250821189,
  author       = {Pith},
  title        = {Pith review of: Faster Linear Algebra Algorithms with Structured Random Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PUSVUI4A}},
  note         = {Machine review of arXiv:2508.21189}
}
read the original abstract

To achieve the greatest possible speed, practitioners regularly implement randomized algorithms for low-rank approximation and least-squares regression with structured dimension reduction maps. Despite significant research effort, basic questions remain about the design and analysis of randomized linear algebra algorithms that employ structured random matrices. This paper develops a new perspective on structured dimension reduction, based on the oblivious subspace injection (OSI) property. The OSI property is a relatively weak assumption on a random matrix that holds when the matrix preserves the length of vectors on average and, with high probability, does not annihilate any vector in a low-dimensional subspace. With the OSI abstraction, the analysis of a randomized linear algebra algorithm factors into two parts: (i) proving that the algorithm works when implemented with an OSI; and (ii) proving that a given random matrix model has the OSI property. This paper develops both parts of the program. First, it analyzes standard randomized algorithms for low-rank approximation and least-squares regression under the OSI assumption. Second, it identifies many examples of OSIs, including random sparse matrices, randomized trigonometric transforms, and random matrices with tensor product structure. These theoretical results imply faster, near-optimal runtimes for several fundamental linear algebra tasks. The paper also provides guidance on implementation, along with empirical evidence that structured random matrices offer exemplary performance for a range of synthetic problems and contemporary scientific applications.

Figures

Figures reproduced from arXiv: 2508.21189 by the authors.

Figure 1
Figure 1. Randomized SVD: Structured vs. Gaussian. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. SparseStack: OSI but not OSE? Estimates for injectivity α (left) and dilation β (right) of SparseStack test matrices (Definition 1.7) with constant row sparsity ζ and embedding dimension k = 2r , applied to subspaces with dimension r = 102 to r = 107 . The markers track the median over 10 trials; shaded regions are bounded by the 10% and 90% quantiles. We estimate α,β by considering the adversarial orthonormal matri… view at source ↗
Figure 3
Figure 3. SparseStack: Acceleration over Gaussian. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Sparse test matrices: Sparsity patterns. [PITH_FULL_IMAGE:figures/full_fig_p025_4.png]
Figure 5
Figure 5. Figure 5: SparseStack versus SparseIID. Relative error∥A − Ab∥ 2 F /∥A∥ 2 F for approximations Ab obtained by the RSVD (Algorithm 1) using a SparseStack (Definition 1.7), a SparseIID (Definition 3.2), or a Gaussian test matrix (Defini￾tion 1.6). We consider four diagonal input m…
Figure 6
Figure 6. Figure 6: Fast trigonometric transform test matrices: Comparison. [PITH_FULL_IMAGE:figures/full_fig_p030_6.png]
Figure 7
Figure 7. Figure 7: Khatri–Rao test matrices: Comparison of base distributions. [PITH_FULL_IMAGE:figures/full_fig_p034_7.png]
Figure 8
Figure 8. Figure 8: Dynamics of imaginary-time Gross–Pitaevskii equation [PITH_FULL_IMAGE:figures/full_fig_p038_8.png]
Figure 9
Figure 9. Figure 9: SparseStack: Scientific data compression. [PITH_FULL_IMAGE:figures/full_fig_p039_9.png]
Figure 10
Figure 10. Figure 10: Khatri–Rao test matrices: Estimating a partition function [PITH_FULL_IMAGE:figures/full_fig_p041_10.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 9 Pith papers

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.

  2. Sharp analysis of sketched least squares and randomized low-rank approximation

    math.NA 2026-05 conditional novelty 8.0 of 10

    Random orthonormal embeddings are minimax optimal for sketched least squares, and rotation-invariant embeddings are minimax optimal for randomized SVD, with sharp error formulas.

  3. Comparison theorems for the extreme eigenvalues of a random symmetric matrix

    math.PR 2026-03 conditional novelty 8.0 of 10

    A comparison theorem shows extreme eigenvalues of independent random matrix sums are dominated by a moment-matched Gaussian matrix, resolving the lower-distortion half of the Nelson-Nguyen conjecture.

  4. Well-invertible column subsets of sparse matrices are rare

    math.PR 2026-07 accept novelty 7.5 of 10

    Under mild sparsity and overlap assumptions, almost every proportional-size column subset of a sparse matrix has smallest singular value o(1), so constant-sparsity SparseStack maps are not (Ω(k), Ω(1))-OSI.

  5. Well-invertible column subsets of sparse matrices are rare

    math.PR 2026-07 accept novelty 7.0 of 10

    Constant-row-sparsity matrices cannot be oblivious subspace injections for proportional subspace dimension, because well-invertible column subsets of sparse matrices are overwhelmingly rare.

  6. Sharp analysis of sketched least squares and randomized low-rank approximation

    math.NA 2026-05 unverdicted novelty 7.0 of 10

    Random orthonormal matrices are minimax optimal for sketched least squares and rotation-invariant embeddings for randomized SVD, yielding the sharpest error bounds.

  7. Oblivious Subspace Injection Is Not Enough for Relative Error

    math.NA 2026-04 unverdicted novelty 7.0 of 10

    OSI alone does not yield relative-error guarantees for sketching; counterexamples for least-squares and randomized SVD show that upper control on the optimal residual is required to recover near-relative error.

  8. Linear-Scaling Tensor Train Sketching

    math.NA 2026-03 accept novelty 7.0 of 10

    TTStack achieves oblivious subspace embedding and injection for tensor trains with sample complexity linear in order d and subspace dimension r, yielding quasi-optimal randomized TT rounding.

  9. Randomized Sketching is Robust to Low-Precision Rounding on GPUs

    cs.PF 2026-06 unverdicted novelty 5.0 of 10

    FP16 SparseStack on GPUs shows embedding quality insensitive to rounding method, with sketch distribution as the primary accuracy driver across tested inputs.

Reference graph

Works this paper leans on

126 extracted references · 39 canonical work pages · cited by 7 Pith papers

  1. [111]

    J. A. T ROPP , Improved analysis of the subsampled randomized hadamard transform, Advances in Adaptive Data Analysis, 3 (2011), pp. 115–126, https://doi.org/https://doi.org/10.1142/S1793536911000787. (Cited on pages 1, 8, 9, 21, 26, 28, 29, and 46.)

    doi:10.1142/s1793536911000787 2011

  2. [115]

    J. A. T ROPP , Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix , Jan. 2025, https://arxiv.org/abs/2501.16578. (Cited on pages 1, 7, 13, 21, 22, 23, 40, 43, 44, 46, and 49.)

    work page Pith review arXiv 2025

  3. [79]

    R. A. M EYER AND H. A VRON , Hutchinson’s estimator is bad at Kronecker-trace-estimation , arXiv preprint arXiv:2309.04952v2, (2025), https://arxiv.org/abs/2309.04952v2. (Cited on pages 10, 29, 33, 38, and 41.)

    arXiv 2025

  4. [59]

    H U AND G

    X. H U AND G. P AOURIS , Small ball probabilities for simple random tensors , arXiv preprint arXiv:2403.20192v1, (2024), https://arxiv.org/abs/arXiv:2403.20192v1. (Cited on pages 34 and 42.)

    arXiv 2024

  5. [1]

    A BDELFATTAH , W

    A. A BDELFATTAH , W. A HRENS , H. A NZT, C. A RMSTRONG , B. B ROCK , A. B ULUC , F . BUSATO , T. C OJEAN , T. D AVIS , J. D EM- MEL , G. D INH , D. G ARDENER , J. F IALA , M. G ATES , A. H AIDER , T. I MAMURA , P . V. LARA , J. M OREIRA , S. L I, P . LUSZCZEK , M. M ELICHENKO , J. M OEIRA , Y. M OKWINSKI , R. M URRAY , S. P ATTY, S. P ELES , T. R IBIZEL ,...

    arXiv 2024

  6. [2]

    A CHLIOPTAS , Database-friendly random projections , in ACM Symposium on Principles of Database Systems, 2001, pp

    D. A CHLIOPTAS , Database-friendly random projections , in ACM Symposium on Principles of Database Systems, 2001, pp. 274–281, https://doi.org/https://doi.org/10.1016/S0022-0000(03)00025-4 . (Cited on pages 1 and 23.)

    doi:10.1016/s0022-0000(03)00025-4 2001

  7. [3]

    T. D. A HLE , M. K APRALOV , J. B. K NUDSEN , R. P AGH , A. V ELINGKER , D. P . WOODRUFF , AND A. Z ANDIEH , Oblivious sketch- ing of high-degree polynomial kernels, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2020, pp. 141–160, https://doi.org/10.1137/1.9781611975994.9. (Cited on pages 1, 10, and 29.)

    work page doi:10.1137/1.9781611975994.9 2020

  8. [4]

    A ILON AND B

    N. A ILON AND B. C HAZELLE , The fast Johnson–Lindenstrauss transform and approximate nearest neighbors, SIAM Journal on Computing, 39 (2009), pp. 302–322,https://doi.org/10.1137/060673096. Appeared in STOC ‘06. (Cited on pages 1, 8, 9, 26, and 27.)

    doi:10.1137/060673096 2009

Show all 126 references
  1. [5]

    A L DAAS , G

    H. A L DAAS , G. B ALLARD , P . CAZEAUX , E. H ALLMAN , A. M I ˛ EDLAR, M. P ASHA , T. W. R EID , AND A. K. S AIBABA , Random- ized algorithms for rounding in the tensor-train format , SIAM Journal on Scientific Computing, 45 (2023), pp. A74–A95, https://doi.org/10.1137/21M145...

    2023 doi

  2. [6]

    A. H. A L-M OHY AND N. J. H IGHAM , Computing the action of the matrix exponential, with an application to exponential integrators, SIAM journal on Scientific Computing, 33 (2011), pp. 488–511, https://doi.org/10.1137/100788860. (Cited on pages 38 and 53.)

    2011 doi

  3. [7]

    A MSEL , P

    N. A MSEL , P . AVI, T. C HEN , F . D. KELES , C. H EGDE , C. M USCO , C. M USCO , AND D. P ERSSON , Query efficient structured matrix learning, arXiv preprint arXiv:2507.19290, (2025), https://www.arxiv.org/pdf/2507.19290. (Cited on page 34.) 53

    2025 arXiv

  4. [8]

    A MSEL , T

    N. A MSEL , T. C HEN , F . D. K ELES , D. H ALIKIAS , C. M USCO , AND C. M USCO , Fixed-sparsity matrix approximation from matrix-vector products, arXiv preprint arXiv:2402.09379v3, (2024), https://arxiv.org/abs/2402.09379v3. (Cited on page 34.)

    2024 arXiv

  5. [9]

    M. H. A NDERSON , J. R. E NSHER , M. R. M ATTHEWS , C. E. W IEMAN , AND E. A. C ORNELL , Observation of bose-einstein condensation in a dilute atomic vapor , science, 269 (1995), pp. 198–201, https://doi.org/10.1126/science.269. 5221.198. (Cited on page 37.)

    1995 doi

  6. [10]

    A NDONI AND H

    A. A NDONI AND H. L. N GUY ˜ÊN, Eigenvalues of a matrix in the streaming model , in Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2013, pp. 1729–1737, https://doi.org/https://doi. org/10.1137/1.9781611973105.124. (Cited on page 11.)

    2013 doi

  7. [11]

    A VRON , P

    H. A VRON , P . MAYMOUNKOV , AND S. T OLEDO , Blendenpik: Supercharging LAPACK’s least-squares solver, SIAM Journal on Scientific Computing, 32 (2010), pp. 1217–1236, https://doi.org/10.1137/090767911. (Cited on pages 1, 2, and 6.)

    2010 doi

  8. [12]

    A VRON , H

    H. A VRON , H. N GUY ˜ÊN, AND D. W OODRUFF , Subspace embeddings for the polynomial kernel , Advances in Neural Infor- mation Processing Systems, 27 (2014), https://dl.acm.org/doi/10.5555/2969033.2969079. (Cited on page 10.)

    2014

  9. [13]

    B AMBERGER , F

    S. B AMBERGER , F . KRAHMER , AND R. W ARD , Johnson–Lindenstrauss embeddings with Kronecker structure, SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 1806–1850, https://doi.org/10.1137/21M1432491. (Cited on page 29.)

    2022 doi

  10. [14]

    A. S. B ANDEIRA , M. T. B OEDIHARDJO , AND R. VAN HANDEL , Matrix concentration inequalities and free probability , Invent. Math., 234 (2023), pp. 419–487, https://doi.org/10.1007/s00222-023-01204-6 , https://doi.org/10. 1007/s00222-023-01204-6 . (Cited on page 46.)

    2023 doi

  11. [15]

    B ARTAN AND M

    B. B ARTAN AND M. P ILANCI , Distributed Sketching Methods for Privacy Preserving Regression , June 2020, https:// arxiv.org/abs/2002.06538. (Cited on page 1.)

    2020 arXiv

  12. [16]

    B ATTAGLINO , G

    C. B ATTAGLINO , G. B ALLARD , AND T. G. KOLDA , A practical randomized CP tensor decomposition, SIAM Journal on Matrix Analysis and Applications, 39 (2018), pp. 876–901, https://doi.org/10.1137/17M1112303. (Cited on page 1.)

    2018 doi

  13. [17]

    B ENNER , R.-C

    P . B ENNER , R.-C. L I, AND N. T RUHAR , On the ADI method for Sylvester equations, Journal of Computational and Applied Mathematics, 233 (2009), pp. 1035–1045, https://doi.org/10.1016/j.cam.2009.08.108. (Cited on page 30.)

    2009 doi

  14. [18]

    B HARADWAJ , O

    V. B HARADWAJ , O. A. M ALIK , R. M URRAY , L. G RIGORI , A. B ULUC , AND J. D EMMEL , Fast exact leverage score sampling from Khatri-Rao products with applications to tensor decomposition , Advances in Neural Information Processing Systems, 37 (2023), pp. 47874–47901, https:/...

    2023

  15. [19]

    D. J. B IAGIONI , D. BEYLKIN , AND G. B EYLKIN , Randomized interpolative decomposition of separated representations, Jour- nal of Computational Physics, 281 (2015), pp. 116–134, https://doi.org/10.1016/j.jcp.2014.10.009. (Cited on page 1.)

    2015 doi

  16. [20]

    B OULLÉ , D

    N. B OULLÉ , D. H ALIKIAS , S. E. O TTO , AND A. T OWNSEND , Operator learning without the adjoint , Journal of Ma- chine Learning Research, 25 (2024), pp. 1–54,https://doi.org/https://dl.acm.org/doi/abs/10.5555/3722577. 3722941. (Cited on page 34.)

    2024 doi

  17. [21]

    B OULLÉ , D

    N. B OULLÉ , D. H ALIKIAS , AND A. T OWNSEND , Elliptic PDE learning is provably data-efficient, Proceedings of the National Academy of Sciences, 120 (2023), p. e2303904120, https://doi.org/10.1073/pnas.2303904120. (Cited on page 34.)

    2023 doi

  18. [22]

    B RAILOVSKAYA AND R

    T. B RAILOVSKAYA AND R. VAN HANDEL , Universality and sharp matrix concentration inequalities , Geom. Funct. Anal., 34 (2024), pp. 1734–1838, https://doi.org/10.1007/s00039-024-00692-9 , https://doi.org/10.1007/ s00039-024-00692-9 . (Cited on page 46.)

    2024 doi

  19. [23]

    B RAVYI , A

    S. B RAVYI , A. C HOWDHURY , D. G OSSET , AND P . WOCJAN , Quantum Hamiltonian complexity in thermal equilibrium, Na- ture Physics, 18 (2022), pp. 1367–1370, https://doi.org/10.1038/s41567-022-01742-5 . (Cited on page 38.)

    2022 doi

  20. [24]

    B UJANOVI ´C, L

    Z. B UJANOVI ´C, L. G RUBIŠI ´C, D. KRESSNER , AND H. Y. L AM, Subspace embedding with random Khatri–Rao products and its application to eigensolvers, IMA Journal of Numerical Analysis, (2025), p. draf043,https://doi.org/10.1093/imanum/ draf043. (Cited on pages 1, 10, 11, 29, ...

    2025 doi

  21. [25]

    C AMAÑO , E

    C. C AMAÑO , E. N. E PPERLY , AND J. A. T ROPP , Successive randomized compression: A randomized algorithm for the com- pressed MPO–MPS product, arXiv preprint 2504.06475v1, (2025), https://arxiv.org/abs/2504.06475v1. (Cited on pages 1, 29, and 30.)

    2025

  22. [26]

    C ARTIS , J

    C. C ARTIS , J. F IALA , AND Z. S HAO , Hashing embeddings of optimal dimension, with applications to linear least squares , arXiv preprint arxiv:2105.11815v1, (2021), https://arxiv.org/abs/2105.11815v1. (Cited on pages 9 and 27.)

    2021 arXiv

  23. [27]

    C HARIKAR , K

    M. C HARIKAR , K. C HEN , AND M. F ARACH -C OLTON , Finding frequent items in data streams , Theoretical Computer Sci- ence, 312 (2004), pp. 3–15, https://doi.org/10.1016/S0304-3975(03)00400-6 . (Cited on pages 24 and 47.)

    2004 doi

  24. [28]

    C HEN AND R

    K. C HEN AND R. J IN, Tensor-structured sketching for constrained least squares, SIAM Journal on Matrix Analysis and Ap- plications, 42 (2021), pp. 1703–1731, https://doi.org/10.1137/20M1374596. (Cited on page 10.)

    2021 doi

  25. [29]

    C HEN , The Lanczos algorithm for matrix functions: A handbook for scientists , Oct

    T. C HEN , The Lanczos algorithm for matrix functions: A handbook for scientists , Oct. 2024, https://arxiv.org/abs/ 2410.11090v1. (Cited on pages 11 and 38.)

    2024 arXiv

  26. [30]

    C HEN , F

    T. C HEN , F . D. KELES , D. H ALIKIAS , C. M USCO , C. M USCO , AND D. P ERSSON , Near-optimal hierarchical matrix approxi- mation from matrix-vector products, in Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Jan. 2025, pp. 2656–2692, https:/...

    2025 doi

  27. [31]

    C HEN , P

    T. C HEN , P . NIROULA , A. R AY, P . SUBRAHMANYA , M. P ISTOIA , AND N. K UMAR , GPU-parallelizable randomized sketch- 54 and-precondition for linear regression using sparse sign sketches , June 2025, https://arxiv.org/abs/2506.03070v2. (Cited on pages 1, 2, 6, 8, 21, 22, 23,...

    2025 arXiv

  28. [32]

    C HENAKKOD , M

    S. C HENAKKOD , M. D EREZI ´NSKI , AND X. D ONG , Optimal oblivious subspace embeddings with near-optimal sparsity , in Proceedings of the 52nd International Colloquium on Automata, Languages and Programming, 2025. Preprint available at https://arxiv.org/abs/2411.08773v2. (Cit...

    2025 arXiv

  29. [33]

    C HENAKKOD , M

    S. C HENAKKOD , M. D EREZI ´NSKI , X. D ONG , AND M. R UDELSON , Optimal embedding dimension for sparse subspace em- beddings, in Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024, pp. 1106–1117, https: //doi.org/10.1145/3618260.3649762. (Cited on pages...

    2024

  30. [34]

    K. L. C LARKSON AND D. P . WOODRUFF , Numerical linear algebra in the streaming model, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 205–214, https://doi.org/10.1145/1536414.1536445. (Cited on pages 1 and 19.)

    2009

  31. [35]

    K. L. C LARKSON AND D. P . WOODRUFF , Low-rank approximation and regression in input sparsity time , Journal of the ACM, 63 (2017), pp. 1–45, https://doi.org/10.1145/3019134. Appeared in STOC ‘13. (Cited on pages 1, 7, 19, 21, 22, 24, and 47.)

    2017 doi

  32. [36]

    M. B. C OHEN , Nearly tight oblivious subspace embeddings by trace inequalities, in Proceedings of the 27th Annual ACM- SIAM Symposium on Discrete Algorithms, 2016, pp. 278–287, https://doi.org/10.1137/1.9781611974331.ch21. (Cited on pages 7, 8, 21, 22, and 23.)

    2016 doi

  33. [37]

    D ASGUPTA , R

    A. D ASGUPTA , R. K UMAR , AND T. S ARLOS , A sparse Johnson–Lindenstrauss transform , in Proceedings of the 42nd ACM Symposium on Theory of Computing, June 2010, pp. 341–350, https://doi.org/10.1145/1806689.1806737. (Cited on page 22.)

    2010

  34. [38]

    T. A. D AVIS AND Y. H U, The university of Florida sparse matrix collection , ACM Transactions on Mathematical Software, 38 (2011), pp. 1–25, https://doi.org/10.1145/2049662.2049663. (Cited on page 2.)

    2011

  35. [39]

    D AWSON , The proper orthogonal decomposition , Cambridge University Press, Jan

    S. D AWSON , The proper orthogonal decomposition , Cambridge University Press, Jan. 2023, pp. 117–132, https://doi. org/10.1017/9781108896214.011. (Cited on page 37.)

    2023 doi

  36. [40]

    D EREZI ´NSKI , Algorithmic gaussianization through sketching: Converting data into sub-gaussian random designs , in The 36th Annual Conference on Learning Theory, 2023, pp

    M. D EREZI ´NSKI , Algorithmic gaussianization through sketching: Converting data into sub-gaussian random designs , in The 36th Annual Conference on Learning Theory, 2023, pp. 3137–3172. (Cited on page 1.)

    2023

  37. [41]

    D ONG AND P .-G

    Y. D ONG AND P .-G. MARTINSSON , Simpler is better: A comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Advances in Computational Mathematics, 49 (2023), p. 66, https://doi.org/10.1007/ s10444-023-10061-z . (Cited on pages 1, 2, 6, 8...

    2023

  38. [42]

    D RINEAS , R

    P . D RINEAS , R. K ANNAN , AND M. W. M AHONEY , Fast Monte Carlo algorithms for matrices. II. Computing a low-rank ap- proximation to a matrix, SIAM J. Comput., 36 (2006), pp. 158–183, https://doi.org/10.1137/S0097539704442696, https://doi.org/10.1137/S0097539704442696. (Cite...

    2006 doi

  39. [43]

    D RINEAS AND M

    P . D RINEAS AND M. W. M AHONEY , On the Nyström method for approximating a Gram matrix for improved kernel- based learning, Journal of Machine Learning Research, 6 (2005), pp. 2153–2175, https://dl.acm.org/doi/10.5555/ 1046920.1194916. (Cited on page 17.)

    2005

  40. [44]

    D RINEAS AND M

    P . D RINEAS AND M. W. M AHONEY , Lectures on randomized numerical linear algebra , American Mathematical Society, 3 (2018), https://arxiv.org/pdf/1712.08880. (Cited on pages 1, 2, 5, and 16.)

    2018 arXiv

  41. [45]

    D RINEAS , M

    P . D RINEAS , M. W. M AHONEY , S. M UTHUKRISHNAN , AND T. S ARLÓS , Faster least squares approximation , Numerische mathematik, 117 (2011), pp. 219–249, https://doi.org/10.1007/s00211-010-0331-6 . (Cited on pages 1 and 19.)

    2011 doi

  42. [46]

    E. N. E PPERLY , Which sketch should I use? , Nov. 2023, https://www.ethanepperly.com/index.php/2023/11/27/ which-sketch-should-i-use/ . (Cited on pages 1, 2, 6, 21, 23, and 27.)

    2023

  43. [47]

    E. N. E PPERLY , Low-rank approximation toolbox: The Gram correspondence, Dec. 2024, https://www.ethanepperly. com/index.php/2024/12/07/low-rank-approximation-toolbox-the-gram-correspondence/ . (Cited on page 17.)

    2024

  44. [48]

    E. N. E PPERLY , M. M EIER , AND Y. NAKATSUKASA , Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers , arXiv preprint arXiv:2406.03468v2, (2024), https://arxiv.org/abs/2406.03468v2. (Cited on pages 6, 8, 21, and 22.)

    2024 arXiv

  45. [49]

    E. N. E PPERLY , J. A. T ROPP, AND R. J. W EBBER , Xtrace: Making the most of every sample in stochastic trace estima- tion, SIAM Journal on Matrix Analysis and Applications, 45 (2024), pp. 1–23, https://doi.org/10.1137/23M1548323. (Cited on pages 11, 36, 39, and 53.)

    2024 doi

  46. [50]

    F ELDMAN , A

    N. F ELDMAN , A. K SHETRIMAYUM , J. E ISERT , AND M. G OLDSTEIN , Entanglement estimation in tensor network states via sampling, PRX Quantum, 3 (2022), p. 030312,https://doi.org/10.1103/PRXQuantum.3.030312. (Cited on pages 29, 30, 33, and 38.)

    2022 doi

  47. [51]

    F RIEZE , R

    A. F RIEZE , R. K ANNAN , AND S. V EMPALA , Fast Monte-Carlo algorithms for finding low-rank approximations, in Proc. 39th Ann. Symp. Foundations of Computer Science (Cat. No.98CB36280), 1998, pp. 370–378, https://doi.org/10.1109/ SFCS.1998.743487. (Cited on page 1.)

    1998

  48. [52]

    Program Generation, Optimization, and Platform Adaptation

    M. F RIGO AND S. G. J OHNSON , The design and implementation of FFTW3, Proceedings of the IEEE, 93 (2005), pp. 216–231, https://doi.org/10.1109/JPROC.2004.840301. Special issue on “Program Generation, Optimization, and Platform Adaptation” . (Cited on page 8.) 55

    2005

  49. [53]

    D. G IRARD , Un algorithme simple et rapide pour la validation croisée généralisée sur des problèmes de grande taille, IMAG, 1987, http://www-ljk.imag.fr/membres/Didier.Girard/TR-665-M-IMAG.pdf . (Cited on page 38.)

    1987

  50. [54]

    G ITTENS , The spectral norm error of the naïve Nyström extension , arXiv preprint arXiv:1110.5305v1, (2011), https: //arxiv.org/abs/1110.5305v1

    A. G ITTENS , The spectral norm error of the naïve Nyström extension , arXiv preprint arXiv:1110.5305v1, (2011), https: //arxiv.org/abs/1110.5305v1. (Cited on page 17.)

    2011 arXiv

  51. [55]

    G ITTENS AND M

    A. G ITTENS AND M. W. M AHONEY , Revisiting the Nyström method for improved large-scale machine learning , The Jour- nal of Machine Learning Research, 17 (2016), pp. 3977–4041, https://doi.org/https://dl.acm.org/doi/abs/10. 5555/2946645.3007070. (Cited on pages 5, 16, and 17.)

    2016

  52. [56]

    G UÉDON , F

    O. G UÉDON , F . KRAHMER , C. K ÜMMERLE , S. M ENDELSON , AND H. R AUHUT , On the geometry of polytopes generated by heavy-tailed random vectors , Communications in Contemporary Mathematics, 24 (2022), pp. Paper No. 2150056, 31, https://doi.org/10.1142/S0219199721500565. (Cite...

    2022 doi

  53. [57]

    H ALIKIAS AND A

    D. H ALIKIAS AND A. T OWNSEND , Structured matrix recovery from matrix-vector products, Numerical Linear Algebra with Applications, 31 (2024), p. e2531, https://doi.org/10.1002/nla.2531. (Cited on page 34.)

    2024 doi

  54. [58]

    H ALKO , P .-G

    N. H ALKO , P .-G. M ARTINSSON , AND J. A. T ROPP , Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions , SIAM Review, 53 (2011), pp. 217–288, https://doi.org/10.1137/ 090771806. (Cited on pages 1, 2, 5, 8, 15, 16, and 17.)

    2011

  55. [60]

    M. F . H UTCHINSON , A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines , Communications in Statistics-Simulation and Computation, 18 (1989), pp. 1059–1076, https://doi.org/10.1080/ 03610919008812866. (Cited on page 38.)

    1989

  56. [61]

    R. J IN, J. K ILEEL , T. G. K OLDA , AND R. W ARD , Scalable Symmetric Tucker Tensor Decomposition, SIAM Journal on Matrix Analysis and Applications, 45 (2024), pp. 1746–1781, https://doi.org/10.1137/23M1582928. (Cited on page 29.)

    2024 doi

  57. [62]

    R. J IN, T. G. K OLDA , AND R. W ARD , Faster Johnson-Lindenstrauss Transforms via Kronecker Products , Information and Inference: A Journal of the IMA, 10 (2021), pp. 1533–1562, https://doi.org/10.1093/imaiai/iaaa028. (Cited on page 29.)

    2021 doi

  58. [63]

    D. M. K ANE AND J. N ELSON , Sparser Johnson-Lindenstrauss transforms, Journal of the ACM, 61 (2014), pp. 1–23, https: //doi.org/10.1145/2559902. Appeared in SODA ‘12. (Cited on pages 1, 6, and 22.)

    2014 doi

  59. [64]

    K APRALOV , V

    M. K APRALOV , V. P OTLURU , AND D. W OODRUFF , How to fake multiply by a gaussian matrix , in Proceedings of The 33rd International Conference on Machine Learning, M. F . Balcan and K. Q. Weinberger, eds., vol. 48 of Proceedings of Ma- chine Learning Research, New York, New Y...

    2016

  60. [65]

    K IREEVA AND J

    A. K IREEVA AND J. A. T ROPP , Randomized matrix computations: Themes and variations , Caltech CMS Lecture Notes 2023-02, Caltech, Pasadena, 2023, https://doi.org/10.7907/7yade-5k351. CIME Summer School on Machine Learning, Cetraro, Calabria, July 2023. To appear in CIME Lectu...

    2023 doi

  61. [66]

    T. G. K OLDA AND B. W. B ADER , Tensor decompositions and applications, SIAM Review, 51 (2009), pp. 455–500, https: //doi.org/10.1137/07070111X. (Cited on pages 10 and 30.)

    2009 doi

  62. [67]

    K OLTCHINSKII AND S

    V. K OLTCHINSKII AND S. M ENDELSON , Bounding the smallest singular value of a random matrix without concentra- tion, International Mathematics Research Notices, 2015 (2015), pp. 12991–13008, https://doi.org/10.1093/imrn/ rnv096. (Cited on pages 1, 12, 13, and 41.)

    2015 doi

  63. [68]

    B. W. L ARSEN AND T. G. K OLDA , Sketching matrix least squares via leverage scores estimates , arXiv preprint arXiv:2201.10638v1, (2022), https://arxiv.org/abs/2201.10638v1. (Cited on page 30.)

    2022

  64. [69]

    H. L I, G. C. L INDERMAN , A. S ZLAM , K. P . S TANTON , Y. K LUGER , AND M. T YGERT , Algorithm 971: An implementation of a randomized algorithm for principal component analysis , ACM Transactions on Mathematical Software, 43 (2017), https://doi.org/10.1145/3004053. (Cited on...

    2017 doi

  65. [70]

    Y. L I, H. L. N GUY ˜ÊN, AND D. P . WOODRUFF , On sketching matrix norms and the top singular vector , in Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2014, pp. 1562–1581,https://doi.org/ https://doi.org/10.1137/1.9781611973402.114. (...

    2014 doi

  66. [71]

    M A AND E

    L. M A AND E. S OLOMONIK , Cost-efficient Gaussian tensor network embeddings for tensor-structured inputs , Advances in Neural Information Processing Systems, 35 (2022), pp. 38980–38993, https://dl.acm.org/doi/abs/10.5555/ 3600270.3603095. (Cited on page 29.)

    2022

  67. [72]

    M. W. M AHONEY AND P . DRINEAS , Structural properties underlying high-quality randomized numerical linear algebra algorithms, in Handbook of Big Data, P . Bühlmann, P . Drineas, M. J. Kane, and M. J. van der Laan, eds., Chapman and Hall/CRC, 2016, pp. 137–154, https://doi.org...

    2016 doi

  68. [73]

    M ARTINSSON AND J

    P .-G. M ARTINSSON AND J. A. T ROPP , Randomized numerical linear algebra: Foundations and algorithms, Acta Numerica, 29 (2020), pp. 403–572, https://doi.org/10.1017/S0962492920000021. (Cited on pages 1, 2, 5, 6, 9, and 17.)

    2020 doi

  69. [74]

    M ELNICHENKO , O

    M. M ELNICHENKO , O. B ALABANOV , R. M URRAY , J. D EMMEL , M. W. M AHONEY , AND P . LUSZCZEK , CholeskyQR with randomization and pivoting for tall matrices (CQRRPT) , SIAM Journal on Matrix Analysis and Applications, 46 (2025), pp. 1701–1734, https://doi.org/https://doi.org/1...

    2025 doi

  70. [75]

    M ENDELSON , A remark on the diameter of random sections of convex bodies , in Geometric aspects of functional anal- ysis, vol

    S. M ENDELSON , A remark on the diameter of random sections of convex bodies , in Geometric aspects of functional anal- ysis, vol. 2116 of Lecture Notes in Math, Springer International Publishing, 2014, pp. 395–404, https://doi.org/10. 1007/978-3-319-09477-9_25 . (Cited on page 41.)

    2014

  71. [76]

    M ENDELSON , Learning without concentration, Journal of the ACM, 62 (2015), pp

    S. M ENDELSON , Learning without concentration, Journal of the ACM, 62 (2015), pp. 1–25, https://doi.org/10.1145/ 2699439. (No citations.)

    2015

  72. [77]

    M ENDELSON , Learning without concentration for general loss functions , Probability Theory and Related Fields, 171 (2018), pp

    S. M ENDELSON , Learning without concentration for general loss functions , Probability Theory and Related Fields, 171 (2018), pp. 459–502, https://doi.org/10.1007/s00440-017-0784-y . (Cited on page 41.)

    2018 doi

  73. [78]

    M ENG AND M

    X. M ENG AND M. W. M AHONEY , Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, June 2013, pp. 91–100, https://doi.org/10.1145/2488608.2488621. (Cited ...

    2013

  74. [80]

    R. A. M EYER , C. M USCO , C. M USCO , AND D. P . WOODRUFF , Hutch++: Optimal stochastic trace estimation , in Sympo- sium on Simplicity in Algorithms, Jan. 2021, pp. 142–155, https://doi.org/10.1137/1.9781611976496.16. (Cited on pages 11, 36, and 39.)

    2021 doi

  75. [81]

    R. A. M EYER , W. S WARTWORTH , AND D. P . WOODRUFF , Understanding the Kronecker matrix-vector complexity of linear algebra, in Proceedings of the 42nd International Conference on Machine Learning, 2025. To appear, preprint available at https://arxiv.org/abs/2502.08029v2. (Ci...

    2025 arXiv

  76. [82]

    M OHRI , A

    M. M OHRI , A. R OSTAMIZADEH , AND A. T ALWALKAR , Foundations of machine learning , Adaptive Computation and Ma- chine Learning, MIT Press, 2012,http://mitpress.mit.edu/books/foundations-machine-learning-0 . (Cited on pages 50 and 51.)

    2012

  77. [83]

    M OTTA , C

    M. M OTTA , C. S UN, A. T. T AN, M. J. O’R OURKE , E. Y E, A. J. M INNICH , F . G. BRANDAO , AND G. K.-L. C HAN , Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution , Nature Physics, 16 (2020), pp. 205–210, https://doi.org/1...

    2020 doi

  78. [84]

    M URRAY , J

    R. M URRAY , J. D EMMEL , M. W. M AHONEY , N. B. E RICHSON , M. M ELNICHENKO , O. A. M ALIK , L. G RIGORI , P . LUSZCZEK , M. D EREZI ´NSKI , M. E. L OPES , T. L IANG , H. L UO, AND J. D ONGARRA , Randomized numerical linear algebra: A perspec- tive on the field with an eye to...

    2023 arXiv

  79. [85]

    R. J. M URRAY , Bringing randomized algorithms to mainstream numerical linear algebra , tech. report, Sandia National Lab.(SNL-CA), Livermore, CA (United States), 2024, https://doi.org/https://doi.org/10.2172/2462906. (Cited on page 6.)

    2024 doi

  80. [86]

    M USCO AND C

    C. M USCO AND C. M USCO , Randomized block krylov methods for stronger and faster approximate singular value decom- position, Advances in Neural Information Processing Systems, 28 (2015), https://proceedings.neurips.cc/paper_ files/paper/2015/file/1efa39bcaec6f3900149160693694...

    2015

  81. [87]

    N AKATSUKASA , Fast and stable randomized low-rank matrix approximation, arXiv preprint arXiv:2009.11392v1, (2020), https://arxiv.org/abs/2009.11392v1

    Y. N AKATSUKASA , Fast and stable randomized low-rank matrix approximation, arXiv preprint arXiv:2009.11392v1, (2020), https://arxiv.org/abs/2009.11392v1. (Cited on pages 1, 8, 19, 20, and 25.)

    2009 arXiv

  82. [88]

    N AKATSUKASA AND J

    Y. N AKATSUKASA AND J. A. T ROPP , Fast and Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems, SIAM Journal on Matrix Analysis and Applications, 45 (2024), pp. 1183–1214,https://doi.org/10.1137/23M1565413. (Cited on pages 6, 8, and 25.)

    2024 doi

  83. [89]

    N EEDELL , W

    D. N EEDELL , W. S WARTWORTH , AND D. P . WOODRUFF , Testing positive semidefiniteness using linear measurements , in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 87–97,https://doi. org/10.1109/FOCS54457.2022.00016. (Cited on page 11.)

    2022

  84. [90]

    N ELSON AND H

    J. N ELSON AND H. L. N GUY ˜ÊN, OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings , in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 117–126,https: //doi.org/10.1109/FOCS.2013.21. (Cited on page...

    2013 doi

  85. [91]

    N ELSON AND H

    J. N ELSON AND H. L. N GUY ˜ÊN, Lower bounds for oblivious subspace embeddings , in International Colloquium on Au- tomata, Languages, and Programming, Springer, 2014, pp. 883–894, https://doi.org/https://doi.org/10.1007/ 978-3-662-43948-7_73 . (Cited on pages 8 and 24.)

    2014

  86. [92]

    R. I. O LIVEIRA , The lower tail of random quadratic forms with applications to ordinary least squares , Probability Theory and Related Fields, 166 (2016), pp. 1175–1194, https://doi.org/10.1007/s00440-016-0738-9 . (Cited on pages 1, 12, 33, and 40.)

    2016 doi

  87. [93]

    O RÚS , Tensor networks for complex quantum systems, Nature Reviews Physics, 1 (2019), pp

    R. O RÚS , Tensor networks for complex quantum systems, Nature Reviews Physics, 1 (2019), pp. 538–550, https://doi. org/10.1038/s42254-019-0086-7 . (Cited on pages 30, 33, and 38.)

    2019 doi

  88. [94]

    P ARULEKAR , A

    A. P ARULEKAR , A. P ARULEKAR , AND E. P RICE , L1 regression with lewis weights subsampling, Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques, (2021), https://doi.org/https://doi.org/10. 4230/LIPIcs.APPROX/RANDOM.2021.49. (Cited on page 19.)

    2021

  89. [95]

    P ERSSON , A

    D. P ERSSON , A. C ORTINOVIS , AND D. K RESSNER , Improved variants of the Hutch++ algorithm for trace estimation , SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 1162–1185,https://doi.org/10.1137/21M1447623. (Cited on pages 11, 36, 39, and 53.) 57

    2022 doi

  90. [96]

    P ERSSON , R

    D. P ERSSON , R. A. M EYER , AND C. M USCO , Algorithm-agnostic low-rank approximation of operator monotone matrix functions, SIAM Journal on Matrix Analysis and Applications, 46 (2025), pp. 1–21, https://doi.org/https://doi. org/10.1137/23M1619435. (Cited on page 17.)

    2025 doi

  91. [97]

    P FEUTY , The one-dimensional Ising model with a transverse field , Annals of Physics, 57 (1970), pp

    P . P FEUTY , The one-dimensional Ising model with a transverse field , Annals of Physics, 57 (1970), pp. 79–90, https: //doi.org/10.1016/0003-4916(70)90270-8 . (Cited on page 39.)

    1970 doi

  92. [98]

    P HAM AND R

    N. P HAM AND R. P AGH , Fast and scalable polynomial kernels via explicit feature maps , in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’13, 2013, pp. 239–247, https:// doi.org/10.1145/2487575.2487591. (Cited on page 29.)

    2013

  93. [99]

    R AKHSHAN AND G

    B. R AKHSHAN AND G. R ABUSSEAU , Tensorized random projections, in International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 3306–3316, https://proceedings.mlr.press/v108/rakhshan20a.html. (Cited on pages 1 and 10.)

    2020

  94. [100]

    B. T. R AKHSHAN AND G. R ABUSSEAU , Rademacher random projections with tensor networks, Feb. 2022, https://arxiv. org/abs/2110.13970. (Cited on page 29.)

    2022 arXiv

  95. [101]

    R ASHTCHIAN , D

    C. R ASHTCHIAN , D. P . W OODRUFF , AND H. Z HU, Vector-matrix-vector queries for solving linear algebra, statistics, and graph problems, arXiv preprint arXiv:2006.14015, (2020), https://doi.org/10.48550/arXiv.2006.14015. (Cited on page 11.)

    2006 doi arXiv

  96. [102]

    R OKHLIN AND M

    V. R OKHLIN AND M. T YGERT , A fast randomized algorithm for overdetermined linear least-squares regression, Proceedings of the National Academy of Sciences, 105 (2008), pp. 13212–13217, https://doi.org/https://doi.org/10.1073/ pnas.0804869105. (Cited on pages 1 and 6.)

    2008

  97. [103]

    A. K. S AIBABA AND A. M I ˛ EDLAR, Randomized low-rank approximations beyond gaussian random matrices, SIAM Journal on Mathematics of Data Science, 7 (2025), pp. 136–162, https://doi.org/https://doi.org/10.1137/23M1593255. (Cited on pages 5 and 16.)

    2025 doi

  98. [104]

    A. K. S AIBABA , B. D. V ERMA , AND G. B ALLARD , Improved analysis of khatri-rao random projections and applications , arXiv preprint arXiv:2507.23207, (2025), https://doi.org/10.48550/arXiv.2507.23207. (Cited on pages 11 and 35.)

    2025 doi

  99. [105]

    T. S ARLOS , Improved approximation algorithms for large matrices via random projections, in 2006 47th annual IEEE sym- posium on foundations of computer science (FOCS’06), IEEE, 2006, pp. 143–152, https://doi.org/10.1109/FOCS. 2006.37. (Cited on pages 1, 2, 5, and 18.)

    2006 doi

  100. [106]

    S HALEV -S HWARTZ AND S

    S. S HALEV -S HWARTZ AND S. B EN-D AVID , Understanding machine learning: From theory to algorithms , Cambridge uni- versity press, 2014, https://doi.org/https://doi.org/10.1017/CBO9781107298019. (Cited on page 51.)

    2014 doi

  101. [107]

    S HEN , K

    Y. S HEN , K. K LYMKO , E. R ABANI , N. M. T UBMAN , D. C AMPS , R. V AN BEEUMEN , AND M. L INDSEY , Simple diagonal de- signs with reconfigurable real-time circuits, arXiv preprint arXiv:2401.04176v3, (2024), https://arxiv.org/abs/2401. 04176v3. (Cited on page 38.)

    2024

  102. [108]

    S LADE , The fast fourier transform in hardware: A tutorial based on an FPGA implementation

    G. S LADE , The fast fourier transform in hardware: A tutorial based on an FPGA implementation . Research- Gate, Mar. 2013, https://www.researchgate.net/publication/235995761_The_Fast_Fourier_Transform_in_ Hardware_A_Tutorial_Based_on_an_FPGA_Implementation. (Cited on page 9.)

    2013

  103. [109]

    H. V. S ORENSEN AND C. S. B URRUS , Efficient computation of the DFT with only a subset of input or output points , IEEE transactions on signal processing, 41 (1993), pp. 1184–1200, https://doi.org/10.1109/78.205723. (Cited on page 26.)

    1993 doi

  104. [110]

    S WARTWORTH AND D

    W. S WARTWORTH AND D. P . WOODRUFF , Optimal eigenvalue approximation via sketching, in Proceedings of the 55th An- nual ACM Symposium on Theory of Computing, 2023, pp. 145–155, https://doi.org/Pages145-155https://doi. org/10.1145/3564246.3585102. (Cited on page 11.)

    2023

  105. [112]

    J. A. T ROPP , Convex recovery of a structured signal from independent random linear measurements , Sampling theory, a renaissance, (2015), pp. 67–101, https://doi.org/https://doi.org/10.1007/978-3-319-19749-4_2 . (Cited on page 50.)

    2015 doi

  106. [113]

    J. A. T ROPP , An introduction to matrix concentration inequalities, Foundations and Trends in Machine Learning, 8 (2015), pp. 1–230, https://doi.org/10.1561/2200000048. (Cited on page 46.)

    2015 doi

  107. [114]

    J. A. T ROPP , Acm 217: Probability in high dimensions , CMS Lecture Notes 2021-01, Caltech, Pasadena, 2021, https:// doi.org/10.7907/mxr0-c422, https://resolver.caltech.edu/CaltechAUTHORS:20220412-221302767 . (Cited on pages 1, 13, 41, and 50.)

    2021 doi

  108. [116]

    J. A. T ROPP AND R. J. W EBBER , Randomized algorithms for low-rank matrix approximation: Design, analysis, and appli- cations, Sept. 2023, https://arxiv.org/abs/2306.12418v3. (Cited on pages 6, 16, and 17.)

    2023 arXiv

  109. [117]

    J. A. T ROPP, A. Y URTSEVER , M. U DELL , AND V. C EVHER , Fixed-rank approximation of a positive-semidefinite matrix from streaming data, Advances in Neural Information Processing Systems, 30 (2017),https://proceedings.neurips. cc/paper_files/paper/2017/file/4558dbb6f6f8bb2e1...

    2017

  110. [118]

    J. A. T ROPP, A. Y URTSEVER , M. U DELL , AND V. C EVHER , Practical sketching algorithms for low-rank matrix approx- imation, SIAM Journal on Matrix Analysis and Applications, 38 (2017), pp. 1454–1485, https://doi.org/https: //doi.org/10.1137/17M1111590. (Cited on pages 8, 18...

    2017 doi

  111. [119]

    J. A. T ROPP, A. Y URTSEVER , M. U DELL , AND V. CEVHER , Streaming low-rank matrix approximation with an application to scientific simulation, SIAM Journal on Scientific Computing, 41 (2019), pp. A2430–A2463, https://doi.org/10.1137/ 18M1201068. (Cited on pages 1, 2, 6, 8, 21...

    2019

  112. [120]

    R. V ERSHYNIN , High-dimensional probability: an introduction with applications to data science , Cambridge University Press, 2nd ed., 2025, https://doi.org/https://doi.org/10.1017/9781108231596. Version 25. (Cited on pages 1, 13, 34, 41, 42, and 50.)

    2025 doi

  113. [121]

    W ILLIAMS AND M

    C. W ILLIAMS AND M. S EEGER , Using the Nyström method to speed up kernel machines , Advances in Neu- ral Information Processing Systems, 13 (2000), https://papers.nips.cc/paper_files/paper/2000/file/ 19de10adbaa1b2ee13f77f679fa1483a-Paper.pdf. (Cited on page 1.)

    2000

  114. [122]

    W IMMER , Y

    K. W IMMER , Y. W U, AND P . ZHANG , Optimal query complexity for estimating the trace of a matrix , in International Colloquium on Automata, Languages, and Programming, Springer, 2014, pp. 1051–1062, https://doi.org/https: //doi.org/10.1007/978-3-662-43948-7_87 . (Cited on page 11.)

    2014 doi

  115. [123]

    D. P . W OODRUFF ET AL ., Sketching as a tool for numerical linear algebra , Foundations and Trends in Theoretical Com- puter Science, 10 (2014), pp. 1–157, https://doi.org/https://doi.org/10.1561/0400000060. (Cited on pages 1, 2, 5, 16, 19, 20, and 21.)

    2014 doi

  116. [124]

    W OOLFE , E

    F . W OOLFE , E. L IBERTY , V. R OKHLIN , AND M. T YGERT , A fast randomized algorithm for the approximation of matrices , Applied and Computational Harmonic Analysis, 25 (2008), pp. 335–366, https://doi.org/10.1016/j.acha.2007. 12.002. (Cited on pages 1, 8, 19, and 27.)

    2008 doi

  117. [125]

    Z ENG AND Y

    R. Z ENG AND Y. Z HANG , Efficiently computing vortex lattices in rapid rotating bose–einstein condensates , Computer Physics Communications, 180 (2009), pp. 854–860, https://doi.org/https://doi.org/10.1016/j.cpc.2008.12

    2009 doi

  118. [126]

    (Cited on page 53.) 59

Pith tools

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