Top

Published in:

2016 | OriginalPaper | Chapter

6. Dictionary Learning on Grassmann Manifolds

Authors : Mehrtash Harandi, Richard Hartley, Mathieu Salzmann, Jochen Trumpf

Published in: Algorithmic Advances in Riemannian Geometry and Applications

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Sparse representations have recently led to notable results in various visual recognition tasks. In a separate line of research, Riemannian manifolds have been shown useful for dealing with features and models that do not lie in Euclidean spaces. With the aim of building a bridge between the two realms, we address the problem of sparse coding and dictionary learning in Grassmann manifolds, i.e, the space of linear subspaces. To this end, we introduce algorithms for sparse coding and dictionary learning by embedding Grassmann manifolds into the space of symmetric matrices. Furthermore, to handle nonlinearity in data, we propose positive definite kernels on Grassmann manifolds and make use of them to perform coding and dictionary learning.

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

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!

inform now

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!

inform 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!

inform now

previous chapter From Covariance Matrices to Covariance Operators: Data Representation from Finite to Infinite-Dimensional Settings

next chapter Regression on Lie Groups and Its Application to Affine Motion Tracking

The function that maps each vector \({{y}} \in T_\mathscr {P}\mathscr {M}\) to a point \(\mathscr {X}\) of the manifold that is reached after a unit time by the geodesic starting at \(\mathscr {P}\) with this tangent vector is called the exponential map. For complete manifolds, this map is defined in the whole tangent space \(T_\mathscr {P}\mathscr {M}\). The logarithm map is the inverse of the exponential map, i.e, \({{y}} = \log _{\mathscr {P}}(\mathscr {X})\) is the smallest vector \({{y}}\) such that \(\mathscr {X} = \exp _\mathscr {P}({{y}})\).

On an abstract Riemannian manifold \({\mathscr {M}}\), the gradient of a smooth real function f at a point \(x \in {\mathscr {M}}\), denoted by \(\mathrm {grad} f(x)\), is the element of \(T_x({\mathscr {M}})\) satisfying \(\langle \mathrm {grad}f(x), \zeta \rangle _x = Df_x[\zeta ]\) for all \(\zeta \in T_x({\mathscr {M}})\). Here, \(Df_x[\zeta ]\) denotes the directional derivative of f at x in the direction of \(\zeta \). The interested reader is referred to [1] for more details on how the gradient of a function on Grassmann manifolds can be computed.

Another situation where this applies in Computer Vision is the study of the essential manifold, which may be envisaged as the coset space of \(SO(3) \times SO(3)\) modulo a subgroup isomorphic to SO(2). For details see [25].

O(d) has dimension \(d(d-1)/2\), since its Lie algebra is the set of \(n\times n\) skew-symmetric matrices.

In our experiments, we observed that the projection kernel almost always outperforms the Binet–Cauchy kernel.

P.A. Absil, R. Mahony, R. Sepulchre, Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, 2008)CrossRefMATH

M. Aharon, M. Elad, A. Bruckstein, K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans. Signal Process. 54(11), 4311–4322 (2006)CrossRef

V. Arsigny, P. Fillard, X. Pennec, N. Ayache, Log-Euclidean metrics for fast and simple calculus on diffusion tensors. Magn. Reson. Med. 56(2), 411–421 (2006)CrossRef

R. Basri, D.W. Jacobs, Lambertian reflectance and linear subspaces. IEEE Trans. Pattern Anal. Mach. Intell. 25(2), 218–233 (2003)CrossRef

E. Begelfor, M. Werman, Affine invariance revisited, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2006), pp. 2087–2094

C. Berg, J.P.R. Christensen, P. Ressel, Harmonic Analysis on Semigroups (Springer, New York, 1984)CrossRefMATH

E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006)MathSciNetCrossRefMATH

H.E. Cetingul, M.J. Wright, P.M. Thompson, R. Vidal, Segmentation of high angular resolution diffusion MRI using sparse Riemannian manifold clustering. IEEE Trans. Med. Imaging 33(2), 301–317 (2014)CrossRef

S. Chen, C. Sanderson, M. Harandi, B.C. Lovell, Improved image set classification via joint sparse approximated nearest subspaces, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2013), pp. 452–459

10.

N. Dalal, B. Triggs, Histograms of oriented gradients for human detection, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2005), pp. 886–893

11.

D.L. Donoho, Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006)MathSciNetCrossRefMATH

12.

M. Elad, Sparse and Redundant Representations - From Theory to Applications in Signal and Image Processing (Springer, New York, 2010)CrossRefMATH

13.

E. Elhamifar, R. Vidal, Sparse subspace clustering: algorithm, theory, and applications. IEEE Trans. Pattern Anal. Mach. Intell. 35(11), 2765–2781 (2013)CrossRef

14.

M. Faraki, M. Harandi, F. Porikli, More about VLAD: a leap from Euclidean to Riemannian manifolds, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2015), pp. 4951–4960

15.

K.A. Gallivan, A. Srivastava, X. Liu, P. Van Dooren, Efficient algorithms for inferences on Grassmann manifolds, in IEEE Workshop on Statistical Signal Processing (2003), pp. 315–318

16.

B. Gong, Y. Shi, F. Sha, K. Grauman, Geodesic flow kernel for unsupervised domain adaptation, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2012), pp. 2066–2073

17.

R. Gopalan, R. Li, R. Chellappa, Unsupervised adaptation across domain shifts by generating intermediate data representations. IEEE Trans. Pattern Anal. Mach. Intell. 36(11), 2288–2302 (2014). doi:10.1109/TPAMI.2013.249

18.

J. Hamm, D.D. Lee, Grassmann discriminant analysis: a unifying view on subspace-based learning, in Proceedings of the International Conference on Machine Learning (ICML) (2008), pp. 376–383

19.

M. Harandi, M. Salzmann, Riemannian coding and dictionary learning: kernels to the rescue, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2015), pp. 3926–3935

20.

M. Harandi, R. Hartley, C. Shen, B. Lovell, C. Sanderson, Extrinsic methods for coding and dictionary learning on Grassmann manifolds. Int. J. Comput. Vis. 114(2–3), 113–136 (2015)MathSciNetCrossRef

21.

M.T. Harandi, M. Salzmann, S. Jayasumana, R. Hartley, H. Li, Expanding the family of Grassmannian kernels: an embedding perspective, in Proceedings of the European Conference on Computer Vision (ECCV), vol. 8695, Lecture Notes in Computer Science, ed. by D. Fleet, T. Pajdla, B. Schiele, T. Tuytelaars (Springer International Publishing, Cham, 2014), pp. 408–423. doi:10.1007/978-3-319-10584-0_27

22.

M.T. Harandi, R. Hartley, B.C. Lovell, C. Sanderson, Sparse coding on symmetric positive definite manifolds using Bregman divergences. IEEE Trans. Neural Netw. Learn. Syst. (TNNLS) PP(99), 1–1 (2015)

23.

R. Hartley, J. Trumpf, Y. Dai, H. Li, Rotation averaging. Int. J. Comput. Vis. 103(3), 267–305 (2013)MathSciNetCrossRefMATH

24.

U. Helmke, K. Hper, J. Trumpf, Newton’s method on Gramann manifolds (2007)

25.

U. Helmke, K. Hüper, P.Y. Lee, J.B. Moore, Essential matrix estimation using Gauss-Newton iterations on a manifold. Int. J. Comput. Vis. 74(2), 117–136 (2007). doi:10.1007/s11263-006-0005-0

26.

J. Ho, Y. Xie, B. Vemuri, On a nonlinear generalization of sparse coding and dictionary learning, in Proceedings of the International Conference on Machine Learning (ICML) (2013), pp. 1480–1488

27.

S. Jayasumana, R. Hartley, M. Salzmann, H. Li, M. Harandi, Kernel methods on Riemannian manifolds with Gaussian RBF kernels. IEEE Trans. Pattern Anal. Mach. Intell. 37(12), 2464–2477 (2015). doi:10.1109/TPAMI.2015.2414422

28.

H. Karcher, Riemannian center of mass and mollifier smoothing. Commun. Pure Appl. Math. 30(5), 509–541 (1977)MathSciNetCrossRefMATH

29.

J.M. Lee, Introduction to Smooth Manifolds, vol. 218 (Springer, New York, 2012)CrossRef

30.

J. Mairal, F. Bach, J. Ponce, G. Sapiro, A. Zisserman, Discriminative learned dictionaries for local image analysis, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (IEEE, 2008), pp. 1–8

31.

J. Mairal, M. Elad, G. Sapiro, Sparse representation for color image restoration. IEEE Trans. Image Process. (TIP) 17(1), 53–69 (2008)MathSciNetCrossRefMATH

32.

J.H. Manton, A globally convergent numerical algorithm for computing the centre of mass on compact lie groups. Int. Conf. Control Autom. Robot. Vis. 3, 2211–2216 (2004)

33.

B.A. Olshausen, D.J. Field, Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381(6583), 607–609 (1996)CrossRef

34.

R. Ramamoorthi, Analytic PCA construction for theoretical analysis of lighting variability in images of a Lambertian object. IEEE Trans. Pattern Anal. Mach. Intell. 24(10), 1322–1333 (2002)CrossRef

35.

B. Schölkopf, R. Herbrich, A.J. Smola, A generalized representer theorem, Computational Learning Theory (Springer, New York, 2001), pp. 416–426CrossRef

36.

J. Shawe-Taylor, N. Cristianini, Kernel Methods for Pattern Analysis (Cambridge University Press, Cambridge, 2004)CrossRefMATH

37.

S. Shirazi, M. Harandi, B. Lovell, C. Sanderson, Object tracking via non-Euclidean geometry: a Grassmann approach, in IEEE Winter Conference on Applications of Computer Vision (WACV) (2014), pp. 901–908. doi:10.1109/WACV.2014.6836008

38.

I. Steinwart, A. Christmann, Support Vector Machines (Springer, Berlin, 2008)

39.

R. Subbarao, P. Meer, Nonlinear mean shift over Riemannian manifolds. Int. J. Comput. Vis. 84(1), 1–20 (2009)CrossRef

40.

R. Tibshirani, Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B (Methodol.) 58, 267–288 (1996)

41.

P. Turaga, A. Veeraraghavan, A. Srivastava, R. Chellappa, Statistical computations on Grassmann and Stiefel manifolds for image and video-based recognition. IEEE Trans. Pattern Anal. Mach. Intell. 33(11), 2273–2286 (2011)

42.

R. Vemulapalli, J.K. Pillai, R. Chellappa, Kernel learning for extrinsic classification of manifold features, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2013), pp. 1782–1789

43.

J. Wang, J. Yang, K. Yu, F. Lv, T. Huang, Y. Gong, Locality-constrained linear coding for image classification, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2010), pp. 3360–3367

44.

Y. Wang, G. Mori, Human action recognition by semilatent topic models. IEEE Trans. Pattern Anal. Mach. Intell. 31(10), 1762–1774 (2009)

45.

L. Wolf, A. Shashua, Learning over sets using kernel principal angles. J. Mach. Learn. Res. 4, 913–931 (2003)MathSciNetMATH

46.

J. Wright, A.Y. Yang, A. Ganesh, S.S. Sastry, Y. Ma, Robust face recognition via sparse representation. IEEE Trans. Pattern Anal. Mach. Intell. 31(2), 210–227 (2009)

47.

J. Wright, Y. Ma, J. Mairal, G. Sapiro, T.S. Huang, S. Yan, Sparse representation for computer vision and pattern recognition. Proc. IEEE 98(6), 1031–1044 (2010)CrossRef

48.

J. Yang, K. Yu, Y. Gong, T. Huang, Linear spatial pyramid matching using sparse coding for image classification, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2009), pp. 1794–1801

Title: Dictionary Learning on Grassmann Manifolds
Authors: Mehrtash Harandi
Richard Hartley
Mathieu Salzmann
Jochen Trumpf
Publisher: Springer International Publishing
Book: Algorithmic Advances in Riemannian Geometry and Applications
Print ISBN: 978-3-319-45025-4

Electronic ISBN: 978-3-319-45026-1

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-45026-1_6

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner