Fast incremental method for matrix completion: An application to trajectory correction

We address the problem of incrementally recovering a matrix of tracked image points, based on partial observations of their trajectories. Besides partial observability, we assume the existence of gross, but sparse, noise on the known entries. This problem has obvious applications in real-time tracking and structure from motion, where observations are plagued by self-occlusion and outliers. Recently, work in the optimization community has spun optimal methods for matrix completion when this matrix is known to be low rank by minimizing the nuclear norm, the sum of its singular values. Despite exhibiting several optimality properties, no available algorithms perform this minimization incrementally. In this paper, we build upon the Nuclear Norm Robust PCA method and SPectrally Optimal Completion to propose a fast and incremental algorithm which is able to cope with outliers. We present experiments showing the competitive speed of our method while maintaining performance comparable to the state-of-the-art.