The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Norm Estimation, Precision Sampling, and Rademacher Type

Andoni, A (Microsoft Research)
Wednesday 12 January 2011, 10:00-11:00

Seminar Room 1, Newton Institute


We describe new algorithms to compute norms of a vector in a stream, which can be seen as linear embeddings into certain low-dimensional "computational spaces". In particular, we show that for a variety of settings, simple algorithms follow from the application of a single simple probabilistic technique, called Precision Sampling. These settings include classic scenarios such as l_p norms for p\in(0,2] and p>2, as well as mixed norms l_p(l_q). In the latter case, we show how (a natural generalization of) the Rademacher type yields essentially tight bounds for all regimes p,q>0.

Precision Sampling itself addresses the problem of estimating a sum of reals \sum a_i from weak estimates of each a_i\in[0,1]. More precisely, one chooses in advance "precisions" w_i>=1 for each i and obtains an estimate of a_i within additive 1/w_i. The core question is: what is the best trade-off between the approximation to \sum a_i and the total precision, \sum_i w_i ?

Joint work with Robert Krauthgamer and Krzysztof Onak.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧