The subspace segmentation problem is fundamental in many applications. The goal is to cluster data drawn from an unknown union of subspaces. In this paper we state the problem and describe its connection to other areas of mathematics and engineering. We then review the mathematical and algorithmic methods created to solve this problem and some of its particular cases. We also describe the problem of motion tracking in videos and its connection to the subspace segmentation problem and compare the various techniques for solving it. 1. Introduction The subspace clustering problem is fundamental in many engineering and mathematics applications [1–11]. It can be described as follows: let be the nonlinear set consisting of a union of subspaces of a Hilbert or a Banach space . Let be a set of data points drawn from . The subspace segmentation (or clustering) problem is then to determine (equivalently determine for ), from the data , that is, to(1)determine the number of subspaces ; (2)find an orthonormal basis for each subspace , ;(3)group the data points belonging to the same subspace into the same cluster. The data is often corrupted by noise; it may have outliers or some of the data vectors may have missing entries. Therefore, any technique for solving the subspace segmentation problem above must be robust and stable for the aforementioned nonideal cases. Depending on the application, the space can be finite or infinite dimensional. For example, the set of all two dimensional images of a given face , obtained under different illuminations and facial positions, can be modeled as a set of vectors belonging to a low dimensional subspace living in a higher dimensional space [12–14]. For this case, a set of such images from different faces is a union . Another application in which a union of subspaces provides a good model is the problem of motion tracking of rigid objects in videos. For this situation (further developed below), a 4-dimensional subspace is assigned to each moving object in a space , where is the number of frames in the video. Examples where is infinite dimensional arise in sampling theory, and in learning theory [15–19]. For example, signals with finite rate of innovations are modeled by a union of subspaces that belongs to an infinite dimensional space such as [2, 3, 20, 21]. 1.1. Known Number of Subspaces and Dimensions In some subspace segmentation problems, the number of subspaces or the dimensions of the subspaces are known or can be estimated [1, 8, 22, 23]. In these cases, the subspace segmentation problem, for both the finite and
References
[1]
A. Aldroubi and A. Sekmen, “Nearness to local subspace algorithm for subspace and motion segmentation,” IEEE Signal Processing Letters, vol. 19, no. 10, Article ID 6275471, pp. 704–707, 2012.
[2]
A. Aldroubi, C. Cabrelli, and U. Molter, “Optimal non-linear models for sparsity and sampling,” Journal of Fourier Analysis and Applications, vol. 14, no. 5-6, pp. 793–812, 2008.
[3]
Y. Ma, A. Y. Yang, H. Derksen, and R. M. Fossum, “Estimation of subspace arrangements with applications in modeling and segmenting mixed data,” SIAM Review, vol. 50, no. 3, pp. 413–458, 2008.
[4]
H.-P. Kriegel, P. Kroeger, and A. Zimek, “Subspace clustering,” WIREs Data Mining and Knowledge Discovery, vol. 2, pp. 351–364, 2012.
[5]
S. Nitzan and A. Olevskii, “Revisiting Landau's density theorems for Paley-Wiener spaces,” Comptes Rendus Mathématique, vol. 350, no. 9-10, pp. 509–512, 2012.
[6]
R. Vidal, Y. Ma, and S. Sastry, “Generalized principal component analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 12, pp. 1–15, 2005.
[7]
G. Chen, A. V. Little, M. Maggioni, and L. Rosasco, “Some recent advances in multiscale geometric analysis of point clouds,” in Wavelets and Multiscale Analysis, J. Cohen and A. I. Zayed, Eds., pp. 199–225, Birkh？user, Boston, Mass, USA, 2011.
[8]
R. Vidal, “Subspace clustering,” IEEE Signal Processing Magazine, vol. 28, no. 3, pp. 52–68, 2011.
[9]
Y. Lyubarskii and W. R. Madych, “Interpolation of functions from generalized Paley-Wiener spaces,” Journal of Approximation Theory, vol. 133, no. 2, pp. 251–268, 2005.
[10]
Y. Sugaya and K. Kanatani, “Improved multistage learning for multibody segmentation, in,” in Proceedings of the 5th International Conference on Computer Vision Theory and Applications (VISAPP '10), pp. 199–206, 2010.
[11]
R. Hu, L. Fan, and L. Liu, “Co-segmentation of 3d shapes via subspace clustering,” Computer Graphics Forum, vol. 31, pp. 1703–1713, 2012.
[12]
R. Vidal, Y. Ma, and S. Sastry, “Generalized principal component analysis (GPCA),” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, pp. 1945–1959, 2005.
[13]
R. Basri and D. W. Jacobs, “Lambertian reflectance and linear subspaces,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 2, pp. 218–233, 2003.
[14]
J. Ho, M. H. Yang, J. Lim, K. C. Lee, and D. Kriegman, “Clustering appearances of objects under varying illumination conditions,” in Proceedings of the Computer Society Conference on Computer Vision and Pattern Recognition, pp. I/11–I/18, June 2003.
[15]
A. Aldroubi and K. Gr？chenig, “Nonuniform sampling and reconstruction in shift-invariant spaces,” SIAM Review, vol. 43, no. 4, pp. 585–620, 2001.
[16]
W. K. Allard, G. Chen, and M. Maggioni, “Multi-scale geometric methods for data sets II: geometric multi-resolution analysis,” Applied and Computational Harmonic Analysis, vol. 32, no. 3, pp. 435–462, 2012.
[17]
M. Soltanolkotabi and E. J. Candés, “A geometric analysis of subspace clustering with outliers,” Annals of Statistics, vol. 40, no. 4, pp. 2195–2238, 2012.
[18]
Y. Sugaya and K. Kanatani, “Multi-stage optimization for multi-body motion segmentation,” in Proceedings of IEICE Transactions on Information and Systems, pp. 1935–1942, 2004.
[19]
A. D. Szlam, M. Maggioni, and R. R. Coifman, “Regularization on graphs with function-adapted diffusion processes,” Journal of Machine Learning Research, vol. 9, pp. 1711–1739, 2008.
[20]
A. Aldroubi and R. Tessera, “On the existence of optimal unions of subspaces for data modeling and clustering,” Foundations of Computational Mathematics, vol. 11, no. 3, pp. 363–379, 2011.
[21]
M. Petrik, “An analysis of laplacian methods for value function approximation in mdps,” in Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. Morgan Kaufmann–2574, 2007.
[22]
A. Aldroubi and A. Sekmen, “Reduced row echelon form and non-linear approximation for subspace segmentation and high-dimensional data clustering,” submitted to Applied and Computational Harmonic Analysis.
[23]
R. Tron and R. Vidal, “A benchmark for the comparison of 3-D motion segmentation algorithms,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '07), June 2007.
[24]
C. Eckart and G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika, vol. 1, no. 3, pp. 211–218, 1936.
[25]
M. Unser, A. Aldroubi, and M. Eden, “B-spline signal processing. Part I. Theory,” IEEE Transactions on Signal Processing, vol. 41, no. 2, pp. 821–833, 1993.
[26]
M. Unser, A. Aldroubi, and M. Eden, “B-spline signal processing. Part II. Efficient design and applications,” IEEE Transactions on Signal Processing, vol. 41, no. 2, pp. 834–848, 1993.
[27]
G. Chen and G. Lerman, “Foundations of a multi-way spectral clustering framework for Hybrid Linear Modeling,” Foundations of Computational Mathematics, vol. 9, no. 5, pp. 517–558, 2009.
[28]
G. Liu, Z. Lin, and Y. Yu, “Robust subspace segmentation by low-rank representation,” in Proceedings of 27th International Conference on Machine Learning (ICML '10), pp. 663–670, June 2010.
[29]
F. De La Torre and M. J. Black, “A framework for robust subspace learning,” International Journal of Computer Vision, vol. 54, no. 1–3, pp. 117–142, 2003.
[30]
E. Candès and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Problems, vol. 23, no. 3, pp. 969–985, 2007.
[31]
G. Haro, G. Randall, and G. Sapiro, “Translated poisson mixture model for stratification learning,” International Journal of Computer Vision, vol. 80, no. 3, pp. 358–374, 2008.
[32]
Y. C. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Transactions on Information Theory, vol. 55, no. 11, pp. 5302–5316, 2009.
[33]
S. Kang and K. H. Kwon, “Recovery of missing samples for oversampling in shift invariant spaces,” Journal of Mathematical Analysis and Applications, vol. 391, no. 1, pp. 139–146, 2012.
[34]
J. Yan and M. Pollefeys, “A general framework for motion segmentation: independent, articulated, rigid, non-rigid, degenerate and nondegenerate,” in Proceedings of the 9th European Conference on Computer Vision, pp. 94–106, 2006.
[35]
S. R. Rao, A. Y. Yang, S. S. Sastry, and Y. Ma, “Robust algebraic segmentation of mixed rigid-body and planar motions from two views,” International Journal of Computer Vision, vol. 88, no. 3, pp. 425–446, 2010.
[36]
T. Lin and H. Zha, “Riemannian manifold learning,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, pp. 796–809, 2008.
[37]
C. Bregler, A. Hertzmann, and H. Biermann, “Recovering non-rigid 3D shape from image streams,” in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR '00), pp. 690–696, June 2000.
[38]
M. Brand, “Morphable 3D models from video,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. II456–II463, December 2001.
[39]
E. J. Candès, “The restricted isometry property and its implications for compressed sensing,” Comptes Rendus Mathématique, vol. 346, no. 9-10, pp. 589–592, 2008.
[40]
E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 489–509, 2006.
[41]
S. Foucart, “A note on guaranteed sparse recovery via ？1-minimization,” Applied and Computational Harmonic Analysis, vol. 29, no. 1, pp. 97–103, 2010.
[42]
P. Boufounos, G. Kutyniok, and H. Rauhut, “Sparse recovery from combined fusion frame measurements,” IEEE Transactions on Information Theory, vol. 57, no. 6, pp. 3864–3876, 2011.
[43]
A. Aldroubi, X. Chen, and A. M. Powell, “Perturbations of measurement matrices and dictionaries in compressed sensing,” Applied and Computational Harmonic Analysis, vol. 33, no. 2, pp. 282–291, 2012.
[44]
Q. Sun, “Recovery of sparsest signals via l(q)-minimization,” Applied and Computational Harmonic Analysis, vol. 32, no. 3, pp. 329–341, 2012.
[45]
M. Aharon, M. Elad, and A. Bruckstein, “K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation,” IEEE Transactions on Signal Processing, vol. 54, no. 11, pp. 4311–4322, 2006.
[46]
M. Aharon, M. Elad, and A. M. Bruckstein, “On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them,” Linear Algebra and Its Applications, vol. 416, no. 1, pp. 48–67, 2006.
[47]
G. Lerman and T. Zhang, “Robust recovery of multiple subspaces by geometric minimization,” The Annals of Statistics, vol. 39, no. 5, pp. 2686–2715, 2011.
[48]
C. Archambeau, N. Delannay, and M. Verleysen, “Mixtures of robust probabilistic principal component analyzers,” Neurocomputing, vol. 71, no. 7-9, pp. 1274–1282, 2008.
[49]
Y. M. Lu and M. N. Do, “A theory for sampling signals from a union of subspaces,” IEEE Transactions on Signal Processing, vol. 56, no. 6, pp. 2334–2345, 2008.
[50]
P. W. Jones, M. Maggioni, and R. Schul, “Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels,” Proceedings of the National Academy of Sciences of the United States of America, vol. 105, no. 6, pp. 1803–1808, 2008.
[51]
Q. Wu, J. Guinney, M. Maggioni, and S. Mukherjee, “Learning gradients: predictive models that infer geometry and statistical dependence,” Journal of Machine Learning Research, vol. 11, pp. 2175–2198, 2010.
[52]
J. Zhang, H. Huang, and J. Wang, “Manifold learning for visualizing and analyzing high-dimensional data,” IEEE Intelligent Systems, vol. 25, no. 4, Article ID 5401149, pp. 54–61, 2010.
[53]
F. Lauer and C. Schnorr, “Spectral clustering of linear subspaces for motion segmentation,” in Proceedings of IEEE International Conference on Computer Vision, 2009.
[54]
A. Aldroubi and M. Unser, “Sampling procedures in function spaces and asymptotic equivalence with Shannon's sampling theory,” Numerical Functional Analysis and Optimization, vol. 15, no. 1-2, pp. 1–21, 1994.
[55]
M. Unser, “Sampling—50 years after Shannon,” Proceedings of the IEEE, vol. 88, no. 4, pp. 569–587, 2000.
[56]
A. Aldroubi, “Non-uniform weighted average sampling and reconstruction in shift-invariant and wavelet spaces,” Applied and Computational Harmonic Analysis, vol. 13, no. 2, pp. 151–161, 2002.
[57]
M. Anastasio and C. Cabrelli, “Sampling in a union of frame generated subspaces,” Sampling Theory in Signal and Image Processing, vol. 8, no. 3, pp. 261–286, 2009.
[58]
J. Xian and W. Sun, “Local sampling and reconstruction in shift-invariant spaces and their applications in spline subspaces,” Numerical Functional Analysis and Optimization, vol. 31, no. 3, pp. 366–386, 2010.
[59]
A. Bhandari and A. I. Zayed, “Shift-invariant and sampling spaces associated with the fractional Fourier transform domain,” IEEE Transactions on Signal Processing, vol. 60, no. 4, pp. 1627–1637, 2012.
[60]
D. Kushnir, M. Galun, and A. Brandt, “Fast multiscale clustering and manifold identification,” Pattern Recognition, vol. 39, no. 10, pp. 1876–1891, 2006.
[61]
S. Ericsson, “Generalized sampling in shift invariant spaces with frames,” Acta Mathematica Sinica, vol. 28, no. 9, pp. 1823–1844, 2012.
[62]
I. Maravi？ and M. Vetterli, “Sampling and reconstruction of signals with finite rate of innovation in the presence of noise,” IEEE Transactions on Signal Processing, vol. 53, no. 8, pp. 2788–2805, 2005.
[63]
J. A. Hogan, “Frame-based nonuniform sampling in Paley-Wiener spaces,” Journal of Applied Functional Analysis, vol. 2, no. 4, pp. 361–400, 2007.
[64]
H. Boche and U. J. M？nich, “There exists no globally uniformly convergent reconstruction for the Paley-Wiener space of bandlimited functions sampled at Nyquist rate,” IEEE Transactions on Signal Processing, vol. 56, no. 7, pp. 3170–3179, 2008.
[65]
H. Boche and U. J. M？nich, “Unboundedness of thresholding and quantization for bandlimited signals,” Signal Processing, vol. 92, no. 12, pp. 2821–2829, 2012.
[66]
S. Rao, R. Tron, R. Vidal, and Y. Ma, “Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 10, pp. 1832–1845, 2010.
[67]
B. A. Bailey, “Multivariate polynomial interpolation and sampling in Paley-Wiener spaces,” Journal of Approximation Theory, vol. 164, no. 4, pp. 460–487, 2012.
[68]
A. Aldroubi, C. Cabrelli, D. Hardin, and U. Molter, “Optimal shift invariant spaces and their Parseval frame generators,” Applied and Computational Harmonic Analysis, vol. 23, no. 2, pp. 273–283, 2007.
[69]
M. Vetterli, P. Marziliano, and T. Blu, “Sampling signals with finite rate of innovation,” IEEE Transactions on Signal Processing, vol. 50, no. 6, pp. 1417–1428, 2002.
[70]
P. L. Dragotti, M. Vetterli, and T. Blu, “Sampling moments and reconstructing signals of finite rate of innovation: shannon meets strang-fix,” IEEE Transactions on Signal Processing, vol. 55, no. 5, pp. 1741–1757, 2007.
[71]
V. Y. F. Tan and V. K. Goyal, “Estimating signals with finite rate of innovation from noisy samples: a stochastic algorithm,” IEEE Transactions on Signal Processing, vol. 56, no. 10, pp. 5135–5146, 2008.
[72]
N. Bi, M. Z. Nashed, and Q. Sun, “Reconstructing signals with finite rate of innovation from noisy samples,” Acta Applicandae Mathematicae, vol. 107, no. 1–3, pp. 339–372, 2009.
[73]
J. Berent, P. L. Dragotti, and T. Blu, “Sampling piecewise sinusoidal signals with finite rate of innovation methods,” IEEE Transactions on Signal Processing, vol. 58, no. 2, pp. 613–625, 2010.
[74]
T. Kanade and D. D. Morris, “Factorization methods for structure from motion,” The Royal Society of London. Philosophical Transactions A, vol. 356, no. 1740, pp. 1153–1173, 1998.
[75]
J. P. Costeira and T. Kanade, “A multibody factorization method for independently moving objects,” International Journal of Computer Vision, vol. 29, no. 3, pp. 159–179, 1998.
[76]
P. H. S. Torr, “Geometric motion segmentation and model selection,” The Royal Society of London. Philosophical Transactions A, vol. 356, no. 1740, pp. 1321–1340, 1998.
[77]
A. Goh and R. Vidal, “Segmenting motions of different types by unsupervised manifold clustering,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '07), vol. 6, June 2007.
[78]
S. Smale and D. X. Zhou, “Shannon sampling II: connections to learning theory,” Applied and Computational Harmonic Analysis, vol. 19, no. 3, pp. 285–302, 2005.
[79]
W. Johnson and J. Linderstrauss, “Extensions of lipshitz mapping into hilbert space,” Contemporary Mathematics, vol. 26, pp. 189–206, 1984.
[80]
D. Achlioptas, “Database-friendly random projections: Johnson-Lindenstrauss with binary coins,” Journal of Computer and System Sciences, vol. 66, no. 4, pp. 671–687, 2003.
[81]
N. Silva and J. Costeira, “Subspace segmentation with outliers: a grassmannian approach to the maximum consensus subspace,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2008.
[82]
R. I. Arriaga and S. Vempala, “Algorithm theory of learning: robust concepts and random projection,” in Proceedings of IEEE 40th Annual Conference on Foundations of Computer Science, pp. 616–623, October 1999.
[83]
A. Aldroubi, M. Anastasio, C. Cabrelli, and U. Molter, “A dimension reduction scheme for the computation of optimal unions of subspaces,” Sampling Theory in Signal and Image Processing, vol. 10, no. 1-2, pp. 135–150, 2011.
[84]
C. W. Gear, “Multibody grouping from motion images,” International Journal of Computer Vision, vol. 29, no. 2, pp. 133–150, 1998.
[85]
R. Vidal, R. Tron, and R. Hartley, “Multiframe motion segmentation with missing data using PowerFactorization and GPCA,” International Journal of Computer Vision, vol. 79, no. 1, pp. 85–105, 2008.
[86]
P. Tseng, “Nearest q-flat to m points,” Journal of Optimization Theory and Applications, vol. 105, no. 1, pp. 249–252, 2000.
[87]
P. S. Bradley and O. L. Mangasarian, “k-plane clustering,” Journal of Global Optimization, vol. 16, no. 1, pp. 23–32, 2000.
[88]
E. Elhamifar and R. Vidal, “Sparse subspace clustering,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPR '09), pp. 2790–2797, June 2009.
[89]
E. Elhamifar and R. Vidal, “Clustering disjoint subspaces via sparse representation,” in Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP '10), pp. 1926–1929, March 2010.
[90]
E. Elhamifar and R. Vidal, “Sparse subspace clustering: algorithm, theory, and applications,” http://arxiv.org/abs/1203.1005.
[91]
A. Sekmen, Susbpace Segmentation, Vanderbilt, 2012.
[92]
O. Faugeras, P. Torr, T. Kanade et al., “Geometric motion segmentation andmodel selection—discussion,” Philosophical Transactions of the Royal Society A, vol. 356, pp. 1338–1340, 1998.
[93]
A. Gruber and Y. Weiss, “Multibody factorization with uncertainty and missing data using the EM algorithm,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '04), pp. I707–I714, July 2004.
[94]
L. Candillier, I. Tellier, F. Torre, and O. Bousquet, “SSC: statistical subspace clustering,” in 5mes Journes d’Extraction et Gestion des Connaissances (EGC '05), pp. 177–182, Paris, France, 2005.
[95]
S. Smale and D.-X. Zhou, “Learning theory estimates via integral operators and their approximations,” Constructive Approximation, vol. 26, no. 2, pp. 153–172, 2007.
[96]
G. Chen, S. Atev, and G. Lerman, “Kernel spectral curvature clustering (KSCC),” in Proceedings of IEEE 12th International Conference on Computer Vision Workshops (ICCV '09), pp. 765–772, October 2009.
[97]
T. Zhang, A. Szlam, Y. Wang, and G. Lerman, “Randomized hybrid linear modeling by local best-fit flats,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '10), pp. 1927–1934, June 2010.
[98]
L. Zappella, X. Lladó, E. Provenzi, and J. Salvi, “Enhanced Local Subspace Affinity for feature-based motion segmentation,” Pattern Recognition, vol. 44, no. 2, pp. 454–470, 2011.
[99]
M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, pp. 381–395, 1981.
[100]
T. Sarlós, “Improved approximation algorithms for large matrices via random projections,” in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS '06), pp. 143–152, October 2006.
