Skip to main content
Top
Published in: Neural Computing and Applications 9/2019

28-02-2018 | Original Article

Adaptive graph orthogonal discriminant embedding: an improved graph embedding method

Authors: Ming-Dong Yuan, Da-Zheng Feng, Ya Shi, Chun-Bao Xiao

Published in: Neural Computing and Applications | Issue 9/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Graph embedding is a popular graph based dimensionality reduction framework, and it consists of two successive steps, i.e., graph construction and embedding. The traditional graph construction methods such as \(k\)-nearest-neighbor (k-NN) and \(\varepsilon\)-ball suffer from the difficulty in parameter selection and are also sensitive to noises. On the other hand, the property of embedding projection is not fully explored by many methods. In this paper, we explicitly investigate these two steps and propose three adaptive graph orthogonal discriminant embedding techniques (termed as AGODE-gs, AGODE-dl and AGODE-tr) for dimensionality reduction, and their differences lie in the way of orthogonalization. In our proposed methods, both the intra-class adjacency graph and the inter-class repulsion graph are constructed by a \(\ell_{2}\)-norm regularized least square, and an orthogonal constraint between the projection vectors is then imposed. The time and space complexity of the proposed methods are also analyzed in detail. We further show that the proposed methods are computationally more efficient than those \(\ell_{1}\)-norm based graph construction methods. Extensive experiments on four face databases (ORL, Yale, CUM-PIE and Extended YaleB) verify the effectiveness and efficiency of the proposed methods with encouraging results.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Turk M, Pentland A (1991) Eigenfaces for recognition. J Cogn Neurosci 3(1):71–86CrossRef Turk M, Pentland A (1991) Eigenfaces for recognition. J Cogn Neurosci 3(1):71–86CrossRef
2.
go back to reference Belhumeur PN, Hespanha JP, Kriegman DJ (1997) Eigenfaces vs. fisherfaces: recognition using class specific linear projection. IEEE Trans Pattern Anal 19(7):711–720CrossRef Belhumeur PN, Hespanha JP, Kriegman DJ (1997) Eigenfaces vs. fisherfaces: recognition using class specific linear projection. IEEE Trans Pattern Anal 19(7):711–720CrossRef
3.
go back to reference Roweis ST, Saul LK (2000) Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500):2323–2326CrossRef Roweis ST, Saul LK (2000) Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500):2323–2326CrossRef
4.
go back to reference He X, Cai D, Yan S, Zhang H-J (2005) Neighborhood preserving embedding. In: IEEE international conference on computer vision. IEEE, pp 1208–1213 He X, Cai D, Yan S, Zhang H-J (2005) Neighborhood preserving embedding. In: IEEE international conference on computer vision. IEEE, pp 1208–1213
5.
go back to reference Belkin M, Niyogi P (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput 15(6):1373–1396CrossRef Belkin M, Niyogi P (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput 15(6):1373–1396CrossRef
6.
go back to reference He X, Niyogi P (2003) Locality preserving projections. In: Proceedings of the 16th international conference on neural information processing systems. MIT Press, pp 153–160 He X, Niyogi P (2003) Locality preserving projections. In: Proceedings of the 16th international conference on neural information processing systems. MIT Press, pp 153–160
7.
go back to reference Yan S, Xu D, Zhang B, Zhang H-J, Yang Q, Lin S (2007) Graph embedding and extensions: a general framework for dimensionality reduction. IEEE Trans Pattern Anal 29(1):40–51CrossRef Yan S, Xu D, Zhang B, Zhang H-J, Yang Q, Lin S (2007) Graph embedding and extensions: a general framework for dimensionality reduction. IEEE Trans Pattern Anal 29(1):40–51CrossRef
8.
go back to reference Nie F, Zeng Z, Tsang IW, Xu D, Zhang C (2011) Spectral embedded clustering: a framework for in-sample and out-of-sample spectral clustering. IEEE Trans Neural Netw 22(11):1796–1808CrossRef Nie F, Zeng Z, Tsang IW, Xu D, Zhang C (2011) Spectral embedded clustering: a framework for in-sample and out-of-sample spectral clustering. IEEE Trans Neural Netw 22(11):1796–1808CrossRef
10.
go back to reference Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Syst 2:849–856 Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Syst 2:849–856
11.
go back to reference He X, Cai D, Niyogi P (2005) Laplacian score for feature selection. In: Proceedings of the 18th international conference on neural information processing systems. MIT Press, pp 507–514 He X, Cai D, Niyogi P (2005) Laplacian score for feature selection. In: Proceedings of the 18th international conference on neural information processing systems. MIT Press, pp 507–514
12.
go back to reference Zhao Z, Liu H (2007) Spectral feature selection for supervised and unsupervised learning. In: Proceedings of the 24th international conference on machine learning. ACM, pp 1151–1157 Zhao Z, Liu H (2007) Spectral feature selection for supervised and unsupervised learning. In: Proceedings of the 24th international conference on machine learning. ACM, pp 1151–1157
13.
go back to reference Chen H-T, Chang H-W, Liu T-L (2005) Local discriminant embedding and its variants. In: IEEE conference on computer vision and pattern recognition. IEEE, pp 846–853 Chen H-T, Chang H-W, Liu T-L (2005) Local discriminant embedding and its variants. In: IEEE conference on computer vision and pattern recognition. IEEE, pp 846–853
16.
go back to reference Jebara T, Wang J, Chang S-F (2009) Graph construction and b-matching for semi-supervised learning. In: Proceedings of the 26th annual international conference on machine learning. ACM, pp 441–448 Jebara T, Wang J, Chang S-F (2009) Graph construction and b-matching for semi-supervised learning. In: Proceedings of the 26th annual international conference on machine learning. ACM, pp 441–448
17.
go back to reference Yang B, Chen S (2010) Sample-dependent graph construction with application to dimensionality reduction. Neurocomputing 74(1–3):301–314CrossRef Yang B, Chen S (2010) Sample-dependent graph construction with application to dimensionality reduction. Neurocomputing 74(1–3):301–314CrossRef
18.
go back to reference Raducanu B, Dornaika F (2012) A supervised non-linear dimensionality reduction approach for manifold learning. Pattern Recogn 45(6):2432–2444CrossRef Raducanu B, Dornaika F (2012) A supervised non-linear dimensionality reduction approach for manifold learning. Pattern Recogn 45(6):2432–2444CrossRef
19.
go back to reference Zhang L, Qiao L, Chen S (2010) Graph-optimized locality preserving projections. Pattern Recogn 43(6):1993–2002CrossRef Zhang L, Qiao L, Chen S (2010) Graph-optimized locality preserving projections. Pattern Recogn 43(6):1993–2002CrossRef
20.
go back to reference Cheng B, Yang J, Yan S, Fu Y, Huang TS (2010) Learning with l1-graph for image analysis. IEEE Trans Image Process 19(4):858–866MathSciNetCrossRef Cheng B, Yang J, Yan S, Fu Y, Huang TS (2010) Learning with l1-graph for image analysis. IEEE Trans Image Process 19(4):858–866MathSciNetCrossRef
21.
go back to reference Qiao L, Chen S, Tan X (2010) Sparsity preserving projections with applications to face recognition. Pattern Recogn 43(1):331–341CrossRef Qiao L, Chen S, Tan X (2010) Sparsity preserving projections with applications to face recognition. Pattern Recogn 43(1):331–341CrossRef
22.
go back to reference Yan S, Wang H (2009) Semi-supervised learning by sparse representation. In: SDM. SIAM, pp 792–801 Yan S, Wang H (2009) Semi-supervised learning by sparse representation. In: SDM. SIAM, pp 792–801
23.
go back to reference Raducanu B, Dornaika F (2014) Embedding new observations via sparse-coding for non-linear manifold learning. Pattern Recogn 47(1):480–492CrossRef Raducanu B, Dornaika F (2014) Embedding new observations via sparse-coding for non-linear manifold learning. Pattern Recogn 47(1):480–492CrossRef
24.
go back to reference Wright J, Yang AY, Ganesh A, Sastry SS, Ma Y (2009) Robust face recognition via sparse representation. IEEE Trans Pattern Anal 31(2):210–227CrossRef Wright J, Yang AY, Ganesh A, Sastry SS, Ma Y (2009) Robust face recognition via sparse representation. IEEE Trans Pattern Anal 31(2):210–227CrossRef
26.
go back to reference Gui J, Sun Z, Jia W, Hu R, Lei Y, Ji S (2012) Discriminant sparse neighborhood preserving embedding for face recognition. Pattern Recogn 45(8):2884–2893CrossRef Gui J, Sun Z, Jia W, Hu R, Lei Y, Ji S (2012) Discriminant sparse neighborhood preserving embedding for face recognition. Pattern Recogn 45(8):2884–2893CrossRef
29.
go back to reference Lou S, Zhao X, Chuang Y, Yu H, Zhang S (2016) Graph regularized sparsity discriminant analysis for face recognition. Neurocomputing 173:290–297CrossRef Lou S, Zhao X, Chuang Y, Yu H, Zhang S (2016) Graph regularized sparsity discriminant analysis for face recognition. Neurocomputing 173:290–297CrossRef
30.
go back to reference Zang F, Zhang J (2011) Discriminative learning by sparse representation for classification. Neurocomputing 74:2176–2183CrossRef Zang F, Zhang J (2011) Discriminative learning by sparse representation for classification. Neurocomputing 74:2176–2183CrossRef
32.
go back to reference Zhang L, Yang M, Feng X, Ma Y, Zhang D (2012) Collaborative representation based classification for face recognition. arXiv preprint arXiv:12042358 Zhang L, Yang M, Feng X, Ma Y, Zhang D (2012) Collaborative representation based classification for face recognition. arXiv preprint arXiv:​12042358
33.
go back to reference Zhang L, Yang M, Feng X (2011) Sparse representation or collaborative representation: Which helps face recognition? In: IEEE international conference on computer vision (ICCV). IEEE, pp 471–478 Zhang L, Yang M, Feng X (2011) Sparse representation or collaborative representation: Which helps face recognition? In: IEEE international conference on computer vision (ICCV). IEEE, pp 471–478
34.
go back to reference Shi Q, Eriksson A, Van Den Hengel A, Shen C (2011) Is face recognition really a compressive sensing problem? In: IEEE conference on computer vision and pattern recognition. IEEE, pp 553–560 Shi Q, Eriksson A, Van Den Hengel A, Shen C (2011) Is face recognition really a compressive sensing problem? In: IEEE conference on computer vision and pattern recognition. IEEE, pp 553–560
36.
go back to reference Yang W, Wang Z, Sun C (2015) A collaborative representation based projections method for feature extraction. Pattern Recogn 48(1):20–27CrossRef Yang W, Wang Z, Sun C (2015) A collaborative representation based projections method for feature extraction. Pattern Recogn 48(1):20–27CrossRef
37.
go back to reference Kokiopoulou E, Saad Y (2007) Orthogonal neighborhood preserving projections: a projection-based dimensionality reduction technique. IEEE Trans Pattern Anal 29(12):2143–2156CrossRef Kokiopoulou E, Saad Y (2007) Orthogonal neighborhood preserving projections: a projection-based dimensionality reduction technique. IEEE Trans Pattern Anal 29(12):2143–2156CrossRef
38.
go back to reference Lei Y-K, Zou J-W, Dong T, You Z-H, Yuan Y, Hu Y (2014) Orthogonal locally discriminant spline embedding for plant leaf recognition. Comput Vis Image Underst 119:116–126CrossRef Lei Y-K, Zou J-W, Dong T, You Z-H, Yuan Y, Hu Y (2014) Orthogonal locally discriminant spline embedding for plant leaf recognition. Comput Vis Image Underst 119:116–126CrossRef
39.
go back to reference Cai D, He X, Han J, Zhang H-J (2006) Orthogonal laplacianfaces for face recognition. IEEE Trans Image Process 15(11):3608–3614CrossRef Cai D, He X, Han J, Zhang H-J (2006) Orthogonal laplacianfaces for face recognition. IEEE Trans Image Process 15(11):3608–3614CrossRef
40.
go back to reference Zheng Y, Fang B, Tang YY, Zhang T, Liu R (2013) Learning orthogonal projections for Isomap. Neurocomputing 103:149–154CrossRef Zheng Y, Fang B, Tang YY, Zhang T, Liu R (2013) Learning orthogonal projections for Isomap. Neurocomputing 103:149–154CrossRef
41.
go back to reference Gao Q, Ma J, Zhang H, Gao X, Liu Y (2013) Stable orthogonal local discriminant embedding for linear dimensionality reduction. IEEE Trans Image Process 22(7):2521–2531CrossRef Gao Q, Ma J, Zhang H, Gao X, Liu Y (2013) Stable orthogonal local discriminant embedding for linear dimensionality reduction. IEEE Trans Image Process 22(7):2521–2531CrossRef
42.
go back to reference Yu X, Wang X (2008) Uncorrelated discriminant locality preserving projections. IEEE Signal Proc Lett 15:361–364CrossRef Yu X, Wang X (2008) Uncorrelated discriminant locality preserving projections. IEEE Signal Proc Lett 15:361–364CrossRef
43.
go back to reference Jin Z, Yang J-Y, Hu Z-S, Lou Z (2001) Face recognition based on the uncorrelated discriminant transformation. Pattern Recogn 34(7):1405–1416CrossRef Jin Z, Yang J-Y, Hu Z-S, Lou Z (2001) Face recognition based on the uncorrelated discriminant transformation. Pattern Recogn 34(7):1405–1416CrossRef
44.
go back to reference Lu C-Y, Huang D-S (2013) Optimized projections for sparse representation based classification. Neurocomputing 113:213–219CrossRef Lu C-Y, Huang D-S (2013) Optimized projections for sparse representation based classification. Neurocomputing 113:213–219CrossRef
45.
go back to reference Ye J (2005) Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems. J Mach Learn Res 6:483–502MathSciNetMATH Ye J (2005) Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems. J Mach Learn Res 6:483–502MathSciNetMATH
46.
go back to reference Peng X, Yi Z, Tang H (2015) Robust subspace clustering via thresholding ridge regression. In: AAAI conference on artificial intelligence (AAAI), Austin, Texas, USA, Jan 25–29, 2015 Peng X, Yi Z, Tang H (2015) Robust subspace clustering via thresholding ridge regression. In: AAAI conference on artificial intelligence (AAAI), Austin, Texas, USA, Jan 25–29, 2015
47.
go back to reference Yuan M-D, Feng D-Z, Liu W-J, Xiao C-B (2016) Collaborative representation discriminant embedding for image classification. J Vis Commun Image Represent 41:212–224CrossRef Yuan M-D, Feng D-Z, Liu W-J, Xiao C-B (2016) Collaborative representation discriminant embedding for image classification. J Vis Commun Image Represent 41:212–224CrossRef
48.
go back to reference Golub G, Cv Loan (1989) Matrix computations, 2nd edn. Johns Hopkins University Press, London Golub G, Cv Loan (1989) Matrix computations, 2nd edn. Johns Hopkins University Press, London
49.
go back to reference Duchene J, Leclercq S (1988) An optimal transformation for discriminant and principal component analysis. IEEE Trans Pattern Anal 10(6):978–983CrossRef Duchene J, Leclercq S (1988) An optimal transformation for discriminant and principal component analysis. IEEE Trans Pattern Anal 10(6):978–983CrossRef
52.
go back to reference Samaria FS, Harter AC (1994) Parameterisation of a stochastic model for human face identification. In: Proceedings of the 2nd IEEE workshop on applications of computer vision. IEEE, pp 138–142 Samaria FS, Harter AC (1994) Parameterisation of a stochastic model for human face identification. In: Proceedings of the 2nd IEEE workshop on applications of computer vision. IEEE, pp 138–142
54.
go back to reference Sim T, Baker S, Bsat M (2003) The CMU pose, illumination, and expression database. IEEE Trans Pattern Anal 25(12):1615–1618CrossRef Sim T, Baker S, Bsat M (2003) The CMU pose, illumination, and expression database. IEEE Trans Pattern Anal 25(12):1615–1618CrossRef
56.
go back to reference Han PY, Jin ATB, Abas FS (2009) Neighbourhood preserving discriminant embedding in face recognition. J Vis Commun Image Represent 20(8):532–542CrossRef Han PY, Jin ATB, Abas FS (2009) Neighbourhood preserving discriminant embedding in face recognition. J Vis Commun Image Represent 20(8):532–542CrossRef
57.
go back to reference Yang W, Sun C, Zheng W (2016) A regularized least square based discriminative projections for feature extraction. Neurocomputing 175:198–205CrossRef Yang W, Sun C, Zheng W (2016) A regularized least square based discriminative projections for feature extraction. Neurocomputing 175:198–205CrossRef
60.
go back to reference Yang M, Zhang L (2010) Gabor feature based sparse representation for face recognition with gabor occlusion dictionary. In: European conference on computer vision. Springer, pp 448–461 Yang M, Zhang L (2010) Gabor feature based sparse representation for face recognition with gabor occlusion dictionary. In: European conference on computer vision. Springer, pp 448–461
Metadata
Title
Adaptive graph orthogonal discriminant embedding: an improved graph embedding method
Authors
Ming-Dong Yuan
Da-Zheng Feng
Ya Shi
Chun-Bao Xiao
Publication date
28-02-2018
Publisher
Springer London
Published in
Neural Computing and Applications / Issue 9/2019
Print ISSN: 0941-0643
Electronic ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-018-3374-8

Other articles of this Issue 9/2019

Neural Computing and Applications 9/2019 Go to the issue

S.I. : Emergence in Human-like Intelligence towards Cyber-Physical Systems

Open-circuit fault detection for three-phase inverter based on backpropagation neural network

Premium Partner