Electrocardiogram (ECG) data is compressible athigh compression ratios using suitable compressive sensing techniques.Methods of detecting QRS complexes in an ECG signal maycomprise receiving compressively-sensed measurements of an ECGsignal; constructing an estimate of the ECG signal from the receivedcompressively-sensed measurements, and detecting QRS complexesin the estimate of the ECG signal. QRS complexes may be detectedby computing the first-order difference of the estimate of theECG signal and processing the first-order difference of the estimateof the ECG signal to locate one or more significant natural blocks,each indicating a QRS complex in the ECG signal. QRS complexesmay also be detected by using a conventional QRS detection algorithmon the estimate of the ECG signal. Also disclosed are relatedsystems for detecting QRS complexes and for compressively sensingECG signals.