Markov chain Monte Carlo methods for detection and estimation with structural constraints

Abstract

Die vorliegende Arbeit befasst sich mit Bayes'scher Detektion und Schätzung mit strukturbezogenen Nebenbedingungen. Konkret werden Detektion und Schätzung spärlich besetzter Folgen mit einer Minimalabstands-Nebenbedingung betrachtet, d.h. aufeinander folgende von Null verschiedene Elemente der Folge müssen einen minimalen Abstand aufweisen. Eine derartige Nebenbedingung ist in zahlreichen Anwendungen relevant, beispielsweise bei der Detektion von Schichtgrenzen, in der medizinischen Bildgebung, in der Seismologie und bei der Schätzung von Mehrwegeausbreitungs-Parametern. In dieser Arbeit werden neue Detektions- und Schätzverfahren vorgeschlagen, die die durch den Minimalabstand bedingte Struktur ausnützen und dadurch eine signifikante Verbesserung der Leistungfähigkeit und Effizienz erzielen.<br />Die vorgeschlagenen Methoden folgen dem Markov-Chain-Monte-Carlo-Ansatz, d.h. die Detektoren und Schätzer verwenden eine aus der a-posteriori-Verbundverteilung der zu schätzenden Parameter gezogene Stichprobe. Der Detektions-/Schätzvorgang besteht daher aus zwei Schritten: (1) der Erzeugung der Stichprobe (wofür eine Markov-Kette verwendet wird) und (2) der Detektion/Schätzung unter Verwendung der Stichprobe. In dieser Arbeit werden beide Schritte behandelt.<br />Für den zweiten Schritt werden zunächst kanonische Maximum-a-posteriori-Detektoren betrachtet und ihre Schwächen im vorliegenden Problem herausgearbeitet. In der Folge werden zwei als "block detector" und "constrained sequence detector" bezeichnete Detektoren vorgeschlagen, die für Probleme mit Minimalabstands-Nebenbedingung geeignet sind. Der "block detector" ist eine einfache Lösung, die in einem praktisch wichtigen Spezialfall verwendet werden kann. Der "constrained sequence detector" benützt eine Metrik, die die gesamte zu detektierende Folge berücksichtigt und den Minimalabstand erzwingt. Der Detektor ist von geringer Komplexität, da er nur die (Monte Carlo-Näherung der) eindimensionalen marginalen a-posteriori-Verteilungen verwendet. Weiters wird eine effiziente sequentielle Implementierung beschrieben, die auf einer Darstellung des Entscheidungsproblems als binärer Baum sowie auf einer rekursiven Berechnung der Metrik beruht. Für den ersten Schritt - die Erzeugung der Stichprobe - wird das kürzlich vorgestellte Konzept des "partially collapsed Gibbs sampler" gewählt. Dieses Konzept wird für zwei praktisch relevante Anwendungen entwickelt, nämlich die blinde Entfaltung und die Schätzung von Parametern eines Ultra-Breitband-Kanals mit Mehrwegeausbreitung. Bei der blinden Entfaltung ist das beobachtete Signal eine unbekannte spärlich besetzte Folge, die mit einem Impuls unbekannter Form gefaltet ist. Es wird sowohl die spärlich besetzte Folge - unter Berücksichtigung des Minimalabstandes - als auch die Impulsform detektiert bzw. geschätzt.<br />Bei der Schätzung der Ultra-Breitband-Mehrwegeparameter werden die Anzahl, die Ankunftsverzögerungen, die Einfallswinkel und die Amplituden der Mehrwegekomponenten sowie auch die Form des Sendeimpulses detektiert bzw. geschätzt. Das verwendete Signalmodell berücksichtigt die Ausbreitungsverzögerungen zwischen den Empfangsantennen einer zweidimensionalen Gruppenantenne. Die spärliche Besetzung der detektierten Mehrwegekomponenten hinsichtlich Ankunftsverzögerung und Einfallswinkel wird durch eine zweidimensionale Minimalabstands-Nebenbedingung sichergestellt. In beiden Anwendungen sind die vorgeschlagenen Verfahren mit der durch den Minimalabstand bedingten komplexen probabilistischen Struktur verträglich bzw. nützen diese sogar aus. Simulationsergebnisse belegen deutliche Leistungsgewinne der vorgestellten Methoden im Vergleich zu aktuellen Verfahren, die nicht speziell für eine Minimalabstands-Nebenbedingung entwickelt wurden. Der wesentliche Vorteil dieser Nebenbedingung ist eine starke Verringerung des Rechenaufwands sowie der Anzahl der Störkomponenten im Schätzergebnis.<br />

This thesis studies Bayesian detection and estimation with structural constraints. More specifically, we consider detection/estimation of sparse sequences under a minimum distance constraint that enforces a prescribed minimum distance between successive nonzero elements of the sequence. Such a constraint is physically relevant in various applications including layer detection, medical imaging, seismology,and multipath parameter estimation. We propose detection/estimation methods that exploit the specific structure induced by this constraint, which is shown to be beneficial with respect to both performance and efficiency.<br />The methods we propose follow the Markov chain Monte Carlo approach, i.e., the detectors and estimators are based on a population (sample) of realizations drawn from the joint posterior distribution of the parameters to be estimated. Thus, detection/estimation consists of two stages: (1) a sampling stage in which the sample is generated (using a Markov chain) and (2) a sample-based detection/estimation stage. In this thesis, both stages are considered.<br />For the second stage, we first consider canonical maximum a posteriori detectors and discuss their shortcomings in the given context. Then, we define two novel detectors termed ``block detector'' and ``constrained sequence detector,'' which are well suited to problems with a minimum distance constraint. The block detector is a simple solution that can be used in a practically relevant special case. The constrained sequence detector uses a metric that depends on the entire constrained sequence and enforces the minimum distance constraint. The detector has low complexity since it involves only the (Monte Carlo approximation of the) one-dimensional marginal posteriors.We also describe an efficient sequential implementation that is based on a binary tree representation and a recursive metric computation. For the first stage, i.e., for generating the sample, we follow the recently introduced partially collapsed Gibbs sampler concept. We develop partially collapsed Gibbs samplers for two practically relevant applications, namely blind deconvolution and ultra-wideband multipath parameter estimation. In blind deconvolution, the observed signal is an unknown sparse sequence convolved with a pulse of unknown shape. We detect/estimate both the minimum distance-constrained sparse sequence and the pulse shape. In ultra-wideband multipath parameter estimation, we detect/estimate the number, times-of-arrival, angles-of-arrival, and amplitudes of the multipath components as well as the sounding pulse.<br />Our signal model accounts for propagation delays between the receive antennas of a 2D antenna array. Temporal-angular sparsity of the detected multipath components is ensured by a 2D minimum distance constraint. For both applications, the proposed sampling methods tolerate and even exploit the challenging probabilistic structure imposed by the minimum distance constraint. Simulation results demonstrate significant performance gains of our methods compared to state-of-the-art methods that are not specifically designed for a minimum distance constraint.<br />The main advantage of the minimum distance constraint is a substantial reduction of omputational complexity and of the number of spurious components in the detection/estimation result.<br />