In order to be injective over some subset of its domain, must a linear operator have codomain with dimension at least as large as that of that subset?

In structured signal recovery problems, one typically considers a subset $\mathcal{S} \subset \mathcal{U}$ containing elements which are parsimonious, in terms of intrinsic dimensionality, in comparison with the dimension of the ambient space $\mathcal{U}$.

For instance, in compressed sensing one considers vectors $x \in \mathcal{U}=\mathbb{R}^n$ having a small (unknown) support (with, say, cardinality $s$). In that case, thus, $S$ is the set of $s$-sparse vectors, which have $s$ degrees of freedom (DOF). (Another example is that of $n_1 \times n_2$ matrices having rank bounded by $r$, which are characterized by $r(n_1 + n_2 - r)$ DOF, as can be seen by counting the DOF of its SVD.)

In this context, the goal is to try to recover a signal $x \in \mathcal{S}$ given a vector of measurements $y \in \mathbb{R}^m$, with $m < \text{dim}(\mathcal{U})$, taken by a linear measurement operator $A : \mathcal{U} \mapsto \mathbb{R}^m$.

A first requirement $A$ must clearly fulfill is that it has to be injective over $\mathcal{S}$, for otherwise given $y=A(x_1)$ and assuming there exists $x_2 \neq x_1$ such that $A(x_1)=A(x_2)$ with $x_1,x_2 \in \mathcal{S}$, we can never guarantee the true measured signal $x_1$ will be recovered from $y$ by any method whatsoever.

Now, it seems quite reasonable for me that, in order to be injective over $\mathcal{S}$, and assuming any signal $x \in \mathcal{S}$ is characterized by $s$ DOF, the codomain of $A$ must have dimension $m \ge s$ (as a necessary condition, not a sufficient one). In other words, it should provide at least as many measurements as the number of DOF of any element in $\mathcal{S}$. My question is: is this formally correct and, if so, is there a fundamental result in information theory which supports this claim?

Edit: It should be noted that $\mathcal{S}$ is not necessarily a subspace of $\mathcal{U}$ (otherwise the result would be trivial). In compressed sensing, for instance, it is a nonconvex set given by a finite union of subspaces. In low-rank matrix recovery, it is rather a manifold.

Since you do not provide a formal definition of "degrees of freedom", I will use the following one: I assume that $S$ contains a subset $S_0$ which is homeomorphic to an open subset $U$ of $\Bbb{R}^s$. Let $\phi :U \to S_0$ be a homeomorphism.
By composition, we obtain an injective continuous map $A\circ\phi : U \to \Bbb{R}^m$, so that the invariance of domain theorem (https://en.m.wikipedia.org/wiki/Invariance_of_domain) yields $s \leq m$ as desired. Note that we did not use linearity of $A$, only continuity.
• I don't think this definition will work for what is meant by DOF above. Take, for instance, the 2-sparse vector (1,1,0) of $\mathbb{R}^3$. It seems logical that $\phi^{-1}$ would map it into $(1,1) \in \mathbb{R}^2$. However, the same reasoning holds for (1,0,1) and (0,1,1); hence, $\phi$ cannot be a homeomorphism. Anyway, you brought up an important issue. I don't see a clear way of formalizing DOF for the moment, I'll think about it. Commented Nov 6, 2015 at 10:19
• @thetouristbr: Yes, it will. Note that I only assume a subset $S_0 \subset S$ to be homeomorphic to an open subset of $\Bbb{R}^s$. Thus, take for example $S_0 := \Bbb{R}^s \times \{0\} \subset \Bbb{R}^n$. This is clearly homeomorphic to $\Bbb{R}^s$ and a subset of the set of $s$-sparse vectors. Commented Nov 6, 2015 at 16:23
• In the sparse vector case, where $S_0$ can be defined as a subspace ($S$ is given by a finite union of subspaces), so that it is easy to prove $m \ge s$. The link I mentioned uses a similar argument to justify the intuition that $A$ cannot satisfy a restricted isometry property for rank-$r$ $m \times n$ matrices unless at least $rn$ measurements are taken. It seems to me that building the required homeomorphism to show that actually at least one needs $m \ge r(m+n-r)$, though a little trickier in this case, can be done as follows: Commented Nov 10, 2015 at 15:52