iccv iccv2013 iccv2013-122 iccv2013-122-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ameet Talwalkar, Lester Mackey, Yadong Mu, Shih-Fu Chang, Michael I. Jordan
Abstract: Vision problems ranging from image clustering to motion segmentation to semi-supervised learning can naturally be framed as subspace segmentation problems, in which one aims to recover multiple low-dimensional subspaces from noisy and corrupted input data. Low-Rank Representation (LRR), a convex formulation of the subspace segmentation problem, is provably and empirically accurate on small problems but does not scale to the massive sizes of modern vision datasets. Moreover, past work aimed at scaling up low-rank matrix factorization is not applicable to LRR given its non-decomposable constraints. In this work, we propose a novel divide-and-conquer algorithm for large-scale subspace segmentation that can cope with LRR ’s non-decomposable constraints and maintains LRR ’s strong recovery guarantees. This has immediate implications for the scalability of subspace segmentation, which we demonstrate on a benchmark face recognition dataset and in simulations. We then introduce novel applications of LRR-based subspace segmentation to large-scale semisupervised learning for multimedia event detection, concept detection, and image tagging. In each case, we obtain stateof-the-art results and order-of-magnitude speed ups.
[1] A. Adler, M. Elad, and Y. Hel-Or. Probabilistic subspace clustering via sparse representations. IEEE Signal Process. Lett., 20(1):63–66, 2013. 8
[2] R. Basri and D. Jacobs. Robust face recognition via sparse representation. IEEE Trans. Pattern Anal. Mach. Intell., 25(3):218–233, 2003. 1
[3] E. J. Cand e`s, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM, 58(3): 1–37, 2011. 5
[4] B. Cheng, G. Liu, J. Wang, Z. Huang, and S. Yan. Multi-task low-rank affinity pursuit for image segmentation. In ICCV,
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15] 2011. 2 B. Cheng, J. Yang, S. Yan, Y. Fu, and T. S. Huang. Learning with l1-graph for image analysis. IEEE Transactions on Image Processing, 19(4):858–866, 2010. 6 J. Costeira and T. Kanade. A multibody factorization method for independently moving objects. International Journal of Computer Vision, 29(3), 1998. 1 E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 2009. 1 B. R. Feng Niu, C. R e´, and S. J. Wright. Hogwild!: A lockfree approach to parallelizing stochastic gradient descent. In NIPS, 2011. 1 S. Gao, I. W. H. Tsang, L. T. Chia, and P. Zhao. Local features are not lonely - laplacian sparse coding for image classification. In CVPR, 2010. 6 C. W. Gear. Multibody grouping from motion images. Int. J. Comput. Vision, 29: 133–150, August 1998. 1, 2 R. Gemulla, E. Nijkamp, P. J. Haas, and Y. Sismanis. Largescale matrix factorization with distributed stochastic gradient descent. In KDD, 2011. 1 T. Hastie and P. Simard. Metrics and models for handwritten character recognition. Statistical Science, 13(1):54–65, 1998. 1 R. He, W.-S. Zheng, B.-G. Hu, and X.-W. Kong. Nonnegative sparse coding for discriminative semi-supervised learning. In CVPR, 2011. 6 W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301): 13–30, 1963. 10 S. Kumar, M. Mohri, and A. Talwalkar. On sampling-based approximate spectral decomposition. In ICML, 2009. 3
[16] Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. UIUC Technical Report UILUENG-09-2214, 2009. 7
[17] G. Liu, Z. Lin, and Y. Yu. Robust subspace segmentation by low-rank representation. In ICML, 2010. 1, 2, 4, 5
[18] G. Liu, H. Xu, and S. Yan. Exact subspace segmentation and outlier detection by low-rank representation. arXiv : 110 9 . 16 4 6v2 [ cs . I ] , 2011. 1, 2, 3, 4, 5, 9, 10, 11 T
[19] G. Liu and S. Yan. Latent low-rank representation for subspace segmentation and feature extraction. In ICCV, 2011. 1
[20] G. Liu and S. Yan. Active subspace: Toward scalable lowrank learning. Neural Computation, 24:3371–3394, 2012. 8
[21] L. Mackey, A. Talwalkar, and M. I. Jordan. Divide-andconquer matrix factorization. In NIPS, 2011. 1, 2, 3, 4, 9
[22] B. Recht. A simpler approach to matrix completion. arXiv : 0 9 10 . 0 6 5 1v2 [ c s . I ] , 2009. 3 T
[23] B. Recht and C. R e´. Parallel stochastic gradient algorithms for large-scale matrix completion. In Optimization Online, 2011. 1
[24] C. Tomasi and T. Kanade. Shape and motion from image streams under orthography. International Journal of Computer Vision, 9(2):137–154, 1992. 1
[25] L. Torresani, M. Szummer, and A. W. Fitzgibbon. Efficient object category recognition using classemes. In ECCV, 2010. 6
[26] R. Vidal, Y. Ma, and S. Sastry. Generalized principal component analysis (gpca). IEEE Trans. Pattern Anal. Mach. Intell., 27(12): 1–15, 2005. 1
[27] F. Wang and C. Zhang. Label propagation through linear neighborhoods. In ICML, 2006. 6, 7
[28] J. Wang, F. Wang, C. Zhang, H. C. Shen, and L. Quan. Linear neighborhood propagation and its applications. IEEE Trans. Pattern Anal. Mach. Intell., 31(9): 1600–1615, 2009. 6
[29] J. Wright, A. Y. Yang, A. Ganesh, S. S. Sastry, and Y. Ma. Robust face recognition via sparse representation. IEEE Trans. Pattern Anal. Mach. Intell., 31(2):210–227, 2009. 6
[30] A. Yang, J. Wright, Y. Ma, and S. Sastry. Unsupervised segmentation of natural images via lossy data compression. Computer Vision and Image Understanding, 110(2):212– 225, 2008. 1
[31] H.-F. Yu, C.-J. Hsieh, S. Si, and I. Dhillon. Scalable coordinate descent approaches to parallel matrix factorization for recommender systems. In ICDM, 2012. 1
[32] L. Zhuang, H. Gao, Z. Lin, Y. Ma, X. Zhang, and N. Yu. Non-negative low rank and sparse graph for semi-supervised learning. In CVPR, 2012. 1, 2, 6, 7 33554503