General analytical theory of the AOWA adaptive time-of-flight estimation scheme: multi-outlier-class extension, robustness to classifier mis-specification, and worst-case energy

The 2014 paper of Apartsin, Cooper, and Intrator introduced AOWA, an adaptive version of optimal weighted averaging for time-of-flight (ToF) estimation in the near-threshold SNR regime where matched-filter estimates are corrupted by autocorrelation side-lobe outliers: a per-ping classifier labels each bias-corrected estimate as an inlier or as one of several outlier classes, pings are acquired adaptively until $k$ inlier-labeled measurements are collected (with a cap of $N$), and the measurements are fused with weights inverse to their label-conditional mean-square errors. The paper's closed-form performance results — the strict positivity of the expected-MSE advantage of adaptive over average-energy-matched non-adaptive acquisition, and a conditioned negative-binomial expected-pulse formula — are derived only for a simplified model with one inlier and one outlier class, exactly known and stationary label statistics, and average-case energy accounting. The open problem is to build the corresponding general analytical theory: extend the expected-error comparison and the pulse-count and composition laws it requires to the full multi-outlier-class model, quantify robustness to mis-estimated classifier statistics and nonstationary SNR, and characterize and control the worst-case energy consumption of the $k$–$N$ stopping rule.

Background

Time-of-flight (ToF) estimation — recovering the unknown delay $t_0$ between a transmitted pulse $s(t)$ and its noisy echo — is the basic measurement step in sonar, ultrasound, radar, and lidar ranging. The standard estimator correlates the received signal with a replica of the transmitted waveform and takes the peak of the correlation; this matched-filter receiver is the maximum-likelihood estimator (MLE) of the delay and is essentially optimal at high signal-to-noise ratio (SNR). Below a certain SNR, however, its mean-square error (MSE) rises abruptly — the threshold effect. For narrowband pulses the effect is driven by outliers: noise elevates a side lobe of the signal's autocorrelation function (the correlation of the waveform with a shifted copy of itself) above the main peak, so the estimator locks onto the wrong peak and returns a badly biased delay. Operating near or below threshold is often unavoidable when the power of a single pulse or the total energy of a measurement is limited.

Apartsin, Cooper, and Intrator developed a remedy inspired by biosonar (the echolocation used by bats and dolphins) in a series of works (an MLSP 2010 paper, two JASA papers, a 2013 DTIC report, and two IEEE TGRS 2014 companion papers). A bank of phase-shifted unmatched filters — filters that do not match the transmitted waveform and therefore return deliberately biased delay estimates — provides, per ping (one transmitted pulse and its echo), a feature vector of biased estimates relative to the matched-filter MLE. A decision-tree classifier trained offline maps this feature vector to a label $K\in\{-l,\dots,0,\dots,l\}$, where label 0 denotes the main autocorrelation peak (the inlier class) and nonzero labels denote particular side-lobe peaks (outlier classes). Training also yields, per label, a bias correction and a conditional squared error $e_j^2=E[(\hat t-t_0)^2\mid K=j]$. Fusing the bias-corrected estimates of several pings by optimal weighted averaging (OWA) — weights inversely proportional to the label-conditional squared errors,

$e_{\mathrm{wa}}^2=\left(\sum_{i=1}^{N}\frac{1}{e_{K_i}^2}\right)^{-1},$

suppresses both the bias and the excess variance that outliers inject into plain averaging.

The source paper of this problem adds the energy dimension. Instead of fixing the number of pings in advance, the adaptive scheme (AOWA) keeps transmitting pings until it has collected $k$ pings labeled inlier, with a hard cap of $N$ pings (the $k$–$N$ rule), and then fuses them by OWA. Because inlier-labeled pings are the informative ones, stopping on the inlier count spends less energy on average for the same accuracy. The paper supports this with closed-form analytical results derived in a simplified model with a single inlier class $I$ and a single outlier class $O$, whose labels across pings are independent Bernoulli trials with inlier probability $q_I$: (i) an adaptive 1–2 scheme (take a second ping only if the first was labeled outlier) strictly improves the expected fused MSE relative to a non-adaptive randomized scheme constrained to the same expected pulse count $2-q_I$ — a coin-flip baseline that decides its ping count before measuring; and (ii) the expected number of pings of the $k$–$N$ rule, obtained by observing that the number of outlier pings before the $k$-th inlier follows a negative-binomial distribution (the number of failures before the $k$-th success in independent Bernoulli trials) and conditioning on stopping by the cap: $E[k+N_O\mid N_O\le N-k]=\frac{k}{q_I}(1-\alpha)$, with $\alpha$ built from the negative-binomial probability mass function and cumulative distribution function. Monte Carlo simulations in the near-threshold narrowband regime confirm average energy savings and suggest design preferences (small $k$, larger $N$).

These analytical results idealize the scheme as actually defined in three ways, and closing that gap is the problem stated here: the closed forms cover only one inlier and one outlier class, although the classifier distinguishes $2l+1$ labels with distinct conditional errors; they assume the label statistics (class probabilities and per-label squared errors) are known exactly and stationary across pings, although they are estimated from a trained classifier and the SNR may drift; and they control only the average, not the worst-case, energy — in rare outcomes the adaptive rule transmits all $N$ pings where an average-energy-matched non-adaptive rule would transmit fewer.

Problem Statement

Overarching objective: replace the two-class idealization with a general analytical performance theory of classifier-driven adaptive pulse acquisition for ToF estimation, at the generality at which the scheme is actually defined — labels $K\in\{-l,\dots,0,\dots,l\}$ with one inlier class and multiple outlier classes carrying distinct conditional biases and squared errors $e_j^2$, per-ping label statistics, OWA fusion weights $w_i\propto 1/e_{K_i}^2$, and the $k$–$N$ stopping rule (stop once $k$ inlier-labeled pings are collected, or after $N$ pings). Three linked results are requested, jointly supporting this objective:

(1) Multi-class expected-error comparison. For the general multi-class model, derive the expected fused MSE of the adaptive $k$–$N$ scheme and of the non-adaptive randomized acquisition rule against which it is compared — the mean-matched analogue of the two-class coin-flip 1-or-2-ping baseline, i.e. a rule that fixes its ping count before measurement by drawing from the two-point distribution on $\lfloor E[T]\rfloor$ and $\lceil E[T]\rceil$ whose mean is the adaptive expected pulse count $E[T]$ (degenerating to the deterministic count when $E[T]$ is an integer), and fuses those pings by the same OWA rule — and establish the conditions on the class probabilities $q_j$ and conditional squared errors $e_j^2$ under which the adaptive advantage relative to this comparator is strictly positive — or exhibit explicit parameter configurations where it is zero or negative.

(2) Multi-class pulse-count and composition laws. The $k$–$N$ stopping time depends only on the inlier-label probability $q_I$ and on $(k,N)$ — an inlier label is a Bernoulli$(q_I)$ event independent of which outlier class otherwise occurs — so the negative-binomial pulse-count formula stated in the Background carries over to the multi-class model unchanged. Determine instead the genuinely class-dependent companion law that the energy-matched comparison requires: the joint distribution (or its explicitly computable moments) of the stopping time and the realized label composition of the fused $k$–$N$ ping set — and, as the induced functional of that law, the law of the realized total fusion precision $\sum_{i=1}^{T}1/e_{K_i}^2$ — in closed form or explicitly computable from the label statistics $q_j$ and $e_j^2$ and from $(k,N)$.

(3) Robustness and worst-case energy. Resolve each of the following sub-questions: (a) Misspecified classifier statistics. Quantify the degradation of the adaptive advantage when the class probabilities $q_j$ or the per-label conditional squared errors $e_j^2$ used in the stopping statistics and the OWA weights differ from their true values, as arises from classifier mis-specification and finite training data. (b) Nonstationary SNR. Under an explicitly declared SNR-drift model in which the per-ping label statistics vary within a stated bounded band — the solver must state the model used and may not assume the label sequence remains independent and identically distributed — quantify how the drift changes the expected fused MSE and the expected pulse count. (c) Worst-case and tail energy. Characterize the worst-case and tail behavior of the pulse count and of the energy of the $k$–$N$ rule relative to average-energy-matched non-adaptive schemes. (d) Risk-aware design rules. Give an explicitly computable rule or bound for choosing $(k,N)$ that trades worst-case cost against average savings, stating the optimality or performance guarantee it achieves. (3)(a)–(d) are independent sub-questions; together with (1) and (2) they constitute the requested theory.

Throughout, 'better/worse' means smaller expected fused MSE at equal expected pulse count, per the source convention. Hardware validation and transfer of the scheme to other matched-filter applications, which the source discussion also mentions as future work, are outside the scope of this problem.

References

1. Alexander Apartsin, Leon N. Cooper, Nathan Intrator, 'Energy-Efficient Time-of-Flight Estimation in the Presence of Outliers: A Machine Learning Approach', IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 7, no. 4, pp. 1306–1313, 2014. DOI: 10.1109/JSTARS.2013.2295324, https://doi.org/10.1109/jstars.2013.2295324
2. Alexander Apartsin, Leon N. Cooper, Nathan Intrator, 'Time-of-Flight Estimation in the Presence of Outliers Part I—Single Echo Processing', IEEE Transactions on Geoscience and Remote Sensing, vol. 52, no. 6, pp. 3382–3392, 2014. DOI: 10.1109/TGRS.2013.2272737, https://doi.org/10.1109/tgrs.2013.2272737
3. Alexander Apartsin, Leon N. Cooper, Nathan Intrator, 'Time-of-Flight Estimation in the Presence of Outliers. Part II—Multiple Echo Processing', IEEE Transactions on Geoscience and Remote Sensing, vol. 52, no. 7, pp. 3843–3850, 2014. DOI: 10.1109/TGRS.2013.2276919, https://doi.org/10.1109/tgrs.2013.2276919
4. 'Time of Flight Estimation in the Presence of Outliers: A Biosonar-Inspired Machine Learning Approach', DTIC technical report ADA597037, published 29 August 2013 (the DOI-registered record lists Leon N. Cooper and Nathan Intrator as authors). DOI: 10.21236/ADA597037, https://doi.org/10.21236/ada597037
5. Alexander Apartsin, Leon N. Cooper, Nathan Intrator, 'Semi-coherent time of arrival estimation using regression', Journal of the Acoustical Society of America, vol. 132, no. 2, pp. 832–837, 2012. DOI: 10.1121/1.4730885, https://doi.org/10.1121/1.4730885
6. Alexander Apartsin, Nathan Intrator, 'A data fusion and multiple ping method for improving the resolution of low-power acoustic and seismic sensing', Journal of the Acoustical Society of America, vol. 124, no. 4 (Supplement 1), p. 2597, 2008 (one-page abstract for the 156th meeting of the Acoustical Society of America). DOI: 10.1121/1.4783265, https://doi.org/10.1121/1.4783265
7. Alexander Apartsin, Leon N. Cooper, Nathan Intrator, 'SNR-dependent filtering for Time Of Arrival estimation in high noise', Proceedings of the IEEE International Workshop on Machine Learning for Signal Processing (MLSP), pp. 427–431, 2010. DOI: 10.1109/MLSP.2010.5588848, https://doi.org/10.1109/mlsp.2010.5588848
8. Devis Tuia, Erzsébet Merényi, Xiuping Jia, Manuel Graña, 'Foreword to the Special Issue on Machine Learning for Remote Sensing Data Processing', IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 7, no. 4, pp. 1007–1011, 2014. DOI: 10.1109/JSTARS.2014.2311915, https://doi.org/10.1109/jstars.2014.2311915
9. 'Table of contents', IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 7, no. 4, pp. 1005–1006, special issue on machine learning for remote sensing data processing, 2014. DOI: 10.1109/JSTARS.2014.2316976, https://doi.org/10.1109/jstars.2014.2316976
10. Chao Zhou, Yueke Wang, Chunjie Qiao, Shen Zhao, Zhigang Huang, 'High-accuracy ultrasonic temperature measurement based on MLS-modulated continuous wave', Measurement, vol. 88, pp. 1–8, 2016. DOI: 10.1016/j.measurement.2016.03.037, https://doi.org/10.1016/j.measurement.2016.03.037
11. Anup Das, 'Deterministic and Bayesian Sparse Signal Processing Algorithms for Coherent Multipath Directions-of-Arrival (DOAs) Estimation', IEEE Journal of Oceanic Engineering, vol. 44, no. 4, pp. 1150–1164, 2019 (online early access 2018). DOI: 10.1109/JOE.2018.2851119, https://doi.org/10.1109/joe.2018.2851119
12. Kwang-Yul Kim, Eui Cheol Jeong, Seong-Il Kim, Yoan Shin, 'Magnetic Anomaly Detection Using Continuous Angle Alignment of Three-Axis Magnetic Signal', IEEE Sensors Journal, vol. 19, no. 2, pp. 743–750, 2019 (online early access 2018). DOI: 10.1109/JSEN.2018.2878890, https://doi.org/10.1109/jsen.2018.2878890
13. Yuliya Shulgina, Maria A. Kostina, P.V. Sorokin, Marina Polonskaya, O.A. Kozhemyak, Andrey Soldatov, 'Quantitative Measurement System of Liquid Products in Sealed Tank', Materials Science Forum, vol. 970, pp. 63–74, 2019. DOI: 10.4028/www.scientific.net/MSF.970.63, https://doi.org/10.4028/www.scientific.net/msf.970.63
14. Zhenqian Wu, Youming Li, Xiaolong Zhang, Xiangpei Meng, Xinrong Lv, Yonghong Wu, 'Multiple Anchors and RIS-Aided Localization Method in Complex NLOS Environments', IEEE Internet of Things Journal, vol. 11, no. 22, pp. 36922–36932, 2024. DOI: 10.1109/JIOT.2024.3433948, https://doi.org/10.1109/jiot.2024.3433948
15. Dorel Aiordăchioaie, 'Some Aspects of Time Delay Estimation Based on Cross-Correlation', Circuits, Systems, and Signal Processing, vol. 45, no. 3, pp. 2139–2163, 2026 (published online September 2025). DOI: 10.1007/s00034-025-03323-2, https://doi.org/10.1007/s00034-025-03323-2
16. Liron Darhi, Ariel Dvorjetski, Yehudit Aperstein, 'Data-Driven Estimation of Helicopter Engine Power Using Regular Flight Data: A Machine Learning Approach', Electronics, vol. 15, no. 1, art. 141, 2026 (published online 28 December 2025). DOI: 10.3390/electronics15010141, https://doi.org/10.3390/electronics15010141