0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$ – user804886 Jul 13 '20 at 4:06
  • $\begingroup$ @user804886, yes sorry for being unclear, first one should be a vector of all 1s. So it's the set of probability vector $\endgroup$ – Duc Nguyen Jul 13 '20 at 19:00
  • 1
    $\begingroup$ The relation $\|x\|_2\leq\|x\|_1$ makes me think what you're looking for holds $\endgroup$ – iarbel84 Jul 14 '20 at 17:33
  • $\begingroup$ @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 $\endgroup$ – Duc Nguyen Jul 17 '20 at 3:13
  • 1
    $\begingroup$ 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. $\endgroup$ – user810049 Jul 23 '20 at 17:43
0
$\begingroup$

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 book``Introduction to Online Convex Optimization'' (Page. 159) and this problem for more details.

$\endgroup$
3
  • $\begingroup$ True, but it might still work with a different type of setting. You can check to see if Bregman distance will work, which is detailed in Chen and Teboulle's work epubs.siam.org/doi/pdf/10.1137/0803026 $\endgroup$ – iarbel84 Jul 19 '20 at 13:45
  • $\begingroup$ Sorry if I misunderstanding your reply. This paper proves the convergence of PPA for Bregman’s distance, but I really don't know why Pythagorean inequality hold. $\endgroup$ – Ze-Nan Li Jul 20 '20 at 1:33
  • $\begingroup$ 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. $\endgroup$ – iarbel84 Jul 20 '20 at 8:55

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.