Consistent and Asymptotically Efficient Localization from Range-Difference Measurements

Guangyang Zeng, Biqiang Mu, Ling Shi, Jiming Chen, Junfeng Wu

Abstract

We consider signal source localization from range-difference measurements. First, we give some readily-checked conditions on measurement noises and sensor deployment to guarantee the asymptotic identifiability of the model and show the consistency and asymptotic normality of the maximum likelihood (ML) estimator. Then, we devise an estimator that owns the same asymptotic property as the ML one. Specifically, we prove that the negative log-likelihood function converges to a function, which has a unique minimum and positive definite Hessian at the true source's position. Hence, it is promising to execute local iterations, e.g., the Gauss-Newton (GN) algorithm, following a consistent estimate. The main issue involved is obtaining a preliminary consistent estimate. To this aim, we construct a linear least-squares problem via algebraic operation and constraint relaxation and obtain a closed-form solution. We then focus on deriving and eliminating the bias of the linear least-squares estimator, which yields an asymptotically unbiased (thus consistent) estimate. Noting that the bias is a function of the noise variance, we further devise a consistent noise variance estimator that involves 3-order polynomial rooting. Based on the preliminary consistent location estimate, a one-step GN iteration suffices to achieve the same asymptotic property as the ML estimator. Simulation results demonstrate the superiority of our proposed algorithm in the large sample case.

Introduction

Locating a signal source via Time Difference of Arrival (TDOA) is a classic problem in signal processing, essential for applications such as GPS, battlefield monitoring, and smart advertising. Mathematically, this involves finding the intersection of multiple hyperboloids, which constitutes a challenging non-convex optimization problem.

TDOA localization geometry showing the source position $\mathbf{x}^o$, sensors $\mathbf{a}_i$, and range measurements $d_i$.

While Maximum Likelihood (ML) estimation is the gold standard for accuracy, it is notoriously difficult to solve because the objective function is often full of local minima. Existing solutions generally fall into two categories: iterative methods that require a near-perfect initial guess to avoid local minima, and sub-optimal relaxations that often introduce biases or fail to reach the theoretical Cramer-Rao Lower Bound (CRLB) as data availability increases.

Methodology

This paper proposes a "Two-Step Estimator" strategy that is both computationally fast ($O(m)$ complexity) and statistically optimal.

Step 1: Bias-Eliminated Linear Least-Squares

The researchers first transform the non-linear TDOA equations into a linear least-squares problem. Standard linearizations are typically biased because the noise in the equations becomes correlated with the regressors. The authors derive an exact mathematical expression for this asymptotic bias and subtract it. Crucially, they include a sub-algorithm that estimates the unknown noise variance ($\sigma^2$) on the fly using 3rd-order polynomial rooting, making the system robust to unknown environments.

Step 2: One-Step Gauss-Newton Refinement

A major theoretical contribution of this work is proving that if the first step provides a "consistent" estimate, performing exactly one iteration of the Gauss-Newton (GN) algorithm is mathematically sufficient to reach the same statistical efficiency as the full ML estimator. This drastically reduces computational overhead compared to traditional iterative solvers.

Results and Key Insights

The algorithm was validated through extensive synthetic simulations with up to 3,000 sensors. The results demonstrate that the proposed "Bias-Eli + GN" method consistently reaches the CRLB as the number of measurements increases, outperforming established methods like "BiasRed" and "GTRS-MPR."

Likelihood surfaces for varying numbers of sensors $m$. As $m$ increases from 4 to 4000, the consistent estimate (red dot) converges to the true position (red triangle) as the objective function's global minimum becomes more pronounced.

As shown in the likelihood surface visualizations, the "attraction region" around the true location expands as the sample size grows. This justifies the strategy of using a consistent starting point followed by local refinement. The algorithm maintains linear time complexity, achieving real-time processing rates (100 Hz) even with thousands of measurements.

Conclusion

This paper provides a robust framework for TDOA localization that guarantees consistency and asymptotic efficiency. While the current model assumes i.i.d. Gaussian noise and a static source, future work will focus on adapting this framework for Non-Line-of-Sight (NLOS) environments and tracking high-speed moving targets.

Summary updated

Abstract

We consider signal source localization from range-difference measurements. First, we give some readily-checked conditions on measurement noises and sensor deployment to guarantee the asymptotic identifiability of the model and show the consistency and asymptotic normality of the maximum likelihood (ML) estimator. Then, we devise an estimator that owns the same asymptotic property as the ML one. Specifically, we prove that the negative log-likelihood function converges to a function, which has a unique minimum and positive definite Hessian at the true source's position. Hence, it is promising to execute local iterations, e.g., the Gauss-Newton (GN) algorithm, following a consistent estimate. The main issue involved is obtaining a preliminary consistent estimate. To this aim, we construct a linear least-squares problem via algebraic operation and constraint relaxation and obtain a closed-form solution. We then focus on deriving and eliminating the bias of the linear least-squares estimator, which yields an asymptotically unbiased (thus consistent) estimate. Noting that the bias is a function of the noise variance, we further devise a consistent noise variance estimator that involves $3$-order polynomial rooting. Based on the preliminary consistent location estimate, a one-step GN iteration suffices to achieve the same asymptotic property as the ML estimator. Simulation results demonstrate the superiority of our proposed algorithm in the large sample case.
BibTeX
@article{zeng2023consistent,
  author = {Guangyang Zeng and Biqiang Mu and Ling Shi and Jiming Chen and Junfeng Wu},
  title = {{Consistent and Asymptotically Efficient Localization from Range-Difference Measurements}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
}
Figure