Improved Time of Arrival measurement model for non‐convex optimization

Juri Sidorenko, Leo R. Ya. Doktorski, Volker Schatz, Norbert Scherer‐Negenborn, Michael Arens, Urs HugentoblerNAVIGATION 2019 · DOI

TL;DR

This paper tackles a common problem in Time of Arrival (ToA) based localization: optimization algorithms can get stuck in local minima, leading to inaccurate position estimates. The authors propose a novel approach by introducing an additional dimension to the optimization problem, effectively transforming local minima into saddle points. This modification significantly reduces the risk of converging to a suboptimal solution, leading to more reliable localization.

What Problem Does This Paper Address?

Accurate positioning is crucial in many applications, from GPS and mobile phone tracking to radar and acoustic systems. The Time of Arrival (ToA) technique is a popular method for determining an object's position by measuring the time it takes for signals to travel from known base stations to the object. Mathematically, this often results in a system of quadratic equations. While these systems can be solved analytically or using optimization algorithms, a major challenge arises with non-convex optimization: algorithms can converge to a local minimum instead of the true global minimum, yielding an incorrect position estimate. This is particularly problematic when the initial guess for the object's position is not ideal. Existing methods sometimes transform the problem into a linear system, but this can be more susceptible to noise. This paper aims to address the issue of local minima convergence in ToA localization by proposing a modified objective function.

Methods

The core of the proposed solution lies in modifying the objective function used for optimization. The authors introduce an additional variable, denoted by $\lambda$, to the standard ToA objective functions ($F_1$ and $F_2$). This augmentation results in new objective functions, $F_{L1}$ and $F_{L2}$. The key idea is that by increasing the dimensionality of the problem, local minima of the original functions are transformed into saddle points in the higher-dimensional space. This transformation is crucial because standard gradient-based optimization algorithms, like the Levenberg-Marquardt algorithm used in this paper, are designed to avoid saddle points, thus increasing the likelihood of converging to the global minimum. While inspired by techniques like dimension lifting, the authors emphasize that their problem remains non-convex. They provide a mathematical proof for the objective function $F_2$, demonstrating that its local minima become saddle points in the augmented problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical simulations using randomly generated base station constellations and initial estimates.

Key Insights and Ideas

  • Local Minima are a Major Hurdle: The paper clearly articulates that the non-convex nature of ToA optimization problems is a significant practical challenge, leading to unreliable position estimates.
  • Dimension Lifting for Optimization Stability: The novel idea of introducing an extra dimension to transform local minima into saddle points is the paper's central contribution. This is a clever way to leverage the behavior of optimization algorithms.
  • Saddle Points as a Solution: By making local minima saddle points, the paper exploits the tendency of gradient descent-based methods to move away from them, thereby guiding the optimization towards the global minimum.
  • Non-Convexity Persists, but is Managed: Unlike some dimension-lifting techniques that aim for convexity, this approach maintains non-convexity but effectively circumvents the local minima problem.
  • The Power of an Additional Variable: The simple addition of a single variable ($\lambda$) proves to be a powerful tool for stabilizing the optimization process.

Key Results

The paper presents strong evidence that the proposed method significantly reduces the occurrence of local minima.

  • Numerical Simulations: Extensive simulations using the Levenberg-Marquardt algorithm show that the improved objective functions ($F_{L1}$ and $F_{L2}$) consistently converge to the global minimum, while the original functions ($F_1$ and $F_2$) frequently converge to local minima.
  • Error Reduction: Tables 7 and 8 demonstrate a dramatic reduction in the "error bigger than 0.5" metric (representing local minima) when using the improved objective functions. For instance, with 4 base stations in a 2D model, $F_1$ resulted in 1357 local minima, whereas $F_{L1}$ resulted in 0. Similar improvements are seen across various numbers of base stations and dimensions.
  • Mean Error: The mean error and standard deviation are also generally lower for the improved objective functions, indicating more accurate overall results.
  • Proof for $F_2$: A mathematical proof is provided showing that local minima of $F_2$ become saddle points for $F_{L2}$.

Limitations and Future Work

  • Proof for $F_1$ is Missing: While numerical results strongly suggest that $F_{L1}$ also transforms local minima of $F_1$ into saddle points, an analytical proof is not provided.
  • Known Base Station Positions: The current approach assumes that the positions of the base stations are known. The authors mention that determining base station positions simultaneously with the object's location is a more complex problem where their approach would be even more valuable.
  • Initial Estimate for $\lambda$: The optimization of $F_{L2}$ requires a non-zero initial estimate for the additional variable $\lambda$. If $\lambda$ starts at zero, $F_{L2}$ effectively reduces to $F_2$, negating the benefit.
  • Future Work: The authors suggest that their approach becomes extremely valuable in scenarios where base station positions are unknown, which is a natural extension of this work.

Summary updated

Abstract

The quadratic system provided by the Time of Arrival technique can be solved analytically or by optimization algorithms. In practice, a combination of both methods is used. An important problem in quadratic optimization is the possible convergence to a local minimum, instead of the global minimum. This article presents an approach how this risk can be significantly reduced. The main idea of our approach is to transform the local minimum to a saddle point, by increasing the number of dimensions. In contrast to similar methods such as, dimension lifting does our problem remains non-convex.
BibTeX
@inproceedings{sidorenko2019improved,
  author = {Juri Sidorenko and Leo R. Ya. Doktorski and Volker Schatz and Norbert Scherer‐Negenborn and Michael Arens and Urs Hugentobler},
  title = {{Improved Time of Arrival measurement model for non‐convex optimization}},
  booktitle = {NAVIGATION},
  year = {2019},
  doi = {10.1002/navi.277},
}
Figure