Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2011 | Published
Book Section - Chapter Open

Non-commutative harmonic analysis in multi-object tracking

Abstract

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.

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.

Attached Files

Published - Kondor2011p18235.pdf

Files

Kondor2011p18235.pdf
Files (342.2 kB)
Name Size Download all
md5:3435ca4221e971ba8a270430a6f615eb
342.2 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024