Pith. sign in

REVIEW 2 cited by

Randomized Nystr\"om Preconditioning

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2110.02820 v2 pith:BS7LPZ3F submitted 2021-10-06 math.NA cs.NA

Zachary Frangella , Joel A. Tropp , Madeleine Udell This is my paper · ORCID
classification math.NAcs.NA
keywords nystralgorithmanalysisapproximationeffectivelinearmatrixmethods
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

This paper introduces the Nystr\"om PCG algorithm for solving a symmetric positive-definite linear system. The algorithm applies the randomized Nystr\"om method to form a low-rank approximation of the matrix, which leads to an efficient preconditioner that can be deployed with the conjugate gradient algorithm. Theoretical analysis shows that preconditioned system has constant condition number as soon as the rank of the approximation is comparable with the number of effective degrees of freedom in the matrix. The paper also develops adaptive methods that provably achieve similar performance without knowledge of the effective dimension. Numerical tests show that Nystr\"om PCG can rapidly solve large linear systems that arise in data analysis problems, and it surpasses several competing methods from the literature.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

    cs.DS 2025-07 conditional novelty 8.0 of 10

    New recursive preconditioning algorithms solve k-well-conditioned linear systems and regressions in Õ(d² + k^ω) time, matching the conditional lower bound and yielding the first nearly-linear-time nuclear norm approximation.

  2. Training Flexible Models of Genetic Variant Effects from Functional Annotations using Accelerated Linear Algebra

    cs.LG 2025-06 conditional novelty 7.0 of 10

    DeepWAS scales full-likelihood training of flexible variant-effect priors to millions of variants and finds larger neural-network priors generalize better than smaller ones.

Pith tools