# An Improved Dictionary-Based Method for Gas Identification with Electronic Nose
## 2 Materials and Methods
### The Analysis of Time Complexity  
Usually, an algorithm can be assessed by the time complexity or space complexity [45]. This paper only analyzed the time complexity from the part of updating the dictionary.  
Figure 7: The flowchart of the improved algorithm.  
Here, the number of training samples was \(m\), the dimension of datasets was \(n\), the number of atoms was \(r\), and the dimension of the diagonal matrix was \(h\).  
First, the traditional K-SVD dictionary learning algorithm was analyzed, where Equation (5) \(E=\|E_{k}-s_{k}x_{k}^{T}\|_{F}^{2}\) requires about \((n*1*m)\) multiplications and \((n*1*m)\) subtractions, and the time complexity is O(\(2 mn\)). Then, the singular value decomposition of E\({}_{k}\) requires \((n*h*1)\) operations, and the time complexity is O(\(nh\)). The formula \(X=QV\) needs \((h*h)\) operations, and the time complexity is O(\(h^{2}\)). Hence, completing the part of updating all atomic columns requires:  
\[T_{a}=\sum_{m}2 nm+nh+h^{2}=2 nm^{2}+nmh+mh^{2} \tag{16}\]  
Then, the time complexity analysis of the improved algorithm was analyzed. From Equation (6), it can be seen that the formula \(E_{r}^{t}=X-\sum_{j\
eq i+1,...,j+r}^{k}d_{j}^{(t-1)}w_{(m\cdot r}^{(t)}\) requires \((2n*(m-2r)*m+2n*r*m)\) operations, and the time complexity is O(\(2n(m-r)\)). The singular decomposition of a sparse matrix requires \((r*h*m)\) operations, and the time complexity is O(\(rhm\)). The formula \(S_{n}=XV^{T}Q^{-1}U\) requires three multiplications including the process of the inversion. In fact, only the diagonal element of the diagonal matrix Q needs to be calculated because Q is a diagonal matrix, so inverting the matrix Q only requires \((h)\) operations. Among them, the formula \(XV^{T}\) requires about \((n*h*m)\) operations, and right multiplying matrix Q\({}^{-1}\) requires \((n*h*h)\) operations. Finally, right multiplying U requires \((n*h*r)\) operations. Hence, completing the part of updating all atomic columns requires:  
\[\begin{array}{ll}T_{b}&=\sum\limits_{\frac{m}{r}}\big{(}2n(m-r)+mlr+h+nhm+nh^ {2}+nhr\big{)}\\ &=\frac{2 nm}{r}(m-r)+m^{2}h+\frac{hm}{r}+\frac{uhn^{2}}{r}+\frac{umh^{2}}{r}+ nmh\end{array} \tag{17}\]  
It can be seen from Equations (16) and (17) that it was not easy to observe the magnitude relationship. For simplicity, by calculating the difference between Equation (17) and Equation (16) under the certain case: \(h=6\); \(m=270\); \(n=24\), it can be expressed as:  
\[\begin{array}{ll}f(r)&=T_{a}-T_{b}=2 nm^{2}-\frac{2 nm}{r}(m-r)-m^{2}h-\frac{ nm}{r}-\frac{umh^{2}}{r}-\frac{umh^{2}}{r}+ml^{2}\\ &=3499200-12960\times\big{(}\frac{270}{r}-1\big{)}-437400-\frac{10732500}{r}+ 36\times 270\\ &=3084480-\frac{1431700}{r}\end{array} \tag{18}\]  
Figure 8 shows the relationship between the computational complexity and the number of updated atomic columns. When the number of updated atomic columns is larger than 5, the computational complexity increases with the increase in the number of updated atomic columns. When the number of updated atomic columns is larger than 15, the curve increases more slowly with the increase in the number of updated atomic columns. Finally, the theoretical analysis proves that the proposed algorithm reduces the computational complexity to a certain extent.