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

arXiv: https://arxiv.org/abs/1706.05736 · HTML: https://mlsanity.com/paper/1706.05736/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2017.

## Built on by (most cited first, 23 of 23)

- [Rewiring with Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2201.12674/) (2022)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [On the Crucial Role of Initialization for Matrix Factorization](https://mlsanity.com/paper/2410.18965/) (2024)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [Log-Euclidean Signatures for Intrinsic Distances Between Unaligned Datasets](https://mlsanity.com/paper/2202.01671/) (2022)
- [Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning](https://mlsanity.com/paper/2407.06120/) (2024)
- [Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching](https://mlsanity.com/paper/2312.11801/) (2023)
- [CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks](https://mlsanity.com/paper/2411.01088/) (2024)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)
- [Efficient error and variance estimation for randomized matrix computations](https://mlsanity.com/paper/2207.06342/) (2022)
- [Connecting Parameter Magnitudes and Hessian Eigenspaces at Scale using Sketched Methods](https://mlsanity.com/paper/2504.14701/) (2025)
- [Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2505.11638/) (2025)
- [Boosting Nystr"om Method](https://mlsanity.com/paper/2302.11032/) (2023)
- [Polynomial Precision Dependence Solutions to Alignment Research Center Matrix Completion Problems](https://mlsanity.com/paper/2401.03999/) (2024)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)
- [NysAct: A Scalable Preconditioned Gradient Descent using Nystrom Approximation](https://mlsanity.com/paper/2506.08360/) (2025)
- [Generalized infinite dimensional Alpha-Procrustes based geometries](https://mlsanity.com/paper/2511.09801/) (2025)
- [Clean: Second-order LLM Training at Linear Memory Cost via Nystr"om Sketching](https://mlsanity.com/paper/2610.04204/) (2026)

## 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.