iccv iccv2013 iccv2013-182 iccv2013-182-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jia Xu, Vamsi K. Ithapu, Lopamudra Mukherjee, James M. Rehg, Vikas Singh
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.
[1] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk. Slic superpixels compared to state-of-the-art superpixel methods. PAMI, 34(1 1):2274–2282, 2012.
[2] T. Arias, A. Edelman, and S. Smith. The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20:303–353, 1998.
[3] S. Arora, R. Ge, R. Kannan, and A. Moitra. Computing a nonnegative matrix factorization provably. In STOC, 2012. –
[4] L. Balzano, R. Nowak, and B. Recht. Online identification and tracking of subspaces from highly incomplete information. In Proceedings of the Allerton Conference on Communication, 2010.
[5] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1): 1–122, 2011.
[6] S. Bucak and B. Gunsel. Incremental subspace learning via nonnegative matrix factorization. Pattern Recog., 42(5):788–797, 2009.
[7] D. Cai, X. He, and J. Han. Spectral regression for efficient regularized subspace learning. In ICCV, 2007.
[8] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? J. ACM, 58(3): 11, 2011.
[9] E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6):717– 772, 2009.
[10] X. Chen, Q. Lin, S. Kim, J. G. Carbonell, and E. P. Xing. Smoothing proximal gradient method for general structured sparse learning. In UAI, 2011.
[11] F. De La Torre and M. Black. A framework for robust subspace learning. IJCV, 54(1): 117–142, 2003.
[12] M. Everingham, J. Sivic, and A. Zisserman. “Hello! My name is Buffy” automatic naming of characters in TV video. In BMVC, 2006.
[13] P. Favaro, R. Vidal, and A. Ravichandran. A closed form solution to robust subspace estimation and clustering. In CVPR, 2011.
[14] J. Hamm and D. D. Lee. Grassmann discriminant analysis: a unifying view on subspace-based learning. In ICML, 2008.
[15] J. He, L. Balzano, and A. Szlam. Incremental gradient on the grassmannian for online foreground and background separation in subsampled video. In CVPR, 2012.
[16] J. Huang, X. Huang, and D. N. Metaxas. Learning with dynamic group sparsity. In ICCV, 2009.
[17] J. Huang and T. Zhang. The benefit of group sparsity. Annals of Statistics, 38: 1978–2004, 2010.
[18] A. Hyvärinen and E. Oja. Independent component analysis: algo–
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30] [3 1]
[32] rithms and applications. Neural Networks, 13(4):41 1–430, 2000. K. Jia, T.-H. Chan, and Y. Ma. Robust and practical face recognition via structured sparsity. In ECCV, 2012. S. Klein, J. P. W. Pluim, M. Staring, and M. A. Viergever. Adaptive stochastic gradient descent optimisation for image registration. IJCV, 81(3):227–239, 2009. Q. V. Le, W. Y. Zou, S. Y. Yeung, and A. Y. Ng. Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis. In CVPR, 2011. L. Li, W. Huang, I. Y. H. Gu, and Q. Tian. Statistical modeling of complex backgrounds for foreground object detection. TIP, 13(1 1): 1459–1472, 2004. S. Z. Li, X. Lu, X. Hou, X. Peng, and Q. Cheng. Learning multiview face subspaces and facial pose estimation using independent component analysis. TIP, 14(6):705–712, 2005. Z. Lin, M. Chen, L. Wu, and Y. Ma. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv, 1009.5055, 2010. J. Mairal, F. Bach, J. Ponce, and G. Sapiro. Online learning for matrix factorization and sparse coding. JMLR, 11:19–60, 2010. J. Mairal, R. Jenatton, G. Obozinski, and F. Bach. Convex and network flow optimization for structured sparsity. JMLR, 12:2681 2720, 2011. L. Mukherjee, V. Singh, J. Xu, and M. D. Collins. Analyzing the subspace structure of related images: Concurrent segmentation of image sets. In ECCV, 2012. J. Nocedal and S. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2006. Z. Qin and D. Goldfarb. Structured sparsity via alternating directions methods. JMLR, 13: 1373–1406, 2012. J. Sivic, M. Everingham, and A. Zisserman. “Who are you?” learning person specific classifiers from video. 2009. K. Toyama, J. Krumm, B. Brumitt, and B. Meyers. Wallflower: Principles and practice of background maintenance. In ICCV, 1999. P. Turaga, A. Veeraraghavan, and R. Chellappa. Statistical analysis on stiefel and grassmann manifolds with applications in computer –
[33]
[34]
[35]
[36]
[37]
[38]
[39] vision. In CVPR, 2008. M. A. Turk and A. P. Pentland. Face recognition using eigenfaces. In CVPR, pages 586–591, 1991. R. Vidal, Y. Ma, and S. Sastry. Generalized principal component analysis (GPCA). PAMI, 27(12): 1945–1959, 2005. P. A. Viola and M. J. Jones. Robust real-time face detection. IJCV, 57(2): 137–154, 2004. N. Wang, T. Yao, J. Wang, and D.-Y. Yeung. A probabilistic approach to robust matrix factorization. In ECCV, 2012. T. Wang, A. Backhouse, and I. Gu. Online subspace learning on grassmann manifold for moving object tracking in video. In Int. Conf. Acoustics, Speech, and Signal Processing, 2008. K. Yu, Y. Lin, and J. Lafferty. Learning image representations from the pixel level via hierarchical sparse coding. In CVPR, 2011. M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society, Series B, 68:49–67, 2006. 33337836