What is the interpolation norm, and how do I find it?

Question

I'm reading a paper found here and it defines an interpolation norm as this $$ \lVert \mathbf{x}\rVert_{1,2,s} =\sqrt{ \sum_{l=1}^{\lceil n/s\rceil} \lVert \mathbf{x}_{S_l}\rVert_{1}^2}$$ where $x\in\mathbb{R}^n$ and $S_1, S_2,...S_n$ are disjoing subsets of $\mathbf{x}$ such that $S_1$ indexes the largest s elements of $\mathbf{x}$ in magnitude, $S_2$ indexes the next s largest elements, and so on. I really need a pointer to better understand this interpolation norm as I am trying to implement this in MATLAB.

Answer 1

The interpolation norm seems to derive its name from the fact that it is sort of an `interpolation' between the $l_2$ and $l_1$ norms. In particular, if $s=1$ then $$||\mathbf{x}||_{1,2,1}=\sqrt{\sum_{l=1}^n{|x_l|^2}}=||\mathbf{x}||_2.$$ On the other hand, when $s=n$,.$$||\mathbf{x}||_{1,2,n}=\sqrt{{||\mathbf{x}||_1^2}}=||\mathbf{x}||_1.$$

In MATLAB, all you need is to first sort the elements in a decreasing order of magnitude. Then you partition the $n$ elements into $\lceil n/s \rceil$ sets (you will have to append $s \lceil n/s \rceil-n$ zeros at the end of $\mathbf{x}$. Afterwards, you compute the $l_1$ norm of each partition and add their squared values before taking the square root.