TU Darmstadt / ULB / TUprints

Sequential Joint Detection and Estimation: Optimal Procedures and Asymptotic Results

Reinhard, Dominik (2021):
Sequential Joint Detection and Estimation: Optimal Procedures and Asymptotic Results. (Publisher's Version)
Darmstadt, Technische Universität,
DOI: 10.26083/tuprints-00019741,
[Ph.D. Thesis]

[img]
Preview
Text
2021-10-14_Reinhard_Dominik.pdf
Available under CC-BY-NC-SA 4.0 International - Creative Commons, Attribution NonCommercial, ShareAlike.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Sequential Joint Detection and Estimation: Optimal Procedures and Asymptotic Results
Language: English
Abstract:

This thesis details the design and analysis of sequential procedures for the joint inference problem associated with hypothesis testing and parameter estimation in the context of sequentially observed data. The goal achieved is to minimize the average number of samples required to meet predefined detection and estimation error levels; thus fast inference with guaranteed performance.

The first half of the thesis is devoted to the design of strictly optimal procedures, i.e., procedures that use, on average, as few samples as possible and fulfill constraints on the detection and estimation error levels. The design problem is formulated as a constrained optimization problem. The selected approach is to convert the problem to an unconstrained optimization problem and subsequently, to an optimal stopping problem. The solution of the optimal stopping problem is characterized by recursively defined non-linear integral equations that are parameterized by a set of cost coefficients. It is shown that the partial derivatives of the cost function, with respect to the cost coefficients, are equal to the detection/estimation errors up to a constant scaling factor. Based on this property, the choice of the coefficients that lead to an optimal solution is formulated as a convex optimization problem. Two numerical algorithms are provided to solve this optimization problem. The first one converts the optimization problem to a linear program. The second one solves it directly via a projected quasi-Newton method. Numerical examples are given that verify the proposed design procedure.

In the second part of this dissertation, asymptotically optimal procedures for sequential joint detection and estimation are detailed. To avoid the computationally expensive solutions associated with optimality, an alternative procedure is proposed, which becomes optimal when the constraints on the detection and estimation errors approach zero. After a formal definition of asymptotic optimality, an asymptotically optimal stopping rule is detailed. This stopping rule is implemented by thresholding the instantaneous cost that is parameterized by a set of cost coefficients. It is shown, asymptotically, and similarly to the strictly optimal procedure, that the partial derivatives of the solution of the optimal stopping problem and the detection/estimation errors, differ only by a constant scaling factor. Using this result, it is shown how the projected quasi-Newton method, derived for the design of optimal procedures, can be adapted to choose the cost coefficients such that the constraints on the detection and estimation errors are fulfilled. The proposed asymptotically optimal procedures are applied to example problems that are motivated by real-world applications. By means of a numerical example, it is shown that the asymptotically optimal procedure uses, on average, only slightly more samples than the strictly optimal one while requiring significantly less computational resources to be implemented.

This thesis provides a coherent framework for the design and analysis of strictly optimal, as well as asymptotically optimal procedures, for the problem of sequential joint detection and estimation.

Alternative Abstract:
Alternative AbstractLanguage

Diese Arbeit beschreibt den Entwurf und die Analyse von sequentiellen Verfahren für das gemeinsame Inferenzproblem im Zusammenhang mit Hypothesentests und Parameterschätzungen im Kontext von sequentiell beobachteten Daten. Das Ziel ist es, die durchschnittliche Anzahl an Datenpunkten zu minimieren, die erforderlich ist, um vordefinierte Detektions- und Schätzfehlerniveaus zu erreichen; also schnelle Inferenz mit garantierter Genauigkeit.

Die erste Hälfte der Arbeit ist dem Entwurf streng optimaler Methoden gewidmet, d.h. Verfahren, die im Durchschnitt so wenige Datenpunkte wie möglich verwenden und die Bedingungen für die Detektions- und Schätzfehlerniveaus erfüllen. Das Entwurfsproblem wird als Optimierungsproblem mit Nebenbedingungen formuliert. Der gewählte Ansatz besteht darin, das Problem in ein Optimierungsproblem ohne Nebenbedingungen und anschließend in ein Problem zur Ermittlung optimaler Stoppzeiten umzuwandeln. Die Lösung des Problems zur Ermittlung optimaler Stoppzeiten ist durch rekursiv definierte nichtlineare Integralgleichungen charakterisiert, die durch einen Satz von Kostenkoeffizienten parametrisiert sind. Es wird gezeigt, dass die partiellen Ableitungen der Kostenfunktion nach den Kostenkoeffizienten bis auf einen konstanten Skalierungsfaktor gleich den Detektions-/Schätzfehlern sind. Basierend auf dieser Eigenschaft wird die Wahl der Koeffizienten, die zu einer optimalen Lösung führen, als ein konvexes Optimierungsproblem formuliert. Zur Lösung dieses Optimierungsproblems werden zwei numerische Algorithmen bereitgestellt. Der erste wandelt das Optimierungsproblem in ein lineares Programm um. Der zweite löst es direkt über ein Quasi-Newton-Verfahren, welches das Ergebnis auf den zulässigen Lösungsraum projiziert (projected quasi-Newton method). Das vorgeschlagene Entwurfsverfahren wird anhand numerischer Beispiele verifiziert.

Im zweiten Teil der Arbeit werden asymptotisch optimale Verfahren zur sequentiellen gemeinsamen Detektion und Schätzung detailliert beschrieben. Um die mit der Optimalität verbundenen rechenintensiven Lösungen zu vermeiden, wird ein alternatives Lösungsverfahren vorgeschlagen, das optimal wird, wenn die Nebenbedingungen für die Detektions- und Schätzfehler gegen Null gehen. Nach einer formalen Definition der asymptotischen Optimalität wird eine asymptotisch optimale Stoppregel beschrieben. Diese Stoppregel wird durch Schwellwertbildung der momentanen Kosten implementiert, welche durch einen Satz von Kostenkoeffizienten parametrisiert sind. Es wird gezeigt, dass sich die partiellen Ableitungen der Lösung des optimalen Stopp-Problems und die Detektions-/Schätzfehler asymptotisch, ähnlich wie beim streng optimalen Verfahren, nur um einen konstanten Skalierungsfaktor unterscheiden. Anhand dieses Ergebnisses wird gezeigt, wie das eigentlich für den Entwurf optimaler Methoden entwickelte Quasi-Newton-Verfahren so angepasst werden kann, dass durch die daraus resultierenden Kostenkoeffizienten die Nebenbedingungen für die Detektions- und Schätzfehler erfüllt werden. Die vorgeschlagenen asymptotisch optimalen Verfahren werden auf Beispielprobleme angewendet, die durch reale Probleme motiviert sind. Anhand eines numerischen Beispiels wird gezeigt, dass das asymptotisch optimale Verfahren im Durchschnitt nur geringfügig mehr Datenpunkte benötigt als das streng optimale Verfahren, während es deutlich weniger Rechenressourcen für die Implementierung benötigt.

Diese Arbeit bietet einen kohärenten Rahmen für den Entwurf und die Analyse sowohl streng optimaler als auch asymptotisch optimaler Verfahren für das Problem der sequentiellen gemeinsamen Detektion und Schätzung.

German
Place of Publication: Darmstadt
Collation: ix, 4, 145 Seiten
Classification DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Signal Processing
Date Deposited: 21 Oct 2021 08:58
Last Modified: 21 Oct 2021 08:58
DOI: 10.26083/tuprints-00019741
URN: urn:nbn:de:tuda-tuprints-197415
Referees: Zoubir, Prof. Dr. Abdelhak M. ; Veeravalli, Prof. Dr. Venugopal V.
Refereed: 12 August 2021
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19741
Export:
Actions (login required)
View Item View Item