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?

Question

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.

Answer 1

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.