Kondor, Risi (2011) Noncommutative harmonic analysis in multiobject tracking. In: Bayesian Time Series Models. Cambridge Books Online. Cambridge University Press , pp. 277294. ISBN 9780511984679. https://resolver.caltech.edu/CaltechAUTHORS:20120522112345062

PDF
 Published Version
See Usage Policy. 334Kb 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20120522112345062
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 noncommutative 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 matrixvalued 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 matrixvalued, each Fourier component ^p(λ) is a matrix, not just a scalar. Apart from this surprising feature, noncommutative Fourier transforms are very similar to their familiar commutative counterparts. In particular, we argue that there is a welldefined sense in which some of the ^p(λ) matrices are the ‘lowfrequency’ 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: 
 
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:20120522112345062  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:20120522112345062  
Official Citation:  Barber, David; Cemgil, A. Taylan; and Chiappa, Silvia. Bayesian Time Series Models. Cambridge University Press, 2011. Cambridge Books Online. http://dx.doi.org/10.1017/CBO9780511984679.014  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  31594  
Collection:  CaltechAUTHORS  
Deposited By:  Jason Perez  
Deposited On:  23 May 2012 18:23  
Last Modified:  03 Oct 2019 03:53 
Repository Staff Only: item control page