# How an $\ell_1$ Inequality Implies Equality

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.

-
Is $\mathbf{h}$ fixed or variable? – Giuseppe Negro Aug 21 '13 at 11:50
@GiuseppeNegro Fixed. – AnonSubmitter85 Aug 21 '13 at 11:52

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