We have recently quantified and validated the potential of the emerging compressed sensing (CS) paradigm for real-time energy-efficient electrocardiogram (ECG) compression on resource-constrained sensors. In the present work, we investigate applying sparsity models to exploit underlying structural information in recovery algorithms. More specifically, re-visiting well-known sparse recovery algorithms, we propose novel model- based adaptations for the robust recovery of compressible signals like ECG. Our results show significant performance gains for the recovery algorithms exploiting the underlying sparsity models.