Streaming Symmetric Norms via Measure Concentration
213 views · Published 14 March 2016 · 34:03 · Indexed 8 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Stephen Chestnut (ETH Zurich) Abstract: We characterize the streaming space complexity of every symmetric norm [Math Processing Error] (a norm on [Math Processing Error] invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of [Math Processing Error]. Specifically, we provide upper and lower bounds on the space complexity of approximating the norm of the stream, where both bounds depend on the median of [Math Processing Error] when [Math Processing Error] is drawn uniformly from the [Math Processing Error] unit sphere. The same quantity governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem. The family of symmetric norms contains several well-studied norms, such as all [Math Processing Error] norms, and indeed we provide a new explanation for the disparity in space complexity between [Math Processing Error] and [Math Processing Error]. In addition, we apply our general results to easily derive bounds for several norms were not studied before in the streaming model, including for example the top-k norm and the k-support norm, which was recently shown to be effective for machine learning tasks. Overall, these results make progress on two outstanding problems in the area of sublinear algorithms (Problems 5 and 30 at sublinear.info).
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...