Electrocardiogram (ECG) signals are primarily used to identify cardiac disorders. However, these data are stored at higher bit resolutions, which affects data transmission and storage efficiency of recording and monitoring instruments. In this context, a new hybrid compression and reconstruction algorithm is proposed by combining singular value decomposition (SVD) and optimized singular value thresholding (SVT). The SVT is an algorithm based on matrix completion, which can recreate the original data from a few observed entries. Furthermore, SVT is integrated with hybrid cuckoo search-gray wolf optimization (Hybrid CS-GWO) for optimum input parameter selection for further improving the reconstruction performance. In this approach, low rank completion property of matrix completion is utilized by converting a 2D ECG array into a low rank approximation using SVD to improve the compression performance. The performance of Hybrid CS-GWO is also validated by comparing it with some popular, well-known optimization algorithms to further confirm the effectiveness of the proposed work. It is tested on some commonly used ECG records affected by different anomalies obtained from the widely used MIT-BIH arrhythmia database. The performance is assessed in terms of frequently used parameters as compression ratio, percentage root–mean–square difference, and quality score, and the obtained values are 17.03, 2.58, and 7.64, respectively.