Abstract: The performance of existing object tracking algorithms decreases obviously when the object undergoes partial or full occlusion, and posture change with complex background. To handle these problems, an online incremental projection non-negative matrix factorization based object tracking algorithm with sparse and time smooth constraints is proposed. The local structure of the target is represented by the basis matrix, which is extracted by non-negative matrix factorization along with the sparse constraint to deal with a variety of challenging scenarios and the time smooth constraint to improve the tracking robustness. The incremental basis matrix updating strategy reduces the amount of computation evidently, resulting in the appearance model updating more efficiently. In the particle filter framework, the observation likelihood function is modified based on the reconstruction error of candidates when projected to the basis matrix, the candidate with a max posteriori probability is recognized as the target in the current frame. Experimental results on various video sequences show that, compared with the state-of-the-art tracking methods, the proposed algorithm achieves favorable performance when the object has large occlusion or scale variation.