Bregman Divergences for Infinite Dimensional Covariance Matrices

Introduction

In this paper, we tackle the problem of employing infinite-dimensional Covariance Descriptors (CovDs) for classification. CovDs are becoming increasingly popular in many computer vision tasks due to their robustness to measurement variations . Such descriptors take the form of, e.g., region covariance matrices for pedestrian detection and texture categorization , human joint covariances for activity recognition , and covariance matrices of the local Brownian motion of water molecules in diffusion tensor imaging (DTI) .

As the name implies, CovDs are obtained by computing the second order statistics of feature vectors extracted at a finite number of observation points, such as the pixels of an image. The resulting descriptors are Symmetric Positive Definite (SPD) matrices and naturally lie on non-linear manifolds known as tensor, or SPD manifolds. As a consequence, Euclidean geometry is often not appropriate to analyze CovDs . To overcome the drawbacks of Euclidean geometry and better account for the Riemannian structure of CovDs, state-of-the-art methods make use of non-Euclidean metrics (e.g., ). In particular, Bregman divergences have recently been successfully employed in a number of CovD-based applications .

Nevertheless, all previous studies work with relatively small CovDs (i.e., at most $50\times 50$, to the best of our knowledge) built from feature vectors whose dimension is typically much smaller than the number of observations. While this could be thought of as a filtering operation, it also implies that the information encoded in such a CovD is inherently poorer than the information jointly contained in all the observations. Recently, it was shown that CovDs could be mapped to Reproducing Kernel Hilbert Space (RKHS) via the use of SPD-specific kernels . While this may, to some degree, enhance the discriminative power of the low-dimensional CovDs, it is unlikely to be sufficient to entirely recover the information lost when constructing them.

In this paper, we overcome this issue by introducing an approach to building and analyzing infinite-dimensional CovDs from a finite number of observations. To this end, we map the original features to RKHS and compute CovDs in the resulting space. Since the dimensionality of the RKHS is much larger than the dimensionality of the observations, the resulting descriptor will encode more information than a CovD constructed in the original lower-dimensional space, and is therefore better suited for classification.

In practice, of course, the mapping to RKHS is unknown and the CovDs cannot be explicitly computed. However, here, we show that several Bregman divergences can be derived in Hilbert space via the use of kernels, thus alleviating the need for the explicit mapping. In particular, we consider the Burg , Jeffreys and Stein divergences, that have proven powerful to analyze SPD matrices. These divergences allow us to perform classification in Hilbert space via a simple nearest-neighbor (NN) classifier, or by making use of more sophisticated distance-based classifiers, such as support vector machines (SVM) with a Gaussian kernel.

We evaluated the resulting descriptors on the tasks of image-based material, texture and virus recognition, person re-identification, and action recognition from motion capture data. Our experimental evaluation clearly evidences the importance of keeping all the data information by mapping to Hilbert space before computing the CovDs. Furthermore, our empirical results show that, with this new representation, a simple NN classifier can achieve accuracies comparable to those of much more sophisticated methods, and that these accuracies can even be boosted beyond the state-of-the-art when using more powerful classifiers.

Theory of Bregman Divergences

In this section, we review several Bregman divergences and discuss the properties that motivated our decision to use them to compare CovDs in RKHS.

While Bregman divergences exhibit a number of useful properties , their general asymmetric behavior is often counter-intuitive and undesirable in practical applications. Therefore, here, we also consider two symmetrized Bregman divergences, namely the Jeffreys and the Stein divergences.

The Jeffreys, or $J$-, divergence is obtained from the Burg divergence, and can be expressed as

The Stein, or $S$-, divergence (also known as the Jensen-Bregman LogDet divergence ) is also obtained from the Burg divergence, but through Jensen-Shannon symmetrization. It can be written as

Here, we present the properties of Bregman divergences that make them a natural choice as a measure of dissimilarity between two CovDs. In particular, we discuss these properties in comparison to the popular Affine Invariant Riemannian Metric (AIRM) on $\mathcal{S}_{++}^{n}$ , which was introduced as a geometrically-motivated way to analyze CovDs.

As indicated by the name, the AIRM was designed to be invariant to affine transformations, which often is an attractive property in computer vision algorithms. In our case, the $B$-divergence exhibits the same invariance property. More specifically, given ${\boldsymbol{A}}\in\rm{GL}(n)$, $B({\boldsymbol{C}}_{1},{\boldsymbol{C}}_{2})=B({\boldsymbol{A}}{\boldsymbol{C}}_{1}{\boldsymbol{A}}^{T},{\boldsymbol{A}}{\boldsymbol{C}}_{2}{\boldsymbol{A}}^{T})$. This can easily be shown from the definition of the $B$-divergence. Since the $J$- and $S$-divergences are obtained from the $B$-divergence, it can easily be verified that they inherit this affine invariance property. Furthermore, these two divergences are also invariant to inversion, i.e.,

Finally, we also note that $B({\boldsymbol{C}}_{1},{\boldsymbol{C}}_{2})=B({\boldsymbol{C}}_{2}^{-1},{\boldsymbol{C}}_{1}^{-1})$.

Positive definite Gaussian kernel:

Recently, kernel methods have been successfully employed on Riemannian manifolds . In particular, an attractive solution is to form a kernel by replacing the Euclidean distance in the popular Gaussian kernel with a more accurate metric on the manifold. However, the resulting kernel is not necessarily positive definite for any metric. In particular, the AIRM does not yield a positive definite Gaussian kernel in general. In contrast, both the $J$- and the $S$-divergences admit a Hilbert space embedding via a Gaussian kernel.

More specifically, for the $J$-divergence, it was shown in that the kernel

is Conditionally Positive Definite (CPD). CPD kernels correspond to Hilbertian metrics and can be exploited in a wide range of machine learning algorithms. An example of this is kernel SVM, whose optimal solution was shown to only depend on the Hilbertian property of the metric . Note that while the kernel $k_{J}(\cdot,\cdot)$ was claimed to be positive definite , we are not aware of any formal proof of this claim.

is not positive definite for all $\beta>0$. However, as was shown in , $k_{S}(\cdot,\cdot)$ is positive definite iff

Note that, here, we are not directly interested in positive definite Gaussian kernels on $\mathcal{S}_{++}^{n}$ to derive our infinite-dimensional CovDs, but only to learn a kernel-based classifier with the divergences between our infinite-dimensional CovDs as input. The properties of the Bregman divergences that we use in the remainder of this paper are summarized in Table 1.

Covariance Descriptors in RKHS

In this section, we show how CovDs can be computed in infinite-dimensional spaces. To this end, we first review some basics on Hilbert spaces.

A Hilbert space is a (possibly infinite-dimensional) inner product space which is complete with respect to the norm induced by the inner product.

where ${\boldsymbol{\mu}}=\dfrac{1}{m}\sum_{i=1}^{m}{\boldsymbol{x}}_{i}$ is the mean of the observations, ${\boldsymbol{J}}={m}^{-3/2}(m\mathbf{I}_{m}-{\boldsymbol{1}}_{m\times m})$ is a centering matrix, and ${\boldsymbol{1}}_{m\times m}$ is a square matrix with all elements equal to 1.

where \Phi_{\boldsymbol{X}}=\big{[}\phi({\boldsymbol{x}}_{1})|\phi({\boldsymbol{x}}_{2})|\cdots|\phi({\boldsymbol{x}}_{m})\big{]}. If $|\mathcal{H}|>m$, then ${\boldsymbol{C}}_{\boldsymbol{X}}$ is rank-deficient, which would make any divergence derived from the Burg divergence indefinite. More precisely, the resulting matrix would be on the boundary of the positive cone, which would make it at an infinite distance from any positive definite matrix, not only for Burg-based divergences, but also according to the AIRM.

Here, we address this issue by exploiting ideas developed in the context of covariance matrix estimation from a limited number of observations . More specifically, we seek to keep the positive eigenvalues of ${\boldsymbol{C}}_{\boldsymbol{X}}$ intact and replace the zero ones with a very small positive number $\rho$, thus making the CovD positive definite. First, using a standard result , we note that the positive eigenvalues of ${\boldsymbol{C}}_{\boldsymbol{X}}$, denoted by $\Lambda_{{\boldsymbol{X}}}$, can be computed from ${\boldsymbol{J}}^{T}\Phi_{{\boldsymbol{X}}}^{T}\Phi_{{\boldsymbol{X}}}{\boldsymbol{J}}={\boldsymbol{J}}^{T}{\boldsymbol{K}}_{{\boldsymbol{X}},{\boldsymbol{X}}}{\boldsymbol{J}}$, where ${\boldsymbol{K}}_{{\boldsymbol{X}},{\boldsymbol{X}}}$ is the $m\times m$ kernel matrix whose elements are defined by the kernel function $k({\boldsymbol{x}}_{i},{\boldsymbol{x}}_{j})$. By eigenvalue decomposition, we can write

This lets us write a (regularized) estimate of ${\boldsymbol{C}}_{\boldsymbol{X}}$ as

with $\mathbf{I}_{{\boldsymbol{X}}}$ the identity matrix whose dimension is the number of positive eigenvalues of ${\boldsymbol{C}}_{\boldsymbol{X}}$ . Note that this derivation can also be employed to model points in $\mathcal{H}$ with lower-dimensional latent variables by retaining only the top $r$ eigenvalues and eigenvectors of ${\boldsymbol{J}}^{T}{\boldsymbol{K}}_{{\boldsymbol{X}},{\boldsymbol{X}}}{\boldsymbol{J}}$ to form ${\boldsymbol{W}}_{{\boldsymbol{X}}}$ .

Bregman Divergences in RKHS

In this section, we derive different Bregman divergences for the infinite-dimensional CovDs introduced in Section 3. In these derivations, we will make use of the equivalence

whose derivation is provided in supplementary material.

The Frobenius norm can easily be computed as

Note that, although not a desirable property , the Euclidean metric is definite for positive semi-definite matrices, which makes it possible to set $\rho$ to zero.

Burg Divergence:

Using the Sylvester determinant theorem , we first note that

Then, from the Woodbury matrix identity , we have

By combining Eqs. 28 and 15, we then obtain

Note that the Burg divergence is independent of $|\mathcal{H}|$. This property is inherited by the Jeffreys and Stein divergences derived below.

Jeffreys Divergence:

From the definition in Section 2, the Jeffreys divergence can be obtained directly from the Burg divergence. This yields

Stein Divergence:

To compute the Stein divergence in $\mathcal{H}$, let us first define

Similarly as in Eq. 28, \det\big{(}(\widehat{{\boldsymbol{C}}}_{{\boldsymbol{X}}}+\widehat{{\boldsymbol{C}}}_{{\boldsymbol{Y}}})/2\big{)} becomes

1 Practical Considerations

When computing divergences in RKHS, it is desirable to minimize the effect of the parameter $\rho$, and thus have divergences that do not depend on its inverse. To this end, let us assume that the same number of eigenvectors were kept to build ${\boldsymbol{C}}_{{\boldsymbol{X}}}$ and ${\boldsymbol{C}}_{{\boldsymbol{Y}}}$. In this case, the Stein divergence can be written as

In our experiments, we used the definitions of Eqs. 25 and 24.

2 Computational Complexity

Computing the $n\times n$ CovDs based on Eq. 7 requires $O(n^{2}m)$. The inverse of an $n\times n$ SPD matrix can be computed by Cholesky decomposition in $\frac{1}{2}n^{3}$ flops. Therefore, computing the $J$-divergence requires $2n^{2}m+2n^{2.3}+n^{3}$ flops, which is dominated by $2n^{2}m$. The complexity of computing the determinant of an $n\times n$ matrix by Cholesky decomposition is $O(\frac{1}{3}n^{3})$. Therefore, computing the $S$-divergence requires $2n^{2}m+n^{2.3}+\frac{2}{3}n^{3}$ flops, which is again dominated by $2n^{2}m$.

In RKHS, computing $K_{{\boldsymbol{X}},{\boldsymbol{X}}}$, $K_{{\boldsymbol{Y}},{\boldsymbol{X}}}$ and $K_{{\boldsymbol{X}},{\boldsymbol{Y}}}$ requires $m^{2}$ flops for each matrix. Therefore, evaluating Eq. 9 requires for $m^{3}$ flops. Assuming that $r$, $r<m$, eigenvectors are used to create ${\boldsymbol{W}}_{\boldsymbol{X}}$ in Eq. 11, computing $J_{\mathcal{H}}$ according to Eq. 33 requires $2m^{3}+3m^{2}+4m^{2}r+2mr^{2}$. For $S_{\mathcal{H}}$, evaluating Eq. 23 takes $6m^{3}+3m^{2}+8m^{2}r+8mr^{2}$ flops.

Generally speaking, the complexity of computing the Jeffreys and Stein divergences in the observation space is linear in $m$ while it is cubic when working in RKHS. Our experimental evaluation shows, however, that working in RKHS remains practical. To illustrate this, we compare the runtimes required to compute the Stein divergence between $500,000$ pairs of CovDs on $\mathcal{S}_{++}^{10}$ using Eq. 4 and Eq. 24. Each CovD on $\mathcal{S}_{++}^{10}$ was obtained from $m=100$ observations. In the observation space, computing the Stein divergence on an i7 machine using Matlab took 53s. For $S_{\mathcal{H}}$, it took 452s, 566s and 868s when keeping 10, 20 and 50 eigenvectors to estimate the covariances, respectively. While slower, these runtimes remain perfectly acceptable, especially when considering the large accuracy gain that working in RKHS entails, as evidenced by our experiments.

Experimental Evaluation

We now present our empirical results obtained with the infinite-dimensional CovDs and their Bregman divergences defined in Sections 3 and 4. In particular, due to their symmetry and the fact that they yield valid Gaussian kernels, we utilized the Jeffreys and Stein divergences, and relied on two different classifiers for each divergence: A simple nearest neighbor classifier, which clearly evidences the benefits of using infinite-dimensional CovDs, and an SVM classifier with a Gaussian kernel, which further boosts the performance of our infinite-dimensional CovDs.

The different algorithms evaluated in our experiments are referred to as:

$J/S$-NN: Jeffreys/Stein based Nearest Neighbor classifier on CovDs in the observation space.

$J/S$-SVM: Jeffreys/Stein based kernel SVM on CovDs in the observation space.

$J_{\mathcal{H}}/S_{\mathcal{H}}$-NN: Jeffreys/Stein based Nearest Neighbor classifier on infinite-dimensional CovDs.

$J_{\mathcal{H}}/S_{\mathcal{H}}$-SVM: Jeffreys/Stein based kernel SVM on infinite-dimensional CovDs.

We also provide the results of the PLS-based Covariance Discriminant Learning (CDL) technique of , which can be considered as the state-of-the-art for CovD-based classification. In all our experiments, we used the RBF kernel to create infinite-dimensional CovDs. The parameters of our algorithm, i.e., the RBF bandwidth and the number of eigenvectors $r$, were determined by cross-validation.

As a first experiment, we used the virus dataset which contains 15 different virus classes. Each class has 100 images of size $41\times 41$ that were segmented automatically . Samples from the virus dataset are shown in Fig. 1. We used the 10 splits provided with the dataset in a leave-one-out manner, i.e., 10 experiments with 9 splits for training and 1 split as query.

At each pixel $(u,v)$ of an image, we computed the 25-dimensional feature vector

where $I_{u,v}$ is the intensity value, $G^{o,s}_{u,v}$ is the response of a 2D Gabor wavelet with orientation $o$ and scale $s$, and $|\cdot|$ denotes the magnitude of a complex value. Here, we generated 20 Gabor filters at 4 orientations and 5 scales.

We report the mean recognition accuracies over the 10 runs in Table 2. The NN results clearly show that the CovDs computed in RKHS are more discriminative than the ones built directly from the original features. Note that applying kernel SVM boosts the performance of all the CovDs. Note also that our simple NN scheme in RKHS achieves comparable performance to the more involved CDL. Our $J_{\mathcal{H}}/S_{\mathcal{H}}$-SVM methods outperform all the baselines. Here, for each split, the runtimes were on average 130s for the Stein divergence in observation space and 1180s for $S_{\mathcal{H}}$, which remains perfectly practical.

In addition to the baselines in Table 2, we evaluated the performance of Local Binary Patterns (LBP) and Gabor filters , which are popular methods to analyze textures. With an NN classifier, we obtained accuracies of $36.8\%\pm 3.9$ and $33.7\%\pm 4.0$ for LBP and Gabor filters, respectively. This clearly shows the difficulty of this task and the notable improvement achieved by using CovDs.

With this dataset, we also evaluated the performance of the Euclidean metric and asymmetric Burg divergence in RKHS. We obtained $52.4\%$ and $63.5\%$ accuracy for the Euclidean metric and the Burg divergence, respectively. This indicates that a simple Euclidean metric is poorly-suited to handle CovDs. In the remainder of this section, we focus on the Stein and Jeffreys divergences.

2 Material Categorization

We then used the KTH-TIPS2b dataset to perform material categorization. KTH-TIPS2b contains images of 11 materials captured under 4 different illuminations, in 3 poses and at 9 scales. This yields a total of $3\times 4\times 9=108$ images for each sample in a category, with 4 samples per material. We resized the original images to $128\times 128$ pixels and generated CovDs from 1024 observations computed on a coarse grid (i.e., every 4 pixels horizontally and vertically). At each point on the grid, we extracted the 23-dimensional feature vector

where $r_{u,v}$, $g_{u,v}$ and $b_{u,v}$ are the color intensities, and $G^{o,s}_{u,v}$ are the same Gabor filter responses as before.

In Table 3, we report the recognition accuracies computed by training on 3 samples per category and testing on the remaining sample. On average, with an NN classifier, our infinite-dimensional CovDs outperform the $23\times 23$-dimensional ones by more than $4\%$. As before, kernel SVM further improves the performance of all CovDs. This yields a maximum average accuracy of 80.1% for our $S_{\mathcal{H}}$-SVM, which, to the best of our knowledge, is state-of-the-art on this dataset .

3 Texture Classification

For texture classification, we used the Kylberg dataset that contains 28 texture classes of different natural and man-made surfaces. Each class has 160 unique samples imaged with and without rotation. Samples from this dataset are shown in Fig. 3.

As in Section 5.2, we resized the images to $128\times 128$ pixels and generated CovDs from 1024 observations obtained on a coarse grid. The feature vector at each pixel on this grid was taken as

We randomly selected 5 images in each class for training and used the remaining ones as test data.

In Table 4, we report recognition accuracies averaged over 10 such random partitions. As before, NN on infinite-dimensional CovDs clearly outperforms NN on $5\times 5$-dimensional CovDs. Interestingly, it even outperforms the more involved CDL method. With kernel SVM, the accuracies of our $J_{\mathcal{H}}$ and $S_{\mathcal{H}}$ divergences are improved to 91%.

4 Person Re-identification

For person re-identification, we used two sequences from the ETHZ dataset . Sequence 1 contains 83 pedestrians in 4,857 images, and Sequence 2 contains 35 pedestrians in 1,936 images. We resized all images to $48\times 24$ pixels, and, at each pixel ${\boldsymbol{u}}=(u,v)$, computed the 17-dimensional feature vector

where $r_{{\boldsymbol{u}}}$, $g_{{\boldsymbol{u}}}$ and $b_{{\boldsymbol{u}}}$ are the color intensities, and, e.g., for the $r$ channel, \dot{r}_{{\boldsymbol{u}}}\mbox{=}\big{(}\left|{\partial r}\middle/{\partial u}\right|,\left|{\partial r}\middle/{\partial v}\right|\big{)} and \ddot{r}_{{\boldsymbol{u}}}\mbox{=}\big{(}\left|{\partial^{2}r}\middle/{\partial u^{2}}\right|,\left|{\partial^{2}r}\middle/{\partial v^{2}}\right|\big{)}. Following , we randomly selected 10 images from each subject for training and used the rest for testing.

In Table 5, we report the accuracies averaged over 10 random partitions. In addition to the usual baselines, we report the state-of-the-art results obtained with the Symmetry-Driven Accumulation of Local Features (SDALF) of . Once again, both $J_{\mathcal{H}}$-NN and $S_{\mathcal{H}}$-NN outperform $J$-NN and $S$-NN, and similarly for SVM. More importantly, $J_{\mathcal{H}}$-NN and $S_{\mathcal{H}}$-NN outperform SDALF, and even more so with kernel SVM. In supplementary material, we provide the Cumulative Matching Characteristic (CMC) curves that are commonly used for person re-identification.

5 Action Recognition from Motion Capture Data

Finally, we performed an experiment on human action recognition from motion capture sequences using the HDM05 database , which contains 14 different actions. Each action is represented by the 3D locations of 31 joints over time. In our experiments, we only used the 4 joints corresponding to arms and legs. This let us compute a 12-dimensional feature vector per frame by concatenating the 3D locations of these 4 joints in that frame. The CovDs are then computed over the frames. We used a leave-one-subject-out setup, where 4 out of the 5 available subjects were used for training and the remaining one for testing.

In Table 6, we report the average accuracies over the 5 runs. Again, infinite-dimensional CovDs outperform the ones computed from the original observations and yield the best results when used in conjunction with kernel SVM.

Conclusions and Future Work

We have introduced an approach to computing infinite-dimensional CovDs, as well as several Bregman divergences to compare them. Our experimental evaluation has demonstrated that the resulting infinite-dimensional CovDs lead to state-of-the art recognition accuracies on several challenging datasets. In the future, we intend to explore how other types of similarity measures, such as the AIRM, can be computed over infinite-dimensional CovDs. Furthermore, we are interested in studying how the Fréchet mean of a set of infinite-dimensional CovDs can be evaluated. This would allow us to perform clustering, and would therefore pave the way to extending well-known methods, such as bag of words, to infinite dimensional CovDs.

Appendix A Appendix

In the following, we provide the detailed derivation of the Bregman divergences in RKHS considered in Section 4 of the main paper. We also provide the CMC curves for the person re-identification experiment of Section 5.4, which were left out of the main paper due to space limitation.

Appendix B Bregman Divergences on RKHS

Recall that in Section 4 of the main paper, we have exploited the equivalence ${\boldsymbol{W}}_{{\boldsymbol{X}}}^{T}\Phi_{{\boldsymbol{X}}}^{T}\Phi_{{\boldsymbol{X}}}{\boldsymbol{W}}_{{\boldsymbol{X}}}=\Lambda_{{\boldsymbol{X}}}-\rho\mathbf{I}_{\boldsymbol{X}}$ (Eq. 12) to derive Bregman divergences in RKHS. We prove this equivalence below:

We now provide additional details for the specific Bregman divergences considered in the paper. The Euclidean metric in RKHS can be derived as

For the Burg and related divergences (i.e., Jeffreys and Stein divergences), we first show that \det\big{(}\widehat{{\boldsymbol{C}}}_{{\boldsymbol{X}}}\big{)}=\rho^{\mathcal{|H|}}\det\big{(}\rho^{-1}\Lambda_{{\boldsymbol{X}}}\big{)}. To this end, we use the Sylvester determinant theorem, which states that, for two matrices ${\boldsymbol{A}}$ and ${\boldsymbol{B}}$ of size $n\times m$ and $m\times n$, \det\Big{(}\mathbf{I}_{n}+{\boldsymbol{A}}{\boldsymbol{B}}\Big{)}=\det\Big{(}\mathbf{I}_{m}+{\boldsymbol{B}}{\boldsymbol{A}}\Big{)}. Therefore,

We then make use of the Woodbury identity, which states that, for two matrices ${\boldsymbol{A}}$ and ${\boldsymbol{B}}$ of size $n\times m$ and $m\times n$,

Recall from Definition 2.3 that the Burg divergence between to SPD matrices can be written as

Using Eq. 28 and Eq. 15, we can thus derive the Burg divergence in RKHS as

Having the Burg divergence at our disposal, it is straightforward to obtain the Jeffreys divergence, which is given by \frac{1}{2}B_{\mathcal{H}}\big{(}\widehat{{\boldsymbol{C}}}_{{\boldsymbol{X}}},\widehat{{\boldsymbol{C}}}_{{\boldsymbol{Y}}}\big{)}+\frac{1}{2}B_{\mathcal{H}}\big{(}\widehat{{\boldsymbol{C}}}_{{\boldsymbol{Y}}},\widehat{{\boldsymbol{C}}}_{{\boldsymbol{X}}}\big{)}. This divergence can thus be written as

The details of the derivation of the Stein divergence are already given in the main paper. We therefore omit this divergence here.

References