jmlr jmlr2013 jmlr2013-50 jmlr2013-50-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Eva L. Dyer, Aswin C. Sankaranarayanan, Richard G. Baraniuk
Abstract: Unions of subspaces provide a powerful generalization of single subspace models for collections of high-dimensional data; however, learning multiple subspaces from data is challenging due to the fact that segmentation—the identification of points that live in the same subspace—and subspace estimation must be performed simultaneously. Recently, sparse recovery methods were shown to provide a provable and robust strategy for exact feature selection (EFS)—recovering subsets of points from the ensemble that live in the same subspace. In parallel with recent studies of EFS with ℓ1 -minimization, in this paper, we develop sufficient conditions for EFS with a greedy method for sparse signal recovery known as orthogonal matching pursuit (OMP). Following our analysis, we provide an empirical study of feature selection strategies for signals living on unions of subspaces and characterize the gap between sparse recovery methods and nearest neighbor (NN)-based approaches. In particular, we demonstrate that sparse recovery methods provide significant advantages over NN methods and that the gap between the two approaches is particularly pronounced when the sampling of subspaces in the data set is sparse. Our results suggest that OMP may be employed to reliably recover exact feature sets in a number of regimes where NN approaches fail to reveal the subspace membership of points in the ensemble. Keywords: subspace clustering, unions of subspaces, hybrid linear models, sparse approximation, structured sparsity, nearest neighbors, low-rank approximation
M. Aharon, M. Elad, and A. Bruckstein. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Processing, 54(11):4311–4322, 2006. E. Arias-Castro, G. Chen, and G. Lerman. Spectral clustering based on local linear approximations. Electron. J. Stat., 5(0):217–240, 2011. R. G. Baraniuk, V. Cevher, M. Duarte, and C. Hegde. Model-based compressive sensing. IEEE Trans. Inform. Theory, 56(4):1982–2001, 2010. R. Basri and D. Jacobs. Lambertian reflectance and linear subspaces. IEEE Trans. Pattern Anal. Machine Intell., 25(2):218–233, February 2003. T. Blumensath and M. Davies. Sampling theorems for signals from the union of finite-dimensional linear subspaces. IEEE Trans. Inform. Theory, 55(4):1872–1882, 2009. G. Chen and G. Lerman. Spectral curvature clustering. Int. J. Computer Vision, 81:317–330, 2009. S. Chen, D. Donoho, and M. Saunders. Atomic decomposition by basis pursuit. SIAM J. Sci. Comp., 20(1):33–61, 1998. G. Davis, S. Mallat, and Z. Zhang. Adaptive time-frequency decompositions. SPIE J. Opt. Engin., 33(7):2183–2191, 1994. E. L. Dyer. Endogenous sparse recovery. Master’s thesis, Electrical & Computer Eng. Dept., Rice University, October 2011. E. L. Dyer, M. Duarte, D. J. Johnson, and R. G. Baraniuk. Recovering spikes from noisy neuronal calcium signals via structured sparse approximation. Proc. Int. Conf. on Latent Variable Analysis and Sig. Separation, pages 604–611, 2010. E. Elhamifar and R. Vidal. Sparse subspace clustering. In Proc. IEEE Conf. Comp. Vis. Patt. Recog. (CVPR), June 2009. E. Elhamifar and R. Vidal. Clustering disjoint subspaces via sparse representation. In Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing (ICASSP), pages 1926–1929, March 2010. 2515 DYER , S ANKARANARAYANAN AND BARANIUK E. Elhamifar and R. Vidal. Sparse subspace clustering: algorithm, theory, and applications. IEEE Trans. Pattern Anal. Machine Intell., 2013. A. S. Georghiades, P. N. Belhumeur, and D. J. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Machine Intell., 23(6):643–660, 2001. B. V. Gowreesunker, A. Tewfik, V. Tadipatri, J. Ashe, G. Pellize, and R. Gupta. A subspace approach to learning recurrent features from brain activity. IEEE Trans. Neur. Sys. Reh, 19(3):240–248, 2011. K. Kanatani. Motion segmentation by subspace separation and model selection. In Proc. IEEE Int. Conf. Comp. Vis. (ICCV), 2001. Y. Lu and M. Do. Sampling signals from a union of subspaces. IEEE Sig. Proc. Mag., 25(2):41–47, March 2008. B. Mailh` , S. Lesage, R. Gribonval, F. Bimbot, and P. Vandergheynst. Shift-invariant dictionary e learning for sparse representations: extending K-SVD. In Proc. Europ. Sig. Processing Conf. (EUSIPCO), 2008. B. Mailh` , D. Barchiesi, and M. D. Plumbley. INK-SVD: Learning incoherent dictionaries e for sparse representations. In Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing (ICASSP), pages 3573 –3576, March 2012. J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman. Discriminative learned dictionaries for local image analysis. In Proc. IEEE Conf. Comp. Vis. Patt. Recog. (CVPR), June 2008. A.Y. Ng, M.I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Proc. Adv. in Neural Processing Systems (NIPS), 2:849–856, 2002. B. Olshausen and D. Field. Sparse coding with an overcomplete basis set: a strategy employed by V1. Vision Res., 37:3311–3325, 1997. R. Ramamoorthi. Analytic PCA construction for theoretical analysis of lighting variability in images of a lambertian object. IEEE Trans. Pattern Anal. Machine Intell., 24(10):1322–1333, 2002. I. Ramirez, P. Sprechmann, and G. Sapiro. Classification and clustering via dictionary learning with structured incoherence and shared features. In Proc. IEEE Conf. Comp. Vis. Patt. Recog. (CVPR), pages 3501–3508, June 2010. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Machine Intell., 22(8):888–905, August 2000. M. Soltanolkotabi and E. J. Cand` s. A geometric analysis of subspace clustering with outliers. e Annals of Statistics, 40(4):2195–2238, 2012. M. Soltanolkotabi, E. Elhamifar, and E. J. Cand` s. e abs/1301.2603, 2013. 2516 Robust subspace clustering. CoRR, G REEDY F EATURE S ELECTION FOR S UBSPACE C LUSTERING J. A. Tropp. Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inform. Theory, 50(10):2231–2242, 2004. J. A. Tropp. Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inform. Theory, 52(3):1030 –1051, March 2006. R. Vidal. Subspace clustering. IEEE Sig. Proc. Mag., 28(2):52–68, 2011. R. Vidal, Y. Ma, and S. Sastry. Generalized principal component analysis (GPCA). IEEE Trans. Pattern Anal. Machine Intell., 27(12):1945–1959, 2005. Y. Wang and H. Xu. Noisy sparse subspace clustering. Proc. Int. Conf. Machine Learning, 2013. J. Yan and M. Pollefeys. A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In Proc. European Conf. Comp. Vision (ECCV), 2006. T. Zhang, A. Szlam, Y. Wang, and G. Lerman. Hybrid linear modeling via local best-fit flats. Int. J. Computer Vision, 100(3):217–240, 2012. 2517