Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from stats.stackexchange.com Jan 14 '13 at 14:34

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

    
Do you know the meaning of "triangle inequality"? –  mark999 Jan 14 '13 at 5: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 5: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. –  mark999 Jan 14 '13 at 6: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 6: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. –  mark999 Jan 14 '13 at 6:48

1 Answer 1

up vote 1 down vote accepted

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.