10
$\begingroup$

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.

$\endgroup$

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Is there an approachable textbook you could recommend that discusses how and why Manhattan Distances are useful in statistics? $\endgroup$ Oct 17, 2010 at 20:44
  • 1
    $\begingroup$ @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 ). $\endgroup$
    – ars
    Oct 17, 2010 at 22:00
  • $\begingroup$ You can see here an intuitive explanation on why the Manhattan distance, or L1 norm, is preferred over other distances. It all comes down to the "curse of dimensionality". Also, to be more specific, $L^n$ is the Lebesgue space of integrable functions, whereas $l^n$ is the vector space for vectors containing arbitrarily many components. Basically, when you're talking about sums of features, you're talking $l^n$ and, when you're integrating functions, it's $L^n$. $\endgroup$ May 11, 2015 at 22:19
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ +1. Though I'm not sure an analysis book, even if it is Rudin, is "approachable". ;-) $\endgroup$
    – ars
    Oct 18, 2010 at 0:35
  • $\begingroup$ @ars: Yes, but I don't know of any one that really is. That's why I pointed out the two Wikipedia articles. $\endgroup$
    – whuber
    Oct 18, 2010 at 3:37
  • $\begingroup$ I know, I liked it -- it's the right recommendation to make in case the OP wants to dig deeper. $\endgroup$
    – ars
    Oct 18, 2010 at 4:12
2
$\begingroup$

$||a||$ denotes a specific function, called norm, defined on a vector space. It maps a $n$-dimensional element of a vector space into a non-negative real number. $||a||_p$ denotes a yet particular norm defined on the vector space. Let $V$ be a vector space. Any function $p:V\to R_+$, also denoted $p(v)\equiv ||v||$ such that

  1. $ p $ is finite and convex
  2. $ p(x)=0 \implies x=0 $
  3. $ \forall \alpha_{}\in R, \forall x\in V, p(\alpha_{}x)=|\alpha_{}|p(x) $

is called a norm in $V$ and $(V,p)\equiv (V,||\cdot||$ is then called a normed space. You can check that your function satisfies all these properties. In your example, also, $V$ is a space of functions, that is $a_i:T\to T'$. That is a generalization of the Euclidean space (with Euclidean norm) that you may be familiar with, which is just a particular case of normed space where the underlying set is the (n-dimensional) real numbers and the norm is the called Euclidean norm, a particular case of the function that appears in your question.

For instance, the euclidean plane is a normed space such that $V=R^2$, $x=(x_1,x_2)\in R^2$, and define the norm on $R^2$ as $p(x)=||x||_2=||x||=\sqrt{(x_1+x_2)^2}=(\sum_{i=1}^2x_i^2)^{1/2}$. So it is just a plane and the norm gives the "magnitude" of the vector. Note that it is just a special case of the norm you mentioned such that $n=2, p=2, a_i(x)=x_i$, and you don't need the absolute value operator because it is a sum of squared terms.

Those topics are covered either in Real Analysis or Linear Algebra (in a more restricted way) textbooks under the rubric of norms or normed spaces.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.