# Kalman Filter Using a Third-Order Tensorial Decomposition of the Impulse Response
## 2 System Identification and TOT Decomposition
### TOT Decomposition  
The computational complexity of the conventional Kalman filter is proportional to the square of the filter length, i.e., \(\mathcal{O}(L^{2})\). This represents a significant challenge when dealing with the identification of long-length impulse responses, which is usually the case in echo cancellation scenarios. In addition, other important performance criteria are also influenced by the length of the filter, like the convergence rate and tracking capability, together with the accuracy of the filter estimate (in terms of misalignment).  
In this context, the TOT decomposition of the impulse response from [36] represents a useful approach, which could lead to important performance gains. The main idea is to take advantage of the low-rank features of the impulse response, in conjunction with the NKP decomposition, so that \(\mathbf{h}(n)\) of length \(L=L_{11}L_{12}L_{2}\) (with \(L_{11}L_{12}\gg L_{2}\)) can be decomposed as [36]  
\[\mathbf{h}(n)=\sum_{l=1}^{L_{2}}\sum_{p=1}^{P}\mathbf{h}_{2}^{l}(n)\otimes \mathbf{h}_{12}^{lp}(n)\otimes\mathbf{h}_{11}^{lp}(n), \tag{12}\]  
where \(P<L_{12}\) and the shorter impulse responses \(\mathbf{h}_{2}^{l}(n)\), \(\mathbf{h}_{12}^{lp}(n)\), and \(\mathbf{h}_{11}^{lp}(n)\) have the lengths \(L_{2}\), \(L_{12}\), and \(L_{11}\), respectively, while \(\otimes\) denotes the Kronecker product [50]. Therefore, in a system identification framework, the problem of estimating large parameter spaces, i.e., \(L\) coefficients of \(\mathbf{h}(n)\), is reformulated based on a combination (via the Kronecker product) of three shorter estimates, which result in a total of \(L_{2}^{2}+PL_{12}L_{2}+PL_{11}L_{2}\) coefficients. As a supporting example, let us consider that \(L=512\), which can be decomposed using \(L_{11}=L_{12}=16\) and \(L_{2}=2\). Usually, \(P\ll L_{12}\), as shown in [36] and also indicated by the simulation results provided in this paper (in the upcoming Section 4). For example, let us consider that \(P=1\) or \(P=2\). In these cases, instead of estimating 512 coefficients of \(\mathbf{h}(n)\), the TOT decomposition requires only \(4+32+32=68\) (for \(P=1\)) or \(4+64+64=132\) (for \(P=2\)) coefficients to be estimated. Consequently, there is a significant reduction in the parameter space, which could lead to important advantages in terms of both performance and complexity.  
For the purpose of the upcoming developments, the three sets of coefficients from the right-hand side of (12) are grouped into three impulse responses of lengths \(L_{2}^{2}\), \(PL_{12}L_{2}\), and \(PL_{11}L_{2}\), respectively, as follows:  
\[\underline{\mathbf{h}}_{2}(n) =\bigg{[}\ \ \big{(}\mathbf{h}_{2}^{1}\big{)}^{T}(n)\ \ \ \big{(}\mathbf{h}_{2}^{2}\big{)}^{T}(n)\ \ \ \cdots\ \ \ \big{(}\mathbf{h}_{2}^{L_{2}}\big{)}^{T}(n)\ \ \bigg{]}^{T}, \tag{13}\] \[\overline{\mathbf{h}}_{12}(n) =\bigg{[}\ \ \big{(}\overline{\mathbf{h}}_{12}^{1}\big{)}^{T}(n)\ \ \ \big{(}\overline{\mathbf{h}}_{12}^{2}\big{)}^{T}(n)\ \ \ \cdots\ \ \ \big{(}\overline{\mathbf{h}}_{12}^{L_{2}}\big{)}^{T}(n)\ \ \bigg{]}^{T},\] (14) \[\overline{\mathbf{h}}_{11}(n) =\bigg{[}\ \ \big{(}\overline{\mathbf{h}}_{11}^{1}\big{)}^{T}(n)\ \ \ \big{(}\overline{\mathbf{h}}_{11}^{2}\big{)}^{T}(n)\ \ \ \cdots\ \ \ \big{(}\overline{\mathbf{h}}_{11}^{L_{2}}\big{)}^{T}(n)\ \ \bigg{]}^{T}, \tag{15}\]  
where  
\[\overline{\mathbf{h}}_{12}^{l}(n) =\bigg{[}\ \ \big{(}\mathbf{h}_{12}^{l1}\big{)}^{T}(n)\ \ \ \big{(}\mathbf{h}_{12}^{l2}\big{)}^{T}(n)\ \ \ \cdots\ \ \ \big{(}\mathbf{h}_{12}^{lp}\big{)}^{T}(n)\ \ \bigg{]}^{T}, \tag{16}\] \[\overline{\mathbf{h}}_{11}^{l}(n) =\bigg{[}\ \ \big{(}\mathbf{h}_{11}^{l1}\big{)}^{T}(n)\ \ \ \big{(}\mathbf{h}_{11}^{l2}\big{)}^{T}(n)\ \ \ \cdots\ \ \ \big{(}\mathbf{h}_{11}^{lp}\big{)}^{T}(n)\ \ \bigg{]}^{T}, \tag{17}\]  
with \(l=1,2,\ldots,L_{2}\). The next goal is to reformulate the Kalman filter in terms of the component impulse responses from (13)-(15). In this manner, their estimates can be further combined similar to (12), in order to model the global impulse response of the unknown system.