The starting assumption for compressed sensing (CS) is that the underlying signal is sparse in some basis, e.g., there are a maximum of non-zero Fourier-coefficients for an $s$-sparse signal. And real life experiences do show that the signals under consideration are often sparse.
The question is - given a signal, before sending out the compressively-sampled bits to the receiver and let her recover to the best of her abilities, is there a way to tell what its sparsity is, and if it is a suitable candidate for compressed sensing in the first place?
Alternatively, is there any additional/alternative characterization of sparsity that can tell us quickly whether CS will be useful or not. One can trivially see that the sender could do exactly what the receiver will do with some randomly chosen set of measurements, and then try to figure out the answer. But is there any alternate way to resolve this question ?
My suspicion is that something like this must have been studied, but I couldn't find a good pointer.
Note : I had posted this question in Mathoverflow, a few weeks back, but didn't get any answer. Hence the cross-post.