In vielen Problemen müssen hochdimensionale diskrete Signale aus verrauschten und

oft unterabgetasteten Daten rekonstruiert werden, was die Problematik der Lösung

von nominal unterdeterminierten, rauschbelasteten Gleichungssystemen aufwirft. Die

Theorie der komprimierten Abtastung besagt (und beweist), dass solche Signale tatsächlich

unter der Annahme der Dünnbesetztheit rekonstruiert werden können. Auf

dem breiten Forschungsgebiet, genannt Compressed Sensing – dessen Anwendungen

beispielsweise in der Medizin (MRT), Hochfrequenz-Kommunikationstechnologie und

Radar liegen – existieren bereits viele Algorithmen zur Rekonstruktion von sparsen

Signalen. Eine der wichtigsten Eigenschaften ist die so genannte Nullraum-Eigenschaft

der Sensormatrix. Sie stellt sicher, dass die sparse oder kompressible Darstellung durch

die ℓ1-Minimierung wiederhergestellt werden kann, die tatsächlich entweder durch konvexe

Optimierungsansätze, wie es der klassische Weg ist, oder alternativ durch schätztheoretische

Ansätze, z. B. durch das erweiterte linearisierte Kalman-Filter, realisiert werden kann.

In dieser Arbeit etablieren wir neue Ansätze zur Rekonstruktion sparser Signale durch

ℓ1-Minimierung mit einem Kalman-Filter. Das Kernstück unseres Kalman-Filters beruht

auf einer einfachen Idee. Auf Grundlage einer partikulären Lösung x_p (es existieren

unendlich viele Lösungen) schätzt das Kalman-Filter in jeder Iteration eine weitere

Lösung aus dem Nullraum der Messmatrix, sodass die Summe beider Vektoren eine

Lösung x = x_p + x_N mit reduzierter ℓ1-Norm erreicht. Im ersten Teil der Arbeit wird

im Kalman-Filter-Algorithmus, mit Hilfe von Konvergenzbeschleunigungsverfahren,

eine konvergierende Folge konstruiert, deren Grenzwert einen Lösungsvektor liefert,

der mit der Lösung des primal-dualen Algorithmus für ℓ1-Minimierung von Chambolle

& Pock übereinstimmt. Die Konvergenzbeschleunigungsverfahren resultieren aus dem

Delta2-Grundverfahren von Aitken. Für das Lösen von ℓ1-Minimierungsproblemen werden

zum Auffinden der Lösung vermehrt sogenannte Thresholdingverfahren eingesetzt. Im

zweiten Teil der Arbeit stellen wir das Kalman-Filter mit einem, den Anforderung genügendem,

externen Thresholdingverfahren vor. Mit diesem externen Thresholding,

welches nicht direkt das Kalman-Filter beeinflusst, können wir sparse Signale sehr

schnell rekonstruieren. Weitere Untersuchungen von rauschbehafteten Signalen mit

dem modifizierten Kalman-Filter bestätigen die Resultate in Bezug auf Rekonstruktionsfehler,

Rekonstruktionszeit, ℓ0-Norm und Supportfehler gegenüber den gängigen

bekannten ℓ1-Minimierungsalgorithmen, wie z. B. der primal-dual Algorithmus für

ℓ1-Minimierung von Chambolle & Pock und der Orthogonal Matching Pursuit.

In many problems, high-dimensional discrete signals need to be reconstructed from

noisy and often undersampled data, raising the issue of solving nominally underdetermined

noise-contaminated systems of equations. The theory of compressed sensing

states (and proves) that such signals can in fact uniquely be reconstructed under

the sparsity assumption. In the broad research field of compressed sensing – whose

applications are found, for example, in medicine (MRT), radar and high-frequency

communication technology, many algorithms already exist for the reconstruction of

sparse signals. One of the most important properties is the so-called null space property

of the sensor matrix. It ensures that the sparse or compressible representation

can be recovered by the ℓ1-minimization, which can in fact be realized either by convex

optimization approaches, which is the classical way, or alternatively by estimationtheoretic

approaches, e.g. by extended linearized Kalman-filters, which is the approach

analyzed in this paper.

In this work new results for the reconstruction of sparse signals by ℓ1-minimization

are established with such a Kalman-filter. The core of our Kalman-filter is based on a

simple idea. On the basis of a particular solution x_p (there are infinitely many solutions),

the Kalman-filter estimates another solution from the null space room of the

measurement matrix in each iteration step, so that the sum of both vectors achieves

a solution x = x_p + x_N with a reduced ℓ1-norm. In the first part, the Kalman-filter

uses convergence acceleration techniques to construct a convergent sequence whose

limit value provides a solution, which corresponds to Chambolle & Pock’s primal-dual

algorithm solution. The convergence acceleration methods result from the Delat2-basic

process of Aitken.

For solving ℓ1-minimization problems so-called thresholding methods are increasingly

used to find the solution. In the second part of the thesis the Kalman-filter is presented

with an external thresholding method. With this external thresholding, which does not

directly affect the Kalman-filter, we can now reconstruct sparse signals very quickly.

Further investigations of noise-affected signals with the modified Kalman-filter confirm

the results in terms of sparse recovery error, ℓ0-norm of the estimates, support mismatch,

and recovery time compared to the usual known ℓ1-minimization algorithms,

e.g., primal-dual algorithm of Chambolle & Pock and Orthogonal Matching Pursuit.