Application of AAK theory for sparse approximation

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 ...