# Robust Long-Term Visual Object Tracking via Low-Rank Sparse Learning for Re-Detection
## 3 Tracking Algorithm Design
### Re-Detection Module  
The DCF-based tracker may lose the target, due to the impact of occlusion, out of view, and so on. Therefore, in this section, we propose a re-detection module that can mine more candidates in the extensive background if the DCF-based tracker is unreliable. The reliability estimation method is described in Section 3.3. In the initial frame, we densely sample a predefined number of target and background templates around the current target's location as the positive and negative training samples, respectively. Due to the dense sampling, the target and background templates may contain many similar ingredients. In addition, to alleviate the impact of occlusion and noise, we should exploit a correlation among these training samples. Here, our method utilizes sparse and low-rank representation [52; 53; 54] in a particle filter. Suppose that the template set \(A=[A_{1},A_{2},...,A_{N}]\in R^{D\times N}\), where \(D\) is the feature dimension of training sample, \(N\) refers to the total number of training samples. Let \(X=[X_{1},X_{2},...,X_{M}]\in R^{D\times M}\) be the data matrix of all test samples. Thus, \(X=AZ+E\)  
Figure 2: Illustration of the MBH. (**a,b**) Reference images at time \(t-1\) and t. (**c**) Horizontal motion boundary histograms. (**d**) Vertical motion boundary histograms. where \(Z=[Z_{1},Z_{2},...,Z_{M}]\in R^{N\times M}\) is the representation matrix of \(X\). Then, we can seek a representation of \(Z\) among all the candidates by solving the following optimization problem:  
\[ \begin{split}& min_{Z,E}\quad rank(Z)+\lambda_{1}\|Z\|_{0}+ \lambda_{2}l(E),\\ & s.t.\quad X=AZ+E,Z\geq 0,\end{split}  \tag{5}\]  
where \(E=[E_{1},E_{2},...,E_{M}]\in R^{D\times M}\) is a noise term, and \(l(E)=\|E\|_{2,1}=\sum_{j=1}^{M}\sqrt{\sum_{i=1}^{D}(|E|_{ij})^{2}}\)[55], so minimizing \(\|E\|_{2,1}\) encourages the columns of \(E\) to be zero. Since solving problem Equation (5) is NP-hard, we can relax rank function to nuclear norm as follows, and relax the \(l_{0}\)-norm to the \(l_{1}\)-norm. Therefore, Equation (5) can be rewritten as follows:  
\[ \begin{split}& min_{Z,E}\quad\|Z\|_{*}+\lambda_{1}\|Z\|_{1}+ \lambda_{2}\|E\|_{2,1},\\ & s.t.\quad X=AZ+E,Z\geq 0.\end{split}  \tag{6}\]  
Here, \(\|\cdot\|_{*}\) indicates the nuclear norm, that is, the sum of the singular values of the matrix. The parameter \(\lambda_{1}>0\) and \(\lambda_{2}>0\) are scalar parameters. We introduce an auxiliary variable \(W\) and convert the Equation (6) into an equivalent optimization problem:  
\[ \begin{split}& min_{Z,E}\quad\|Z\|_{*}+\lambda_{1}\|W\|_{1}+ \lambda_{2}\|E\|_{2,1},\\ & s.t.\quad X=AZ+E,Z=W,Z\geq 0.\end{split}  \tag{7}\]  
We can solve the optimization problem and obtain the low-rank sparse dictionary \(\hat{Z}\) and the noise matrix \(\hat{E}\) by the linearized alternating direction method with the adaptive penalty (LADMAP) [52]. The augmented Lagrangian function of Equation (7) is  
\[ \begin{split} L(Z,E,W,Y_{1},Y_{2},\mu)=&\|Z\|_{*}+ \lambda_{1}\|W\|_{1}+\lambda_{2}\|E\|_{2,1}\\ +&\langle Y_{1},X-AZ-E\rangle+\langle Y_{2},Z-W\rangle \\ +&\frac{\mu}{2}(\|X-AZ-E\|_{F}^{2}+\|Z-W\|_{F}^{2}), \end{split}  \tag{8}\]  
where \(\mu\) is the corresponding penalty factor. \(Y_{1}\) and \(Y_{2}\) denote the Lagrangian multiplier. \(\langle.,.\rangle\) is the inner product. Adopting LADMAP [52], we minimize the function \(L\) with other two variables fixed to update the variables \(Z\), \(E\), \(W\) alternately. When the target needs to be re-detected, we should first obtain a certain amount of the region of interest (ROI) candidates. Unlike random sampling or exhaustive sliding window search to obtain the candidates, we use EdgeBox algorithm [56] to produce a group of candidate bounding boxes and their proposal scores, and select the top \(M\) proposals as our candidate sample set \(x=\{x_{1},x_{2},...,x_{M}\}\). Further, we need to evaluate the reliability of these M candidate samples.