[2601.00361] Deterministic Coreset for Lp Subspace

Computer Science > Data Structures and Algorithms arXiv:2601.00361 (cs) This paper has been withdrawn by Supratim Shit [Submitted on 1 Jan 2026 (v1), last revised 4 Mar 2026 (this version, v2)] Title:Deterministic Coreset for Lp Subspace Authors:Rachit Chhaya, Anirban Dasgupta, Dan Feldman, Supratim Shit View a PDF of the paper titled Deterministic Coreset for Lp Subspace, by Rachit Chhaya and 2 other authors No PDF available, click to view other formats Abstract:We introduce the first iterative algorithm for constructing a $\varepsilon$-coreset that guarantees deterministic $\ell_p$ subspace embedding for any $p \in [1,\infty)$ and any $\varepsilon > 0$. For a given full rank matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ where $n \gg d$, $\mathbf{X}' \in \mathbb{R}^{m \times d}$ is an $(\varepsilon,\ell_p)$-subspace embedding of $\mathbf{X}$, if for every $\mathbf{q} \in \mathbb{R}^d$, $(1-\varepsilon)\|\mathbf{Xq}\|_{p}^{p} \leq \|\mathbf{X'q}\|_{p}^{p} \leq (1+\varepsilon)\|\mathbf{Xq}\|_{p}^{p}$. Specifically, in this paper, $\mathbf{X}'$ is a weighted subset of rows of $\mathbf{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 $\ell_p$ subspace embedding. For an error parameter $\v...