# What is the meaning of $\|a\|_p=\left(\sum _{i=1}^n \left|a_i(t)\right|{}^p\right){}^{\frac{1}{p}}$?

What is the meaning of $\|a\|_p=\left(\sum _{i=1}^n \left|a_i(t)\right|{}^p\right){}^{\frac{1}{p}}$?

This formula is called out on the fifth page of An Improved Data Stream Summary: The Count-Min Sketch and its Applications (which can be found here). I'm implementing the Count-Min Sketch and can understand the basic concepts just fine, but some of the finer points are explained in terms of this equation and some other terminology that I'm unacquainted with.

-

It's the $L^p$ norm. See for example the Wikipedia articles:

If you use $p = 2$, you'll find it resolves to the more familiar Euclidean norm -- i.e. the most familiar measure used as length of the vector $a$. Other values of p give others ways of measuring length as outlined in the article -- see the sections on Euclidean norm, Taxicab norm, etc.

-
Is there an approachable textbook you could recommend that discusses how and why Manhattan Distances are useful in statistics? –  Kaelin Colclasure Oct 17 '10 at 20:44
@Kaelin: Unfortunately I can't think of a text which discusses this in particular. I can tell you that the L1 distance is preferred since it's less sensitive to outliers. It's also related to distances between empirical distributions in probability theory ( L1 is twice the "total variation distance": en.wikipedia.org/wiki/Total_variation_distance ). –  ars Oct 17 '10 at 22:00
This paper does not appear to use $L^p$ norms in any essential way--every one of the results references the $L^1$ norm explicitly. The problem itself determines which norm to use. In this case interest focuses on the cardinality of multisets. A multiset is represented as a vector of counts of its elements, whence its cardinality happens to be the same as its $L^1$ norm. Often results proven for one norm may hold without any change needed in the proof for a wide range of $p$ (typically $1 \le p \le \infty$). The opportunity for greater generality at no cost will lead many papers like this to talk about $L^p$ norms.
$L^p$ norms come into their own in discussions of duality in Hilbert and Banach space theory. Advanced, but introductory (it's not a contradiction!) books on analysis usually cover this material thoroughly. For an introduction to some of the relationships among these norms, read about the Holder Inequality and the Minkowski Inequality.