If $x \ge 0$ and $\mathbf{1}^Tx \le \|x\|^2$ then $\mathbf{1}^T(I - xx^T / \|x\|^2) \mathbf{1} \ge \| [\mathbf{1} - x]_+ \|^2$

Question

Notation. Denote $\mathbf{1}=(1,1,\ldots,1)$ as the vector-of-ones in $\mathbb{R}^n$. Write the "positive part" as $[\alpha]_+ = \max\{\alpha,0\}$ for $\alpha\in\mathbb{R}$ and $[(x_1,x_2,\ldots,x_n)]_+ = ([x_1]_+,[x_2]_+,\ldots,[x_n]_+)$ for $x\in\mathbb{R}^n$. Example: $[(1,-2,0,3)]_+ = (1,0,0,3)$.

Let $x \in \mathbb{R}^n$ satisfy $x \ge 0$ and $\mathbf{1}^Tx \le \|x\|^2$ where nonnegativity is interpreted elementwise. Then, I conjecture the following lower-bound $$\mathbf{1}^T(I - xx^T / \|x\|^2) \mathbf{1} \ge \| [\mathbf{1} - x]_+ \|^2$$ Why is this bound true? (Or is there a counterexample?)

I have spent hours verifying the bound over random $x$ and could not find a counterexample. Note that the claim is false if we replace the RHS by $\| \mathbf{1} - x \|^2$; for example, let $x=(0,2)$. I suspect that a proof must somehow work with the cardinality of $x$, since $\mathbf{1}^T\mathbf{1}=n$ and $\mathbf{1}^Tx=\|x\|_1$ and $(\|x\|_1/\|x\|_2)^2\le\mathrm{card}(x)$.

Answer 1

Another way to prove this: Rewrite your condition $\mathbf{1}^Tx\le\|x\|^2$ as $$a:=s_2/s_1\ge1$$ and your target inequality $$\mathbf{1}^T(I-xx^T/\|x\|^2)\mathbf{1}\ge\|[\mathbf{1}-x]_+\|^2$$ as $$s_2 s_h\ge s_1^2,$$ where $$s_1:=\sum x_i,\quad s_2:=\sum x_i^2,\quad s_h:=\sum h(x_i),$$ $$h(u):=1-(1-u)_+^2.$$ Note that for any real $b\ge1$ we have $$h(u)\ge g_b(u):=\frac{2u}b-\frac{u^2}{b^2}$$ for all real $u\ge0$. So, with $$s_{g_b}:=\sum g_b(x_i)=\frac{2s_1}b-\frac{s_2}{b^2},$$ it is enough to show that $$s_2 s_{g_a}=s_1^2,$$ which is true. $\Box$

Answer 2

Ah this turns out to be a fairly elementary result with the right intution. The left-hand side is obviously the project distance from $\mathbf{1}$ onto the line spanned by $x$, as in $$ \mathbf{1}^{T}(I-xx^{T}/\|x\|^{2})\mathbf{1}=\min_{t}\|\mathbf{1}-tx\|^{2}. $$ The key insight is that the right-hand side is the projection distance of $x$ onto the set $\{x\in\mathbb{R}^{n}:x_{i}\ge1\}$, as in $$ \|[\mathbf{1}-x]_{+}\|=\min_{y\ge\mathbf{1}}\|x-y\|. $$ As such, for an arbitrary $x$, we can increase the RHS by scaling $x\gets\alpha x$ for $\alpha<1$ towards zero. We can shrink $x$ this way until $\mathbf{1}^{T}x=\|x\|^{2}$, and at this critical point, $x$ coincides with the projection point of $\mathbf{1}$ onto the line spanned by $x$.

Here's a more rigorous proof. First, we can verify by inspection that $$ \alpha<1\implies\|[\mathbf{1}-\alpha x]_{+}\|\ge\|[\mathbf{1}-x]_{+}\|. $$ Hence, we define $u=\alpha x$ such that $\mathbf{1}^{T}u=\|u\|^{2}$. At this point, we can verify that $$ \mathbf{1}^{T}(I-uu^{T}/\|u\|^{2})\mathbf{1}=\min_{t}\|\mathbf{1}-tu\|^{2}=\|\mathbf{1}-u\|^{2} $$ because $(\mathbf{1}-u)^{T}u=0$ implies $(\mathbf{1}-u)\perp u$. Finally, we observe that $$ \|\mathbf{1}-u\|^{2}=\sum_{i=1}^{n}(1-u_{i})^{2}\ge\sum_{u_{i}\le1}(1-u_i)^{2}=\|[\mathbf{1}-u]_{+}\|^{2}. $$ Combined, we have $$\begin{align*} \mathbf{1}^{T}(I-xx^{T}/\|x\|^{2})\mathbf{1} & =\mathbf{1}^{T}(I-uu^{T}/\|u\|^{2})\mathbf{1}\\ & =\|\mathbf{1}-u\|^{2}\ge\|[\mathbf{1}-u]_{+}\|^{2}\ge\|[\mathbf{1}-x]_{+}\|^{2} \end{align*}$$ as desired.