# An Efficient Method to Learn Overcomplete Multi-Scale Dictionaries of ECG Signals
## 1 Introduction
However, the atoms of the dictionary are either selected randomly from segments of the signal or taken directly from the first half of the ECG without any attempt to determine the most relevant waveforms. In this work, we describe an efficient method to construct an overcomplete and multi-scale dictionary for sparse ECG representation using waveforms recorded from real-world patients. Unlike on-line dictionary methods (which require multiple alternative iterations of the dictionary learning and sparse representation stages), the proposed approach learns the dictionary first, and then applies a fast sparse inference algorithm, Convolutional Sparse Approximation (CoSA) [21], to model the signal using the constructed dictionary. As a result, our method is much more efficient from a computational point of view than other existing algorithms, thus becoming amenable to deal with long recordings from multiple patients. Regarding the dictionary construction, we locate all the QRS complexes in the training database first, then we compute a single average waveform per patient, and finally we select the most representative waveforms (using a correlation-based approach) as the basic atoms that will be resampled to construct the multi-scale dictionary. With respect to the approach of [PERSON] et al., our method selects the optimal atoms to construct the dictionary, thus resulting in a much more compact solution. Numerical simulations demonstrate that the proposed approach is able to obtain a very sparse representation without missing any QRS complex or introducing spurious activations. Note that a preliminary version of this paper, where a single waveform was used to construct the overcomplete and multi-scale dictionary, was published in [22]. From a theoretical point of view, the main extension with respect to [22] is the proposal of a precise and novel procedure to incorporate multiple waveforms in the construction of the dictionary. Additional improvements, such as the simple and effective approach to remove the edge effects that appear after each resampling stage, have also been introduced in the pre-processing stages. Finally, a much more detailed literature review has been performed and many more numerical simulations, including both patients and channels (leads) not used to derive the dictionary, have been performed to characterize the behavior of the novel scheme. The rest of the paper is organized as follows. Section 2 formulates the sparse representation problem of ECGs, emphasizing the importance of an appropriate dictionary. Then, in Section 3, we describe in detail the procedure followed to derive a multi-scale dictionary from real-world signals: the database used, the pre-processing steps, and the actual dictionary construction. Finally, Section 4 validates the proposed approach (focusing on the capability of the derived dictionary to model different ECG leads from multiple patients), and the paper is closed by the conclusions and future lines in Section 5. Throughout the paper, we concentrate on the description of the proposed method without focusing on any particular application. However, note that the constructed dictionary can be useful in many practical applications: lossy compression of ECG signals for their storage and transmission [17; 20], denoising of ECGs contaminated by different types of interferences using sparse inference techniques [23], compressed sampling and sparse inference for heart rate variability analysis [24], sparse coding for atrial fibrillation (AF) classification [25], etc.