{'fraction_non_alphanumeric': 0.02336696760488582, 'fraction_numerical': 0.0037174721189591076, 'mean_word_length': 5.386440677966101, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Solving the data association problem in multi-object tracking by Fourier analysis on the symmetric group

In addition to modeling the position of individual targets, multi-object tracking must also address the combinatorial problem of matching objects to corresponding tracks. In general, maintaining a probability distribution over all n! possibilities is clearly infeasible, while just maintaining an n×n matrix of “first order marginals” is a very impoverished representation. In this work we explain how to harness the theory of harmonic analysis on the symmetric group to get a hierarchy of approximations of increasing fidelity to this problem. Importatantly, not only are such band-limited approximations theoretically well justifiable, but they also admit efficient observations updates based on some ideas from Clausen’s FFT for the symmetric group. Experiments show that our algebraic approach can outperform more conventional solutions to the data association problem while still remaining computationalliy feasible for n in the 30 ∼ 40 range. The theory of group representations leads to an elegant generalization of Fourier transformation to arbitrary compact groups, even non-commutative one, such as the symmetric group Sn of permutations of n objects. Diaconis’ well known book [1] has done a lot to popularize this theory in the statistics community, but its applicability to machine learning has until lately been largely unexplored. The recent paper [3] by the present authors was the first to show the relevance of this theory to the data association problem, shortly followed by [2] which developed the framework even further. In general, the idea is that given a (continuous time) noise model on matchings, the space of distributions p(σ) over permutations splits into different modes, and we find that the “low-frequency” modes correspond to Fourier components