Is there any alternative characterization of sparsity of a signal in compressed sensing

Question

The starting assumption for compressed sensing (CS) is that the underlying signal is sparse in some basis, e.g., there are a maximum of $s$ 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.

Answer 1

If I understood well your question,

It is very unlikely that inference on sparsity can be made blindly from the receiver side in a generic setting starting from the random measurements provided by compressed sensing. In fact, one can show that if the signal being sampled is not too unusual, i.e., it is for example a mixing process, then the measurements will be approximately independent Gaussian RVs, particularly when the input dimensionality grows.

As for the transmitter (i.e., the CS encoder), you can easily estimate the sparsity with either an inverse given the sparsity basis, or basis pursuit given the dictionary chosen for the sparse representation. Then you basically check if the obtained representation in the sparsity basis or dictionary is sparse/compressible, i.e., you check the observable decay in the magnitude of the sorted coefficients or the ratio of energy (up to a certain threshold) represented by the k largest coefficients, and that is a good measure of the sparsity of your signal.