Pith. sign in

REVIEW 3 major objections 5 minor 62 references

Uniformly sampling about (log n)/ε⁴ columns of a symmetric matrix with entries bounded by 1 suffices to approximate, for every eigenvalue λ with |λ| ≥ εn, a unit vector v with ‖Av − λv‖₂ ≤ εn, with each entry of v computable in poly(log n,

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-05 00:11 UTC pith:YM3NYAFZ

load-bearing objection Strong top-eigenvector result and lower bound, but the all-eigenvector theorem rests on a middle-eigenvalue bound that the cited lemma doesn't actually supply. the 3 major comments →

arxiv 2608.00840 v1 pith:YM3NYAFZ submitted 2026-08-01 cs.DS cs.NAmath.NA

Sublinear Time Eigenvector Approximation via Column Sampling

Rajarshi Bhattacharjee , Cameron Musco , Dominic Rutkowski This is my paper
classification cs.DS cs.NAmath.NA MSC 68W2065F1515A18
keywords sublinear-time algorithmseigenvector approximationrandom column samplingprincipal submatrixbackward errorNyström methodquantum-inspired algorithmssubspace embedding
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper claims that the outlying eigenvectors of a huge symmetric matrix can be recovered from a tiny random sample of its columns. For a matrix with entries bounded in magnitude by 1, uniformly sampling roughly (log n)/ε⁴ columns — reading only about n/ε⁴ entries — lets one output, for every eigenvalue λ with |λ| ≥ εn, a unit vector v with ‖Av − λv‖₂ ≤ εn. Each approximate eigenvector is a linear combination of the sampled columns, so any single entry of v costs poly(log n, 1/ε) time. If correct, this gives the first sublinear-time algorithms for approximating the eigenvectors of general symmetric matrices — all outlying ones at once, not just the top — and extends to the sampling-and-query model used in quantum-inspired algorithms. For the single largest eigenvalue the sample count drops to (log n)/ε², which the paper proves tight up to logarithmic factors even for adaptive algorithms, and for positive semidefinite matrices a Nyström variant needs only about 1/ε columns.

Core claim

The central claim, Theorem 1, is that the outlying eigenvectors of a bounded-entry symmetric matrix are recoverable from a random principal submatrix. The algorithm forms a scaled sampling matrix S̄ that keeps each column independently with probability s/n, computes the eigenvectors x of the s×s matrix S̄ᵀAS̄, and lifts each back through the original matrix: v = AS̄x/‖AS̄x‖₂. With s = O((log n)/(ε⁴δ) · log³(1/(εδ))), every eigenvalue of magnitude at least εn is matched to an output pair with eigenvalue error and backward (residual) error both at most εn, with probability 1−δ. The proof splits A into A_o (projection onto eigenvalues of magnitude at least ε√δ n) and A_m (the rest), uses the in

What carries the argument

The load-bearing object is the scaled column-sampling matrix S̄ with the 'sample-and-lift' construction: x is an eigenvector of the sampled principal submatrix S̄ᵀAS̄, and the approximate eigenvector is v = AS̄x/‖AS̄x‖₂, a unit vector in the span of the sampled columns. Two properties of S̄ carry the proof: Property 1, a min(R/λ, 1/10)-distortion subspace embedding for the span of eigenvectors with eigenvalue magnitude at least λ — obtained for uniform sampling from the incoherence bound ‖U_{≥λ}‖²_{2,inf} ≤ n/λ² on outlying eigenvectors of a bounded-entry matrix — and a middle-eigenvalue bound ‖S̄ᵀA_mS̄‖₂ ≤ εn showing sampling does not amplify small eigenvalues. Two further constructions ext

Load-bearing premise

The guarantee collapses if the outlying eigenvectors are coherent — concentrated on a few coordinates — because the proof's subspace embedding for the outlying eigenspace rests on the incoherence bound ‖U_{≥λ}‖²_{2,inf} ≤ n/λ², which is available only because entries of A are bounded by 1; a uniform column sample can then miss the outlying structure entirely.

What would settle it

Build the hardest instance the assumptions admit: an n×n symmetric matrix with ⌈1/ε²⌉ disjoint εn×εn all-ones blocks (each contributing an eigenvalue εn, entries in {0,1}, so ‖A‖_∞ = 1) and run Algorithm 1 with s = c log n/ε⁴ sampled columns across many trials. An entire block must be hit for its eigenvector to be discovered, and a miss produces residual error ≈ εn, exactly the claimed threshold; recording the fraction of trials in which at least one block-eigenvector is missed, as a function of c and ε, settles whether the (log n)/ε⁴ exponent and its constant are correct.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Every outlying eigenvector of an n×n bounded-entry symmetric matrix becomes approximable from about n/ε⁴ sampled entries, simultaneously for all eigenvalues of magnitude ≥ εn, not just the top few.
  • Individual entries of each approximate eigenvector cost poly(log n, 1/ε) time, giving the first sublinear-time classical eigenvector-approximation algorithms in the sampling-and-query (quantum-inspired) model, with error ε‖A‖_F.
  • For approximating just the top eigenvector, (log n)/ε² sampled columns suffice, and the paper proves this is tight up to logarithmic factors against any adaptive, possibly non-adaptive algorithm.
  • For positive semidefinite matrices, ridge leverage score sampling reduces the sample count to about (1/ε) log(1/εδ) columns for εn error, with error improved to ε·tr(A) when columns are sampled proportionally to diagonal entries.
  • A rank-truncated Nyström variant recovers the optimal (log n)/ε² sample complexity for all outlying eigenvectors of general symmetric matrices, at the price of giving up poly(log n, 1/ε) entrywise output.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • One testable extension is to benchmark Algorithm 1 against a planted instance of r ≈ 1/ε² disjoint εn×εn all-ones blocks: since an entire block must be sampled for its eigenvalue to be discovered, the measured whole-block miss rate versus s directly calibrates the true constant inside the (log n)/ε⁴ exponent.
  • The εn error scale is an artifact of the bounded-entry normalization; for sparse or numerically sparse matrices the ε‖A‖_F variant is the practically relevant one, and the zeroing step of Algorithm 2 suggests the framework was built with that comparison in mind.
  • Because each output vector is a sparse random combination of columns, the same construction yields a local-computation oracle — O(s) row entries per queried coordinate — which points toward spectral-cut certification and dense-graph testing applications where a single residual query should cost poly(log n, 1/ε) rather than n.
  • The paper explicitly leaves open whether the gap between the (log n)/ε⁴ uniform bound and the (log n)/ε² Nyström bound for all outlying eigenvectors can be closed inside the simple sample-and-lift scheme; feeding the dyadic level-set analysis already used for the top eigenvector into the all-outliers proof is the natural next step.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies sublinear-time approximation of outlying eigenvectors of symmetric matrices by column sampling. The main result (Theorem 1) claims that for a symmetric A with entries bounded by 1, uniformly sampling O~(log n / ε^4) columns suffices to output, for every eigenvalue λ with |λ| ≥ ε n, a unit vector v with backward error ||Av - λ v||_2 ≤ ε n, and that a stronger O~(1/ε^2) bound holds for the top eigenvector (Theorem 2). Similar guarantees are claimed under squared column-norm sampling, with error ε||A||_F, together with a quantum-inspired SQ-access extension, a lower bound for top-eigenvector estimation, and a rank-truncated Nyström method that achieves O~(1/ε^2) columns at the cost of losing entrywise query access. The analysis builds on imported eigenvalue-approximation results from BDD+24 and SW25, and the paper also gives improved bounds for PSD matrices and a lower bound of Ω(1/ε) columns for the PSD case.

Significance. If the central theorems hold, the paper would be a substantive contribution: it gives the first sublinear-time classical algorithms for approximating outlying eigenvectors of general symmetric matrices, with the useful structural property that approximate eigenvectors are spanned by a small number of sampled columns and can be queried entrywise in poly(log n, 1/ε) time. The lower bound for top-eigenvector estimation is a valuable contribution, as are the rank-truncated Nyström bounds for indefinite matrices and the PSD-specific sampling results. The paper also makes good use of published results, and the algorithmic structure is clean and reproducible from the pseudocode. However, the main all-eigenvector guarantee of the uniform-sampling algorithm rests on a proof step in Lemma 8 that appears to use an unsupported bound on the sampled middle-eigenvalue matrix; this is a load-bearing gap that must be repaired before the main claim can be accepted.

major comments (3)
  1. [§4.3, Lemma 8, Eq. (18)–(19)] In the proof of Lemma 8, with L = ε√δ n in Definition 3.1, the first error term in (18) is bounded using the claim that, for s ≥ c log n / (ε^4 δ), Imported Lemma 4 gives ||S^T A_m S||_2 ≤ ε^2 n. As stated, Imported Lemma 4 guarantees only ||S^T A_m S||_2 ≤ ε n for this choice of A_m; the stronger ε^2 n bound would require redefining A_m with the smaller threshold L = ε^2√δ n. That change is not compatible with the ε-subspace embedding for U_o invoked at the same point, since the distortion min(R/λ, 1/10) is only constant for the low end of the enlarged U_o. Concretely, if A_m = μ uu^T with μ = ε√δ n / 2 and u incoherent, then ||S^T A_m S||_2 ≈ Θ(ε n) with high probability, contradicting the ε^2 n bound used to show the first term in (18) is O(ε n). This gap affects the central guarantee of Theorem 1 for all outlying eigenvectors produced by Algorithm 1. The top-eigenvector Lemma 7 is no
  2. [§4.4 (Lemma 15, Theorem 6) and §7.2.2 (Lemma 27)] Several results that are needed for the squared column-norm and Nyström analogues are not actually proved. Lemma 15, which is the column-norm analogue of Lemma 8 for all outlying eigenvectors, is dismissed with 'We omit the details here'; Theorem 6, the column-norm top-eigenvector result, is stated with 'We omit the proof'; and Lemma 27, the spectral error bound for the rank-truncated Nyström approximation under column-norm sampling, is only a proof-by-analogy that does not verify the algebra with the zeroed-out matrix A′ and the truncated pseudoinverse. These results carry the corresponding main theorems (Theorems 5, 6, 12), so the omissions are not merely cosmetic. In particular, Lemma 15 may inherit the issue identified in Lemma 8. Full, self-contained proofs are required.
  3. [Theorem 6 statement] The statement of Theorem 6 refers to 'Algorithm 1' although the section concerns squared column-norm sampling (Algorithm 2/3), and item 1 uses the condition ||A||_2 ≥ 2ε n, which is inconsistent with the column-norm error scale ε||A||_F used elsewhere in that theorem (item 2 uses 2ε||A||_F). The proof is also omitted. Please correct the statement, align the conditions and algorithm references, and provide the proof, or explicitly subsume the theorem under a proved result.
minor comments (5)
  1. [§4.3, Lemma 8 proof] In the first-term bound, '∥¯ST A¯S∥2 ≤ ε^2 n' should read '∥¯ST A_m¯S∥2 ≤ ε^2 n'; in the second-term bound, 'From Lemma 5' should be 'From Lemma 4'; and the bound obtained from Imported Lemma 4 is ε n, not ε^2 n, as discussed in the major comment.
  2. [§4.4, Lemma 12 statement] The final inequality contains a typo: 'C|A∥2' should be 'C||A||_2'.
  3. [§2.1 proof sketch] The sketch says that Property 1 applied with 'error parameter ε^2' gives an ε-subspace embedding for U_o with O~(1/ε^4) columns. The formal analogue is exactly the delicate point in Lemma 8; the sketch glosses over the threshold mismatch identified above.
  4. [Throughout] There are several typos and minor errors: 'cpnstant' in Lemma 8, 'byy' in the proof of Theorem 2, 'f rac' in Theorem 12, and the notation '|A∥2' in Lemma 12. These should be cleaned up.
  5. [§5, Lemma 20] Lemma 20 states a bound for any unit vector v, but the sign ambiguity is only resolved later in Lemma 21/the proof of Theorem 3 by replacing v with −v if necessary. This is fine, but it should be stated explicitly in Lemma 20 for clarity.

Circularity Check

0 steps flagged

No significant circularity; the eigenvector derivation is self-contained given published, independently checkable imported lemmas.

full rationale

The derivation chain is not circular. The central claim (Theorem 1) is a new eigenvector residual guarantee obtained by lifting eigenvectors of the scaled sampled principal submatrix; the proof is a direct analysis of ||A S_bar x|| and the residual in terms of A_o and A_m. Every imported result is a stated, published theorem from prior work: subspace embedding properties (SW25), middle eigenvalue bounds (BDD+24/SW25), eigenvalue approximation (SW25), the zeroing-out bound (BDD+24), and ridge leverage score sampling (MM17). The BDD+24 citations overlap with the present authors, but they are not load-bearing in a circular sense: they are peer-reviewed, stated with assumptions that do not include the target eigenvector conclusions, and used as black-box lemmas. No parameter is fitted to data, and no 'prediction' is manufactured from an input; the theorem parameters (epsilon, delta, s) are analytic sample-complexity choices. The only flagged concern, namely Lemma 8's use of the stronger epsilon^2 n middle-eigenvalue bound when Imported Lemma 4 is stated with L = epsilon sqrt(delta) n, is a potential correctness gap in the application of an imported lemma, not a circular identification of output with input; it does not change the circularity score.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No parameters are fitted to data; error thresholds (epsilon n, epsilon ||A||_F) are user-specified accuracy targets, and all constants c are absolute constants chosen sufficiently large. The rank-truncated Nystrom construction for indefinite matrices is a new algorithmic method, not a postulated entity. The listed axioms are the imported prior results and standard tools that the new analysis builds on.

axioms (5)
  • domain assumption Random column sample S_bar satisfies Property 1 (subspace embedding for outlying eigenspaces, min(R/lambda, 1/10) distortion) under uniform sampling of bounded-entry matrices and under squared column-norm sampling.
    Imported from Lemmas 4.2/4.3 of [SW25] (Imported Lemmas 1 and 2). It is the engine behind every residual-error bound; it holds because outlying eigenvectors of bounded-entry matrices are incoherent with leverage scores at most n/lambda^2.
  • domain assumption Middle-eigenvalue bounds: ||S_bar^T A_m S_bar||_2 <= epsilon n (uniform) or epsilon ||A||_F (column-norm), and ||A_m S_bar||_2 <= epsilon n.
    Imported Lemma 4 from [BDD+24] and Lemmas 4/11 here use Tropp's random submatrix bound; these control the contribution of small eigenvalues after sampling. The uniform version is imported, the column-norm version is adapted.
  • domain assumption Eigenvalue approximation of sampled principal submatrix: for s = Omega~(1/epsilon^2), eigenvalues of S_bar^T A S_bar approximate those of A to additive error epsilon n (uniform) or epsilon ||A||_F (column-norm).
    Imported Theorems 1 and 2 of [SW25]; used to match output pairs to true eigenvalues and to handle the top-eigenvector normalization.
  • domain assumption Distributed detection lower bound: any adaptive randomized algorithm solving (epsilon, n)-distributed detection must read Omega(n/epsilon^2) entries [BDM+24].
    Crucial for the tight lower bound Theorem 3; imported from [BDM+24].
  • standard math Standard tools: Weyl's inequality, Davis-Kahan/Wedin bounds, Tropp's random submatrix concentration, Chernoff bounds, Poisson splitting, and Le Cam's inequality for Poisson/binomial TV distances.
    Used throughout Sections 4-7 without proof; standard in the field.

pith-pipeline@v1.3.0-alltime-deepseek · 58196 in / 17137 out tokens · 179857 ms · 2026-08-05T00:11:49.520319+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Sublinear Time Eigenvector Approximation via Column Sampling." pith.science (2026). https://pith.science/paper/YM3NYAFZ

@misc{pith2026260800840,
  author       = {Pith},
  title        = {Pith review of: Sublinear Time Eigenvector Approximation via Column Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YM3NYAFZ}},
  note         = {Machine review of arXiv:2608.00840}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We study sublinear time sampling methods for approximating the outlying eigenvectors of large matrices. Our main result is an algorithm that uniformly samples just $\tilde{O}(\log n/\epsilon^4)$ columns of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries bounded in magnitude by $1$, and, for any eigenvalue $\lambda$ of $A$ with $|\lambda| \ge \epsilon n$, outputs an approximate eigenvector $v$ satisfying $\|Av - \lambda v\|_2 \le \epsilon n$. For approximating just the eigenvector of the largest magnitude eigenvalue, our algorithm samples only $\tilde{O}(\log n/\epsilon^2)$ columns. Given the ability to sample rows and columns of $A$ proportional to their squared norms, we give a similar result with an improved error bound of $\epsilon \|A\|_F$. For top eigenvector approximation, we show our bound is tight up to logarithmic terms. A key feature of our algorithms is that the output eigenvectors are spanned by a small number of $A$'s columns, and individual entries can be computed rapidly, in poly(log n, 1/epsilon) time per entry. This makes them applicable in the quantum-inspired algorithms framework of [Tang, STOC 2019], where we give the first sublinear time classical algorithms for eigenvector approximation with additive error $\epsilon \|A\|_F$. Finally, we present an alternative approach, based on a truncated Nystrom method, that, while not allowing poly(log n, 1/epsilon) time entrywise computation of the approximate eigenvectors, achieves near optimal sample complexity for general symmetric matrices, and improved bounds for positive semidefinite matrices. Technically, our bounds build on recent work on approximating the outlying eigenvalues of symmetric matrices via random sampling in [Bhattacharjee et al. '22] and [Swartworth and Woodruff '25]. We demonstrate for the first time that these approaches extend to the problem of eigenvector estimation.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 47 canonical work pages · 1 internal anchor

  1. [1]

    Algorithmica , pages=

    Sublinear time eigenvalue approximation via random sampling , author=. Algorithmica , pages=. 2024 , publisher=

    work page 2024

  2. [2]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Tight Sampling Bounds for Eigenvalue Approximation , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    work page 2025

  3. [3]

    Comptes Rendus

    Norms of random submatrices and sparse approximation , author=. Comptes Rendus. Math

    work page

  4. [4]

    15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages=

    Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra , author=. 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , pages=. 2024 , organization=

    work page 2024

  5. [5]

    2018 , publisher=

    High-dimensional probability: An introduction with applications in data science , author=. 2018 , publisher=

    2018

  6. [6]

    Advances in neural information processing systems , volume=

    Recursive sampling for the nystrom method , author=. Advances in neural information processing systems , volume=

  7. [7]

    Journal of the ACM , volume=

    Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning , author=. Journal of the ACM , volume=. 2022 , publisher=

    2022

  8. [8]

    The asymptotic distribution law for the eigenvalues of linear partial differential equations (with applications to the theory of black body radiation) , volume =

    Weyl, Hermann , journal =. The asymptotic distribution law for the eigenvalues of linear partial differential equations (with applications to the theory of black body radiation) , volume =

    work page

  9. [9]

    arXiv preprint arXiv:1811.04909 , year=

    Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension , author=. arXiv preprint arXiv:1811.04909 , year=

    Pith/arXiv arXiv

  10. [10]

    BIT Numerical Mathematics , volume=

    Perturbation bounds in connection with singular value decomposition , author=. BIT Numerical Mathematics , volume=. 1972 , publisher=

    1972

  11. [11]

    The spectral norm error of the na

    Gittens, A , year=. The spectral norm error of the na

    work page

  12. [12]

    Using the Nystr

    Williams, Christopher and Seeger, Matthias , journal=. Using the Nystr

  13. [13]

    A note on element-wise matrix sparsification via a matrix-valued

    Drineas, Petros and Zouzias, Anastasios , journal=. A note on element-wise matrix sparsification via a matrix-valued

    work page

  14. [14]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Spectral guarantees for adversarial streaming PCA , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

    work page 2024

  15. [15]

    Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

    Numerical linear algebra in the streaming model , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

    work page

  16. [16]

    Advances in Neural Information Processing Systems , volume=

    Approximating the top eigenvector in random order streams , author=. Advances in Neural Information Processing Systems , volume=

    work page

  17. [17]

    Fast matrix multiplication is stable , year =

    Demmel, James and Dumitriu, Ioana and Holtz, Olga and Kleinberg, Robert , journal =. Fast matrix multiplication is stable , year =

    work page

  18. [18]

    A refined laser method and faster matrix multiplication , year =

    Alman, Josh and Williams, Virginia Vassilevska , booktitle =. A refined laser method and faster matrix multiplication , year =

    work page

  19. [19]

    Matrix computations , Year =

    Golub, Gene H and Van Loan, Charles F , Publisher =. Matrix computations , Year =

    work page

  20. [20]

    Numerical methods for large eigenvalue problems:

    Saad, Yousef , publisher =. Numerical methods for large eigenvalue problems:

    work page

  21. [21]

    The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

    Spectral Estimation with Free Decompression , author=. The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

    work page

  22. [22]

    International Conference on Algorithmic Learning Theory , pages=

    Adaptive power method: Eigenvector estimation from sampled data , author=. International Conference on Algorithmic Learning Theory , pages=. 2023 , organization=

    work page 2023

  23. [23]

    International Conference on Machine Learning , pages=

    Faster kernel matrix algebra via density estimation , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    2021

  24. [24]

    Testing matrix rank, optimally , year =

    Balcan, Maria-Florina and Li, Yi and Woodruff, David P and Zhang, Hongyang , booktitle =. Testing matrix rank, optimally , year =

    work page

  25. [25]

    Testing positive semi-definiteness via random submatrices , year =

    Bakshi, Ainesh and Chepurko, Nadiia and Jayaram, Rajesh , date-added =. Testing positive semi-definiteness via random submatrices , year =

    work page

  26. [26]

    Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

    A quantum-inspired classical algorithm for recommendation systems , author=. Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

  27. [27]

    International Conference on Machine Learning , pages=

    Quantum-inspired algorithms from randomized numerical linear algebra , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    work page 2022

  28. [28]

    III , author=

    The rotation of eigenvectors by a perturbation. III , author=. SIAM Journal on Numerical Analysis , volume=. 1970 , publisher=

    1970

  29. [29]

    International Conference on Machine Learning , pages=

    Revisiting the nystrom method for improved large-scale machine learning , author=. International Conference on Machine Learning , pages=. 2013 , organization=

    work page 2013

  30. [30]

    Communications on Pure and Applied Mathematics , volume=

    Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations , author=. Communications on Pure and Applied Mathematics , volume=. 2025 , publisher=

    work page 2025

  31. [31]

    Frieze, Alan and Kannan, Ravi and Vempala, Santosh , journal=. Fast. 2004 , publisher=

    work page 2004

  32. [32]

    arXiv preprint arXiv:1104.1377 , year=

    Fast local computation algorithms , author=. arXiv preprint arXiv:1104.1377 , year=

    Pith/arXiv arXiv

  33. [33]

    Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Space-efficient local computation algorithms , author=. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2012 , organization=

    work page 2012

  34. [34]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Sublinear time low-rank approximation of positive semidefinite matrices , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    work page 2017

  35. [35]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Robust and sample optimal algorithms for PSD low rank approximation , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    work page 2020

  36. [36]

    Conference on Learning Theory , pages=

    Near-optimal entrywise sampling of numerically sparse matrices , author=. Conference on Learning Theory , pages=. 2021 , organization=

    work page 2021

  37. [37]

    Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Optimal column-based low-rank matrix reconstruction , author=. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2012 , organization=

    work page 2012

  38. [38]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Optimal CUR matrix decompositions , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    work page

  39. [39]

    Proceedings of the National Academy of Sciences , volume=

    CUR matrix decompositions for improved data analysis , author=. Proceedings of the National Academy of Sciences , volume=. 2009 , publisher=

    2009

  40. [40]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Sublinear Time Low-Rank Approximation of Hankel Matrices , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    work page 2026

  41. [41]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Sublinear time low-rank approximation of toeplitz matrices , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    work page 2024

  42. [42]

    Advances in Neural Information Processing Systems , volume=

    Sublinear time low-rank approximation of distance matrices , author=. Advances in Neural Information Processing Systems , volume=

    work page

  43. [43]

    2017 , publisher=

    Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis , author=. 2017 , publisher=

    2017

  44. [44]

    , author=

    An approximation theorem for the Poisson binomial distribution. , author=

    work page

  45. [45]

    Acta Numerica , volume=

    Randomized numerical linear algebra: Foundations and algorithms , author=. Acta Numerica , volume=. 2020 , publisher=

    2020

  46. [46]

    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Low-rank PSD approximation in input-sparsity time , author=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2017 , organization=

    work page 2017

  47. [47]

    Advances in neural information processing systems , volume=

    Random features for large-scale kernel machines , author=. Advances in neural information processing systems , volume=

  48. [48]

    Conference on Learning Theory , pages=

    Sample-optimal low-rank approximation of distance matrices , author=. Conference on Learning Theory , pages=. 2019 , organization=

    work page 2019

  49. [49]

    ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages=

    Low-rank Toeplitz matrix estimation via random ultra-sparse rulers , author=. ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages=. 2020 , organization=

    work page 2020

  50. [50]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Toeplitz low-rank approximation with sublinear query complexity , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    work page 2023

  51. [51]

    Proceedings of the 24th acm sigkdd international conference on knowledge discovery & data mining , pages=

    Approximating the spectrum of a graph , author=. Proceedings of the 24th acm sigkdd international conference on knowledge discovery & data mining , pages=

    work page

  52. [52]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Improved spectral density estimation via explicit and implicit deflation , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    work page 2025

  53. [53]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Sublinear time spectral density estimation , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    work page

  54. [54]

    arXiv preprint arXiv:2009.11392 , year=

    Fast and stable randomized low-rank matrix approximation , author=. arXiv preprint arXiv:2009.11392 , year=

    Pith/arXiv arXiv 2009

  55. [55]

    Machine learning , volume=

    Clustering large graphs via the singular value decomposition , author=. Machine learning , volume=. 2004 , publisher=

    work page 2004

  56. [56]

    SIAM Journal on computing , volume=

    Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix , author=. SIAM Journal on computing , volume=. 2006 , publisher=

    work page 2006

  57. [57]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    A quantum speed-up for approximating the top eigenvectors of a matrix , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    work page 2025

  58. [58]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Randomized low-rank approximation for symmetric indefinite matrices , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2023 , publisher=

    work page 2023

  59. [59]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Fast deterministic approximation of symmetric indefinite kernel matrices with high dimensional datasets , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2022 , publisher=

    work page 2022

  60. [60]

    International Conference on Machine Learning , pages=

    Scalable learning in reproducing kernel Krein spaces , author=. International Conference on Machine Learning , pages=. 2019 , organization=

    work page 2019

  61. [61]

    Locally Approximating the Top Eigenvector of Bounded Entry Matrices

    Locally Approximating the Top Eigenvector of Bounded Entry Matrices , author=. arXiv preprint arXiv:2607.08556 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  62. [62]

    Journal of the ACM (JACM) , volume=

    Property testing and its connection to learning and approximation , author=. Journal of the ACM (JACM) , volume=. 1998 , publisher=

    work page 1998