Streaming symmetric norms via measure concentration
Streaming symmetric norms via measure concentration
复制标题
DOI：
10.1145/3055399.3055424
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Jarosław Błasiok;Vladimir Braverman;Stephen R. Chestnut;Robert Krauthgamer;Lin F. Yang
中科院分区：
文献类型：
--
作者：
Jarosław Błasiok;Vladimir Braverman;Stephen R. Chestnut;Robert Krauthgamer;Lin F. Yang
我们通过将空间复杂度与 l 的测量浓度特征相关联来表征每个对称范数 l（符号翻转和坐标排列下 ℝn 不变的范数）的流空间复杂度。具体来说，我们提供了几乎匹配的上限和下限，用于计算每 0 2 的流范数的 (1 ± ε) 近似值。此外，我们应用我们的一般结果来轻松导出流模型中以前未研究过的几个范数的界限，包括最近用于机器学习任务的 top-k 范数和 k-support 范数。总的来说，这些结果在次线性算法领域的两个突出问题上取得了进展（http://sublinear.info 中的问题 5 和 30）。
We characterize the streaming space complexity of every symmetric norm l (a norm on ℝ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 ± ε)-approximation to the norm of the stream, for every 0 2. 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 http://sublinear.info.