Adaptive least trimmed square

From (0.3), the residuals, r_i with the corresponding τ_i ≠ 0, would deviate from zero, which suggests that the set of outliers can be identified through thresholding as follows

where E is the set of detected outliers, k is a tuning parameter controlling the sensitivity of the model, and r_med is the median of {|r|i}i=1n. We denote the number of elements in set E as |E| and let N be the number of true outliers in the data. First, we can use least squares and formula (0.4) to obtain a rough estimate of E denoted as E^. Let the cardinality of E^ be N¯. Since the model at this moment is inaccurate with contamination of outliers, N¯ is an overestimation of N which can be used to get an underestimate via N_=α1N¯ with α₁ ∈ (0, 1). With N_, we can then update the least square fitting after removing the N_ samples with the largest absolute value of residuals and obtain an improved estimate of E and the corresponding N¯. We can improve the model by repeating the procedure, but we need to increase the underestimate of outliers, N_, by a factor of α₂ with α₂ > 1 for each iteration to force the convergence between N¯ and N_. In sum, we initialize our algorithm by setting

which is the OLS solution. For the jth iteration, where j ≥ 1, we update N¯(j) by

where the min(⋅, ⋅) operator guarantees that N¯(j), an overestimation of N, is non-increasing. Similarly, we update N_(j) through

where ⌈x⌉ means the ceiling of x∈R, α₁ ∈ (0, 1) is used to obtain a lower bound for N in the first step, α₂ > 1 guarantees the monotonicity of N_(j), and the min(⋅, ⋅) operator guarantees N_(j) is smaller than N¯(j). Then we update β^ and r after removing N_(j) outliers by

We repeat this procedure until N_ and N¯ converge.

Hence, we hereby report a novel approach, coined as adaptive Least Trimmed Square (aLTS), to automatically detect and remove contaminating outliers. Our aLTS is an extension of the iterative LTS algorithm proposed by Xu et al. [31] which is designed for binary output such as the comparison between two images or videos.