Getting into Norms: a technical postscript

For mathematicians’ eyes only. The post doesn’t require much theoretical knowledge to understand, but I haven’t given many definitions.

In the last two posts I’ve been talking about an example I made with four-dimensional vectors a, b, c such that \|a\|_1 > \|b\|_1 > \|c\|_1, \|b\|_{2} > \|c\|_{2} > \|a\|_{2} and \|c\|_{\infty}>\|a\|_{\infty}>\|b\|_{\infty}. Finding it was more difficult than I at first expected, so I thought I would write the investigation up, which happily gives me an excuse to introduce a useful inequality.

My first thoughts were to choose something like c=(10,0,0,0) and a=(6,6,0,0) or a=(4,4,4,0), and then I’d got stuck choosing b. So I decided to try to prove the opposite.

First of all, it’s not possible to create such an example in two dimensions. Let’s focus on selecting a=(a_1, a_2) and b= (b_1, b_2) first. The ordering within each vector is irrelevant, as all three norms under consideration are symmetric (they treat each coordinate equally). Since \|a\|_{\infty} > \|b\|_{\infty} we have a_1 > b_1, and likewise \|a\|_{1}>\|b\|_{1} implies that a_1 + a_2 > b_1+b_2. This means that the sequence a essentially majorizes the sequence b.

Definition. A real sequence (x_1, x_2, \ldots, x_n) ordered such that x_1 \geq x_2 \geq \cdots \geq x_n weakly majorizes a sequence (y_1, y_2, \ldots, y_n) with y_1 \geq y_2 \geq \cdots \geq y_n if each initial partial sum of the first sequence is greater than the second, that is \sum_{i=1}^k x_i \geq \sum_{i=1}^k y_i for each 1 \leq k \leq n.

Because of majorization, we can now discover something about the \ell_2 norm: the function x \mapsto x^2 is easily seen to be strictly convex, and so we may apply a version of Karamata’s inequality!

Karamata’s inequality (alternate form). If a descending real sequence (x_1 \geq x_2 \geq \cdots \geq x_n) weakly majorizes (y_1 \geq y_2 \geq \cdots \geq y_n), then for any non-decreasing strictly convex function f we will have f(x_1) + f(x_2) + \cdots + f(x_n) \geq f(y_1) + f(y_2) + \cdots + f(y_n).

Note: the function needs only to be strictly convex and defined on a real interval containing both sequences.

You can remove the ‘non-decreasing’ condition and gain Karamata’s usual inequality, by: deleting all the ‘weakly’s in the definition and theorem above; and by requiring the two full sums to be equal: \sum_{i=1}^n x_i = \sum_{i=1}^n y_i.

Therefore we have a_1^2 + a_2^2 > b_1^2+b_2^2, and so \|a\|_{2} > \|b\|_{2}, the opposite of what we wanted, meaning the inequalities we were trying to prove are not possible in two dimensions.

What about in three dimensions and higher? From the two ‘extreme’ norms, we will still have a_1>b_1 and a_1+a_2+a_3 > b_1+b_2+b_3. If we choose a and b such that a_1 + a_2> b_1+b_2, then we can again apply Karamata’s inequality and repeating the two-dimensional work will lead to failure. So that means we must require a_1 + a_2 < b_1 + b_2 to have any hope of succeeding.

So I chose a = (10, 6, 2), and b = (9, 8, 0). The initial partial sums of b briefly overtake those of a, but fall behind again: ie. stage by stage in the addition, we have 10>9, 16<17, and 18>17. Then, fixing \|c\|_1=16 to be the smallest in the \ell_1 norm, I cheated and tried a few randomised possibilities for the coordinates of c in Excel, and was quickly rewarded with: c=(11.4, 2.4, 2.2).

I specifically wanted a four-dimensional example for the post, so I added a final coordinate all equal to 1 on the end of each, which wouldn’t change any of the inequalities, and messed up the ordering of the sequences a bit.

There may be some elementary way of seeing all this, but Karamata’s inequality is neat and allows easy generalisation from the p=2 case to non-integer p. This could mean salvation from the guilty temptation to incorrectly interpolate to get inequalities for such p, once you have similar inequalities for the integer powers on either side.

While I’m revisiting old posts, Karamata’s inequality is a generalisation of the more widely known Jensen’s inequality, which is in turn a generalisation of the arithmetic-geometric inequality, which, perhaps surprisingly, contributed to a day of strikes in Britain. The link is a proposed change from RPI to the lower CPI in public sector pensions.

Finally, “Karamata’s inequality” doesn’t quite scan to the tune of the Katamari Damacy theme, but if singing “Na naaa na na na nana nana na na Karamata’s inequality” helps you to remember this useful but perhaps overlooked inequality, does an extra syllable really matter?


Leave a comment

Filed under Technical

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s