Let $x_0 \in \mathbb{R}^{m}$ be a signal whose support $T_0 = \{ t \mid x_{0}(t) \neq 0\}$ is assumed to be of small cardinality. The recovery of $x_0$ from a small number of $n \ll m$ linear measurements is the compressed sensing problem $$y = Ax_{0},$$ where $A \in \mathbb{R}^{n \times m}$ is a sensing matrix. Obviously this is a very famous problem, with equally famous and celebrated results concerning the conditions required for the recovery of $x_0$.
But what if we do not care to recover $x_0$ completely? Instead we wish to partition $\{1, \dotsc, m \}$ into subsets $U_{i},\; i=1,\dotsc, |T_{0}|$ where $U_{i} \subset \{1, \dotsc, m\}$, $U_{i} \cap U_j =\emptyset\;\forall i,j$ and $|U_{i}\cap T_{0}|=1\;\forall i$.
In other words, we wish to find disjoint subsets $U_i \subset\{1, \dotsc, m\}$ such that for all $i$ there is only one value of $t \in U_i$ where $x_0(t)$ is nonzero.
Clearly, the conditions for recovery are sufficient to generate such a partition. However, it is not clear to me whether we can generate such a partition with significantly weaker conditions on $A$. For example, is it possible to construct these subsets with fewer measurements than would be required to recover $x_0$?
Does anyone have any insights on this? Has such a problem been studied in literature before?
It's been about a week and seem like no one has any ideas.
The best insight I have is as follows. Let $x_0$ be known to be a $k$-sparse vector. My thought is that the "information content" of the support of $x_0$, if treated as a random variable is something like $$H(x_0) = \log \left( \binom{m}{k}\right) = O(k \log(m)).$$ But the information content of this partition is much lower, as shown in this paper by Fredman and Komlos,
$$H(U_1,\dotsc, U_k) = O(k + \log\log(m))$$
This shows nothing, but perhaps lends some credence to the idea that the partition can be constructed with fewer measurements.
\midinstead of|in $T_0 = \{ t \mid x_{0}(t) \neq 0\}$. $\endgroup$