Hello jarvis323! Thank you for your help.
My basic understanding is that we can sub-sampled a signal (i.e. capture less digital samples than Nyquist theorem requires) and still be able to reconstruct the original signal (a very good approximation of it), if the signal has structure, is compressible, and sparse in some domain (i.e. under some basis like the Fourier basis, the cosine basis, the wavelet basis, etc.)
In general, we have a continuous signal ##s(t)## and we sample it to obtain its discrete version ##x[n]##. To reconstruct ##x(t)##, we need ##N## samples by sampling at the frequency $$f=\frac {1}{2BW}$$. We then use interpolation to reconstruct ##x(t)## from its collected discrete samples.
In the case of compressible signals (lossy compression), we later discard the data that is less relevant and still reconstruct the original signal ##x(t)##. That is what happens jpeg, mp3, etc.
In compressed sensing, we directly capture the signal information that matters. That is cool.
This leads to solving an under-determined linear system of equations: $$ y= \Phi x$$ where ##x## is the original discrete signal, ##\Phi## is the random sampling matrix, ##y## is a vector with the measured samples. The signal ##x## is equal to ##x = \Psi \times s ## where ##\Psi## is a matrix containing basis vector and ##s## is a sparse vector...The goal is to find ##s##! Do we need to know the basis ##\Psi## under which the signal ##x(t)## is sparse a priori?
Eventually, the problem to solve is $$y = \Phi \Psi s$$ The matrix ##\Phi## is a random matrix...What kind of randomness are we taking about? We are essentially randomly subsampling the signal ##x[n]##...
Am I on the right track?