Space-time localization using times of arrival

We provide a computationally efficient framework for utilizing Time of Arrival (ToA) sensors to localize multiple events in close proximity in space and time. Conventional ToA-based localization algorithms are typically designed for single events. Naive approaches for associating ToAs with events and then applying a conventional localization algorithm incur complexity exponential in the number of sensors. An alternative approach of hypothesis testing over a space-time grid also has excessive complexity for large deployment regions. We propose an approach that sidesteps such computational bottlenecks by using discretization in time to efficiently generate a list of candidate events (including true as well as "phantom" events), and then employ statistical techniques to refine these estimates and to solve the ToA-to-event matching problem using linear programming on a bipartite graph. The algorithm automatically rejects phantom events and accounts for misses and outliers, providing performance close to that of a genie-based algorithm with ideal knowledge of ToA-to-event matching.