Is the basis of the sparse signal assumed known in compressed sensing?

Question

I'm new to compressed sensing, and am a little confused about the assumption of the basis matrix $\Psi$. Is $\Psi$ assumed known in compressed sensing?

Specifically, suppose that a signal $x$ is sparse in some basis, say $\Psi$, i.e. $x=\Psi\alpha$, where $\alpha$ is $k$-sparse, i.e. $\|\alpha\|_0\le k$. My understanding is that in compressed sensing, we store $y=Ax$, where $A$ is the $m\times n$ sensing matrix with RIP. Later on, we can recover $x$ theoretically by

$$\hat\alpha=\underset{\alpha\::\:y=A\Psi\alpha}{\arg\min}\|\alpha\|_0,$$

(or use $l$-1 norm) and then $\hat x=\Psi\hat\alpha.$

In doing so, we need to know $\Psi$ to recover $x$, don't we? But if we know $\Psi$, why don't we just measure $z=\Psi^{-1}x=\Psi^{-1}\Psi\alpha=\alpha$, and store the value and index of the non-zero components of $z$ ($=\alpha$)? Can the dimensions ($m$) of $y$ be less than $2k$? Or is it that $z$ won't be perfectly equal to $\alpha$ due to noise, and we don't want to do thresholding on the fly? Or some other reason?

I'm confused about the rationale of compressed sensing, and would appreciate any pointers, comments, and clarifications. Thanks a lot!

Answer 1

Compressive Sensing is an approach to reconstruct sparse signals from incomplete set of measurements.

In doing so, we need to know $Ψ$ to recover $x$, don't we?

yes, we do.

But if we know $Ψ$, why don't we just measure $z=Ψ^{−1}x=Ψ^{−1}Ψα=a$, and store the value and index of the non-zero components of $z (=α)$?

Compressive Sensing as the name indicates is a method to sense the incoming signal not to compress it. Which means the signal is not present yet and we are going to sample it, this sampling is efficient and requires minimum number of samples for signal reconstruction. There is a misunderstanding here, we might know $Ψ$ in advance but we usually do not have the signal itself $x$, if we do, clearly compression techniques are preferred. The other reason is that sampling domain could be different from the domain in which the signal has a sparse representation. For example, we might sample a fourier sparse signal in time (e.g. radiowaves) or sample a fourier sparse image in space (e.g. Cameras, MRI,..). And then reconstruct it it in fourier domain.

Can the dimensions ($m$) of $y$ be less than $2k$?

Observing this bands guarantees perfect reconstruction (with overwhelming high probability) for any $k$-sparse signal, but reconstruction is still probable for $m < 2k $; So, as the number of measurements ($m$) is reduced probability of reconstruction reduces as well. But if you mean maintaining the perfect reconstruction probability while minimizing $m$, I think it would depend on your matrix design.