mlsanityData to 7 Oct 2026

Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data

arXiv 1706.05736 ↗First posted 18 Jun 2017math.NA cs.DS cs.NAcited by 22

Not on the map. Why?

Abstract (arXiv)

Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retain a sketch of the psd matrix. This paper develops a new algorithm for fixed-rank psd approximation from a sketch. The approach combines the Nystrom approximation with a novel mechanism for rank truncation. Theoretical analysis establishes that the proposed method can achieve any prescribed relative error in the Schatten 1-norm and that it exploits the spectral decay of the input matrix. Computer experiments show that the proposed method dominates alternative techniques for fixed-rank psd matrix approximation across a wide range of examples.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Jun 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 3; 2024: 5; 2025: 7; 2026: 1.

22 papers.

Sort:

  1. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 35
  2. 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 31
  3. 2021Learning to Forecast Dynamical Systems from Streaming Datacited by 17
  4. 2023Sampling-based Nystr"om Approximation and Kernel Quadraturecited by 17
  5. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  6. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  7. 2022Log-Euclidean Signatures for Intrinsic Distances Between Unaligned Datasetscited by 5
  8. 2024Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuningcited by 5
  9. 2023Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketchingcited by 4
  10. 2024CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networkscited by 4
  11. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  12. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
10 more
  1. 2026Low-Rank Adaptation Redux for Large Modelscited by 2
  2. 2025Connecting Parameter Magnitudes and Hessian Eigenspaces at Scale using Sketched Methodscited by 1
  3. 2025Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebracited by 1
  4. 2022Efficient error and variance estimation for randomized matrix computationscited by 0
  5. 2023Boosting Nystr"om Methodcited by 0
  6. 2024Polynomial Precision Dependence Solutions to Alignment Research Center Matrix Completion Problemscited by 0
  7. 2024Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+cited by 0
  8. 2025What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?cited by 0
  9. 2025NysAct: A Scalable Preconditioned Gradient Descent using Nystrom Approximationcited by 0
  10. 2025Generalized infinite dimensional Alpha-Procrustes based geometriescited by 0