GOSUS: Grassmannian Online Subspace Updates with Structured-sparsity

        Jia Xu*Vamsi Ithapu*Lopamudra Mukherjee+James M. Rehg#Vikas Singh*     

*University of Wisconsin-Madison     +University of Wisconsin-Whitewater     #Georgia Institute of Technology

 
b00244_orig.jpg b00247_orig.jpg b00257_orig.jpg
b00244_fg_gosus.jpg b00247_fg_gosus.jpg b00257_fg_gosus.jpg
 

Abstract

We study the problem of online subspace learning in the context of sequential observations involving structured perturbations. In online subspace learning, the observations are an unknown mixture of two components presented to the model sequentially -- the main effect which pertains to the subspace and a residual/error term. If no additional requirement is imposed on the residual, it often corresponds to noise terms in the signal which were unaccounted for by the main effect. To remedy this, one may impose "structural" contiguity, which has the intended effect of leveraging the secondary terms as a covariate that helps the estimation of the subspace itself, instead of merely serving as a noise residual. We show that the corresponding online estimation procedure can be written as an approximate optimization process on a Grassmannian. We propose an efficient numerical solution, GOSUS, Grassmannian Online Subspace Updates with Structured-sparsity, for this problem. GOSUS is expressive enough in modeling both homogeneous perturbations of the subspace and structural contiguities of outliers, and after certain manipulations, solvable via an alternating direction method of multipliers (ADMM). We evaluate the empirical performance of this algorithm on two problems of interest: online background subtraction and online multiple face tracking, and demonstrate that it achieves competitive performance with the state-of-the-art in near real time.


Publication

  • Jia Xu, Vamsi K. Ithapu, Lopamudra Mukherjee, James M. Rehg, Vikas Singh. GOSUS: Grassmannian Online Subspace Updates with Structured-sparsity. In Proceedings of International Conference on Computer Vision (ICCV), December 2013. PDF, Supplement , Poster , Bibtex.

  • Source code and video results

    Full video results.
    Source code.
    Frame-wise results (7GB) for head-to-head comparison.

    Acknowledgments

    We thank Laura Balzano, Maxwell Collins, and anonymous reviewers for helpful comments. This research is funded via grants NSF RI 1116584, NSF CGV 1219016, NSF Award 0916687, and NSF EA 1029679. Partial support was provided by UW-ICTR and UW Graduate School/WARF grant.