High-Dimensional Geometric Streaming in Polynomial Space
High-Dimensional Geometric Streaming in Polynomial Space
复制标题
DOI：
10.1109/focs54457.2022.00075
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
David P. Woodruff;T. Yasuda
中科院分区：
文献类型：
--
作者：
David P. Woodruff;T. Yasuda
Many existing algorithms for streaming geometric data analysis have been plagued by exponential dependencies in the space complexity, which are undesirable for processing high-dimensional data sets, i.e., large d. In particular, once $d\geq\log n$, there are no known non-trivial streaming algorithms for problems such as maintaining convex hulls and Löwner-John ellipsoids of n points, despite a long line of work in high-dimensional streaming computational geometry since [2]. We simultaneously improve all of these results to poly $(d,\ \log n)$ bits of space by trading off with a poly $(d,\ \log n)$ factor distortion. We achieve these results in a unified manner, by designing the first streaming algorithm for maintaining a coreset for $\ell_{\infty}$ subspace embeddings with poly $(d,\ \log n)$ space and poly $(d,\ \log n)$ distortion. Our algorithm also gives similar guarantees in the online coreset model. Along the way, we sharpen known results for online numerical linear algebra by replacing a $\log$ condition number dependence with a $\log n$ dependence, answering an open question of [13]. Our techniques provide a novel connection between leverage scores, a fundamental object in numerical linear algebra, and computational geometry. For $\ell_{p}$ subspace embeddings, our improvements in online numerical linear algebra yield nearly optimal tradeoffs between space and distortion for one-pass streaming algorithms. For instance, we obtain a deterministic coreset using $o(d^{2}\log n)$ space and $o((d\log n)^{\frac{1}{2}-\frac{1}{p}})$ distortion for $p\gt 2$, whereas previous deterministic algorithms incurred a poly (n) factor in the space or the distortion [26]. Our techniques have implications also in the offline setting, where we give optimal trade-offs between the space complexity and distortion of a subspace sketch data structure, which preprocesses an $n\times d$ matrix A and outputs $\Vert \mathrm{A}\mathrm{x}\Vert_{p}$ up to a poly (d) factor distortion for any x. To do this we give an elementary proof of a “change of density” theorem of [42] and make it algorithmic.11Extended abstract; full version available at https://arxiv.org/abs/ 2204.03790.
Many existing algorithms for streaming geometric data analysis have been plagued by exponential dependencies in the space complexity, which are undesirable for processing high-dimensional data sets, i.e., large d. In particular, once $d\geq\log n$, there are no known non-trivial streaming algorithms for problems such as maintaining convex hulls and Löwner-John ellipsoids of n points, despite a long line of work in high-dimensional streaming computational geometry since [2]. We simultaneously improve all of these results to poly $(d,\ \log n)$ bits of space by trading off with a poly $(d,\ \log n)$ factor distortion. We achieve these results in a unified manner, by designing the first streaming algorithm for maintaining a coreset for $\ell_{\infty}$ subspace embeddings with poly $(d,\ \log n)$ space and poly $(d,\ \log n)$ distortion. Our algorithm also gives similar guarantees in the online coreset model. Along the way, we sharpen known results for online numerical linear algebra by replacing a $\log$ condition number dependence with a $\log n$ dependence, answering an open question of [13]. Our techniques provide a novel connection between leverage scores, a fundamental object in numerical linear algebra, and computational geometry. For $\ell_{p}$ subspace embeddings, our improvements in online numerical linear algebra yield nearly optimal tradeoffs between space and distortion for one-pass streaming algorithms. For instance, we obtain a deterministic coreset using $o(d^{2}\log n)$ space and $o((d\log n)^{\frac{1}{2}-\frac{1}{p}})$ distortion for $p\gt 2$, whereas previous deterministic algorithms incurred a poly (n) factor in the space or the distortion [26]. Our techniques have implications also in the offline setting, where we give optimal trade-offs between the space complexity and distortion of a subspace sketch data structure, which preprocesses an $n\times d$ matrix A and outputs $\Vert \mathrm{A}\mathrm{x}\Vert_{p}$ up to a poly (d) factor distortion for any x. To do this we give an elementary proof of a “change of density” theorem of [42] and make it algorithmic.11Extended abstract; full version available at https://arxiv.org/abs/ 2204.03790.