Jensen-Bregman LogDet divergence with application to efficient similarity search for covariance matrices

Anoop Cherian, Suvrit Sra, Arindam Banerjee, Nikolaos P Papanikolopoulos

Research output: Contribution to journalArticle

81 Citations (Scopus)

Abstract

Covariance matrices have found success in several computer vision applications, including activity recognition, visual surveillance, and diffusion tensor imaging. This is because they provide an easy platform for fusing multiple features compactly. An important task in all of these applications is to compare two covariance matrices using a (dis)similarity function, for which the common choice is the Riemannian metric on the manifold inhabited by these matrices. As this Riemannian manifold is not flat, the dissimilarities should take into account the curvature of the manifold. As a result, such distance computations tend to slow down, especially when the matrix dimensions are large or gradients are required. Further, suitability of the metric to enable efficient nearest neighbor retrieval is an important requirement in the contemporary times of big data analytics. To alleviate these difficulties, this paper proposes a novel dissimilarity measure for covariances, the Jensen-Bregman LogDet Divergence (JBLD). This divergence enjoys several desirable theoretical properties and at the same time is computationally less demanding (compared to standard measures). Utilizing the fact that the square root of JBLD is a metric, we address the problem of efficient nearest neighbor retrieval on large covariance datasets via a metric tree data structure. To this end, we propose a K-Means clustering algorithm on JBLD. We demonstrate the superior performance of JBLD on covariance datasets from several computer vision applications.

Original languageEnglish (US)
Article number6378374
Pages (from-to)2161-2174
Number of pages14
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume35
Issue number9
DOIs
StatePublished - Aug 2 2013

Fingerprint

Bregman Divergence
Similarity Search
Covariance matrix
Computer vision
Metric
Diffusion tensor imaging
Computer Vision
Nearest Neighbor
Retrieval
Visual Surveillance
Clustering algorithms
Dissimilarity Measure
Activity Recognition
Data structures
K-means Algorithm
K-means Clustering
Dissimilarity
Riemannian Metric
Tree Structure
Square root

Keywords

  • Bregman divergence
  • LogDet divergence
  • Region covariance descriptors
  • activity recognition
  • image search
  • nearest neighbor search
  • video surveillance

Cite this

@article{3b490b7745c244daa49885aa62e3507d,
title = "Jensen-Bregman LogDet divergence with application to efficient similarity search for covariance matrices",
abstract = "Covariance matrices have found success in several computer vision applications, including activity recognition, visual surveillance, and diffusion tensor imaging. This is because they provide an easy platform for fusing multiple features compactly. An important task in all of these applications is to compare two covariance matrices using a (dis)similarity function, for which the common choice is the Riemannian metric on the manifold inhabited by these matrices. As this Riemannian manifold is not flat, the dissimilarities should take into account the curvature of the manifold. As a result, such distance computations tend to slow down, especially when the matrix dimensions are large or gradients are required. Further, suitability of the metric to enable efficient nearest neighbor retrieval is an important requirement in the contemporary times of big data analytics. To alleviate these difficulties, this paper proposes a novel dissimilarity measure for covariances, the Jensen-Bregman LogDet Divergence (JBLD). This divergence enjoys several desirable theoretical properties and at the same time is computationally less demanding (compared to standard measures). Utilizing the fact that the square root of JBLD is a metric, we address the problem of efficient nearest neighbor retrieval on large covariance datasets via a metric tree data structure. To this end, we propose a K-Means clustering algorithm on JBLD. We demonstrate the superior performance of JBLD on covariance datasets from several computer vision applications.",
keywords = "Bregman divergence, LogDet divergence, Region covariance descriptors, activity recognition, image search, nearest neighbor search, video surveillance",
author = "Anoop Cherian and Suvrit Sra and Arindam Banerjee and Papanikolopoulos, {Nikolaos P}",
year = "2013",
month = "8",
day = "2",
doi = "10.1109/TPAMI.2012.259",
language = "English (US)",
volume = "35",
pages = "2161--2174",
journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
issn = "0162-8828",
publisher = "IEEE Computer Society",
number = "9",

}

TY - JOUR

T1 - Jensen-Bregman LogDet divergence with application to efficient similarity search for covariance matrices

AU - Cherian, Anoop

AU - Sra, Suvrit

AU - Banerjee, Arindam

AU - Papanikolopoulos, Nikolaos P

PY - 2013/8/2

Y1 - 2013/8/2

N2 - Covariance matrices have found success in several computer vision applications, including activity recognition, visual surveillance, and diffusion tensor imaging. This is because they provide an easy platform for fusing multiple features compactly. An important task in all of these applications is to compare two covariance matrices using a (dis)similarity function, for which the common choice is the Riemannian metric on the manifold inhabited by these matrices. As this Riemannian manifold is not flat, the dissimilarities should take into account the curvature of the manifold. As a result, such distance computations tend to slow down, especially when the matrix dimensions are large or gradients are required. Further, suitability of the metric to enable efficient nearest neighbor retrieval is an important requirement in the contemporary times of big data analytics. To alleviate these difficulties, this paper proposes a novel dissimilarity measure for covariances, the Jensen-Bregman LogDet Divergence (JBLD). This divergence enjoys several desirable theoretical properties and at the same time is computationally less demanding (compared to standard measures). Utilizing the fact that the square root of JBLD is a metric, we address the problem of efficient nearest neighbor retrieval on large covariance datasets via a metric tree data structure. To this end, we propose a K-Means clustering algorithm on JBLD. We demonstrate the superior performance of JBLD on covariance datasets from several computer vision applications.

AB - Covariance matrices have found success in several computer vision applications, including activity recognition, visual surveillance, and diffusion tensor imaging. This is because they provide an easy platform for fusing multiple features compactly. An important task in all of these applications is to compare two covariance matrices using a (dis)similarity function, for which the common choice is the Riemannian metric on the manifold inhabited by these matrices. As this Riemannian manifold is not flat, the dissimilarities should take into account the curvature of the manifold. As a result, such distance computations tend to slow down, especially when the matrix dimensions are large or gradients are required. Further, suitability of the metric to enable efficient nearest neighbor retrieval is an important requirement in the contemporary times of big data analytics. To alleviate these difficulties, this paper proposes a novel dissimilarity measure for covariances, the Jensen-Bregman LogDet Divergence (JBLD). This divergence enjoys several desirable theoretical properties and at the same time is computationally less demanding (compared to standard measures). Utilizing the fact that the square root of JBLD is a metric, we address the problem of efficient nearest neighbor retrieval on large covariance datasets via a metric tree data structure. To this end, we propose a K-Means clustering algorithm on JBLD. We demonstrate the superior performance of JBLD on covariance datasets from several computer vision applications.

KW - Bregman divergence

KW - LogDet divergence

KW - Region covariance descriptors

KW - activity recognition

KW - image search

KW - nearest neighbor search

KW - video surveillance

UR - http://www.scopus.com/inward/record.url?scp=84880825073&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880825073&partnerID=8YFLogxK

U2 - 10.1109/TPAMI.2012.259

DO - 10.1109/TPAMI.2012.259

M3 - Article

VL - 35

SP - 2161

EP - 2174

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

SN - 0162-8828

IS - 9

M1 - 6378374

ER -