What is the meaning of $l_p$ norm in this model for sparse channel estimation?

Question

The signal $y(n)$ can be modeled in the time-domain as

$$y(n) = \sum_{i=0}^{L-1}h(i) x(n-i) + v(t) \tag{1}$$

where $\mathbf{h} = [h_1,h_2,\ldots,h_L]^T$ is the coefficient of length $L-1$, and $v(t)$ is the additive White Gaussian noise with variance $\sigma^2_v$.

In the Eq(20) found in the paper, http://www.eurasip.org/Proceedings/Eusipco/Eusipco2008/papers/1569101936.pdf

the eq has the term ${||h||}^p_p$ and the Authors mention that here $0<p \le 1$.

Consider an array $h = [1,0.2,0,0.5]$. What is meant by ${||h||}^p_p$ Is it the difference between the elements of $h$? What would be the meaning when p =0, p=1, and p=2?

The Authors in Eq(24)present the derivative of the cost function computed in Eq(20). The derivative is taken with respect to $h$ parameter. In that, they use the term $p\lambda \tilde{h}$ where $\tilde{h}$ is the sparse coefficient. I think here $p$ may not be zero.

Answer 1

The symbol ${||h||}_p$ refers to the p-norm of the vector. It is calculated as

$${||h||}_p=\sqrt[p]{\left|h_1\right|^p+\left|h_2\right|^p+...+\left|h_n\right|^p}$$

When they write ${||h||}^p_p$, it is just that multiplied by itself $p$ times, so that the root disappears. Mathematically:

$${||h||}^p_p=\sum\limits_{i=1}^n \left|h_i\right|^p$$

Answer 2

To add on @Tendero, the expression $\sum_k x_k^p$ is sometimes called the "power $p$-norm" when $p\ge 1$. Most often, you can see mentions of the "squared $\ell_2$ norm" or "$\ell_2$ norm squared". For $p=1$, the exponent does not modify the computation, so it is just called the $\ell_1$ norm.

The use of the power is often more convenient mathematically and computationally: having a $p$-root ($\sqrt[p]{\cdot}$) can be cumbersome in computing derivatives to find extrema.

When $p\ge 1$, it satisfies all the norm axioms. But when $0<p<1$, the triangle inequality is not satisfied anymore, so it should not be called a norm. The correct denomination is a quasi-norm, with a modulus of concavity modulus $K$ such that

$$\ell_p(x+y) \le K(\ell_p(x) +\ell_p(y))\,. $$

When $p=0$, this is not a norm nor a quasi-norm anymore. It can be called cardinality function, sparsity, count index.

In signal processing where sparsity is considered useful, $\ell_0$ is usually the target to minimize: number of non-zero samples, number of taps for a filter.

However, it is quite intractable too (not differentiable). Under some theoretical conditions, the minimization of an $\ell_0$ penalty can be replaced by an $\ell_1$ penalty, the "last" convex $\ell_p^p$ term.

However, more and more works address non-convex penalties ($p<1$) that better approximate $\ell_0$.

Finally, in a Bayesian context, the prior of a Laplacian distribution can be encapsulated in an $\ell_1$ penalty, as the Gaussian distribution can be encapsulated in an $\ell_2$ penalty, see for instance Why is Laplace prior producing sparse solutions?.