0
$\begingroup$

How to prove $\|y-\sum_{i=1}^n a_ix_i\|\leq \sum_{i=1}^n a_i\|y-x_i\|$? $\ \ \ \ \sum_i a_i = 1$, $0\leq a_i \leq 1$ and $y,x_i\in \mathbb{R}^m, \ \ \forall i$

It seems simple however I have no idea to prove it formally?

Pf:
Suppose $n=2$

\begin{aligned} y-(a_1x_1+a_2x_2) &= a_1y+a_2y-a_1x_1-a_2x_2-(a_1+a_2)y+y\\ &= a_1(y-x_1)+a_2(y-x_2)-(a_1+a_2)y+y\\& \end{aligned}

So take norm on both sides:

\begin{aligned} \|y-(a_1x_1+a_2x_2)\| &= \|a_1(y-x_1)+a_2(y-x_2)-(a_1+a_2)y+y\|\\& \end{aligned}

By triangle inequality:

\begin{aligned} \|y-(a_1x_1+a_2x_2)\| &\leq \|a_1(y-x_1)\|+\|a_2(y-x_2)\|+\|(a_1+a_2)y+y\|\\& \end{aligned}

Then how to deal with the tail term?

Here I want to show $ \|y-(a_1x_1+a_2x_2)\| \leq \|a_1(y-x_1)\|+\|a_2(y-x_2)\|$

$\endgroup$
6
  • $\begingroup$ Don't you want to show the $\underline{norm}$ of the left side is less than or equal to the right side? $\endgroup$
    – user84413
    Commented Dec 24, 2015 at 21:34
  • $\begingroup$ @user84413 If the one with norm holds then get rid of the norm of LHS, which will hold. Or any other better way? $\endgroup$ Commented Dec 24, 2015 at 21:36
  • $\begingroup$ As stated, the problem doesn't seem correct, since the left side is a vector in $R^m$ and the right side is a number. Furthermore, the statement seems false if all $a_i=0$. (Maybe you want to assume that their sum is 1.) $\endgroup$
    – user84413
    Commented Dec 24, 2015 at 21:39
  • $\begingroup$ I fix it. It should be correct now. $\endgroup$ Commented Dec 24, 2015 at 21:42
  • $\begingroup$ $\{a_i\}$ should be stochastic like $\endgroup$ Commented Dec 24, 2015 at 21:48

1 Answer 1

2
$\begingroup$

You have $\|y-\sum_{i=1}^{n}a_ix_i\|=\|\sum_{i=1}^n(a_iy-a_ix_i)\|=\|\sum_{i=1}^n a_i(y-x_i)\|\le\sum_{i=1}^n a_i\|y-x_i\|$

$\endgroup$
2
  • $\begingroup$ Thanks for terse and powerful answer. $\endgroup$ Commented Dec 24, 2015 at 21:54
  • $\begingroup$ You're welcome! $\endgroup$
    – user84413
    Commented Dec 24, 2015 at 21:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .