Let $\mathbf{x}\in\mathbb{R}^n, \mathbf{y}\in\mathbb{R}^n$. We are given the following assumptions:
\begin{equation}\tag{1}
\text{argmax}_j\{ |x_j| – |x_i|\}\geq \lambda > 0, \quad \forall i
\end{equation}
\begin{equation}\tag{2}
\Big| |y_j| – |x_j|\Big|\leq \frac{\lambda}{3} , \quad \forall j
\end{equation}
Meaning that the largest absolute value element is of $\mathbf{x}$ is greater than all the others by some strictly positive value, and that all the elements of $\mathbf{x}, \mathbf{y}$ are distant no more that $\lambda/3$.
Question: Assume w.l.o.g that element $k$ is the largest in $\mathbf{x}$: $k = \text{argmax}_j\ |x_j|$.I would like to prove that
\begin{equation}\tag{3}
|y_k| – |y_j|\geq \frac{\lambda}{3} , \quad \forall j.
\end{equation}
I tried proving this using the triangle inequality, but didn't get exactly what I needed. What I have so far is:
\begin{aligned}
\lambda&\leq |x_k| – |x_j|=\Big||x_k| – |x_j|\Big|\leq \Big||x_k|-|y_k|\Big|+\Big||y_k| – |x_j|\Big|
\leq \frac{\lambda}{3}+\Big||y_k| – |x_j|\Big| \\ &\leq \frac{\lambda}{3} +\Big||y_k| – |y_j|\Big| + \Big||y_j| – |x_j|\Big|\leq \frac{2\lambda}{3}+\Big||y_k| – |y_j|\Big|
\end{aligned}
where the first equality is since we know that $|x_k|>|x_j|$ and the other transitions use the triangle inequality and the problem assumptions.
Overall we have $\Big||y_k| -|y_j|\Big|\geq \frac{\lambda}{3}$,
however I'm still left with the "outer" absolute value wrapping both terms, so this doesn't fully prove what I want.
Can anyone assist in proving equation $(3)$?
Best Answer
It's easiest to be a little more careful in the computation to see this holds true without the outer absolute value. $$ \begin{align} \lambda &< |x_k|-|x_j|\\ &= |x_k| - |y_k| + |y_k| - |x_j| \\ &\leq \big||x_k| - |y_k|\big| + |y_k|-|x_j|\\ &\leq \frac{\lambda}{3} + |y_k|-|x_j|\\ &= \frac{\lambda}{3} + |y_k|-|y_j|+|y_j|-|x_j|\\ &\leq \frac{\lambda}{3} + |y_k|-|y_j|+\big||y_j|-|x_j|\big|\\ &\leq \frac{2\lambda}{3} + |y_k| - |y_j| \end{align} $$
The intuition behind your argument was very useful, though.