0

I am a bit confused about the proof of the convexity of the norm. Suppose I consider 1 norm form in which case the function is $f(x) = ||x||_1$

Referring to this pdf, http://ttic.uchicago.edu/~argyriou/courses/lec3.pdf. They have given something like

enter image description here

I didn't get this proof. How come they consider it a triangle? I mean $\lambda w$ and $(1-\lambda)z$ are just points so how come the triangular equality came into. I think I am finding it difficult to visualize. Can anyone suggest something?

user34790
  • 4,192
  • Do you know the meaning of "triangle inequality"? –  Jan 14 '13 at 05:28
  • @mark999 Yeah, I know what it is. But I didn't get how it fits in the above problem. I just need the visualization. I am finding it difficult to visualize – user34790 Jan 14 '13 at 05:32
  • Presumably you can visualise the triangle inequality in $R^2$ or $R^3$. It's hard to visualise in higher dimensions, but the point is that the triangle inequality still applies (as part of the definition of a norm), even though it can't really be visualised. –  Jan 14 '13 at 06:21
  • @mark999 I meant to say $\lambda w$ and $(1-\lambda)z$ are just points so how come they form a triangle. Is it that I take the line from the origin to these points as the sides of the triangle. I am just considering $R^2$ for example – user34790 Jan 14 '13 at 06:43
  • Yes, take the line from the origin, or an arrow from the origin to the point. You can then shift one of the arrows so that it starts where the other arrow ends, to represent vector addition. –  Jan 14 '13 at 06:48
  • @mark999 I am a bit confused how the three vectors form a triangle then – user34790 Jan 14 '13 at 07:18
  • http://en.wikipedia.org/wiki/File:Vector_triangle_inequality.PNG –  Jan 14 '13 at 07:42

1 Answers1

1

Think of $w$ as one direction. $z$ is the other direction. For example, $w = \left(1,0\right)$ can be the $x$ axis, and $z=\left(0,1\right)$ can be the $y$ axis in two-dimensional space.

The triangle inequality says that the distance from $\left(0,0\right)$ to $\lambda w + \left(1-\lambda\right)z$ is no greater than the distance from $\left(0,0\right)$ to $\lambda w$ plus the distance from $\lambda w$ to $\lambda w + \left(1-\lambda\right)z$.

The fact that $w$ and $z$ are vectors in high dimensional space is irrelevant - when there are only three points involved, these points always form a two-dimensional triangle (think of three vertices of a cube).

Guy Adini
  • 126