Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

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

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

Pith's one-line read The paper proves that any well-conditioned algorithm estimating the trace or top eigenvalue of a matrix through Kronecker-structured queries must use exponentially many queries in the number of tensor factors q.

desk verdict A genuinely new orthogonality observation gives exponential lower bounds for Kronecker query complexity, modulo an honest conditioning assumption that is the main open step. read the letter →

arxiv 2502.08029 v2 pith:GUW4OBEA submitted 2025-02-12 cs.DS cs.NAmath.NA

Raphael A. Meyer , William Swartworth , David P. Woodruff This is my paper · ORCID
classification cs.DScs.NAmath.NA MSC 68Q2568W2015A69
keywords Kroneckerproductmatrix-vectorquerycomplexitytraceestimationspectralnormlowerboundzerotestingtensorsketchingrandomizedalgorithmsorthogonality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how many Kronecker matrix-vector products, queries of the form $\mathbf{A}x$ with $x = x_1 \otimes \cdots \otimes x_q$, are needed to estimate basic properties of a large matrix $\mathbf{A}$. It proves that for trace and spectral-norm estimation, every well-conditioned algorithm must use a number of queries exponential in $q$, even to achieve a coarse approximation. The engine is a near-orthogonality lemma: a random Kronecker-structured unit vector has exponentially small squared inner product with any fixed Kronecker-structured vector. The same phenomenon implies an exponential gap between Gaussian and Rademacher query vectors for zero-testing, and shows that choosing a different subgaussian distribution can change query complexity exponentially. If true, these results explain why existing Kronecker sketching methods necessarily incur exponential cost and why structural assumptions on $\mathbf{A}$ are needed for fast algorithms.

What carries the argument

The load-bearing object is Lemma 8, the near-total orthogonality of random Kronecker-structured vectors. For $u = u_1 \otimes \cdots \otimes u_q$ with each $u_i$ uniform on the unit sphere of $\mathbb{R}^n$ and any fixed Kronecker-structured unit vector $v = v_1 \otimes \cdots \otimes v_q$, the lemma gives $\Pr[\langle u, v\rangle^2 \ge C_\tau^{-q}/n^q] \le C_0^{-q}$ for universal constants $C_\tau, C_0 > 1$. Because the inner product of two Kronecker vectors factorizes as $\prod_{i=1}^q \langle u_i, v_i\rangle$, the logarithm of the inner product is a sum of independent subexponential variables, and Bernstein concentration yields a tail that decays exponentially in $q$ rather than polynomially. This lemma is plugged into an information-theoretic lower-bound framework for adaptive matrix-vector queries; the algorithm's query matrix $V$ is required to have condition number at most $\kappa$, which converts the sparse inner products into bounds on KL divergence between the planted and unplanted distributions.

What would settle it

For $n=2$ and $q$ up to 20, run a numerical search over Kronecker-structured unit vectors $v^{(1)}, \dots, v^{(t)}$ with $t = \operatorname{poly}(q)$ and condition number $\exp(\Omega(q))$: if the squared norm of the projection of a random Kronecker vector $u$ onto their span exceeds $n^{-q}$ with probability that does not decay as $c^{-q}$, then Conjecture 23 is false, and the conditioning assumption could be hiding the real complexity.

Watch

Extended reading notes

Core claim

The central claim is that the Kronecker matrix-vector oracle is exponentially weak for the basic linear algebra tasks. Theorem 7 states that any $\kappa$-conditioned Kronecker vector-matrix-vector algorithm estimating $\operatorname{tr}(\mathbf{A})$ of a PSD matrix to $(1 \pm \varepsilon)$ relative error needs $t = \Omega(\min\{C_0^{q/2}, C_\tau^{q/2}/(\kappa^2\sqrt{\varepsilon})\})$ queries; Theorem 6 gives the analogous exponential lower bound for spectral-norm estimation, and Corollary 16 says even deciding whether $\|\mathbf{A}\|_2 \le 3$ or $\|\mathbf{A}\|_2 \ge C^q$ requires $t = \Omega(\min\{C_0^{q/2}, C^q/\kappa^2\})$ queries. The proofs plant a random Kronecker-structured vector $u$ on Gaussian data and use Lemma 8, which bounds $\langle u, v\rangle^2 \le C_\tau^{-q}/n^q$ with probability at least $1 - C_0^{-q}$ for every fixed Kronecker-structured unit vector $v$. For zero-testing, Theorem 10 and Theorem 18 show that queries built from a small alphabet such as $\{\pm 1\}$ need $\Theta(2^q)$ queries even though a single Gaussian Kronecker query succeeds with probability 1. The paper also establishes that Rademacher-based trace estimation has optimal complexity $\Theta(2^q)$ for $n=2$, matching an earlier algorithm, and that the same task is easier with continuous vectors.

Load-bearing premise

The premise that can break the lower bounds is the $\kappa$-conditioning assumption: every query matrix the algorithm builds must have condition number at most $\kappa$ for every input $\mathbf{A}$; if an algorithm is allowed exponentially ill-conditioned query matrices, the stated exponential lower bounds no longer apply.

Editorial extensions

If this is right

  • Khatri-Rao sketches, including Kronecker JL and Kronecker Hutchinson, must use exponentially many measurements in the worst case to estimate the trace or spectral norm, matching prior empirical and theoretical observations.
  • Trace estimation with Rademacher Kronecker queries is exactly $\Theta(2^q)$ for $n=2$, so Rademacher vectors cannot achieve the query complexity of Gaussian or uniform-unit-vector sketches for this problem.
  • Zero-testing a tensor requires $\Theta(2^q)$ Kronecker measurements over the alphabet $\{\pm 1\}$, and $\Theta((4/3)^q)$ over $\{\pm 1, \pm i\}$, so small-alphabet algorithms are exponentially weaker than a single Gaussian query.
  • Any polynomial-query Kronecker algorithm must exploit additional structure in $\mathbf{A}$ beyond the oracle itself; the worst-case matrix is a planted rank-one term hidden in Gaussian noise.

Reading between the lines

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

  • The abstract lower-bound framework in Appendix D is not specific to Kronecker structure; the same planted-vector recipe could yield exponential query lower bounds for other restricted query families, such as sparse or low-rank matrix-vector products.
  • The Gaussian-vs-Rademacher gap suggests a design principle for Kronecker algorithms: prefer continuous or large-alphabet sketches, since subgaussianity alone does not control query complexity in this model.
  • If Conjecture 23 holds, the conditioning assumption in the trace and spectral-norm bounds can be removed; if it fails, there may exist ill-conditioned query matrices that beat the exponential lower bounds, turning the assumption into a genuine separation.
  • A practical takeaway for tensor network computations is that near-orthogonality of random Kronecker vectors makes norm and trace estimation information-theoretically hard without additional structure, so algorithm design should target structured tensor formats.
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

3 major / 5 minor

Summary. The paper studies the query complexity of linear-algebra problems in an oracle model where the only access to a matrix A is through products with Kronecker-structured vectors x = x_1 ⊗ ... ⊗ x_q. The central tool is Lemma 8, which states that a random Kronecker-structured unit vector has squared inner product at most Cτ^{-q}/n^q with probability at least 1 - C0^{-q} against any fixed Kronecker-structured unit vector. Using this, the authors prove exponential lower bounds on the number of queries needed for spectral-norm approximation (Theorem 6) and trace estimation (Theorem 7), both for κ-conditioned algorithms as defined in Definition 5. They also prove tight bounds for zero-testing with small alphabets (Theorems 18-19), showing that Rademacher queries require Θ(2^q) measurements while a single Gaussian Kronecker query succeeds with probability 1. The appendix generalizes the lower-bound framework of Simchowitz et al. to restricted query sets.

Significance. If the main claims hold, the paper gives a clean explanation for the exponential sketching dimension observed in Khatri-Rao and Kronecker JL methods, and it demonstrates a striking gap between subgaussian distributions that does not appear in the non-Kronecker setting. The zero-testing section (Theorems 18-19) is the strongest part: it is self-contained, the alphabet calculations are explicit, and the matching upper and lower bounds are rigorous. The paper is also honest about the main caveat: the norm and trace lower bounds apply only to κ-conditioned algorithms, and the paper states as Conjecture 23 the open question of whether this assumption can be removed. The generalized Simchowitz framework in Appendix D is a useful contribution in its own right. However, the central 'all algorithms' claim is conditional, the trace lower bound is proved only for the weaker vector-matrix-vector oracle, and one technical lemma (Lemma 25) is false as stated. These issues are fixable, but they affect the scope and rigor of the advertised results.

major comments (3)
  1. [Section 3.1, Definition 5; Theorems 6 and 7; Conjecture 23] The κ-conditioning assumption is load-bearing. The bounds in Theorem 7 and Theorem 6 contain κ in the denominator: t = Ω(min{C0^{q/2}, Cτ^{q/2}/(κ²√ε)}) and t = Ω(min{C0^{q/2}, Cτ^{q/2}/κ²}). If an algorithm were allowed ill-conditioned queries with κ = exp(Ω(q)), both bounds would degenerate to Ω(1). The paper argues that the assumption is 'mild' because typical Khatri-Rao sketches are well-conditioned, but this does not rule out adaptive algorithms that deliberately choose ill-conditioned Kronecker queries. Conjecture 23, which the paper states as open, is exactly the statement that would remove the assumption, and it is open even for non-adaptive measurements. As written, the advertised all-algorithm lower bounds hold only for a restricted class, so the abstract's phrase 'modulo a mild conditioning assumption' overstates the current state of knowledge.
  2. [Appendix A, Lemma 25; used in Appendix C (proof of Theorem 15)] Lemma 25 is false. It claims E[e^{η|⟨u,θ⟩|}] ≤ 1 + 2η/n^q based on the identity E[|⟨u1,θ1⟩|] = 1/n. But for a uniformly random unit vector u1 and fixed unit vector θ1, the inner product is symmetric about 0, and E[|⟨u1,θ1⟩|] = Θ(1/√n), not 1/n (specifically the constant is approximately √(2/π)). The proof incorrectly treats ⟨u1,θ1⟩ as a nonnegative Beta(1/2,(n-1)/2) random variable and uses its mean instead of the mean absolute value. The error could be repaired: replacing 1/n^q by (β/√n)^q in the moment bound changes the exponential factor to (Cτ/β)^q and preserves the qualitative exponential lower bound. Nevertheless, the lemma as stated and used in the Appendix C proof is incorrect, so the proof of Theorem 15 needs revision.
  3. [Abstract; Section 4.1; Theorem 7; Corollary 22] The trace lower bound is proved only for the vector-matrix-vector oracle (scalar queries x^T A x), not for the matrix-vector oracle of Definition 1. The reduction in Section 4.1 sets A = aa^T; for such a rank-one PSD matrix, a single matrix-vector query with any x satisfying a^T x ≠ 0 returns y = (a^T x)a, from which the algorithm can compute the trace exactly: if d = a/‖a‖, then ‖a‖² = ‖y‖ / |(y/‖y‖)^T x|. Thus the rank-one construction cannot support a lower bound for the Definition 1 oracle. The abstract's wording that the paper proves exponential lower bounds for 'matrix-vector products' including the trace, and Corollary 22's phrase 'matrix-vector queries', overstate the scope. These statements should be corrected to refer to vector-matrix-vector (scalar quadratic-form) queries, or a genuinely new lower bound for the matrix-vector oracle must be supplied.
minor comments (5)
  1. [Theorem 6] The phrase 'to multiplicative less than error Cτ^{q/2}' is unclear; it should be stated as a relative-error guarantee or as a factor-C separation as in Corollary 16. The constants Cτ in Theorem 6 and C in Corollary 16 should also be aligned, since Corollary 16 is presented as an immediate consequence.
  2. [Appendix C, proof of Theorem 15 Restated] There is a sign error in the sentence 'so long as t ≤ O(C0^{-q/2})' near the end of the first computation; from (1+8t)C0^{-q/2} ≤ 1/27 the condition should be t ≤ O(C0^{q/2}).
  3. [Lemmas 35 and 36] The final bounds write t = O(Cτ^{q/2}/(κ²√ε)) after earlier expressions use λ = 6√ε and t = O(Cτ^{q/2}/(κ²λ)); the constant factor 6 should be tracked explicitly to ensure the stated bound is correct.
  4. [Theorem 19(i)] The statement 'requires at least 2/3 Ω(P_F(L,n)^{-q})' is unconventional; the constant 2/3 should be incorporated into the Ω notation or stated explicitly as, for example, m ≥ (1/3)P_F(L,n)^{-q}.
  5. [Throughout] There are several typos: the title line in the full text has a stray space in 'L inear Algebra'; 'kronecker-strucutred' appears in Lemma 8 itself; 'otehr' appears in Appendix A's heading; and the proof of Lemma 24 refers to the distribution of 'the first entry' but the density formula is for |X|/√n, which is correct but should be stated more clearly.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: the lower bounds are self-contained planted-instance reductions; the only self-citation (Meyer-Avron 2023) serves as a context/matching benchmark, and the κ-conditioning assumption is an honest stated hypothesis whose removal is left open.

full rationale

The paper's central lower bounds (Theorems 6, 7, 13, 15 and the zero-testing results) are proved by reducing to externally defined planted-distinguishing problems: distinguishing a0=g from a1=g+λu, distinguishing a Wigner matrix from a rank-one deformation, and zero-testing against explicit alphabets. The engine, Lemma 8, is proved self-contained in Appendix A via subexponential concentration of log-absolute-entries of uniform sphere vectors; it is not imported from prior work. The constants C0 and Cτ are universal constants from that proof, not fitted to any target quantity, so no prediction reduces to a fit by construction. The κ-conditioning restriction in Definition 5 is an explicit hypothesis of the theorems, and the paper honestly states in Section 6 that removing it is open (Conjecture 23); this is a limitation on scope, not a circular assumption of the conclusion. Citations to Meyer-Avron 2023 (which shares an author with this paper) are used for motivation and as a matching upper-bound benchmark for trace estimation, but they do not justify Lemma 8 or any lower-bound step; thus they are not load-bearing for the derivation. A localized technical slip in Lemma 25's first-moment computation would affect a constant in one bound but does not make the argument circular, since the exponential structure is preserved with a corrected constant. Overall, the derivation chain is self-contained and no circular step is present.

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

The central claims rest on: (1) the Kronecker query oracle as the computational model; (2) the κ-conditioning premise on the algorithm's query matrix, whose mildness is argued but not proven (Conjecture 23); (3) the imported adaptive lower-bound framework of Simchowitz et al. 2017; and (4) standard probability facts (concentration, KL/Pinsker/Neyman-Pearson). The hand-chosen constants C0 and Cτ in Lemma 8 are not fitted to data but are only known to be of the form e^α with α ∈ (0, 0.006), so the exponential bases are close to 1; λ = 6√ε in the testing reduction is a benign design choice. No new entities such as particles, forces, mediators, or conserved quantities are introduced; the planted vector u and planted rank-one matrix λuu^T are standard adversarial instances. One error to note: Lemma 25's moment calculation is incorrect, using E|⟨u1,v1⟩| = 1/n instead of the true ~0.8/√n.

free parameters (2)
  • C0, Cτ (and α in Lemma 8) = C0 = Cτ = e^α with α ∈ (0, 0.006); exact values not computed
    These universal constants control the near-total orthogonality of Lemma 8 and hence the base of the exponential lower bounds. They are not fitted to data, but their only known lower bound gives bases extremely close to 1, so the trace and spectral 'exponential' bounds are numerically weak in q.
  • λ = 6√ε (reduction in Problem 14) = 6√ε
    Hand-chosen constant in the reduction from L2 estimation to the two-point testing problem (Problem 14, Lemma 30). It is a fixed function of ε rather than a fitted value, but the specific choice is ad hoc.
assumptions (5)
  • standard math Bernstein-type concentration inequalities, KL divergence, Pinsker's inequality, Neyman-Pearson lemma, and Gaussian moment-generating identities
    Used throughout Section 4 and Appendices A-C for the planted-instance arguments and hypothesis-testing bounds.
  • domain assumption Kronecker matrix-vector oracle model (Definition 1): queries are restricted to x1 ⊗ ... ⊗ xq, and responses are exact real arithmetic values
    Defines the problem regime; without the oracle restriction the classical matrix-vector query complexity applies.
  • domain assumption κ-conditioning of the query matrix V (Definition 5): cond([v^(1) ... v^(t)]) ≤ κ for all inputs A
    Load-bearing premise of Theorems 6 and 7. The paper argues it is mild for Khatri-Rao sketches via Lemma 8 and states no counterexample, but the full removal is left as open Conjecture 23 in Section 6.
  • domain assumption Imported lower-bound machinery from Simchowitz et al. 2017 (their Proposition 5.1, Theorem 5.3, Lemma C.3 and C.4), restated as Imported Theorems 34, 43, 44, 45, and 47
    The adaptive lower bounds inherit this framework; the paper generalizes it to constrained query sets rather than re-proving it.
  • standard math Distributional identities for entries of uniform unit vectors in R^n: the squared first coordinate is Beta(1/2,(n-1)/2), and digamma identities give E log of Beta variables
    Underlies Lemma 8 and Lemma 25. Note that Lemma 25's proof misapplies the first moment (uses 1/n for E|⟨u1,v1⟩| instead of the true ~0.8/√n); this error is flagged separately in red_flags.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra." pith.science (2026). https://pith.science/paper/GUW4OBEA

@misc{pith2026250208029,
  author       = {Pith},
  title        = {Pith review of: Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GUW4OBEA}},
  note         = {Machine review of arXiv:2502.08029}
}
abstract

We study the computational model where we can access a matrix $\mathbf{A}$ only by computing matrix-vector products $\mathbf{A}\mathrm{x}$ for vectors of the form $\mathrm{x} = \mathrm{x}_1 \otimes \cdots \otimes \mathrm{x}_q$. We prove exponential lower bounds on the number of queries needed to estimate various properties, including the trace and the top eigenvalue of $\mathbf{A}$. Our proofs hold for all adaptive algorithms, modulo a mild conditioning assumption on the algorithm's queries. We further prove that algorithms whose queries come from a small alphabet (e.g., $\mathrm{x}_i \in \{\pm1\}^n$) cannot test if $\mathbf{A}$ is identically zero with polynomial complexity, despite the fact that a single query using Gaussian vectors solves the problem with probability 1. In steep contrast to the non-Kronecker case, this shows that sketching $\mathbf{A}$ with different distributions of the same subguassian norm can yield exponentially different query complexities. Our proofs follow from the observation that random vectors with Kronecker structure have exponentially smaller inner products than their non-Kronecker counterparts.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Faster Linear Algebra Algorithms with Structured Random Matrices

    cs.DS 2025-08 accept novelty 8.0 of 10

    Randomized sketching needs only the new OSI property, not the full subspace embedding, and multiple structured matrices satisfy it with near-optimal cost.

Reference graph

Works this paper leans on

31 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [1]

    D., Kapralov, M., Knudsen, J

    Ahle, T. D., Kapralov, M., Knudsen, J. B., Pagh, R., Velingker, A., Woodruff, D. P., and Zandieh, A. (2020). Oblivious sketching of high-degree polynomial kernels. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 141--160. SIAM

    work page 2020

  2. [2]

    Ahle, T. D. and Knudsen, J. B. (2019). Almost optimal tensor sketch. arXiv preprint arXiv:1909.01821

    work page Pith review arXiv 2019

  3. [3]

    W., and Saibaba, A

    Al Daas, H., Ballard, G., Cazeaux, P., Hallman, E., Mikedlar, A., Pasha, M., Reid, T. W., and Saibaba, A. K. (2023). Randomized algorithms for rounding in the tensor-train format. SIAM Journal on Scientific Computing , 45(1):A74--A95

    work page 2023

  4. [4]

    Avron, H., Nguyen, H., and Woodruff, D. (2014). Subspace embeddings for the polynomial kernel. Advances in neural information processing systems , 27

    work page 2014

  5. [5]

    Biamonte, J. (2019). Lectures on quantum tensor networks. arXiv preprint arXiv:1912.10049

    arXiv 2019

  6. [6]

    Bujanovi \'c , Z., Grubi s i \'c , L., Kressner, D., and Lam, H. Y. (2024). Subspace embedding with random khatri-rao products and its application to eigensolvers. arXiv preprint arXiv:2405.11962

    arXiv 2024

  7. [7]

    and Kressner, D

    Bujanovic, Z. and Kressner, D. (2021). Norm and trace estimation with random rank-one vectors. SIAM Journal on Matrix Analysis and Applications , 42(1):202--223

    work page 2021

  8. [8]

    and K \"o rner, J

    Csisz \'a r, I. and K \"o rner, J. (2011). Information theory: coding theorems for discrete memoryless systems . Cambridge University Press

    work page 2011

Show all 31 references
  1. [9]

    Feldman, N., Kshetrimayum, A., Eisert, J., and Goldstein, M. (2022). Entanglement estimation in tensor network states via sampling. PRX Quantum , 3(3):030312

    2022

  2. [10]

    Golub, G. H. and Van Loan, C. F. (2013). Matrix computations . JHU press

    2013

  3. [11]

    Grasedyck, L. (2004). Existence and computation of low kronecker-rank approximations for large linear systems of tensor product structure. Computing , 72:247--265

    2004

  4. [12]

    Grasedyck, L., Kressner, D., and Tobler, C. (2013). A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen , 36(1):53--78

    2013

  5. [13]

    G., and Ward, R

    Jin, R., Kolda, T. G., and Ward, R. (2021). Faster johnson--lindenstrauss transforms via kronecker products. Information and Inference: A Journal of the IMA , 10(4):1533--1562

    2021

  6. [14]

    Y., Ceruti, G., and Kressner, D

    Lam, H. Y., Ceruti, G., and Kressner, D. (2024). Randomized low-rank runge-kutta methods. arXiv preprint arXiv:2409.06384

    2024 arXiv

  7. [15]

    and Cichocki, A

    Lee, N. and Cichocki, A. (2014). Fundamental tensor operations for large-scale data analysis in tensor train formats. arXiv preprint arXiv:1405.7786

    2014 arXiv

  8. [16]

    Li, X., Haupt, J., and Woodruff, D. (2017). Near optimal sketching of low-rank tensor regression. Advances in Neural Information Processing Systems , 30

    2017

  9. [17]

    V., Woodruff, D

    Mahankali, A. V., Woodruff, D. P., and Zhang, Z. (2024). Near-linear time and fixed-parameter tractable algorithms for tensor decompositions. In Guruswami, V., editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berke...

    2024

  10. [18]

    Meyer, R. A. and Avron, H. (2023). Hutchinson's estimator is bad at kronecker-trace-estimation. arXiv preprint arXiv:2309.04952

    2023 arXiv

  11. [19]

    A., Musco, C., Musco, C., and Woodruff, D

    Meyer, R. A., Musco, C., Musco, C., and Woodruff, D. P. (2021). Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity in Algorithms (SOSA) , pages 142--155. SIAM

    2021

  12. [20]

    and Pearson, E

    Neyman, J. and Pearson, E. S. (1933). Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character , 231(694-706):289--337

    1933

  13. [21]

    and Pagh, R

    Pham, N. and Pagh, R. (2013). Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 239--247

    2013

  14. [22]

    Saibaba, A. K. and Mikedlar, A. (2025). Randomized low-rank approximations beyond gaussian random matrices. SIAM Journal on Mathematics of Data Science , 7(1):136--162

    2025

  15. [23]

    Sedighin, F. (2024). Tensor methods in biomedical image analysis. Journal of Medical Signals & Sensors , 14(6):16

    2024

  16. [24]

    and Dam, E

    Selvan, R. and Dam, E. B. (2020). Tensor networks for medical image classification. In Medical imaging with deep learning , pages 721--732. PMLR

    2020

  17. [25]

    E., and Recht, B

    Simchowitz, M., Alaoui, A. E., and Recht, B. (2017). On the gap between strict-saddles and true convexity: An omega (log d) lower bound for eigenvector approximation. arXiv preprint arXiv:1704.04548

    2017 arXiv

  18. [26]

    Simchowitz, M., El Alaoui, A., and Recht, B. (2018). Tight query complexity lower bounds for pca via finite sample deformed wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 1249--1259

    2018

  19. [27]

    P., and Zhong, P

    Song, Z., Woodruff, D. P., and Zhong, P. (2019a). Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2772--2789. SIAM

    2019

  20. [28]

    P., and Zhong, P

    Song, Z., Woodruff, D. P., and Zhong, P. (2019b). Relative error tensor low rank approximation. In Chan, T. M., editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 , pages 2772--2789. SIAM

    2019

  21. [29]

    A., and Udell, M

    Sun, Y., Guo, Y., Tropp, J. A., and Udell, M. (2021). Tensor random projection for low memory dimension reduction. arXiv preprint arXiv:2105.00105

    2021 arXiv

  22. [30]

    Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science , volume 47. Cambridge university press

    2018

  23. [31]

    and Chen, S

    Zhang, H. and Chen, S. X. (2020). Concentration inequalities for statistical inference. arXiv preprint arXiv:2011.02258

    2020 arXiv

Pith tools

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