Reasoning over combinatorial spaces for multi-object inference
Abstract/Contents
- Abstract
- In this thesis, we study a set of tools and methodology for reasoning over combinatorial spaces, i.e., permutations and homogeneous spaces, with applications to multi-object tracking. Recently, the Fourier machinery for representing distributions over permutations has been introduced. Due to the uncertainty principle, the Fourier representation suffers from high complexity for representing sparse distributions. We present an algorithm that can adaptively decompose the large tracking problem into independent components under the Fourier representation framework. Such an adaptive algorithm helps greatly to improve the scalability of the non-adaptive Fourier approach. Another line of research of representing distributions over permutations uses the information form representation for the problem. We identify an interesting duality relationship between Fourier representations and the information form representations. The pros and cons of the two representations compensate for each other, which motivates us to develop a hybrid algorithm that can switch between two representation forms. It turns out that using a hybrid approach can yield better balance between inference accuracy and scalability. In many cases, it suffices to tell the class of a moving object, say if it is a friend or foe, rather than exactly tell who it is. In such a case, one can collapse the space of permutations to a smaller combinatorial space, e.g., a homogeneous space. It turns out that the Fourier bases for permutations are then collapsed into Radon bases. The binary structure of the Radon bases allows us to do several computations in a very fast way. With the Radon machinery, we study the property management problem using a novel over-complete bases representation framework. We also consider an inverse problem based on Radon base representations, which can help us to discover high level community structures about the objects of interest. An optimization problem that can identify the community structures among the objects is formulated. Such an optimization problem has theoretical guarantees about the existence, correctness, uniqueness, and stability of the solution. We also develop a column generation based approximation algorithm, which achieves polynomial time complexity for this problem. We justify our results with experiments on real-world data.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Jiang, Xiaoye |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Guibas, Leonidas J |
| Thesis advisor | Guibas, Leonidas J |
| Thesis advisor | Carlsson, Gunnar |
| Thesis advisor | Ye, Yinyu |
| Advisor | Carlsson, Gunnar |
| Advisor | Ye, Yinyu |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Xiaoye Jiang. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Xiaoye Jiang
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...