iccv iccv2013 iccv2013-134 iccv2013-134-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Suraj Jain, Venu Madhav Govindu
Abstract: The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. In this paper we present our approach of Sparse Grassmann Clustering (SGC) that combines attributes of both categories. While we decompose the higherorder similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. We demonstrate the performance of our SGC method on a variety of segmentation problems including planar seg- mentation of Kinect depth maps and motion segmentation of the Hopkins 155 dataset for which we achieve performance comparable to the state-of-the-art.
[1] S. Agarwal, J. Lim, L. Zelnik Manor, P. Perona, D. Kriegman, andS. Belongie. Beyondpairwiseclustering. InCVPR, 2005.
[2] L. Balzano, R. Nowak, and B. Recht. Online identification and tracking of subspaces from highly incomplete information. In Proceedings of Allerton Conference on Communication, Control and Computing, 2010.
[3] G. Chen and G. Lerman. Spectral curvature clustering (scc). IJCV, 81(3), March 2009. IJCV,
[4] Y. Chikuse. Statistics on Special Manifolds. Springer, 2003.
[5] A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM Journal on Matrix Analysis and Applications, 20(2), 1998.
[6] E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm, theory, and applications. PAMI, 35(11), 2013.
[7] P. Favaro, R. Vidal, and A. Ravichandran. A closed form solution to robust subspace estimation and clustering. CVPR, 2011. In CVPR,
[8] V. M. Govindu. A tensor decomposition for geometric grouping and segmentation. In CVPR, 2005.
[9] J. He, L. Balzano, and A. Szlam. Incremental gradient on the grassmannian for online foreground and background separation in subsampled video. In CVPR, 2012.
[10] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. J. Mach. Learn. Res., Aug 2010.
[11] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma. Robust recovery of subspace structures by low-rank representation. PAMI, 35(1), 2013. PAMI,
[12] U. Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4), December 2007.
[13] A. Shashua, R. Zass, and T. Hazan. Multi-way clustering using super-symmetric non-negative tensor factorization. In ECCV, 2006. ECCV,
[14] R. Tron and R. Vidal. A benchmark for the comparison of 3-d motion segmentation algorithms. In CVPR, 2007.
[15] P. Turaga, A. Veeraraghavan, A. Srivastava, and R. Chellappa. Statistical computations on grassmann and stiefel manifolds for image and video-based recognition. PAMI, 33(1 1), November 2011.
[16] R. Vidal. Subspace clustering. IEEE Signal Processing Magazine, May 2011.
[17] Y. Weiss. Segmentation using eigenvectors: A unifying view. In ICCV, 1999.
[18] J. Yan and M. Pollefeys. A general framework for motion segmentation: independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In ECCV, 2006. 3355 11 81