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. For instance, the best known algorithms for maintaining convex hulls and Löwner-John ellipsoids use ε -Θ(d) bits of space; maintaining ℓp subspace embeddings use d p/2+1 bits of space; and selecting k out of n given vectors in R d maximizing the k-dimensional volume uses 2 k d bits of space. These are all intractable for large d, p, or k. In particular, once d ≥ 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 [AHV04] (J. ACM 2004).

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 ℓ∞ 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 [BDM + 20] (FOCS 2020). Our techniques provide a novel connection between leverage scores, a fundamental object in numerical linear algebra, and computational geometry.

For ℓp subspace embeddings, our improvements in online numerical linear algebra yield nearly optimal trade-offs 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) 1 2 -1 p ) distortion for p > 2, whereas previous deterministic algorithms incurred a poly(n) factor in the space or the distortion [CDW18] (ICML 2018).

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 × d matrix A and outputs Ax 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 [LT80] (J. Functional Analysis 1980) and make it algorithmic. 1 2 -1 p ) distortion, significantly improving upon the earlier deterministic one-pass algorithms of [CDW18], which incurred a poly(n) factor in either the space complexity or distortion. This nearly matches the guarantee obtained by using Lewis weights in the offline setting [Lew78, SZ01, CP15], and in fact achieves optimal trade-offs, up to poly log n factors. See Table 1 for a summary of our results.

Furthermore, many of our algorithms yield mergeable summaries, i.e., the data structures for two matrices A 1 and A 2 can be merged with little overhead to form a data structure for the concatenation [A ⊤ 1 A ⊤ 2 ] ⊤ . This allows our algorithms to apply to distributed settings, where the rows of the input are partitioned among many servers [CDW18].

Although our streaming ℓ p subspace sketch achieves nearly optimal trade-offs up to polylogarithmic factors, it is still possible to ask for improvements in these bounds, as well as faster algorithms, in the offline setting where we have unlimited access to A. In a third contribution, in the offline setting, we construct ℓ p subspace embeddings with nearly optimal trade-offs between space complexity and distortion, which shave all poly log n factors off of the distortion. As a crucial step, we give a new elementary proof of a "change of density" theorem in geometric functional analysis due to Lewis and Tomczak-Jaegermann [LT80], by using Lewis weights [Lew78,SZ01,CP15]. This allows us to make the construction algorithmic, and in fact, nearly input sparsity time. Our space complexity upper bound matches a subspace sketch lower bound due to [LWW21]. These subspace sketch lower bounds also witness the near tightness of our streaming ℓ p subspace sketch algorithms. See Table 2 for our results on the offline subspace sketch problem.

Furthermore, our fast algorithms for computing these ℓ p subspace embeddings give the fastest known running times for ℓ p regression and ℓ p column subset selection, when we allow for distortions which scale as poly(d) (see Table 3). Note that algorithms for ℓ p column subset selection already incur distortions on the order poly(d) [CGK + 17, DWZ + 19] (as they must due to known lower bounds).

Finally, we return to the study of streaming algorithms for ℓ p subspace embeddings, and implement the above offline trade-off by showing how to compute Lewis weights using a small number of passes. This requires generalizations of Lewis weight computation and sampling results [CP15] as well as our "change of density" theorem that work with only O(log n) bit complexity, which may be of i