Local Strong Convexity of Source Localization and Error Bound for Target Tracking under Time-of-Arrival Measurements

Yuen-Man Pun, Anthony Man-Cho SoIEEE TSP 2022 · DOI · OpenReview

Introduction

Target tracking—estimating the position of a moving object using noisy signals—is a cornerstone of robotics, surveillance, and wireless sensor networks. One of the most common approaches uses Time-of-Arrival (TOA) measurements, where sensors record when a signal from the target arrives to calculate distance. This paper provides a theoretical breakthrough by proving that the non-convex loss function used in TOA localization is actually locally strongly convex around its global minima.

The Challenge of Non-Convexity

Mathematically, target tracking is usually framed as a sequential least-squares problem. However, researchers face two major hurdles:

  1. Non-Convexity: The TOA loss function is non-convex, meaning standard optimization proofs (which usually assume convexity) don't easily apply.
  2. Computational Constraints: In real-time tracking, sensors often have limited power and very little time between measurements. Solving a complex optimization problem to perfection at every millisecond is impractical.

While previous research suggested using Online Newton’s Method (ONM), that approach is computationally expensive and lacked a rigorous proof of effectiveness under TOA-specific conditions.

Methodology: Bridging Theory and Practice

The authors bridge the gap between theory and practice using a two-step analytical approach:

  • Static Analysis: They prove that under standard noise assumptions and sensor geometries, the loss function is locally strongly convex in a neighborhood around the least-squares estimate.
  • Dynamic Analysis: They apply Online Gradient Descent (OGD) to the tracking problem. By using their new local strong convexity results, they prove that if the target's movement and noise levels are "well-behaved," the OGD iterates will stay within the "safe" strongly convex region of the next time step's loss function.
  • Performance Metric: Instead of abstract metrics like "regret," they use Cumulative Target Tracking Error (CTTE), which directly measures the physical distance between the algorithm's estimate and the target's actual position.

Key Insights: OGD as a Natural Smoother

A key "aha" moment in the research is the realization that OGD's relative "laziness" compared to second-order methods is actually a feature. In high-noise scenarios, Online Newton’s Method (ONM) tends to overfit to the noisy optimal solution of the current time step. Because OGD is a first-order method and moves more "slowly," it acts as a natural smoother, often staying closer to the true trajectory than the more aggressive ONM.

Target trajectory tracking under diminishing noise ($\sigma_t = 0.01/\sqrt{t}$). OGD (blue) acts as a natural smoother compared to the more volatile ONM (red) and LS estimates (green).

Key Results and Robustness

The authors established a sublinear bound for CTTE, meaning the average tracking error eventually vanishes if the target's speed and noise levels are bounded. Numerical simulations validated these findings:

  • Stability: OGD is significantly more stable than ONM when noise levels are high or when the target's path varies significantly.
  • Speed: OGD is computationally lighter, running 2–3 times faster than ONM. In MATLAB simulations, OGD iterations took approximately $5 \times 10^{-6}$ seconds, compared to $1.3 \times 10^{-5}$ seconds for ONM.
Cumulative Target Tracking Error (CTTE) under high noise ($\sigma_t = 0.01$), showing OGD's superior stability over ONM.

Conclusion

By proving the local strong convexity of the TOA loss function, this work justifies the use of simple, low-complexity algorithms for complex tracking tasks. OGD not only provides theoretical guarantees but also outperforms more complex methods in practical, noisy environments. Future work will extend this analysis to Time-Difference-of-Arrival (TDOA) measurements and explore further online optimization variants.

Summary updated

Abstract

In this paper, we consider a time-varying optimization approach to the problem of tracking a moving target using noisy time-of-arrival (TOA) measurements. Specifically, we formulate the problem as that of sequential TOA-based source localization and apply online gradient descent (OGD) to it to generate the position estimates of the target. To analyze the tracking performance of OGD, we first revisit the classic least-squares formulation of the (static) TOA-based source localization problem and elucidate its estimation and geometric properties. In particular, under standard assumptions on the TOA measurement model, we establish a bound on the distance between an optimal solution to the least-squares formulation and the true target position. Using this bound, we show that the loss function in the formulation, albeit non-convex in general, is locally strongly convex at its global minima. To the best of our knowledge, these results are new and can be of independent interest. By combining them with existing techniques from online strongly convex optimization, we then establish the first non-trivial bound on the cumulative target tracking error of OGD. Our numerical results corroborate the theoretical findings and show that OGD can effectively track the target at different noise levels.
BibTeX
@article{pun2022local,
  author = {Yuen-Man Pun and Anthony Man-Cho So},
  title = {{Local Strong Convexity of Source Localization and Error Bound for Target Tracking under Time-of-Arrival Measurements}},
  journal = {IEEE Trans. Signal Process.},
  year = {2022},
  doi = {10.1109/tsp.2021.3137953},
}
Figure