3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ how is the support set input ? $\endgroup$
    – kodlu
    Jun 27, 2020 at 4:15
  • 1
    $\begingroup$ The setup is meant to exactly parallel the standard compressed sensing setup, in, for example arxiv.org/pdf/math/0503066.pdf by Candes and Tao (Section 1.1). It would even be of interest to deal with the case of $|T_0| = k \ll m$, where $k$ is known. Not sure if that answers your question, let me know! :) $\endgroup$
    – J1996
    Jun 27, 2020 at 4:27
  • 1
    $\begingroup$ Use \mid instead of | in $T_0 = \{ t \mid x_{0}(t) \neq 0\}$. $\endgroup$
    – Rodrigo de Azevedo
    Jun 27, 2020 at 7:09
  • $\begingroup$ Do you actually know a way of doing this with $O(k \log m)$ measurements? Which is the traditional entropy estimate of the subset (as opposed to the partition from Fredman/Komlos). Note that there are many famous algorithmic problems where the information theoretic lower bound has not been attained. $\endgroup$
    – kodlu
    Jul 7, 2020 at 0:05
  • $\begingroup$ Here is one of the fundamental results of CS. In section 4.1, it shows that UUP is satisfied with high probability for a gaussian i.i.d matrix when $n = O(k\log(m))$. This UUP implies that linear programing can be used to reconstruct $x_0$. $\endgroup$
    – J1996
    Jul 7, 2020 at 18:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.