Abstract: In the object tracking, object is often lost because of the object appearance changes. Thus, an improved compressive tracking algorithm based on the online feature updating and weighting is proposed in this paper. Firstly, the rectangle features are extracted based on the compressed sensing theory. The reliability of each feature is determined according to their classification performances for object tracking in the current frame. Then unreliable features are updated in time. Secondly, the values of reliable features’ weights are increased in real-time such that their importances can be emphasized. Finally, these new weighted candidate features are inputted into the Beyesian classifier to distinguish the object from background in the next frame. Eight challenging video sequences are chosen to verify the performances of our proposed algorithm. Compared with traditional compressive tracking algorithm, locality sensitive histograms tracking algorithm and online AdaBoost, experimental results show that our algorithm achieves better tracking results and is robust for appearance changes. The frame rate is 39fps in average, which satisfies the requirement of real-time tracking.