High-Dimensional Geometric Streaming in Polynomial Space
From MaRDI portal
Abstract: 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. In particular, once , there are no known non-trivial streaming algorithms for problems such as maintaining convex hulls and L"owner-John ellipsoids of points, despite a long line of work in streaming computational geometry since [AHV04]. We simultaneously improve these results to bits of space by trading off with a factor distortion. We achieve these results in a unified manner, by designing the first streaming algorithm for maintaining a coreset for subspace embeddings with space and distortion. Our algorithm also gives similar guarantees in the emph{online coreset} model. Along the way, we sharpen results for online numerical linear algebra by replacing a log condition number dependence with a dependence, answering a question of [BDM+20]. Our techniques provide a novel connection between leverage scores, a fundamental object in numerical linear algebra, and computational geometry. For subspace embeddings, we give nearly optimal trade-offs between space and distortion for one-pass streaming algorithms. For instance, we give a deterministic coreset using space and distortion for , whereas previous deterministic algorithms incurred a factor in the space or the distortion [CDW18]. Our techniques have implications in the offline setting, where we give optimal trade-offs between the space complexity and distortion of subspace sketch data structures. To do this, we give an elementary proof of a "change of density" theorem of [LT80] and make it algorithmic.
This page was built for publication: High-Dimensional Geometric Streaming in Polynomial Space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6395997)
