# An Efficient Method to Learn Overcomplete Multi-Scale Dictionaries of ECG Signals
## 2 Problem Formulation
Let us now group all the candidate waveforms into a single matrix \(\mathbf{A}=[\mathbf{A}_{0}\;\;\mathbf{A}_{1}\;\;\cdots\;\;\mathbf{A}_{N-M-1}]\), where the \(N\times P\) matrices \(\mathbf{A}_{k}\) (for \(k=0,\ldots,N-M-1\)) have column entries equal to \(\Gamma_{p}[m-k]\) for \(m=k,\ldots,k+M-1\) and \(0\) otherwise. Then, the model of Equation (2) can be expressed more compactly in matrix form as follows:  
\[\mathbf{x}=\mathbf{A}\boldsymbol{\beta}+\varepsilon, \tag{3}\]  
where \(\mathbf{x}=[x[0],\ldots,x[N-1]]^{\top}\) is an \(N\times 1\) vector with all the ECG samples, \(\boldsymbol{\beta}=[\beta_{0,1},\ldots,\beta_{0,P},\beta_{1,1},\ldots,\beta_{1,P},\ldots,\beta_{N-M-1,1},\ldots,\beta_{N-M-1,P}]^{\top}\) is an \((N-M)P\times 1\) coefficients vector, and \(\boldsymbol{\varepsilon}=[\varepsilon[0],\ldots,\varepsilon[N-1]]^{\top}\) is the \(N\times 1\) noise vector. Note that the matrix \(\mathbf{A}\) can be considered as a global dictionary composed of \(N-M\) sub-dictionaries, \(\mathbf{A}_{k}\) for \(k=0,1,\ldots,N-M-1\), that contain replicas of the candidate waveforms time shifted to \(t_{0}=0\), \(t_{1}=T_{s}\),..., \(t_{N-M-1}=(N-M-1)T_{s}\). In practice, the usual approach is to either use a single or several different waveforms with different time scales (_atoms_) to cope with the uncertainty about the shape and duration of the pulses that can be found in \(x[n]\). Hence, as a result, we obtain an _overcomplete dictionary_ (as the number of columns is larger than the number of rows, i.e., \((N-M)P>N\)) composed of time-shifted, multi-scale waveforms which resemble the relevant electrical impulses that can be observed in the recorded ECGs. Now, two key questions arise:  
Figure 1: Example of a clean P-QRS-T cycle, with the peaks of all the relevant waveforms marked. The signal has been generated in Matlab using the ECGSYN waveform generator [26] with the following command: [s, ipeaks] = ecgsyn(1000,60,0,60,1,0.5,1000);  
1. Which is the optimal dictionary to model external ECG signals and how can we construct it? 2. Given an overcomplete dictionary, how can we obtain the optimal set of coefficients that represent only the relevant signal components? Regarding the second question, let us remark that the only unknown term in Equation (3) is \(\mathbf{\beta}\) when the dictionary is fixed. A classical solution to obtain this set of coefficients \(\mathbf{\beta}\) is then minimizing the \(L_{2}\) norm of the error between the model and the observed signal, thus obtaining the least squares (LS) solution:  
\[\mathbf{\hat{\beta}}_{LS}=\arg\min_{\mathbf{\beta}}\|\mathbf{x}-\mathbf{A}\mathbf{\beta} \|_{2}^{2}, \tag{4}\]  
with \(\|\cdot\|_{2}\) denoting the \(L_{2}\) norm of a vector. The solution of Equation (4) is not unique, as it requires solving an overdetermined system of linear equations, but the standard solution (i.e., the solution that minimizes the \(L_{2}\) norm of the obtained coefficients) is \(\mathbf{\hat{\beta}}_{LS}=\mathbf{A}^{\sharp}\mathbf{x}\), where \(\mathbf{A}^{\sharp}=(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\) denotes the pseudoinverse of \(\mathbf{A}\). (Note that, even though \(\mathbf{\hat{\beta}}_{LS}\) can be computed analytically from a theoretical point of view, it requires inverting an \((N-M)P\times(N-M)P\) matrix. Hence, we can easily encounter computational or numerical problems when \((N-M)P\) is large and/or \(\mathbf{A}\) is ill-conditioned.) However, the LS approach leads to a solution where all the coefficients in \(\mathbf{\hat{\beta}}_{LS}\) are likely to be non-zero. This solution does not take into account the sparse nature of the relevant waveforms in \(x[n]\) and results in overfitting, as part of the noise and interference terms are also implicitly modeled by the first term in Equation (3).