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)$?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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