Towards Generalized and Efficient Metric Learning on Riemannian Manifold

1 Introduction

Many works on computer vision tasks (e.g., visual tracking, action recognition, and motion segmentation) have shown methods built on non-linear manifolds are superior to ones in Euclidean space. Among them, Riemannian manifold of symmetric positive definite (SPD) matrices [Pennec et al., 2006; Tuzel et al., 2008; Caseiro et al., 2011; Harandi et al., 2012; Li et al., 2013; Caseiro et al., 2013; Huang et al., 2015b; Jayasumana et al., 2015; Wang et al., 2016; Harandi et al., 2017] and Grassmann manifold [Hamm and Lee, 2008; Harandi et al., 2011; Turaga et al., 2011; Harandi et al., 2014b; Huang et al., 2015a; Jayasumana et al., 2015] are two most widely used manifolds in computer vision community. The SPD matrices capture high order statistics of data, and have several different forms, e.g., covariance region descriptors of images [Tuzel et al., 2008], covariance matrices of image sets [Wang et al., 2012], resulting matrix of Gaussian distribution [Wang et al., 2017], and structure tensors [Caseiro et al., 2011]. Grassmann manifold is a special type of Riemannian manifold, which is composed of sets of linear subspaces with the same dimensionality in Euclidean space [Jayasumana et al., 2015; Huang et al., 2015a].

∗The corresponding author

Existing metric learning methods on SPD manifold and Grassmann manifold can be roughly divided into three categories in terms of projection space, i.e., frommanifold to tangent space [Li et al., 2013; Huang et al., 2015b], from manifold to Reproducing Kernel Hilbert Space (RKHS) [Hamm and Lee, 2008; Harandi et al., 2011; 2012; Jayasumana et al., 2015] and from manifold to low-dimensional manifold [Huang et al., 2015a; Harandi et al., 2017]. The methods based on projection of tangent space make traditional Euclidean methods workable on non-linear manifolds, but they do not take full advantage of geometry structures of manifolds. The methods projecting data points on manifolds into RKHS via some kernel functions seem make sense, however they are high computational cost and not scalable to large scale problems. In addition, some methods aim at learning metric to project original manifold to a more discriminative manifold [Harandi et al., 2017; Huang et al., 2015a] with full consideration of geometry structure of manifold. Although various metric learning methods have been studied on nonlinear manifolds, aforementioned methods are only designed for a specific type of manifold. Furthermore, most existing methods rely on optimization problems requiring computationally expensive iterations, where complex Riemannian operations usually are performed.

Towards addressing above problems, we propose a generalized and efficient Riemannian manifold metric learning (RMML) method, which is adopted on both SPD manifold and Grassmann manifold. Inspired by Euclidean metric learning method [Zadeh et al., 2016], our manifold metric learning method is formulated as seeking a transformation matrix to minimize sum of geodesic distances of all similar pairs and the interpoint geodesic distances of all dissimilar ones on either SPD manifold or Grassmann manifold. It is both strictly convex and strictly geodesically convex. To optimize our RMML, we first demonstrate the similar and dissimilar matrices associated with data points on manifolds are symmetric positive semi-definite, then the global closed-form solution of our proposed RMML can be achieved by computing matrix geometric mean between inverse of similarity matrix and dissimilarity matrix. It is worth mentioning that, instead of costly Riemannian geometric mean in [Zadeh et al., 2016], we compute matrix geometric mean using more efficient LogEuclidean Riemannian framework [Arsigny et al., 2007] to further improve efficiency. The experimental results on image set classification, video based face recognition, and material classification tasks demonstrate the favorable performance and high efficiency of our RMML method against the stateof-the-art counterparts.

2 RelatedWork

Metric learning on SPD manifold. Affine Invariant Riemannian metric (AIRM) [Pennec et al., 2006] and Log-Euclidean Riemannian metric (LERM) [Arsigny et al., 2007] are widely used to handle SPD matrices. The LERM framework maps SPD manifold to its tangent space (a linear space) through the matrix logarithm, performing more efficient than AIRM framework, so many methods on SPD manifold are developed based on LERM. To learn the metric for d × d SPD matrices, methods in [Sivalingam et al., 2009; Carreira et al., 2012; Vemulapalli and Jacobs, 2015] firstly embed an d × d SPD matrix into its tangent space (a d(d + 1)/2 dimensional linear space) under LERM framework, then perform classical Euclidean metric learning methods. Instead of learning metric in tangent space, methods in [Huang et al., 2015b; Harandi et al., 2017] learn intrinsic metrics to project original SPD manifold to a more discriminative SPD manifold characterized by MΣMT with a transformation matrix M for SPD matrix Σ. In contrast to above methods, kernel-based methods [Wang et al., 2012; Quang et al., 2014] exploit some kernel functions to map SPD matrices into a reproducing kernel Hilbert space (RKHS), where kernelized methods (e.g., linear discriminant analysis (kLDA) and partial least square (kPLS)) are performed for discriminative learning.

Metric learning on Grassmann manifold. Compared to metric learning methods on SPD manifold, metric learning on Grassmann manifold are performed in either RKHS or the original manifold. For kernel-based metric learning methods, kernel functions are derived on Grassmann manifold to map original space to a high-dimensional RKHS [Hamm and Lee, 2008; Harandi et al., 2011; 2014b; Jayasumana et al., 2015]. Therein, Grassmann Discriminant Analysis (GDA) uses Fisher criterion to learn a low-dimensional space mapping [Hamm and Lee, 2008]. Grassmann Graph-embedding Discriminant Analysis (GGDA) exploits the graph embedding strategy to further improve the performance of GDA [Harandi et al., 2011]. In [Jayasumana et al., 2015], projection Gaussian kernel is derived and various applications in RKHS are discussed. Different from kernel-based methods, [Huang et al., 2015b] learns a discriminative projection metric on the original Grassmann manifold.

The formulation of the proposed RMML is quite different from existing ones on Riemannian manifold. Our RMML method can learn intrinsic metrics on both SPD and Grassmann manifolds in the same formulation, which takes into full consideration geometry structures of manifolds. Moreover, its optimization can be achieved by a global closed-form solution benefiting high efficiency.

3 Parametric RiemannianManifoldMetrics

In this section, we first give a brief introduction of parametric metrics on SPD and Grassmann manifolds, which will be adopted to our proposed RMML method.

3.1 Parametric Metrics on SPDManifold

We use (M, d) to represent a Riemannian manifold, where M is the topological space and d is the dimension of the manifold. Notably, Riemannian metric is a family of inner products on all tangent spaces and (M, d) is a differentiable manifold equipped with a smoothly varying inner product on each tangent space. It is well known that space of d×d SPD matrices forms a Riemannian manifold endowed with a Riemannian metric, called SPD manifold Sd+. The LERM and AIRM are two most commonly used metrics to match SPD matrices. Although AIRM has better properties 1 , it suffers from high computational complexity [Arsigny et al., 2007]. Therefore, we exploit LERM in this paper.

For a point S1 ∈ Sd+, the set of all tangent vectors at S1 on Sd+ constructs the tangent space of S1, denoted as TS1 Sd+. Log-Euclidean metric exploits the Lie group structure of SPD matrices, benefiting low computational cost [Arsigny et al., 2007]. For two points S1, S2 on the SPD manifold Sd+, the logarithmic multiplication is defined as:

where log (·) and exp (·) are matrix logarithmic and exponential operations, respectively. Under LERM framework, exponential and logarithmic maps can be represented in the forms of matrix exponential and logarithmic operations, i.e.,

Then, the scalar product between two elements V1 and V2 at a point S is calculated as

After that, the geodesic distance between two SPD matrices is defined as:

In this way, the geodesic distance on SPD manifold is converted to Euclidean distance in the tangent space at identity matrix with matrix logarithm. Please refer to [Arsigny et al., 2007] for more details.

In our applications, we first compute SPD matrices for a set of images or features (denoted as S = {S1, S2, ..., Sn}). Let f : Sd+ → Sr+ be a smooth mapping from original SPD

1 AIRM is affine invariant, while LERM is similarity invariant.

manifold to a new manifold Sr+. Thus, for a point Si, the mapping of tangent space from Sd+ to Sr+ is defined as:

where the mapping TF (Si) is an injection and mapping f is a smooth map [Huang et al., 2015b]. Thus if we can find a transformation M ∈ Rd×r of point Si from original tangent space TSi Sd+ to space Tf(Si)Sr+, geodesic distance between Si ,Sj on original SPD manifold can be represented as:

where MMT is a rank-r symmetric positive semi-definite (SPSD) matrix ensuring that the converted space is a tangent space of SPD matrices in the logarithm domain. Let T = log (S), and Q = MMT . We can rewrite the formulation (6) as:

where Q is a rank-r SPSD matrix, so A=QQ is also a rank-r SPSD matrix. Given an SPD matrix S, we first embed it to T with mapping function φ, e.g., matrix logarithm or square root operation [Wang et al., 2017], then compare two SPD matrices using Eq. (7). We can see that metric in Eq. (7) involves the parameter A, which will be learned for more discriminative matching or classification.

3.2 Parametric Metrics on GrassmannManifold

Let G be an n-dimensional vector space, a Grassmann manifold Gr(k, G) can be regarded as a set of all k-dimensional subspaces in G, denoted as Gr(k, d)(k < d). An element on Grassmann manifold Gr(k, d) is a linear subspace spanned by a d × k full rank orthonormal basis matrix Y, where YT Y = Ik and Ik is an identity matrix of the size k × k. In this paper, we employ commonly used projection distance to match two points Y1, Y2 on Grassmann manifold, i.e.,

where Y1Y1 T and Y2Y2 T are projection matrices and above projection distance approaches the geodesic distance at a scale of √2 [Huang et al., 2015a].

Suppose there is a set of images or features {X1,X2, ...,Xn}, where Xi ∈ Rd×mi , d is the size of sample and mi is the number of samples in the ith target, i = 1, 2, .., n. Firstly, we represent data Xi using a k-dimensional linear space, which is spanned by the corresponding orthonormal basis matrix, i.e., XiXTi ≃ YiΛiYT i , where Yi is the matrix composed of the top k largest eigenvectors of Xi. Then the distance between Xi and Xj can be converted to the distance between YiYT i and YjYT j . Similar to the distance metrics on SPD manifold, we first define a mapping f : Gr (k, d) → Gr (k, r), and denote the transformation matrix of f as M. Notably, M is a d × r matrix of full column rank. We use MT Yi ′ to represent the orthonormal components of MT Yi, which is the orthonormal basis matrix of the new Grassmann manifold Gr (k, r).

Then the learned projection metric on the low-dimensional Grassmann manifold is defined as

where Q = MMT is a d×d rank-r SPSD matrix and Tij = Yi ′ Yi ′ T -Yj ′ Yj ′ T . Let A = QQ, then we can rewrite the projection distance (9) as:

where A is a parameter to be learned.

Notably, we find that parametric metric on Grassmann manifold (10) shares the similar form with one on SPD manifold (7), which encourages us to develop a metric learning method to handle both manifolds.

4 RiemannianManifoldMetric Learning

In this section, we propose a generalized metric learning method. The corresponding model and optimization are described as follows.

4.1 Model

Inspired by the geometric mean metric learning (GMML) in Euclidean space [Zadeh et al., 2016], we present a novel metric learning method to learn the distance metrics for both SPD manifold and Grassmann manifold. Given a set of training data {X1, ...Xi, ...,Xn}, Xi ∈ Rd×mi where d and mi are feature dimension and the number of samples in the ith target, respectively. In real-world applications, Xi can be an image set in video based face recognition, or a set of local features extracted from images. The goal of our method is to learn an appropriate parameter A in metrics (7) and (10) to further improve performance of model matching.

According to training data {X1, ...Xi, ...,Xn} with label information, we can compute a set of SPD matrices {S1, ...Si, ..., Sn} with Si ∈ Rd×d or a set of linear subspaces {Y1, ...Yi, ...,Yn} with Yi ∈ Rk×d on SPD manifold or Grassmann manifold. By using available label information, we can generate a set of positive pairs (two points with the same label) and negative pairs (two points with different labels). The principle of metric learning is usually to learn parameter (i.e., A in our case) to pull the distances between positive (similar) pairs ((hi, hj) ∈ P) to be as small as possible, while the distances between negative (dissimilar) pairs ((hi, hj) ∈ N) are pushed as large as possible.

As suggested in [Zadeh et al., 2016], instead of decreasing the sum of distances over all similar pairs while increasing ones over all dissimilar pairs in previous methods, we learn A with minimizing the geodesic distance of similar pairs and the interpoint geodesic distance (described by A-1 ) of dissimilar ones on nonlinear manifolds. Then our metric learning method can be formulated as:

where hi and hj represent two points on SPD manifold or Grassmann manifold. As shown in [Zadeh et al., 2016], both of distances dA and dA-1 are monotonous but their tendencies of change are completely opposite. That is, ∑ (hi ,hj )∈P dA(hi, hj) is minimized to pull the points in pos-

itive pairs closer while ∑ (hi ,hj )∈N dA-1(hi, hj) is minimized

to enlarge the distances between two points in negative pairs.

According to the distance metrics in (7) and (10), our metric learning problem are described as follows. For SPD manifold, the objective function is formulated as:

where Ti = log(Si) or S 1 2 , and Si is an SPD matrix. Let P and N denote similar matrix and dissimilar matrix on the manifold, respectively. Thus, we have

For Grassmann manifold, the objective function is formulated as:

We can see that our metric learning on both SPD (12) and Grassmann (15) manifolds can be reformulated in terms of A, P and N as following:

Meanwhile, we show P and N are positive semi-definite for both SPD manifold and Grassmann manifold, which is given in the following lemma:

Lemma 1 For SPD manifold and Grassmann manifold, P and N in (13) and (15) are symmetric positive semi-definite (SPSD).

Proof 1 For two points Si, Sj on SPD manifold, the matrices Ti, Tj are SPD matrices as well. Ti-Tj is also a symmetric matrix. Since the square of an arbitrary symmetric real matrix is a SPSD matrix, (Ti -Tj) (Ti -Tj) is easily proved to be a SPSD matrix. Hence, P and N are symmetric positive semi-definite.

For Grassmann manifold, as Yi ′ Yi ′ T is symmetric, Tij is also symmetric. Thus, it is easily proved that for Grassmann manifold P and N are symmetric positive semi-definite.

The property of positive semi-definite lying in P and N plays a key role in optimizing our RMML (16), which will be introduced as follows.

,

Algorithm 1 RMML-SPD and RMML-GM Algorithms

Input:

Training data {Xi, X2, ..., Xn} , Xi ∈ mi×d .

• 1: RMML-SPD: Compute SPD matrices Si from Xi, i = 1, 2, ..., n. Compute Ti, and P and N by using (13). RMML-GM: Compute Yi for all train data Xi and P and N by using (15).
• 2: Compute A by using (21).

Output:

Distance Metric matrix A

4.2 Optimization and Algorithm

Since objective function (16) is strictly convex and geodesically convex [Zadeh et al., 2016], we can seek the globally optimal solution of A if it satisfies ∇f (A) = 0. So, by computing the gradient of f with respect to A and setting it to

It is easy to know that (17) is a Riccati equation and its globally optimal solution is the midpoint of geodesic curve joining matrices P-1 and N on SPD manifold. So, the solution of A can be easily achieved by computing the Riemannian geometric mean between SPD matrices P-1 and N, i.e,

Obviously, since A is Riemannian geometric mean between SPD matrices P-1 and N, it is naturally symmetric positive definite.

However, it is well known that computation of geometric mean (18) involves expensive Riemannian operations. In this paper, we optimize A as geometric mean between SPD matrices P-1 and N under efficient LERM framework. Thus, we have

Compared with solution (18), our optimization (19) is more efficient. Note that solution (19) needs P-1 and N are symmetric positive definite. The Lemma 1 proves P-1 and N are naturally symmetric positive semi-definite, then we introduce a regularizer with parameter λ ≥ 0 to ensure P and N be positive definite. In this way, the solution has

Besides, a weight parameter t (0 ≤ t ≤ 1 ) is introduced to balance the effect of the distances between positive pairs and those between negative pairs. Thus, the final solution of matrix A is obtained as

The proposed metric learning method on SPD manifold (RMML-SPD) and Grassmann manifold (RMML-GM) is summarized in Algorithm 1.

For each sample in probe sets, we compute the distance between it and each training sample with the matrix A computed in Algorithm 1, then we use simple NN for classification.

4.3 Discussions

Compared with pervious manifold metric learning methods (e.g., LEML [Huang et al., 2015b] and PML [Huang et al., 2015a]) relying on computationally expensive iterations, our RMML can be efficiently optimized with a global closed-form solution. Moreover, the learned parameter in our method is naturally positive definite without additional regularization. Our RMML is inspired by GMML [Zadeh et al., 2016], however, the proposed RMML aims at learning metrics on non-linear manifolds rather than in linear Euclidean space. Furthermore, instead of optimization based on Riemannian operation in [Zadeh et al., 2016], our RMML is optimized under more efficient LERM framework.

5 Experiments

In this section, we evaluate the proposed method on three tasks, including object recognition, video based face recognition and material classification.

Datasets. We conduct experiments on five datasets, including ETH-80 [Leibe and Schiele, 2003], Flickr Material dataset [Sharan et al., 2009], and UIUC material [Liao et al., 2013], YouTube Celebrities [Kim et al., 2008], and YouTube Face dataset [Wolf et al., 2011].

ETH-80 dataset contains 80 image sets of 8 object categories [Leibe and Schiele, 2003]. There are 10 sub-objects for each category, and each sub-object has 41 images from different views. Following the experimental settings in [Wang et al., 2012], we randomly choose 5 objects as gallery and the other 5 objects as probes in each category. The size of each image is resized to 20×20, and the intensity feature is used.

Flickr material dataset (FMD) contains 1000 images of 10 materials categories in the wild [Sharan et al., 2009]. We pass each image through VGG-VD16 model pre-trained on ImageNet dataset, and employ the outputs of the last convolution layer as local features with size of mi × 512. Following the common setting in [Wang et al., 2016], we randomly choose half of images in each category as gallery and the other half as probes.

UIUC material dataset has 216 images and 18 categories of material in the wild [Liao et al., 2013]. The feature extraction strategy is used as the same as that in Flickr material dataset. We randomly choose half of images in each category for gallery and the other half for probes.

YouTube Celebrities (YTC) dataset has 1910 video clips of 47 subjects [Kim et al., 2008], and the number of frames in each video varies significantly. Following the common setting in [Wang et al., 2012; Huang et al., 2015b], we randomly select 3 image sets per subject for gallery and 6 image sets for probes. Histogram equalization is used to eliminate lighting effects as a preprocessing step. Then, each image is resized to a 20 × 20 image and intensity is used to represent images.

YouTube Face (YTF) dataset contains 3425 videos of 1595 peoples [Wolf et al., 2011]. Each video has many sequences with variations of poses, illuminations and expressions. Following [Huang et al., 2015b], we intercept the face part of every frame and resized it into 20 × 40 pixels. 5000 video pairs are used to perform ten-fold cross validation tests. In each fold there are 500 pairs, including 250 pairs of the same person and 250 pairs of different persons.

Evaluation methods. To evaluate the effectiveness and efficiency of our proposed method, we compare RMML with various state-of-the-art counterparts including nonlinear manifold learning methods and metric learning methods on manifolds. They are summarized as follows.

• Nonlinear manifold based methods: Manifold-Manifold Distance (MMD) [Wang et al., 2008]; Manifold Discriminant Analysis (MDA) [Wang and Chen, 2009].
• Affine subspace based methods: Affine and Convex Hull based Image Set Distance (AHISD and CHISD) [Cevikalp and Triggs, 2010].
• SPD manifold based methods: SPD Manifold Learning (SPDML) [Harandi et al., 2014a]; Log-Euclidean Metric Learning (LEML) [Huang et al., 2015b].
• Grassmann manifold based methods: Grassmann Graph embedding Discriminant Analysis (GGDA) [Harandi et al., 2011]. Projection Metric Learning (PML) [Huang et al., 2015a];

Parameters setting. For metric learning on SPD manifold, we first compute mean vector µ and sample covariance S of a set of data to obtain a Gaussian descriptor. Meanwhile as suggested in [Wang et al., 2016], we estimate covariance matrix ˆΣ with vN-MLE method. As the space of Gaussian distribution forms a Riemannian manifold, we embed them into the

is a positive parameter to balance the dimension and orders of magnitude between mean vector and covariance.

For LEML method, since the distance metrics are learned in the tangent space, we compute Ti = log (Si) for all SPD matrices. As suggested in [Huang et al., 2015b], we add a positive real number (i.e.,0.001×tr(Si)) to the diagonal elements of Si for numerical stability, and exploit Gaussian embedding followed by matrix logarithm. Following the existing metric learning algorithms on Grassmann manifold [Harandi et al., 2011; Huang et al., 2015a], the number of orthonormal bases for each linear subspace is set as 10.

For fair comparison, we exploit the source codes of competitive methods provided by the authors, and set the parameters suggested by the original papers. For MMD, the variance percentage to preserve in PCA is set to 90%. For MDA, we set three parameters as same as [Wang and Chen, 2009]. For linear and non-linear versions of AHISD and CHISD [Cevikalp and Triggs, 2010], the 98% energy by PCA is retained in non-linear AHISD and the value of error penalty C in CHISD is set as same as [Cevikalp and Triggs, 2010]. The reduced feature dimension is set to (c - 1) for LDA, where c is the number of classes. For LEML, η is tuned from 0.001 to 1000 and the value of ζ is tuned from 0.1 to 1. For GGDA, the graph parameter v is set from 1 to 10 and the size of projection matrix r is set to (c - 1). Besides, its parameter β is tuned from 1e2 to 1e6 . There are two parameters λ and t for RMML. We simply set λ to 0.1 on all datasets, and set t from {0.2, 0.4, 0.6, 0.8} by cross-validation on the training set.

Accuracy. The performances of all competitive methods are evaluated in terms of both accuracy and efficiency. Table ?? shows accuracies of different methods on five datasets. Ten random trials are run on ETH-80, FMD, UIUC material and YTC datasets, then the average results are reported. For YTF, the standard ten-fold cross validation are used for evaluation. As GGDA cannot be applied to verification task, the result of GGDA on YTF dataset is not reported. From Table ?? one can see that our RMML-SPD and RMML-GM get better performance than their counterparts in both classification and verification tasks. Compared with metric learning methods on SPD manifold, our RMML-SPD significantly improves the second best LEML over 1.50%, 2.28%, 7.13%, 8.20%, 2.36% on five datasets, respectively. Compared with metric learning methods on Grassmann manifold, the proposed RMML-GM achieves the best results on four datasets except UIUC. The promising performance of our RMML maybe owe to effective objective function and global closed-form solution.

Running time. Then we compare the running time of different methods. The experiments are run on a PC equipped with a single Intel(R) Core(TM) i7-6700 (3.40GHz). For our RMML-SPD and RMML-GM, both SPD matrices and linear subspaces can be computed offline, leading the computation of P and N in (13) and (15) can be regarded as a preprocessing step. Therefore, we report the time of solving (21) as the training time of RMML. For LEML, the computation of SPD matrices and logarithmic operation is considered as a preprocessing step and the time for the cyclic Bregman projection algorithm is recorded as the training time. For PML, we compute the linear subspaces before training and report the time of projection metric learning. As for GGDA, the Gram matrix is first computed as a preprocessing step. The time for computing within-class and between-class graph similarity matrices and eigen decomposition is recorded.

The training time of various methods on five datasets is listed in Table 2. From it we can see that RMML-SPD and RMML-GM are much faster than LEML and PML, respectively. It owes to RMML has a closed-form solution while LEML and PML both need several iterations for optimization. Compared with GGDA, RMML is more scalable to large scale problems. Besides, RMML is also suitable for online learning because P and N in (13) and (15) can be easily updated by adding the distance information of new pairs. Then distance metrics are learned efficiently with a closedform solution. On the contrary, metric learning methods relying on iterative optimization will be time consuming.

6 Conclusions and FutureWork

In this paper, we proposed a novel Riemannian manifold metric learning (RMML) towards handling two most widely used manifolds (i.e., SPD manifold and Grassmann manifold) in the same formulation. To this end, we first introduce parametric metrics on SPD and Grassmann manifolds, and formulate metric learning problem as minimizing the geodesic distance of similar pairs and the interpoint geodesic distance of dissimilar ones on manifolds. The proposed RMML has a global optimum and is efficiently optimized with a closedform solution under LERM framework. Experiments on various computer vision tasks demonstrate the effectiveness and efficiency of the proposed RMML. In future, we will adopt RMML to more possible types of Riemannian manifolds and apply our method to more other tasks.

Acknowledgments

This work was supported by the National Natural Science Foundation of China under Grants 61502332 and 61732011, Natural Science Foundation of Tianjin Under Grants 17JCZDJC30800.