Advanced signal processing is widely used in healthcare systems and equipment. Compressing ECG signals is beneficial in long-term monitoring of patients’ behavior. Compressed Sensing (CS) based ECG compression has shown superiority over the existing ECG compression approaches. In current CS ECG compression methods, sparsity order (number of basis vectors involved in the compression) is determined either empirically or by thresholding approaches. Here, we propose a new method denoted by Optimum Sparsity Order Selection (OSOS) that calculates the sparsity order by minimizing reconstruction error. In addition, we have shown that basis matrix based on raised Cosine kernel has more efficiency in compression over the Gaussian basis matrices. The fundamentals of OSOS algorithm is such that the method is robust to observation noise. Simulation results confirm efficiency of our method in terms of compression ratio.