Streaming Symmetric Norms via Measure Concentration
| Autor: | Robert Krauthgamer, Jaroslaw Blasiok, Vladimir Braverman, Lin F. Yang, Stephen R. Chestnut |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Data stream
Unit sphere Discrete mathematics FOS: Computer and information sciences Sublinear function 0102 computer and information sciences 010501 environmental sciences Sublinear algorithms 01 natural sciences Upper and lower bounds Combinatorics 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Norm (social) Invariant (mathematics) Critical dimension 0105 earth and related environmental sciences Mathematics |
| Zdroj: | STOC |
| Popis: | We characterize the streaming space complexity of every symmetric norm $l$ (a norm on $\mathbb{R}^n$ invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of $l$. Specifically, we provide nearly matching upper and lower bounds on the space complexity of calculating a $(1\pm\epsilon)$-approximation to the norm of the stream, for every $02$. In addition, we apply our general results to easily derive bounds for several norms that were not studied before in the streaming model, including the top-$k$ norm and the $k$-support norm, which was recently employed for machine learning tasks. Overall, these results make progress on two outstanding problems in the area of sublinear algorithms (Problems 5 and 30 in~\url{http://sublinear.info}). Comment: published in STOC 2017 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|