Dynamic Regret Bound for Moving Target Tracking Based on Online Time-of-Arrival Measurements

Abstract

The use of online algorithms to track a moving target is gaining attention in the control community for its simpler and faster computation. In this work, we study the dynamic regret of online gradient descent (OGD) for tackling a time-of-arrival (TOA)-based least-squares formulation of the tracking problem. Since the formulation is non-convex, most existing dynamic regret analyses cannot be applied to it directly. To circumvent this difficulty, we proceed in two steps. First, we show that under standard assumptions on the TOA measurement noise, the loss function at each time step will, with high probability, be locally strongly convex at that time step. Moreover, we give an explicit estimate of the size of the strong convexity region. To the best of our knowledge, this result is new and can be of independent interest. Second, we show that under the aforementioned assumptions on the TOA measurement noise and mild assumptions on the target trajectory, the location estimate of the target at each time step will lie in the strong convexity region of the loss function at the next time step with high probability. This allows us to exploit existing analysis for online strongly convex optimization to give the first dynamic regret bound of OGD for the TOA-based target tracking problem. Simulation results are presented to illustrate our theoretical findings. Show more