# Deterministic Coreset for Lp Subspace

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 53 references that are in the map.
- First posted on arXiv 1 Jan 2026.

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

- [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)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Data-Independent Neural Pruning via Coresets](https://mlsanity.com/paper/1907.04018/) (2019)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Coreset-Based Neural Network Compression](https://mlsanity.com/paper/1807.09810/) (2018)
- [Coresets for Robust Training of Neural Networks against Noisy Labels](https://mlsanity.com/paper/2011.07451/) (2020)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [Fast Regression for Structured Inputs](https://mlsanity.com/paper/2203.07557/) (2022)
- [On Coresets For Regularized Regression](https://mlsanity.com/paper/2006.05440/) (2020)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Approximating Spectral Clustering via Sampling: a Review](https://mlsanity.com/paper/1901.10204/) (2019)
- [Streaming Coresets for Symmetric Tensor Factorization](https://mlsanity.com/paper/2006.01225/) (2020)
- [Improved Iteration Complexities for Overconstrained p-Norm Regression](https://mlsanity.com/paper/2111.01848/) (2021)
- [Computing Lewis Weights to High Precision](https://mlsanity.com/paper/2110.15563/) (2021)
- [Coresets for Clustering with Missing Values](https://mlsanity.com/paper/2106.16112/) (2021)
- [Coresets for Kernel Regression](https://mlsanity.com/paper/1702.03644/) (2017)
- [Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Norms](https://mlsanity.com/paper/1807.02571/) (2018)
- [The Vector Balancing Constant for Zonotopes](https://mlsanity.com/paper/2210.16460/) (2022)
- [Randomized Composable Coresets for Matching and Vertex Cover](https://mlsanity.com/paper/1705.08242/) (2017)
- [Accurate Coresets for Latent Variable Models and Regularized Regression](https://mlsanity.com/paper/2412.20189/) (2024)

## Abstract (arXiv)

We introduce the first iterative algorithm for constructing a varepsilon-coreset that guarantees deterministic ℓp subspace embedding for any p ∈ [1,∞) and any varepsilon > 0. For a given full rank matrix X ∈ ℝn × d where n gg d, X' ∈ ℝm × d is an (varepsilon,ℓp)-subspace embedding of X, if for every q ∈ ℝd, (1-varepsilon)|Xq|pp ≤ |X'q|pp ≤ (1+varepsilon)|Xq|pp. Specifically, in this paper, X' is a weighted subset of rows of X which is commonly known in the literature as a coreset. In every iteration, the algorithm ensures that the loss on the maintained set is upper and lower bounded by the loss on the original dataset with appropriate scalings. So, unlike typical coreset guarantees, due to bounded loss, our coreset gives a deterministic guarantee for the ℓp subspace embedding. For an error parameter varepsilon, our algorithm takes O(poly(n,d,varepsilon-1)) time and returns a deterministic varepsilon-coreset, for ℓp subspace embedding whose size is Oleft(fracd^max1,p/2varepsilon2right). Here, we remove the log factors in the coreset size, which had been a long-standing open problem. Our coresets are optimal as they are tight with the lower bound. As an application, our coreset can also be used for approximately solving the ℓp regression problem in a deterministic manner.