# Online Row Sampling

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2016.

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

- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Online Active Regression](https://mlsanity.com/paper/2207.05945/) (2022)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions](https://mlsanity.com/paper/2410.05462/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Improved large-scale graph learning through ridge spectral sparsification](https://mlsanity.com/paper/2604.20078/) (2026)
- [Online Sub-Sampling for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2106.07203/) (2021)
- [Distribution-Aware Feature Selection for SAEs](https://mlsanity.com/paper/2508.21324/) (2025)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)
- [AGILE-GS: Anchor-Guided Fast Next-Best-View Selection for Active 3D Gaussian Splatting](https://mlsanity.com/paper/2609.34176/) (2026)

## Abstract (arXiv)

Finding a small spectral approximation for a tall n × d matrix A is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows are sampled from those of A. Row sampling improves interpretability, saves space when A is sparse, and preserves row structure, which is especially important, for example, when A represents a graph. However, correctly sampling rows from A can be costly when the matrix is large and cannot be stored and processed in memory. Hence, a number of recent publications focus on row sampling in the streaming setting, using little more space than what is required to store the outputted approximation [KL13, KLM+14]. Inspired by a growing body of work on online algorithms for machine learning and data analysis, we extend this work to a more restrictive online setting: we read rows of A one by one and immediately decide whether each row should be kept in the spectral approximation or discarded, without ever retracting these decisions. We present an extremely simple algorithm that approximates A up to multiplicative error ε and additive error δ using O(d log d log(ε||A||2/δ)/ε2) online samples, with memory overhead proportional to the cost of storing the spectral approximation. We also present an algorithm that uses O(d2) memory but only requires O(dlog(ε||A||2/δ)/ε2) samples, which we show is optimal. Our methods are clean and intuitive, allow for lower memory usage than prior work, and expose new theoretical properties of leverage score based matrix approximation.