# Turnstile ℓp leverage score sampling with applications

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 61 references that are in the map.
- First posted on arXiv 1 Jun 2024.

## Builds on (most cited first, 24 of 24)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [New Subset Selection Algorithms for Low Rank Approximation: Offline and Online](https://mlsanity.com/paper/2304.09217/) (2023)
- [Non-Adaptive Adaptive Sampling on Turnstile Streams](https://mlsanity.com/paper/2004.10969/) (2020)
- [Streaming Coresets for Symmetric Tensor Factorization](https://mlsanity.com/paper/2006.01225/) (2020)
- [ℓp Row Sampling by Lewis Weights](https://mlsanity.com/paper/1412.0588/) (2014)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing](https://mlsanity.com/paper/2104.12946/) (2021)
- [Streaming Euclidean k-median and k-means with o(log n) Space](https://mlsanity.com/paper/2310.02882/) (2023)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [Truly Perfect Samplers for Data Streams and Sliding Windows](https://mlsanity.com/paper/2108.12017/) (2021)
- [Clustering High Dimensional Dynamic Data Streams](https://mlsanity.com/paper/1706.03887/) (2017)
- [Perfect Lp Sampling in a Data Stream](https://mlsanity.com/paper/1808.05497/) (2018)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)
- [On Approximating Functions of the Singular Values in a Stream](https://mlsanity.com/paper/1604.08679/) (2016)
- [Tight Lower Bound for Linear Sketches of Moments](https://mlsanity.com/paper/1306.6295/) (2013)

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

- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)
- [Fast Length-Squared Sampling for Positive-Semidefinite Matrices](https://mlsanity.com/paper/2608.12503/) (2026)

## Abstract (arXiv)

The turnstile data stream model offers the most flexible framework where data can be manipulated dynamically, i.e., rows, columns, and even single entries of an input matrix can be added, deleted, or updated multiple times in a data stream. We develop a novel algorithm for sampling rows ai of a matrix A∈ℝn× d, proportional to their ℓp norm, when A is presented in a turnstile data stream. Our algorithm not only returns the set of sampled row indexes, it also returns slightly perturbed rows tildeai ≈ ai, and approximates their sampling probabilities up to varepsilon relative error. When combined with preconditioning techniques, our algorithm extends to ℓp leverage score sampling over turnstile data streams. With these properties in place, it allows us to simulate subsampling constructions of coresets for important regression problems to operate over turnstile data streams with very little overhead compared to their respective off-line subsampling algorithms. For logistic regression, our framework yields the first algorithm that achieves a (1+varepsilon) approximation and works in a turnstile data stream using polynomial sketch/subsample size, improving over O(1) approximations, or exp(1/varepsilon) sketch size of previous work. We compare experimentally to plain oblivious sketching and plain leverage score sampling algorithms for ℓp and logistic regression.