Application of AAK theory for sparse approximation
von Vlada Pototskaia
Datum der mündl. Prüfung:2017-10-16
Erschienen:2017-10-27
Betreuer:Prof. Dr. Gerlind Plonka-Hoch
Gutachter:Prof. Dr. Gerlind Plonka-Hoch
Gutachter:Prof. Dr. Stefan Kunis
Zum Verlinken/Zitieren:
http://dx.doi.org/10.53846/goediss-6546
Dateien
Name:thesis.pdf
Size:3.26Mb
Format:PDF
Lizenzbestimmungen:
Zusammenfassung
Englisch
Sparse approximation of structured signals is a common problem in signal processing and system theory. In particular, approximation by exponential sums often arises in natural sciences for the analysis of decay processes. In many applications it can be assumed that the signal is either exactly or approximately a finite linear combination of non-increasing exponentials with complex exponents. Thus, the nonlinear inverse problem of recovering the parameters of the exponential sum from a suitable number of samples becomes relevant. Due to Kronecker's Theorem the length of the exponential sum corresponds to the rank of the infinite Hankel matrix generated by samples of the sum. Therefore the parameter estimation problem for the exponential sums is closely related to the structured low rank approximation problem of Hankel matrices. Unfortunately, the singular value decomposition cannot be applied in this case, since it does not preserve the Hankel structure of the matrix. In most applications one is interested in obtaining the shortest possible exponential sum which satisfies a presumed approximation error in order to reduce further computational costs. This leads to the following problem, which we study in this thesis. Given samples of an exponential sum of length N we want to find a new sum of a shorter length n, such that the samples of the new sum satisfy a certain error estimation with respect to the samples of the original sum. For solving the above problem we employ the theory of Adamjan, Arov and Krein (AAK theory) in this work. The main theorem of the AAK theory can be seen as a structured low rank approximation approach for infinite matrices and is widely used by engineers for model reduction. We develop a new algorithm for solving the n-term approximation problem for sequences of samples of exponential sums. The obtained error estimates are related to singular values of the corresponding Hankel matrix. Our algorithm also includes a technique for the computation of all singular values of the infinite Hankel matrix generated by samples of exponential sums. Further, we provide a new proof of the AAK Theorem for Hankel matrices with finite rank in the discrete context. To our knowledge this is the first proof, which employs only tools from linear algebra and Fourier analysis and completely avoids the fundamental theorems from operator theory. For this purpose we characterize all mathematical objects used in our proof in the framework of linear algebra and establish the connection to the continuous setting using the Fourier transform. Also the connection between the AAK theory and Prony’s method becomes clear in this work. Thus, this thesis can be seen as a solid groundwork for further investigations approaching this theory from the field of linear algebra.
Keywords: sparse approximation; exponential sums; AAK theory; Prony method; structured low rank approximation; parameter estimation; Hankel matrices
