# An Efficient Method to Learn Overcomplete Multi-Scale Dictionaries of ECG Signals
## 1 Introduction  
Since the development of the first practical apparatus for the recoding of the electrocardiogram (ECG) by [PERSON] in 1903, ECGs have been widely used by physicians to diagnose and monitor many cardiac disorders. Indeed, the use of the ECG has become so widespread that it is nowadays routinely used in both clinical and ambulatory settings to obtain a series of indicators related to the health status of patients [1]. This ubiquitous presence of ECGs in the medical field has been greatly enabled by digital signal processing (DSP) techniques: ECGs were the first biomedical signals where DSP algorithms were extensively applied to remove noise and interferences, detect and characterize the different waveforms contained in the ECG, extract the signals of interest (e.g., the fetal ECG) from the composite ECG, etc. [1,2]. By its own nature, the ECG is typically a sparse signal, composed of regular activations (the QRS complexes and other waveforms, such as the P and T waves) and periods of inactivity (corresponding toisoleucine intervals, such as the PQ or ST segments), as well as noise and interferences (baseline wander, powerline interference, electromyographic noise, motion artifacts, etc.) [1]. Since the introduction of the Least Absolute Shrinkage and Selection Operator (LASSO) regularizer by [PERSON] in 1996 [3], many sparse inference and representation techniques have been developed and successfully applied for all kinds of signals [4]: images, sound/audio recordings, biomedical waveforms, etc. However, to obtain a good sparse model for a given signal, it is essential to have an adequate dictionary composed of atoms that properly represent the significant waveforms contained in the observed signals. This has led to the development of many families of dictionaries (based on wavelets and wavelet packets, curvelets, contourlets, etc.) for different applications, as well as several on-line dictionary learning algorithms (e.g., see [5; 6; 7] for reviews of different dictionary learning methods for sparse inference) that typically require multiple alternative iterations of the dictionary learning and sparse representation stages. In electrocardiographic signal processing, many approaches have been proposed for the sparse representation of single-channel and multi-channel ECGs using different types of simple analytical waveforms: Gaussians [8; 9; 10], generalized Gaussians and Gabor dictionaries [11], several families of wavelets (e.g., the Mexican hat or the coiflet4) [12; 13], etc. Although these approaches can lead to good practical results, the resulting models usually contain many spurious activations that must be removed to obtain physiologically interpretable signals, for instance by means of a post-processing stage [9; 13] or through the minimization of a complex non-convex cost function [14]. Conversely, a customized dictionary, built from real-world signals, will provide a better performance in terms of the reconstruction error obtained for a given level of sparsity. Consequently, several _on-line_ dictionary learning approaches have also been applied, both in the context of sparse inference and compressed sensing (CS), to ECG signals: the K-SVD algorithm in [15], the shift-invariant K-SVD in [16], and the method of optimal directions in [17]. Unfortunately, all these methods have a high computational cost (due to their need to iterate between the dictionary learning and sparse approximation stages) and lead to dictionaries whose atoms do not correspond to real-world signals (thus reducing the interpretability of the sparse model, as well as the ability to easily locate the relevant waveforms). Alternatively, an _off-line_ dictionary construction methodology (where a dictionary with real-world waveforms is initially built and then directly used for CS and sparse modeling without any further modification) was recently proposed by [PERSON] et al. [12; 18; 19; 20].