High-Dimensional Geometric Streaming in Polynomial Space

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.
^1
1
Extended abstract; full version available at https://arxiv.org/abs/ 2204.03790.