Deterministic Coreset for Lp Subspace

arXiv:2601.00361v3 Announce Type: replace-cross Abstract: We introduce the first iterative algorithm for constructing a arepsilon-coreset that guarantees deterministic ell_p subspace embedding for any p in [1,infty) and any arepsilon > 0. For a given full rank matrix mathbf{X} in R^{n imes d} where n gg d, mathbf{X}' in R^{m imes d} is an (arepsilon,ell_p)-subspace embedding of mathbf{X}, if for every mathbf{q} in R^d, (1-arepsilon)|mathbf{Xq}|{p}^{p} leq |mathbf{X'q}|{p}^{p} leq (1+arepsilon)|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 arepsilon, our algorithm takes O(poly(n,d,arepsilon^{-1})) time and returns a deterministic arepsilon-coreset, for ell_p subspace embedding whose size is Oleft(frac{d^{max{1,p/2}}}{arepsilon^{2}}right). 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 ell_p regression problem in a deterministic manner.

Source: arXiv cs.LG | 2026-05-18