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.

Suppose that for scalar $\epsilon$ we know that $\vert \epsilon \vert$ is small enough such that the sign pattern on $\mathbf{x}\in\mathbb{R}^n$ is equal to that on $\mathbf{x} + \epsilon \mathbf{h}$, which makes the $\ell_1$ norm continuous and differentiable in this region. Now, if it is true that

$$ \Vert \mathbf{x} \Vert_1 \leq \Vert \mathbf{x} + \epsilon \mathbf{h} \Vert_1 $$

for each such $\epsilon$, must it be true that $\Vert \mathbf{x} \Vert_1 = \Vert \mathbf{x} + \epsilon \mathbf{h} \Vert_1$?

What I am reading claims that it is and uses the following wording: "[Since] the above relationship [referring to the inequality] holds for both positive and negative values of $\epsilon$ in a region where the $\ell_1$ function is continuous and differntiable, [...] the only way this could be true is if the above inequality is satisfied as an equality."

I don't understand how this conclusion is drawn. If $f$ is continuous and differentiable, just because $f(x)\leq f(x \pm \delta)$ does not mean that $f(x)=f(x\pm \delta)$.

Edit:

So the best I've come up with is this. If we let $\mathbf{s}$ be a vector of $\pm1$'s such that $\Vert \mathbf{x} \Vert_1 = \mathbf{s}^{\mathrm{T}} \mathbf{x}$, then since there is no sign change we have

$$\begin{array}{rcl} \mathbf{s}^{\mathrm{T}} \mathbf{x} & \leq & \mathbf{s}^{\mathrm{T}} \left( \mathbf{x} + \epsilon \mathbf{h} \right) \\ \mathbf{s}^{\mathrm{T}} \mathbf{x} & \leq & \mathbf{s}^{\mathrm{T}} \left( \mathbf{x} - \epsilon \mathbf{h} \right) \end{array} $$

$$ \Rightarrow \begin{array}{rcl} 0 & \leq & +\epsilon \, \mathbf{s}^{\mathrm{T}} \mathbf{h} \\ 0 & \leq & -\epsilon \, \mathbf{s}^{\mathrm{T}} \mathbf{h}, \end{array} $$

which means that $\mathbf{s}^{\mathrm{T}} \mathbf{h} = 0$ and that, hence, $\Vert \mathbf{x} + \epsilon \mathbf{h} \Vert_1 = \mathbf{s}^{\mathrm{T}} \left( \mathbf{x} - \epsilon \mathbf{h} \right) = \mathbf{s}^{\mathrm{T}}\mathbf{x} = \Vert \mathbf{x} \Vert_1$.

I doubt this is what the author had in mind though as it does not use the continuity nor differentiability of the function, so I suspect that I am forgetting something fundamental here.

share|improve this question
    
Is $\mathbf{h}$ fixed or variable? –  Giuseppe Negro Aug 21 '13 at 11:50
    
@GiuseppeNegro Fixed. –  AnonSubmitter85 Aug 21 '13 at 11:52
add comment

1 Answer

Let $ f=\operatorname{sign}(\mathbf x)$, that is, the vector of $+1,-1,0$ corresponding to positive, negative, or zero entries of $\mathbf x$. Note that $ f\in (\ell_1)^*$; it's called the norming functional of $\mathbf x$. By assumption we have $$\|\mathbf x+\epsilon \mathbf h\|= f(\mathbf x+\epsilon \mathbf h) \tag1$$ for all small $\epsilon$.

The right side of (1) is a linear function of $\epsilon$. Thus, $ f(\mathbf x+\epsilon \mathbf h)\le f(\mathbf x)$ can hold in a neighborhood of $0$ only if it holds as an equality.

share|improve this answer
    
Can you recheck your answer? It cannot be that $\Vert x + \epsilon h \Vert = f(x+\epsilon h)$, for one is in $\mathbb{R}$ and the other in $\mathbb{R}^n$. Also, is this what you mean when you say it is a linear function of $\epsilon$: $\operatorname{sign}(x+\epsilon h) = \operatorname{sign}(x) + \operatorname{sign}(\epsilon) h$? –  AnonSubmitter85 Aug 24 '13 at 2:50
    
@Anon $f$ is a unit vector in $\ell_\infty$ which acts on $\ell_1$ in the usual way, $\sum x_iy_i$. Thus, it is a linear functional on $\ell_1$, taking scalar values. Note that $f $ does not depend on $\epsilon$, it's fixed. By a linear function I mean a linear function in the sense of calculus - a thing with slope amd intercept. –  user Aug 24 '13 at 4:14
    
So when you write $f(x+\epsilon h)$ you mean the vector $f$ multiplies the vector $(x+\epsilon h)$? Based on your answer, I read $f(x+\epsilon h)$ to be $\operatorname{sign}(x+\epsilon h)$. –  AnonSubmitter85 Aug 24 '13 at 4:17
    
I have to assume you meant $f^{T}(\cdot)$ rather than $f(\cdot)$, which means that this the same answer I put in my edit. –  AnonSubmitter85 Aug 24 '13 at 4:52
add comment

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.