Abstract This paper deals with the problem of tele-monitoring EEG signals. In EEG tele-monitoring system, the integral step is to compress the signals in computationally efficient manner so that they can be transmitted over a limited bandwidth. In such a situation a Compressed Sensing (CS) framework for compressing and recovering the signals is the most viable approach. Previously the well known synthesis prior formulation is used for reconstruction. For the first time in this work, we show that the lesser known analysis prior formulation is a more appropriate way to frame the reconstruction problem. We show that our method yields better results than the previous synthesis prior formulation.