Let $x \in \mathbb{R}^n$ and $0 \neq a \in \mathbb{R}^n$ be a given vector and $b$ be a scalar such that the half-space defined by $a^{\top}x \leq b$ always include $0$.
Question
1- Is there any relationship between $z=\arg\min_{a^{\top}v \leq b}\|v-x\|^2$ and
$y \in \text{Argmin}_{a^{\top}v \leq b \text{ and } \|v\|_0 \leq s} \|v-x\|^2$ for a given integer $1 \leq s < n$ where $\|v\|_0$ is the number of non-zero elements in $v$?
My try
I can write $z=x -\frac{a^{\top}x-b}{\|a\|^2}$. I can see from the picture that the sparse solution is either on the intersection of the hyperplane and the axis $y^{(2)}$ or just on the axis $y^{(1)}$ . If this is right, how can I rigorously show it? Is there any connection between my observation and $z$?
Best Answer
Let's call:
$H$ the hyperplane $a^{\top}x=b$,
$H^-$ the half-space $a^{\top}x \le b$,
$S$ the set $\{v, \|v\|_0 \le s \}$ for a given $s$. $S$ is the union of all vector subspaces generated by any $s$ principal axes among $n$; there are $n \choose s$ such subspaces.
(Note that $S(\text{for }s=1) \subset S(\text{for }s=2) \subset S(\text{for }s=3) \dots$).
So the question is to study $\arg\min_{v \in H^- \cap S} \|v-x\|^2$ and its relationship with $z = \arg\min_{v \in H^-} \|v-x\|^2$.
Define $p(x) = \arg\min_{v \in S} \|v-x\|^2$, i.e. projection of $x$ on the closest point in $S$, which may be one or more points. $p(x)$ is actually $x$ where its $s$ largest (in absolute value) coordinates have been kept and the other coordinates put to $0$.
Let's look at cases.
We could try distinguishing $x \in H^-$ (where $z=x$), from $x \notin H^-$, but it makes no real difference.
Now we distinguish between $p(x) \cap H^- \ne \emptyset$, and $p(x) \cap H^- = \emptyset$:
If $p(x) \cap H^- \ne \emptyset$, $\arg\min_{v \in H^- \cap S} = p(x) \cap H^-$ by definition of $p(x)$ (closest points of $S$ from $x$).
Your drawing is in this case.
If $p(x) \cap H^- = \emptyset$, let's decompose $S \cap H^-$.
$H^-$ is convex.
$S$ is the union of subspaces $C_k$, $k = 1 .. {n \choose s}$. Each of them is convex.
So $S \cap H^- = \bigcup_k (C_k \cap H^-)$ where each $C_k \cap H^-$ is convex.
So the closest point of $C_k \cap H^-$ from $x$ is unique. It is either$^{(*)}$ the orthogonal projection of $x$ on $C_k$, if it is inside $H^-$, or $C_k \cap H$, intersection of the hyperplane with $C_k$.
Then we take the closests of those points to get p(x).
(*) If the orthogonal projection of $x$ on $C_k$ (let's call it $w$) $\notin H^-$, then call $u$ the closest point of $C_k \cap H^-$ from $x$. In the 3-dim plane $P$ defined by $(x, w, u)$, $H$ separates $w$ from $u$ (as $w \notin H^-$ and $u \in H^-$). As $\|w-x\| < \|u-x\|$, and $\|w-x\|$ is minimum distance from $x$ of all points on line $w-u$, $u$ is on $H$ otherwise the point on $H$ would be closer to $x$ than $u$.
In this second case, it is possible that $\arg\min_{v \in H^- \cap S} \|v-x\|^2$ consists in more than one point, some of which are orthogonal projections of $x$ on some subspace $C_k$ of $S$ (and they are in $H^-$), some of which are on some $C_k \cap H$.
Example in $\mathbb R ^2$: $x=(3,5), a=(1,4), b=4, s=1$, closest points from $H^- \cap S$ to $x$ are $(0,1)$ on $H$ and $(3,0)$ inside $H^-$.
There is no significant relationship between $\arg\min_{v \in H^- \cap S} \|v-x\|^2$ and $z = \arg\min_{v \in H^-} \|v-x\|^2$, at least none that I see.
In the (rather simple) example above, $z=(\frac {32} {17}, \frac 9 {17})$ has no relationship with $(0,1)$ and $(3,0)$.