TY - JOUR
T1 - Inference in particle tracking experiments by passing messages between images
AU - Chertkov, M.
AU - Kroc, L.
AU - Krzakala, F.
AU - Vergassola, M.
AU - Zdeborová, L.
PY - 2010/4/27
Y1 - 2010/4/27
N2 - Methods to extract information from the tracking of mobile objects/particles have broad interest in biological and physical sciences. Techniques based on simple criteria of proximity in time-consecutive snapshots are useful to identify the trajectories of the particles. However, they become problematic as the motility and/or the density of the particles increases due to uncertainties on the trajectories that particles followed during the images' acquisition time. Here, we report an efficient method for learning parameters of the dynamics of the particles from their positions in time-consecutive images. Our algorithm belongs to the class of message-passing algorithms, known in computer science, information theory, and statistical physics as belief propagation (BP). The algorithm is distributed, thus allowing parallel implementation suitable for computations on multiple machines without significant intermachine overhead. We test our method on the model example of particle tracking in turbulent flows, which is particularly challenging due to the strong transport that those flows produce. Our numerical experiments show that the BP algorithm compares in quality with exact Markov Chain Monte Carlo algorithms, yet BP is far superior in speed. We also suggest and analyze a random distance model that provides theoretical justification for BP accuracy. Methods developed here systematically formulate the problem of particle tracking and provide fast and reliable tools for the model's extensive range of applications.
AB - Methods to extract information from the tracking of mobile objects/particles have broad interest in biological and physical sciences. Techniques based on simple criteria of proximity in time-consecutive snapshots are useful to identify the trajectories of the particles. However, they become problematic as the motility and/or the density of the particles increases due to uncertainties on the trajectories that particles followed during the images' acquisition time. Here, we report an efficient method for learning parameters of the dynamics of the particles from their positions in time-consecutive images. Our algorithm belongs to the class of message-passing algorithms, known in computer science, information theory, and statistical physics as belief propagation (BP). The algorithm is distributed, thus allowing parallel implementation suitable for computations on multiple machines without significant intermachine overhead. We test our method on the model example of particle tracking in turbulent flows, which is particularly challenging due to the strong transport that those flows produce. Our numerical experiments show that the BP algorithm compares in quality with exact Markov Chain Monte Carlo algorithms, yet BP is far superior in speed. We also suggest and analyze a random distance model that provides theoretical justification for BP accuracy. Methods developed here systematically formulate the problem of particle tracking and provide fast and reliable tools for the model's extensive range of applications.
KW - Belief propagation
KW - Message passing
KW - Particle image velocimetry
KW - Statistical inference
KW - Turbulence
UR - http://www.scopus.com/inward/record.url?scp=77952375742&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952375742&partnerID=8YFLogxK
U2 - 10.1073/pnas.0910994107
DO - 10.1073/pnas.0910994107
M3 - Article
C2 - 20368454
AN - SCOPUS:77952375742
SN - 0027-8424
VL - 107
SP - 7663
EP - 7668
JO - Proceedings of the National Academy of Sciences of the United States of America
JF - Proceedings of the National Academy of Sciences of the United States of America
IS - 17
ER -