Fast algorithms for multidimensional harmonic retrieval [Elektronische Ressource] = Schnelle Algorithmen zur Erkennung von mehrdimensionalen Harmonischen / by Marius Pesavento

Sujets

• Mathematics

Informations

• Publié par: ruhr-universitat_bochum
• Publié le: 01 janvier 2005
• Nombre de lectures: 41
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Fast Algorithms for Multidimensional
Harmonic Retrieval
A DISSERTATION
submitted to the Faculty of
Electrical Engineering and Information Sciences
at the Ruhr-Universität Bochum
in a fulfillment of the requirements
for the degree of
Doctor of Engineering
by
Marius Pesavento
Bochum 2005Schnelle Algorithmen zur Erkennung
von mehrdimensionalen Harmonischen
DISSERTATION
zur
Erlangung des Grades
eines Doktor-Ingenieurs
der
Fakultät für Elektrotechnik und Informationstechnik
an der Ruhr-Universität Bochum
von
Marius Pesavento
Bochum 2005Tag der Einreichung: 8. Dezember 2004
Tag der Promotion: 2. Februar 2005
Referent: Prof. Dr.-Ing. Johann F. Böhme
Korreferent: Prof. Dr.-Ing Alex B. Gershmani
Abstract
Classic multidimensional harmonic retrieval is the estimation problem in a variety of practical
applications, including sensor array processing, radar, mobile communications, multiple-input
multiple-output (MIMO) channel estimation and nuclear magnetic resonance spectroscopy. Nu-
merous parametric subspace approaches have been proposed recently to solve this problem,
among which the so-called ESPRIT-based algorithms are most popular due to their compu-
tational efficiency and comparably simple implementations. In these algorithms certain shift
invariances contained in the measurements are exploited to estimate the parameters of interest
by solving a joint eigenvalue problem. In many applications the measurements are obtained
through uniform sampling along one or multiple dimensions. In these cases, the ESPRIT meth-
ods usually fail to exploit all prior information contained in the highly structured measurement
data resulting in a significant performance loss in the parameter estimation.
In this work a different approach towards multidimensional harmonic retrieval is taken. A suit-
able parameterization enables the estimation of the harmonics of interest separately along the
various dimensions, thus avoiding the computationally expensive optimization of a multidimen-
sional cost function which would otherwise be required. This procedure makes the estimation
problem computationally tractable while retaining much of the benefits inherent in the multi-
dimensional nature of the measurement data such as, for example, relatively mild uniqueness
conditions and high resolution capability compared to one dimensional data. Several matrix
rank and polynomial rooting criteria are derived to obtain the parameters of interest separately
along the various dimensions. New insight is gained from interpreting the proposed rank criteria
in diverse contexts: as a relaxation approach in minimizing the classic root-MUSIC criterion, in
a Gaussian-elimination framework, and as a rooting-based solution of the multiple invariance
equations. The different viewpoints not only yield new stochastic uniqueness conditions for the
rank reduction estimators, but also lead to efficient parameter association strategies to correctly
group the parameters corresponding to a specific multidimensional harmonic signal. Further,
a link between the popular ESPRIT-type methods and the root-MUSIC based approaches is
discovered that allows to reformulate the rank reduction idea in terms of a joint generalized
eigenproblem. Casting the multidimensional harmonic retrieval problem as an eigenproblem
significantly simplifies the parameter estimation and association procedure and makes the algo-
rithm equally applicable to the cases of pure and damped harmonic retrieval.
Simulation results obtained from synthetic data for the single and multiple snapshot case are
presented and illustrate that the proposed algorithms are competitive with other existing meth-
ods from both a numerical viewpoint and also in terms of estimation performance. Further,
in the example of parametric MIMO channel identification, it is demonstrated that the novel
algorithms perform well if applied to real measurement data obtained from a channel-sounding
campaign.iii
Kurzfassung
Eine Reihe praktisch relevanter Anwendungen lassen sich auf das klassische Problem der Erken-
nung von mehrdimensionalen Harmonischen zurückführen. Hierzu gehören unter anderem
Anwendungen im Bereich der Sensorgruppensignalverarbeitung, der Radarsignalverarbeitung,
der mobilen Kommunikation aber auch die Identifizierung von Multiple-Input Multiple-Output
(MIMO) Systemen und die Nukleare Magnetische Resonanz Spektroskopie. Zur Lösung dieses
Problems sind in letzter Zeit eine Vielzahl parametrischer Unterraummethoden entwickelt wor-
den, unter denen die so genannten ESPRIT-basierten Algorithmen aufgrund ihres geringen
Rechenaufwandes und ihrer vergleichsweise einfachen Implementierung große Beliebtheit er-
langt haben. Diese Algorithmen nutzen bestimmte Verschiebungs-Invarianzen in den Mess-
daten aus, um die Schätzparameter als Lösung eines gemeinsamen Eigenwertproblems zu er-
halten. In vielen Anwendungen liegt den Messdaten eine gleichförmige Abtastung entlang
einer oder mehrerer Dimensionen zugrunde. In diesen Fällen gelingt es mit den ESPRIT Algo-
rithmen nicht, das gesamte, in den hoch strukturierten Messdaten vorhandene a priori Wissen
auszunutzen mit dem Ergebnis einer merklich verringerten Schätzgenauigkeit.
In der vorliegenden Arbeit wird ein anderer Unterraumansatz zur mehrdimensionalen Harmon-
ischenerkennung gewählt. Mittels einer geeigneten Parameterisierung gelingt es, die gesuchten
Harmonischen entlang der einzelnen Dimensionen getrennt voneinander zu schätzen, um so die
ansonsten notwendige und rechenaufwendige Optimierung einer mehrdimensionalen Kosten-
funktion zu umgehen. Dieses Vorgehen macht das Schätzproblem numerisch handhabbar, wobei
gleichzeitig ein Großteil an Vorzügen der multidimensionaler Messdaten wie z.B. die rela-
tiv schwachen Eindeutigkeitsanforderungen und das hohe Auflösungsvermögen im Vergleich
zu eindimensionalen Messdaten erhalten bleiben. Verschiedene Matrixrang- und Polynom-
nullstellen-Kriterien werden hergeleitet, aus denen die gesuchten Parameter entlang der ver-
schiedenen Dimensionen getrennt voneinander bestimmt werden können. Die Interpretation
der vorgeschlagenen Rangkriterien unter ganz verschiedenen Gesichtspunkten, nämlich a) als
Relaxierungsansatz bei der Minimierung des klassischen root-MUSIC Kriteriums, b) im Rah-
men eines Gauß’schen Eliminierungsansatzes oder c) als eine auf Nullstellensuche basierte
Lösung der multiplen Invarianzgleichungen, ermöglicht ein gänzlich neues Verständnis. Da-
raus gehen nicht nur neue stochastische Eindeutigkeitsbedingung für die Rangreduzierungsver-
fahren hervor, sondern es werden auch effiziente Zuordnungsstrategien entwickelt, die eine
korrekte Gruppierung der Parameter zu den entsprechenden mehrdimensionalen Harmonis-
chen erlauben. Außerdem wird ein enger Zusammenhang zwischen den auf ESPRIT basierten
und den so genannten nullstellenbasierten Verfahren hergeleitet, der es gestattet, das Problem
der mehrdimensionalen Harmonischenerkennung als ein gekoppetes System verallgemeinerter
Eigenwertprobleme aufzufassen. Dadurch vereinfacht sich zum einen die Parameterschätzung
sowie die -zuordnung merklich und zum anderen ermöglicht es, den Algorithmus sowohl für
die Schätzung von ungedämpften wie auch gedämpften Harmonischen anzuwenden.iv
Für den Einfach- und Mehrfachschnappschussfall werden Simulationsergebnisse mit synthetis-
chen Daten vorgestellt. Sie belegen, dass die entwickelten Algorithmen in Punkto Rechen-
aufwand und Schätzgenauigkeit überaus konkurrenzfähig zu den bekannten Methoden sind.
Außerdem wird am Beispiel von parametrischer MIMO Kanalidentifizierung gezeigt, dass die
neuen Algorithmen auch im Einsatz an gemessenen Channel-Sounder-Daten ihre Leistungs-
fähigkeit beweisen.v
Acknowledgments
I would like to express my deep gratitude to Prof. Johann F. Böhme for his great support and
encouragement, which went far beyond purely academic matters. His suggestions and critical
advice - in the course of numerous fruitful discussions we had - were and are highly appreciated
and were also a significant contribution to the success of this work.
I am also indebted to Prof. Alex B. Gershman for the review of my thesis. He introduced me
to the field of signal processing and I began my research activities under his guidance. His
enthusiasm, inquiring mind and friendship have been truly inspiring.
I would like to give special thanks to Dr.-Ing Christoph Mecklenbräuker for the comprehensive
scientific collaboration, reviewing important parts of this manuscript, as well as for the provision
of the experimental data by the Telecommunications Research Center Vienna (ftw).
A critical review of the manuscript was carried out by Dipl. Ing. Markus Bühren and Dipl.-
Ing. Rubén Villarino-Villa. The readers of this work owe them as much thanks as I do. I
would further like to thank all of my colleagues in the Signal Processing Group, to whom I owe
countless valuable discussions and advice, and - last but not least - great fun in the course of my
work.
Finally, I would like to express thanks to my parents, Ursula and Modesto Pesavento, for giving
me the opportunity to study. Their great expectations in me were expressed thr