# An Efficient Method to Learn Overcomplete Multi-Scale Dictionaries of ECG Signals
## 2 Problem Formulation  
Let us assume that we have a single discrete-time ECG, \(x[n]\), that has been obtained from a properly filtered and amplified continuous-time ECG, \(x_{c}(t)\), through uniform sampling with a sampling period \(T_{s}=1/f_{s}\), i.e., \(x[n]=x_{c}(nT_{s})\). An _external ECG_ captures the electrical activity occurring within the heart that triggers the mechanical cycle (systole and diastole) of the heart. Consequently, it is composed of a set of waveforms that reflect the different stages of the electrical cycle of the heart [1]: atrial depolarization (P waveform), ventricular depolarization (QRS complex) and ventricular repolarization (T waveform). Note that atrial repolarization cannot be observed in external ECGs, since it is masked by the ventricular depolarization, which happens simultaneously and produces a much stronger signal.All of these waveforms repeat themselves regularly during the heart's electrical cycle (thus leading to the well-known P-QRS-T cycle), although important changes in morphology, as well as fluctuations in amplitude, duration and interarrival times can be observed both for intra-patient and inter-patient recordings. Figure 1 shows an example of a single cycle from a clean synthetic ECG generated using the ECGSYN waveform generator [26] downloaded from Physionet [27], where all the relevant P-QRS-T waveforms, as well as the QRS onset and offset (also known as \(\mu\) and \(j\) points [28]) can be clearly identified. On top of the relevant electrical activity, the ECG also contains several types of noise and interference signals [1]: additive white Gaussian noise introduced by the electronic equipment used to acquire the ECGs (sensors, amplifiers and filters), baseline wander caused by the patient's respiration, powerline interference arising from the electrical network, electromyographic noise, motion artifacts, electrode contact noise, etc. Mathematically, this situation can be modeled as the superposition of the waveforms of interest (QRS complexes, P and T waveforms) as well as all the noise and interferences:  
\[x[n]=\sum_{k=-\infty}^{\infty}E_{k}\Phi_{k}(t_{n}-T_{k})+\epsilon[n],\ \ n=0, \ldots,N-1, \tag{1}\]  
where \(T_{k}\) denotes the arrival time of the \(k\)th electrical pulse; \(E_{k}\) its amplitude; \(\Phi_{k}\) is the associated, unknown pulse shape corresponding to QRS complexes, P and T waveforms; and \(\epsilon[n]\) the noise and interference term. Note that, in real-world applications, \(\Phi_{k}\), \(T_{k}\), and \(E_{k}\) are not precisely known. However, for the ECG, the typical shapes and durations of the \(\Phi_{k}\) are known for all of the relevant waveforms. Therefore, they can be approximated by a time-shifted, multi-scale dictionary of known waveforms with finite support \(M\ll N\) that can then be used to infer the \(E_{k}\) and \(T_{k}\). More precisely, let us define a set of \(P\) candidate waveforms, \(\Gamma_{p}\) for \(p=1,\ldots,P\), with a finite support of \(M_{p}\) samples such that \(M_{1}<M_{2}<\cdots<M_{P}\) and \(M=\max_{p=1,\ldots,P}M_{p}=M_{P}\). If properly chosen, these waveforms can provide a good approximation of the local behavior of the signal around each sampling point, thus allowing us to approximate Equation (1) through the following model:  
\[x[n]=\sum_{k=0}^{N-M-1}\sum_{p=1}^{P}\beta_{k,p}\Gamma_{p}[n-k]+\varepsilon[n ],\;\;n=0,\ldots,N-1, \tag{2}\]  
where the \(\beta_{k,p}\) are coefficients that indicate the amplitude of the \(p\)th waveform shifted to the \(k\)th time instant, \(t_{k}=kT_{s}\); and \(\varepsilon[n]\) includes also the additional approximation error associated to using Equation (2) instead of Equation (1), as well as all the noise and interferences already contained in \(\varepsilon[n]\).