# What are $\ell_p$ norms and how are they relevant to regularization?

I have been seeing a lot of papers on sparse representations lately, and most of them use the $\ell_p$ norm and do some minimization. My question is, what is the $\ell_p$ norm, and the $\ell_{p, q}$ mixed norm? And how are they relevant to regularization?

Thanks

-

$\ell_p$ norms are functions that take vectors and return nonnegative numbers. They're defined as $$\|\vec x\|_p = \left(\sum_{i=1}^d |x_i|^p\right)^{1/p}$$ In the case where $p=2$, this is called the Euclidean norm. You can define the Euclidean distance as $\|\vec x - \vec y\|_2$. When $p = \infty$, this just means $\|\vec x\|_\infty = \sup_i x_i$ (or $\max_i x_i$). Strictly speaking, $p$ must be at least one for $\|\vec x\|_p$ to be a norm. If $0 < p < 1$, then $\|\vec x\|_p$ isn't really a norm, because norms must satisfy the triangle inequality.

(There are also $L_p$ norms, which are defined analagously, except for functions instead of vectors or sequences -- really this is the same thing, since vectors are functions with finite domains.)

I'm not aware of any use for a norm in a machine learning application where $p > 2$, except where $p = \infty$. Usually you see $p = 2$ or $p = 1$, or sometimes $1 < p < 2$ where you want to relax the $p = 1$ case; $\|\vec x\|_1$ isn't strictly convex in $\vec x$, but $\|\vec x\|_p$ is, for $1 < p < \infty$. This can make finding the solution "easier" in certain cases.

In the context of regularization, if you add $\|\vec x\|_1$ to your objective function, what you're saying is that you expect $\vec x$ to be sparse, that is, mostly made up of zeros. It's a bit technical, but basically, if there is a dense solution, there's likely a sparser solution with the same norm. If you expect your solution to be dense, you can add $\|\vec x\|_2^2$ to your objective, because then it's much easier to work with its derivative. Both serve the purpose of keeping the solution from having too much weight.

The mixed norm comes in when you're trying to integrate several sources. Basically you want the solution vector to be made up of several pieces $\vec{x}^j$, where $j$ is the index of some source. The $\ell_{p,q}$ norm is just the $q$-norm of all the $p$-norms collected in a vector. I.e., $$\|\vec x\|_{p,q} = \left( \sum_{j = 1}^m \left( \sum_{i=1}^d |x_i^j|^p\right)^{q/p}\right)^{1/q}$$

The purpose of this is not to "oversparsify" a set of solutions, say by using $\|\vec x\|_{1,2}$. The individual pieces are sparse, but you don't risk nuking a whole solution vector by taking the $1$-norm of all of the solutions. So you use the $2$-norm on the outside instead.

Hope that helps.

See this paper for more details.

-
+1 for the explanation of mixed norms. I never understood them myself. –  Suresh Venkatasubramanian Jul 13 '12 at 4:55
(+1) Nice answer. Welcome to CrossValidated, John! –  MånsT Jul 13 '12 at 8:50