Suppose we are in $\mathbb{R}^n$ and we are given some integer $k$ such that $1 \leq k \leq n$. Let $\Vert x \Vert_0 = \#\{i\ |x_i \neq 0\}$ be the $L_0$-norm counting the number of non-zero entries of a vector (actually not really a norm).
Let $P = conv\{x\ |\ \Vert x \Vert_2 = 1, \Vert x \Vert_0 \leq k \}$ be the convex hull of all points on the unit ball that have at most $k$ non-zero entries. This can be seen as as the convex hull of all unit spheres/disks of dimension at most $k$ in $\mathbb{R}^n$.
Suppose now I have some arbitrary $x \in \mathbb{R}^n$ given. How could I determine whether $x$ lies in $P$ (apart from the obvious case when $\Vert x \Vert_0 \leq k$)? If $x$ doesn't lie in $P$, how can I find its projection onto $P$, i.e. the closest point w.r.t. the euclidean norm?
Any help is greatly appreciated!
Thanks
Best Answer
Found an answer to this myself: Apparently $P$ defines a ball w.r.t. the so-called $k$-Support-Norm, on which there's quite a bit of literature, see e.g. the original paper.