6
$\begingroup$

My (probably naive) understanding of compressive sensing is that it is a technique that allows to efficiently reconstruct an $N$-dimensional signal $\boldsymbol x$, provided that it is sparse in some basis (without the need to know the sparsity basis), using a number $M\ll N$ of measurements.

More formally, if the signal can be written as $\boldsymbol x = \Psi\boldsymbol s$ with $\boldsymbol s$ $K$-sparse, and we are measuring in an incoherent $M$-dimensional measurement basis $\boldsymbol y = \Phi\boldsymbol x$ with $M\ll N$, then we can reconstruct the signal $\boldsymbol x$ using only $M$ measurements (provided $M\ge K$) (with the notation of Baraniuk 2007).

What I don't understand is why doesn't the above sparsity requirement apply to all possible signals. I mean, isn't any signal sparse in its own basis? Regardless of the choice of $\boldsymbol x$, I can always take as $\Psi$ any matrix whose first column is $\boldsymbol x$, and this will result in $\boldsymbol x$ being representable with the $1$-sparse vector $\boldsymbol s\equiv (1,0,0,...)^T$.

So why can't I efficiently reconstruct a signal which is $1$-sparse in a basis like the above? More generally, what are the requirements on the basis in which the signal has to be sparse for a CS approach to work?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ You can, but doing so doesn't get you any benefit. You still have $N$ "coefficients" to deal with. The basis is not interesting. See also dsp.stackexchange.com/questions/3531/… $\endgroup$
    – MBaz
    Commented Dec 5, 2017 at 19:24
  • $\begingroup$ @MBaz I don't think I understand. From my argument it would seem that being any signal "$1$-sparse in some basis", you would only need $\mathcal O(1)$ single measurements to completely reconstruct any $N$-dimensional signal. This is obviously false, no? $\endgroup$
    – glS
    Commented Dec 5, 2017 at 19:28
  • 4
    $\begingroup$ The thing is that the receiver needs to know the basis! In your scenario, this amounts to the receiver already knowing the signal, so there's not even a need to sample and transmit it. (I'm using "transmit" and "receive" in a very wide sense). $\endgroup$
    – MBaz
    Commented Dec 5, 2017 at 19:35
  • 2
    $\begingroup$ The measurement matrix can be chosen randomly, but that doesn't mean that transmitter and receiver can choose their own matrices at random! They still need to use the same matrix. Having said that -- I want to point out that I'm not an expert in CS, and hopefully somebody that knows more than me will give you an authoritative answer. $\endgroup$
    – MBaz
    Commented Dec 5, 2017 at 23:42
  • 1
    $\begingroup$ What I mean by "transmittter" is the process of taking a signal and representing it as a set of coefficients ("samples") in some basis. The "receiver" takes the coefficients and reconstructs the signal. I may be mistaken, but it is my belief that both need to use the same matrix, even if the matrix was determined at random. Have you seen ieeexplore.ieee.org/document/4286571 ? $\endgroup$
    – MBaz
    Commented Dec 6, 2017 at 15:15

1 Answer 1

Reset to default
6
$\begingroup$

You can measure and reconstruct such a 1-sparse signal as you describe in your question. The crucial misunderstanding here is, as @MBaz points out, that you have to know the basis $\Psi$.

You can take measurements in a universal manner without knowing the dictionary $\Psi$ beforehand, if you choose the measurement matrix $\Phi$ as a sufficiently random matrix - could be a random Gaussian matrix. What universality gives you is the ability to reconstruct $x$ again with good accuracy almost no matter what $\Psi$ turns out to be. You can take such universal measurements at the encoder without knowing $\Psi$, but you still have to know some $\Psi$, that admits a sparse representation of $x$, (and $\Phi$) at the decoder.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Mmh.. ok I think I see it know, also what @MBaz meant. Using the notation of the paper I linked, I wasn't appreciating the fact that the constraint for the convex optimization is $\Theta\boldsymbol s=\boldsymbol y$, where $\Theta$ contains the information about the sparsity basis. So one can apply CS basically regardless of the sparsity basis, provided however that the sparsity basis is known? For some reason I convinced myself that you needn't know it in advance. I guess it makes sense that you do though. $\endgroup$
    – glS
    Commented Dec 6, 2017 at 22:27
  • $\begingroup$ Yes, and actually the sparsity basis does not have to be known until you reconstruct. $\endgroup$
    – Thomas Arildsen
    Commented Dec 8, 2017 at 5:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.