is the set of k-sparse vectors in R^d a manifold? Is it homeomorphic to some Euclidean space of dimension r

Question

Is the isomorphism defined? Or any associated results or bounds.

PS: I am from PG in ECE and do not have advanced level understanding of certain topics. Any leads/theorems etc. are appreciated

Answer 1

It depends on the precise definition of sparse vectors. The most common definition is that a vector $v$ in ${\mathbb R}^n$ (or ${\mathbb C}^n$) is $k$-sparse if at most $k$ components (coordinates) of $v$ are nonzero. With this definition, the subset $\Sigma_k$ of $k$-sparse vectors in ${\mathbb R}^n$ (or ${\mathbb C}^n$) is not a submanifold. The easiest example is to take $n=2$ and $k=1$. Then the subset $\Sigma_1$ is the union of the two coordinate lines. These lines meet at the origin where $\Sigma_1$ fails to be locally homeomorphic to a Euclidean space of any dimension. Hence, $\Sigma_1$ is not a submanifold. With a bit more thought, you will realize that this example generalizes to $k$-sparse vectors in ${\mathbb R}^n$ (or ${\mathbb C}^n$) and $\Sigma_k$ is not a manifold unless $k=n$ or $k=0$ (two utterly boring examples).

However, you can modify the definition of sparse vectors and require that exactly $k$ components of $v$ are nonzero. Then the set $\Sigma'_k$ of $k$-sparse vectors will be a $k$-dimensional submanifold (real or complex, depending on the setting). However (with a couple of trivial exceptions), $\Sigma'_k$ will not be homeomorphic to a Euclidean space. With a couple of exceptions, $\Sigma'_k$ will be disconnected. For instance, if you work over the complex numbers, then there will be $$ { n \choose k} $$ connected components. If you work over the real numbers, the number of connected components of $\Sigma'_k$ will be $$ 2^k { n \choose k} $$ and each component will be homeomorphic to ${\mathbb R}^k$.