×

Schubert varieties and distances between subspaces of different dimensions. (English) Zbl 1365.14065

Authors’ abstract: We resolve a basic problem on subspace distances that often arises in applications: How can the usual Grassmann distance between equidimensional subspaces be extended to subspaces of different dimensions? We show that a natural solution is given by the distance of a point to a Schubert variety within the Grassmannian. This distance reduces to the Grassmann distance when the subspaces are equidimensional and does not depend on any embedding into a larger ambient space. Furthermore, it has a concrete expression involving principal angles and is efficiently computable in numerically stable ways. Our results are largely independent of the Grassmann distance – if desired, it may be substituted by any other common distances between subspaces. Our approach depends on a concrete algebraic geometric view of the Grassmannian that parallels the differential geometric perspective that is well established in applied and computational mathematics.

MSC:

14M15 Grassmannians, Schubert varieties, flag manifolds
15A18 Eigenvalues, singular values, and eigenvectors
14N20 Configurations and arrangements of linear subspaces
51K99 Distance geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P.-A. Absil, R. Mahony, and R. Sepulchre, {\it Optimization Algorithms on Matrix Manifolds}, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, {\it Riemannian geometry of Grassmann manifolds with a view on algorithmic computation}, Acta Appl. Math., 80 (2004), pp. 199-220. · Zbl 1052.65048
[3] P.-A. Absil, R. Mahony, R. Sepulchre, and P. Van Dooren, {\it A Grassmann-Rayleigh quotient iteration for computing invariant subspaces}, SIAM Rev., 44 (2002), pp. 57-73, http://dx.doi.org/10.1137/S0036144500378648 doi:10.1137/S0036144500378648. · Zbl 0995.65037
[4] A. Ashikhmin and A. R. Calderbank, {\it Grassmannian packings from operator Reed-Muller codes}, IEEE Trans. Inform. Theory, 56 (2003), pp. 5689-5714. · Zbl 1366.94574
[5] H. Bagherinia and R. Manduchi, {\it A theory of color barcodes}, in Proceedings of the 14th International IEEE Conference on Computer Vision Workshops (ICCV), IEEE, 2011, pp. 806-813.
[6] L. Balzano, R. Nowak, and B. Recht, {\it Online identification and tracking of subspaces from highly incomplete information}, in Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, 2010, pp. 704-711.
[7] A. Barg and D. Yu. Nogin, {\it Bounds on packings of spheres in the Grassmannian manifold}, IEEE Trans. Inform. Theory, 48 (2002), pp. 2450-2454. · Zbl 1062.05034
[8] R. Basri, T. Hassner, and L. Zelnik-Manor, {\it Approximate nearest subspace search}, IEEE Trans. Pattern Anal. Mach. Intell., 33 (2011), pp. 266-278.
[9] C. A. Beattie, M. Embree, and D. C. Sorensen, {\it Convergence of polynomial restart Krylov methods for eigenvalue computations}, SIAM Rev., 47 (2005), pp. 492-515, http://dx.doi.org/10.1137/S0036144503433077 doi:10.1137/ S0036144503433077. · Zbl 1073.65028
[10] \AA. Björck and G. H. Golub, {\it Numerical methods for computing angles between linear subspaces}, Math. Comp., 27 (1973), pp. 579-594. · Zbl 0282.65031
[11] S.-C. T. Choi, {\it Minimal Residual Methods for Complex Symmetric, Skew Symmetric, and Skew Hermitian Systems}, preprint, Report ANL/MCS-P3028-0812, Computation Institute, University of Chicago, IL, 2013.
[12] J. H. Conway, R. H. Hardin, and N. J. A. Sloane, {\it Packing lines, planes, etc.: Packings in Grassmannian spaces}, Experiment. Math., 5 (1996), pp. 83-159. · Zbl 0864.51012
[13] N. P. Da Silva and J. P. Costeira, {\it The normalized subspace inclusion: Robust clustering of motion subspaces}, in Proceedings of the 12th IEEE International Conference on Computer Vision Workshops (ICCV), IEEE, 2009, pp. 1444-1450.
[14] M. M. Deza and E. Deza, {\it Encyclopedia of Distances}, 2nd ed., Springer, Heidelberg, 2013. · Zbl 1259.51001
[15] I. S. Dhillon, R. W. Heath, Jr., T. Strohmer, and J. A. Tropp, {\it Constructing packings in Grassmannian manifolds via alternating projection}, Experiment. Math., 17 (2008), pp. 9-35. · Zbl 1155.52304
[16] B. Draper, M. Kirby, J. Marks, T. Marrinan, and C. Peterson, {\it A flag representation for finite collections of subspaces of mixed dimensions}, Linear Algebra Appl., 451 (2014), pp. 15-32. · Zbl 1326.14118
[17] A. Edelman, T. A. Arias, and S. T. Smith, {\it The geometry of algorithms with orthogonality constraints}, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303-353, http://dx.doi.org/10.1137/S0895479895290954 doi:10.1137/ S0895479895290954. · Zbl 0928.65050
[18] N. Figueiredo, P. Georgieva, E. W. Lang, I. M. Santos, A. R. Teixeira, and A. M. Tomé, {\it SSA of biomedical signals: A linear invariant systems approach}, Stat. Interface, 3 (2010), pp. 345-355. · Zbl 1245.62112
[19] R. Fioresi and C. Hacon, {\it On infinite-dimensional Grassmannians and their quantum deformations}, Rend. Sem. Mat. Univ. Padova, 111 (2004), pp. 1-24. · Zbl 1167.14325
[20] G. H. Golub and C. Van Loan, {\it Matrix Computations}, 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[21] J. Hamm and D. D. Lee, {\it Grassmann discriminant analysis: A unifying view on subspace-based learning}, in Proceedings of the 25th International Conference on Machine Learning (ICML ’08), ACM, New York, 2008, pp. 376-383.
[22] T. F. Hansen and D. Houle, {\it Measuring and comparing evolvability and constraint in multivariate characters}, J. Evolution. Biol., 21 (2008), pp. 1201-1219.
[23] G. Haro, G. Randall, and G. Sapiro, {\it Stratification learning: Detecting mixed density and dimensionality in high dimensional point clouds}, in Advances in Neural Information Processing Systems (NIPS), Vol. 19, 2006, pp. 553-560.
[24] Q. He, F. Kong, and R. Yan, {\it Subspace-based gearbox condition monitoring by kernel principal component analysis}, Mech. Systems Signal Process., 21 (2007), pp. 1755-1772.
[25] A. Ya. Helemskii, {\it Lectures and Exercises on Functional Analysis}, Transl. Math. Monogr. 233, AMS, Providence, RI, 2006. · Zbl 1123.46001
[26] R. A. Horn and C. R. Johnson, {\it Topics in Matrix Analysis}, Cambridge University Press, Cambridge, UK, 1991. · Zbl 0729.15001
[27] D. Husemoller, {\it Fibre Bundles}, 3rd ed., Grad. Texts Math. 20, Springer, New York, 1994. · Zbl 0144.44804
[28] T. Kato, {\it Perturbation Theory for Linear Operators}, Classics Math., Springer-Verlag, Berlin, 1995. · Zbl 0836.47009
[29] A. V. Knyazev and M. E. Argentati, {\it Majorization for changes in angles between subspaces, Ritz values, and graph Laplacian spectra}, SIAM J. Matrix Anal. Appl., 29 (2006), pp. 15-32, http://dx.doi.org/10.1137/060649070 doi:10.1137/060649070. · Zbl 1196.15016
[30] G. Lerman and T. Zhang, {\it Robust recovery of multiple subspaces by geometric \(l_p\) minimization}, Ann. Statist., 39 (2011), pp. 2686-2715. · Zbl 1232.62097
[31] H. Li and A. Li, {\it Utilizing improved Bayesian algorithm to identify blog comment spam}, in Proceedings of the 2002 IEEE Symposium on Robotics and Applications (ISRA), IEEE, 2012, pp. 423-426.
[32] J. Liesen and Z. Strakoš, {\it Krylov Subspace Methods}, Oxford University Press, Oxford, 2013. · Zbl 1263.65034
[33] L.-H. Lim, K. S.-W. Wong, and K. Ye, {\it Statistical Estimation and the Grassmannian of Affine Subspaces}, preprint, https://arxiv.org/abs/1607.01833 arXiv:1607.01833 [stat.ME], 2016.
[34] D. J. Love, R. W. Heath, Jr., and T. Strohmer, {\it Grassmannian beamforming for multiple-input multiple-output wireless systems}, IEEE Trans. Inform. Theory, 49 (2003), pp. 2735-2747. · Zbl 1301.94080
[35] D. Luo and H. Huang, {\it Video motion segmentation using new adaptive manifold denoising model}, in Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, OH, 2014, pp. 65-72.
[36] Y. Ma, A. Y. Yang, H. Derksen, and R. Fossum, {\it Estimation of subspace arrangements with applications in modeling and segmenting mixed data}, SIAM Rev., 50 (2008), pp. 413-458, http://dx.doi.org/10.1137/060655523 doi:10.1137/060655523. · Zbl 1147.52010
[37] J. W. Milnor and J. D. Stasheff, {\it Characteristic Classes}, Ann. of Math. Stud. 76, Princeton University Press, Princeton, NJ, 1974. · Zbl 0298.57008
[38] L. I. Nicolaescu, {\it Lectures on the Geometry of Manifolds}, 2nd ed., World Scientific, Hackensack, NJ, 2007. · Zbl 1155.53001
[39] M. Peng, D. Bu, and Y. Wang, {\it The measure of income mobility in vector space}, Phys. Procedia, 3 (2010), pp. 1725-1732.
[40] E. Sharafuddin, N. Jiang, Y. Jin, and Z.-L. Zhang, {\it Know your enemy, know yourself: Block-level network behavior profiling and tracking}, in Proceedings of the 2010 IEEE Global Telecommunication Conference (GLOBECOM), IEEE, 2010, pp. 1-6.
[41] B. St. Thomas, L. Lin, L.-H. Lim, and S. Mukherjee, {\it Learning Subspaces of Different Dimensions}, preprint, http://arxiv.org/abs/1404.6841 arXiv:1404.6841v3 [math.ST], 2014.
[42] G. W. Stewart and J. Sun, {\it Matrix Perturbation Theory}, Academic Press, Boston, MA, 1990. · Zbl 0706.65013
[43] T. Strohmer and R. W. Heath, Jr., {\it Grassmannian frames with applications to coding and communication}, Appl. Comput. Harmon. Anal., 14 (2003), pp. 257-275. · Zbl 1028.42020
[44] X. Sun, L. Wang, and J. Feng, {\it Further results on the subspace distance}, Pattern Recognition, 40 (2007), pp. 328-329. · Zbl 1106.68402
[45] R. Vidal, Y. Ma, and S. Sastry, {\it Generalized principal component analysis}, IEEE Trans. Pattern Anal. Mach. Intell., 27 (2005), pp. 1945-1959.
[46] L. Wang, X. Wang, and J. Feng, {\it Subspace distance analysis with application to adaptive Bayesian algorithm for face recognition}, Pattern Recognition, 39 (2006), pp. 456-464. · Zbl 1158.68481
[47] R. Wang, S. Shan, X. Chen, and W. Gao, {\it Manifold-manifold distance with application to face recognition based on image set}, in Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, 2008, pp. 1-8.
[48] Y.-C. Wong, {\it Differential geometry of Grassmann manifolds}, Proc. Natl. Acad. Sci. USA, 57 (1967), pp. 589-594. · Zbl 0154.21404
[49] J. Yan and M. Pollefeys, {\it A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate}, in Proceedings of the 9th European Conference on Computer Vision (ECCV), Graz, Austria, 2006, pp. 94-106.
[50] L. Zheng and D. N. C. Tse, {\it Communication on the Grassmann manifold: A geometric approach to the noncoherent multiple-antenna channel}, IEEE Trans. Inform. Theory, 48 (2002), pp. 359-383. · Zbl 1071.94503
[51] G. Zuccon, L. A. Azzopardi, and C. J. van Rijsbergen, {\it Semantic spaces: Measuring the distance between different subspaces}, in Quantum Interaction, P. Bruza, D. Sofge, W. Lawless, K. van Rijsbergen, M. Klusch, eds., Lecture Notes in Artificial Intelligence 5494, Springer-Verlag, Berlin, 2009, pp. 225-236. · Zbl 1229.68073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.