Compressed Sensing and Sparsity
As far as choosing the right dictionary (basis) goes, there are several things to take into account. You do want your representation $s$ to be as sparse as possible and that depends a lot on the chosen dictionary. In practice, people are often looking at a particular type of signals $x$ which they know from domain knowledge to be sparse in some dictionary (discrete wavelet transform, discrete Fourier transform, etc.). However, you also need the dictionary $\Psi$ to "work well" together with the measurement matrix $\Phi$. This can be measured by their coherence (see e.g. Candès &amp; Wakin, 2008). If you are free to choose $\Phi$ as you like, you can select the dictionary $\Psi$ that gives you the sparsest representation and then select $\Phi$ to be incoherent with $\Psi$. In practice $\Phi$ is often limited by hardware constraints and then you may have to select a suboptimal $\Psi$ with respect to sparsity in order to achieve incoherence with $\Phi$.

Another approach is dictionary learning where you can use (many) examples of the type of signal $x$ you are looking for to learn a dictionary $\Psi$, see for example Aharon, Elad, Bruckstein, 2006.