Wireless telemonitoring of physiological signals provides an opportunity for compressed sensing. Biomedical signals are known to be sparse in some known basis, such as wavelet, discrete cosine transform, and Gabor. For orthogonal or tight-framed basis, one can use the synthesis formulation. Row sparsity is one way to exploit structure for multi-channel signal recovery. It sparsifies the signal in the temporal direction and exploits structure/correlation along the channels. Another approach would be to sparsify in both dimensions, that is, along the temporal direction as well as along the channels. In this approach, the sparsifying transform along the channels effectively “whitens” the correlations, leading to a very sparse representation. This chapter illustrates the decay of coefficients from a two-dimensional Fourier transform applied on the multi-channel electroencephalogram data matrix.