Support vector machine (SVM) based tracking algorithms training with dense circulant samples have shown favourable performance due to its strong discriminative power and high efficiency. However, the challenges caused by the circulant sampling remain unaddressed. In this study, the authors give each training sample a weight based on their accuracy to reduce the influence of inaccurate samples. Moreover, they reform the SVM model with weighted circulant training samples. Secondly, they advocate an efficient solution by using the property of circulant matrices to solve the learning problem. Thirdly, a model update strategy is introduced to prevent the tracking models polluted by wrong samples. Experimental results on large benchmark datasets with 50 and 100 video sequences demonstrate that the authors’ tracking algorithms achieve state-of-art performance in terms of precision and accuracy. In addition, their tracker runs in real time.