A Caltech Library Service

Non-commutative harmonic analysis in multi-object tracking

Kondor, Risi (2011) Non-commutative harmonic analysis in multi-object tracking. In: Bayesian Time Series Models. Cambridge Books Online. Cambridge University Press , pp. 277-294. ISBN 9780511984679.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Simultaneously tracking n targets in space involves two closely coupled tasks: estimating the current positions x1, x2, . . . , xn of their tracks, and estimating the assignment σ: {1, 2, . . . , n} → {1, 2, . . . , n} of targets to tracks. While the former is often a relatively straightforward extension of the single target case, the latter, called identity management or data association, is a fundamentally combinatorial problem, which is harder to fit in a computationally efficient probabilistic framework. Identity management is difficult because the number of possible assignments grows with n!. This means that for n greater than about 10 or 12, representing the distribution p(σ) explicitly as an array of n! numbers is generally not possible. In this chapter we discuss a solution to this problem based on the generalisation of harmonic analysis to non-commutative groups, specifically, in our case, the group of permutations. According to this theory, the Fourier transform of p takes the form ^p(λ)= Σ_(σ∈S_n)p(σ)pλ(σ) where S_n denotes the group of permutations of n objects, λ is a combinatorial object called an integer partition, and ρλ is a special matrix-valued function called a representation. These terms are defined in our short primer on representation theory in Section 13.2. What is important to note is that, since ρλ is matrix-valued, each Fourier component ^p(λ) is a matrix, not just a scalar. Apart from this surprising feature, non-commutative Fourier transforms are very similar to their familiar commutative counterparts. In particular, we argue that there is a well-defined sense in which some of the ^p(λ) matrices are the ‘low-frequency’ components of p, and approximating p with this subset of components is optimal. A large part of this chapter is focused on how to define such a notion of ‘frequency’, and how to find the corresponding Fourier components.We describe two seemingly very different approaches to answering this question, and find, reassuringly, that they give exactly the same answer. Of course, in addition to a compact way of representing p, efficient inference also demands fast algorithms for updating p with observations. Section 13.6 gives an overview of the fast Fourier methods that are employed for this purpose.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2012 Cambridge University Press. Publisher: Cambridge University Press; Print Publication Year: 2011; Online Publication Date: September 2011. The author thanks Andrew Howard and Tony Jebara for their contributions to [12], the original paper that this chapter is largely based on. He is also indebted to Jonathan Huang, Carlos Guestrin and Leonidas Guibas for various discussions.
Subject Keywords:Pattern Recognition and Machine Learning, Computational statistics, machine learning and information science
Series Name:Cambridge Books Online
Record Number:CaltechAUTHORS:20120522-112345062
Persistent URL:
Official Citation:Barber, David; Cemgil, A. Taylan; and Chiappa, Silvia. Bayesian Time Series Models. Cambridge University Press, 2011. Cambridge Books Online.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:31594
Deposited By: Jason Perez
Deposited On:23 May 2012 18:23
Last Modified:03 Oct 2019 03:53

Repository Staff Only: item control page