# rStaple: A Robust Complementary Learning Method for Real-Time Object Tracking
## 3 Preliminaries  
### Kernelized Correlation Filter  
The core of correlation filter-based trackers [18; 19; 20; 21; 22; 23; 24; 25; 26; 27] is that they adopt the circulant matrix to construct training samples. Since the correlation operation corresponds to the dot product operation in the Fourier domain, the circulant matrix can be diagonalized by Fourier transform. Thus, the computational complexity can be significantly reduced. In other words, it can be implemented efficiently via Fourier transform. A correlation filter generally adopts a ridge regression model [37] to train a classifier in order to find a function \(f(x)=w^{T}x\), where \(x\) represents the input training samples and \(w\) corresponds to the model parameters. It minimizes the squared error between the training samples \(x_{i}\) and the regression target \(y_{i}\). The ridge regression model can be formulated as an unconstrained optimization problem expressed as:  
\[\min_{w}\sum_{i}\left(f(x_{i})-y_{i}\right)^{2}+\lambda\|w\|^{2} \tag{1}\]  
where \(\lambda\) is a regularization parameter to avoid overfitting. One reason for using the ridge regression model to train a classifier is that the optimization problem of Equation (1) has a closed-form solution, which is given by [37]:  
\[w=\left(X^{H}X+\lambda I\right)^{-1}X^{H}y \tag{2}\]  
Note that each row in \(X\) corresponds to a training sample generated by cyclic shifts and each element in \(y\) represents the regression score of the training sample. The regression score of each sample conforms to a Gaussian distribution which decays from 1 to 0 when the cyclic samples gradually shift away from the target center. The sample \(X\) can be diagonalized by the discrete Fourier transform (DFT) and expressed as:  
\[X=Fdiag(\hat{x})F^{H} \tag{3}\]  
where \(F\) denotes a constant matrix and \(\hat{x}=F(x)\) denotes the DFT of \(x\). \(X^{H}X\) can be obtained by:  
\[X^{H}X=Fdiag(\hat{x}^{*})diag(\hat{x})F^{H}=Fdiag(\hat{x}^{*}\odot\hat{x})F^{H} \tag{4}\]  
where \(\odot\) denotes element-wise product operation and \(\hat{x}^{*}\) is the complex-conjugate of \(\hat{x}\). The closed-form of Equation (2) can be represented in Fourier domain as:  
\[\hat{w}=\frac{\hat{x}^{*}\odot\hat{y}}{\hat{x}^{*}\odot\hat{x}+\lambda} \tag{5}\]  
[PERSON] et al. introduced a kernel trick to improve the discriminating ability of the classifier. The linear regression function is replaced by a non-linear regression function \(f(z)=w^{T}\phi(z)\), while the implementation speed of the non-linear correlation filters is still guaranteed to be as fast as the linear correlation filters. The input linear problem can be mapped to a non-linear space through the kernel trick. The solution \(w\) can be expressed as a linear combination of \(x\) by:  
\[w=\sum_{i}\alpha_{i}\varphi(x_{i}) \tag{6}\]  
The optimization problem of \(w\) can be converted into an optimization problem of \(\alpha\)  
Equation (7) has a closed-form solution, which is given by [37]:  
\[\alpha=(K+\lambda I)^{-1}y \tag{8}\]  
One way to speed up the calculation is to convert the inversion operation into an element-wise product, which needs the diagonalization of the matrix \(K\). This indicates finding a kernel function that transforms the kernel correlation matrix \(K\) into a circulant matrix. The parameter \(k\) is defined as:  
\[k^{xx^{\prime}}=\exp(-\frac{1}{\sigma^{2}}(\|x\|^{2}+\|x^{\prime}\|^{2}-2F^{-1} (\hat{x}^{*}\odot\hat{x}^{\prime}))) \tag{9}\]  
By substituting the kernel correlation matrix \(K\) in Equation (8), the closed-form \(\alpha\) can be expressed as:  
\[\hat{\alpha}=\frac{\hat{y}}{\hat{k}^{xx}+\lambda} \tag{10}\]  
The above operation converts a complex matrix inverse problem into a simple basic operation problem, which greatly reduces the computational complexity. In this way, a correlation filter algorithm would achieve high-speed object tracking.