[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

GrassCaré: Visualizing the Grassmannian on the Poincaré Disk

Published: 28 February 2024 Publication History

Abstract

This paper introduces a novel method for visualizing high-dimensional Grassmannians through 2D embeddings on the Poincaré disk. The proposed approach involves the construction of affinity matrices on each manifold, followed by the minimization of KL-divergence between the geodesics affinity. This process enables the identification of an optimal projection that effectively preserves the geometry of the original high-dimensional Grassmannian. Our main theoretical contribution lies in bounding the embedding loss with respect to two factors: the logarithm of the number of subspaces and a term dependent on the distribution of subspaces within the Grassmannian. Notably, this term is smaller when subspaces exhibit well-defined clusters, and larger in the absence of any discernible structure. We complement our theoretical analysis with comprehensive experiments on both synthetic and real datasets. The experimental results showcase the superiority of our embedding in accurately visualizing Grassmannians compared to existing representations.

References

[1]
Knudsen T Consistency analysis of subspace identification methods based on a linear regression approach Automatica. 2001 37 1 81-9
[2]
Jansson M and Wahlberg B A linear regression approach to state-space subspace system identification Signal Process. 1996 52 2 103-29
[3]
Vaswani N, Bouwmans T, Javed S, and Narayanamurthy P Robust subspace learning: robust PCA, robust subspace tracking, and robust subspace recovery IEEE Signal Process Mag. 2018 35 4 32-55
[4]
Dai W, Milenkovic O, and Kerman E Subspace evolution and transfer (set) for low-rank matrix completion IEEE Trans Signal Process. 2011 59 7 3120-32
[5]
Vidal R and Favaro P Low rank subspace clustering (LRSC) Pattern Recogn Lett. 2014 43 47-61
[6]
Cao J, Zhang K, Luo M, Yin C, and Lai X Extreme learning machine and adaptive sparse representation for image classification Neural Netw. 2016 81 91-102
[7]
Chen G and Lerman G Spectral curvature clustering (SCC) Int J Comput Vis. 2009 81 3 317-30
[8]
Hong W, Wright J, Huang K, and Ma Y Multiscale hybrid linear models for lossy image representation IEEE Trans Image Process. 2006 15 12 3655-71
[9]
Lu L, Vidal R. Combined central and subspace clustering for computer vision applications; 2006. p. 593–600.
[10]
Koohi H and Kiani K A new method to find neighbor users that improves the performance of collaborative filtering Expert Syst Appl. 2017 83 30-9
[11]
Ullah F, Sarwar G, and Lee S N-screen aware multicriteria hybrid recommender system using weight based subspace clustering Sci World J. 2014 2014 1-10
[12]
Zhang W, Wang Q, Yoshida T, and Li J RP-LGMC: rating prediction based on local and global information with matrix clustering Comput Oper Res. 2021 129 105228
[13]
Sun W, Zhang L, Du B, Li W, and Lai YM Band selection using improved sparse subspace clustering for hyperspectral imagery classification IEEE J Sel Top Appl Earth Observ Remote Sens. 2015 8 6 2784-97
[14]
Ahmed MS, Khan L. SISC: a text classification approach using semi supervised subspace clustering. In: 2009 IEEE international conference on data mining workshops. IEEE; 2009. p. 1–6.
[15]
Xia C-Q, Han K, Qi Y, Zhang Y, and Yu D-J A self-training subspace clustering algorithm under low-rank representation for cancer classification on gene expression data IEEE/ACM Trans Comput Biol Bioinform. 2017 15 4 1315-24
[16]
Mevel L, Hermans L, and Auweraer H Application of a subspace-based fault detection method to industrial structures Mech Syst Signal Process. 1999 13 6 823-38
[17]
Goodman-Strauss C Compass and straightedge in the poincaré disk Am Math Monthly. 2001 108 1 38-49
[18]
Parsons L, Haque E, and Liu H Subspace clustering for high dimensional data: a review ACM SIGKDD Explor Newsl. 2004 6 1 90-105
[19]
Yang AY, Wright J, Ma Y, and Sastry SS Unsupervised segmentation of natural images via lossy data compression Comput Vis Image Understand. 2008 110 2 212-25
[20]
Vidal R, Tron R, and Hartley R Multiframe motion segmentation with missing data using powerfactorization and GPCA Int J Comput Vis. 2008 79 1 85-105
[21]
Elhamifar E and Vidal R Sparse subspace clustering: algorithm, theory, and applications IEEE Trans Pattern Anal Mach Intell. 2013 35 11 2765-81
[22]
Agrawal R, Gehrke J, Gunopulos D, Raghavan P. Automatic subspace clustering of high dimensional data for data mining applications. In: Proceedings of the 1998 ACM SIGMOD international conference on management of data; 1998. p. 94–105.
[23]
Bahadori MT, Kale D, Fan Y, Liu Y. Functional subspace clustering with application to time series. In: International conference on machine learning. PMLR; 2015. p. 228–237.
[24]
Recht B A simpler approach to matrix completion J Mach Learn Res. 2011 12 12 3413-3430
[25]
Kang Z, Peng C, Cheng Q. Top-n recommender system via matrix completion. In: Proceedings of the AAAI conference on artificial intelligence, vol. 30; 2016.
[26]
Ji H, Liu C, Shen Z, Xu Y, Robust video denoising using low rank matrix completion. In: 2010 IEEE computer society conference on computer vision and pattern recognition. IEEE; 2010. p. 1791–8.
[27]
Zhang H, Ericksen SS, Lee C-P, Ananiev GE, Wlodarchak N, Yu P, Mitchell JC, Gitter A, Wright SJ, Hoffmann FM, et al. Predicting kinase inhibitors using bioactivity matrix derived informer sets PLoS Comput Biol. 2019 15 8 1006813
[28]
Lee D, Kim BH, Kim KJ. Detecting method on illegal use using PCA under her environment. In: 2010 International Conference on Information Science and Applications. IEEE; 2010. p. 1–6.
[29]
He J, Balzano L, Lui J. Online robust subspace tracking from partial information. arXiv preprint arXiv:1109.3827; 2011.
[30]
Xu J, Ithapu VK, Mukherjee L, Rehg JM, Singh V. GOSUS: Grassmannian online subspace updates with structured-sparsity. In: Proceedings of the IEEE international conference on computer vision; 2013. p. 3376–3383.
[31]
Stewart GW. An updating algorithm for subspace tracking. Technical report; 1998.
[32]
Balzano L, Nowak R, Recht B. Online identification and tracking of subspaces from highly incomplete information. In: 2010 48th Annual Allerton conference on communication, control, and computing (Allerton). IEEE; 2010. p. 704–711.
[33]
Novembre J, Johnson T, Bryc K, Kutalik Z, Boyko AR, Auton A, Indap A, King KS, Bergmann S, Nelson MR, et al. Genes mirror geography within Europe Nature. 2008 456 7218 98-101
[34]
Song Y, Westerhuis JA, Aben N, Michaut M, Wessels LF, and Smilde AK Principal component analysis of binary genomics data Brief Bioinform. 2019 20 1 317-29
[35]
Wu J, Zhang X. A PCA classifier and its application in vehicle detection. In: IJCNN’01. International Joint Conference on Neural Networks. Proceedings (Cat. No. 01CH37222), vol. 1. IEEE; 2001. p. 600–604.
[36]
Wu J, Zhang X, Zhou J. Vehicle detection in static road images with PCA-and-wavelet-based classifier. In: ITSC 2001. 2001 IEEE Intelligent Transportation Systems. Proceedings (Cat. No. 01TH8585). IEEE; 2001. p. 740–744.
[37]
Kirby M, Peterson C. Visualizing data sets on the Grassmannian using self-organizing mappings. In: 2017 12th International Workshop on Self-organizing Maps and Learning Vector Quantization, Clustering and Data Visualization (WSOM). IEEE; 2017. p. 1–6.
[38]
Kohonen T Self-organized formation of topologically correct feature maps Biol Cybern. 1982 43 1 59-69
[39]
Kohonen T The self-organizing map Proc IEEE. 1990 78 9 1464-80
[40]
Kohonen T The self-organizing map Neurocomputing. 1998 21 1–3 1-6
[41]
Kohonen T Essentials of the self-organizing map Neural Netw. 2013 37 52-65
[42]
McInnes L, Healy J, Melville J. UMAP: uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426; 2018.
[43]
Tang J, Liu J, Zhang M, Mei Q. Visualizing large-scale and high-dimensional data. In: Proceedings of the 25th international conference on world wide web; 2016. p. 287–297.
[44]
Belkin M and Niyogi P Laplacian eigenmaps and spectral techniques for embedding and clustering Adv Neural Inf Process Syst. 2001 14 1-7
[45]
Belkin M and Niyogi P Laplacian eigenmaps for dimensionality reduction and data representation Neural Comput. 2003 15 6 1373-96
[46]
Tenenbaum JB, Silva V, and Langford JC A global geometric framework for nonlinear dimensionality reduction Science. 2000 290 5500 2319-23
[47]
Liu S, Maljovec D, Wang B, Bremer P-T, and Pascucci V Visualizing high-dimensional data: advances in the past decade IEEE Trans Vis Comput Graph. 2016 23 3 1249-68
[48]
Engel D, Hüttenberger L, Hamann B. A survey of dimension reduction methods for high-dimensional data analysis and visualization. In: Visualization of large and unstructured data sets: applications in geospatial planning, modeling and engineering-proceedings of IRTG 1131 Workshop 2011. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2012.
[49]
Ashokkumar P and Don S High dimensional data visualization: a survey J Adv Res Dyn Control Syst. 2017 9 12 851-66
[50]
Kiefer A, Rahman M, et al.: An analytical survey on recent trends in high dimensional data visualization. arXiv preprint arXiv:2107.01887; 2021.
[51]
Santos KR, Giovanis DG, Shields MD. Grassmannian diffusion maps based dimension reduction and classification for high-dimensional data. arXiv preprint arXiv:2009.07547; 2020.
[52]
Coifman RR, Lafon S, Lee AB, Maggioni M, Nadler B, Warner F, and Zucker SW Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps Proc Natl Acad Sci. 2005 102 21 7426-31
[53]
Hinton G, Roweis ST. Stochastic neighbor embedding. In: NIPS, vol. 15. Citeseer; 2002. p. 833–840.
[54]
Maaten L and Hinton G Visualizing data using t-SNE J Mach Learn Res. 2008 9 11 1-2
[55]
Nickel M and Kiela D Poincaré embeddings for learning hierarchical representations Adv Neural Inf Process Syst. 2017 30 6338-47
[56]
Klimovskaia A, Lopez-Paz D, Bottou L, and Nickel M Poincaré maps for analyzing complex hierarchies in single-cell data Nat Commun. 2020 11 1 1-9
[57]
Bonnabel S Stochastic gradient descent on Riemannian manifolds IEEE Trans Autom Control. 2013 58 9 2217-29
[58]
Absil P-A, Mahony R, and Sepulchre R Optimization algorithms on matrix manifolds 2009 Princeton Princeton University Press
[59]
Li H, Pimentel-Alarcón D. Visualizing Grassmannians via poincare embeddings; 2023.
[60]
Kingma DP, Ba J. Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980; 2014.
[61]
Adams LM, Nazareth JL, et al. Linear and nonlinear conjugate gradient-related methods 1996 Philadelphia SIAM
[62]
Shaham U, Steinerberger S. Stochastic neighbor embedding separates well-separated clusters. arXiv preprint arXiv:1702.02670; 2017.
[63]
Tron R, Vidal RA, benchmark for the comparison of 3-d motion segmentation algorithms. In: 2007 IEEE conference on computer vision and pattern recognition. IEEE; 2007 p. 1–8.
[64]
Tomasi C and Kanade T Shape and motion from image streams under orthography: a factorization method Int J Comput Vis. 1992 9 2 137-54
[65]
Kanatani K-I. Motion segmentation by subspace separation and model selection. In: Proceedings eighth IEEE international conference on computer vision. ICCV 2001, vol. 2. IEEE; 2001. p. 586–91.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SN Computer Science
SN Computer Science  Volume 5, Issue 3
Mar 2024
750 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 February 2024
Accepted: 29 December 2023
Received: 26 July 2023

Author Tags

  1. Grassmannian
  2. Manifold learning
  3. Poincaré disk
  4. t-SNE
  5. High-dimensional data and dimensionality reduction

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media