# Pythagorean inequality in l1 norm for projection onto simplex

Let $$x$$ be a point in $$\mathbb{R}^d$$, let $$z$$ be the projection of $$x$$ onto the $$d-1$$ dimensional simplex ($$z^\top \mathbf{1}= 1$$ and $$z \succeq 0$$). So basically

$$z = \arg\min_w \{\rVert x-w\rVert_2 \,\,|\,\, w^\top \mathbf{1} = 1\,,w\succeq 0 \}$$

Let $$y$$ be any other point in the simplex. Is it true that $$\rVert z- y\rVert_1 \leq \rVert x- y\rVert_1$$?

I could prove this for $$\mathbb{R}^2$$ but not sure how to generalize it to $$\mathbb{R}^d$$. The above inequality actually holds for Euclidean norm (not sure if it has an official name but some people refer to it as the Pythagorean inequality for projection onto convex sets)

but I'm interested in L1 norm instead. Any leads/related problems are greatly appreciated!

Thanks

• When writing $z^\top 1 = 1$, is the first $1$ the column vector in $\Bbb{R}^d$ consisting of all $1$s? That is, is the simplex the set of all vectors in $\Bbb{R}^d$ in the positive orthant whose components sum to $1$? – user804886 Jul 13 '20 at 4:06
• @user804886, yes sorry for being unclear, first one should be a vector of all 1s. So it's the set of probability vector – Duc Nguyen Jul 13 '20 at 19:00
• The relation $\|x\|_2\leq\|x\|_1$ makes me think what you're looking for holds – iarbel84 Jul 14 '20 at 17:33
• @iarbel84 good point, in fact, we can show that $\frac{1}{\sqrt{d}} \rVert z-y\rVert_1 \leq \rVert z-y\rVert_2 \leq \rVert x-y\rVert_2 \leq \rVert x - y\rVert_1$. Getting rid of the $\frac{1}{\sqrt{d}}$ seems hard though – Duc Nguyen Jul 17 '20 at 3:13
• I'm pretty sure this does hold, but a formal proof with any kind of elegance eludes me. My PhD is on projections, and I can confirm that this property does not hold for general convex sets in $\Bbb{R}^d$, but I think the specific structure of this set, being a face of the $1$-sphere, will mean the $2$-projection will lie inside the $1$-projection. – user810049 Jul 23 '20 at 17:43

It seems that the Pythagorean inequality only holds for inner-product norms rather than all norms. Thus this result may not hold for $$\ell_1$$ norm. One can refer to this bookIntroduction to Online Convex Optimization'' (Page. 159) and this problem for more details.
• You can use some convex function that will hold the Bregman distance properties w.r.t. the l-1 norm (for example, $\sum_{i=1}^{n}x_i \log x_i$). It's a long shot, but maybe you'll be able to construct what you're looking for - possibly by using the Three-point Lemma from the article. – iarbel84 Jul 20 '20 at 8:55