On Greedy Reconstruction Algorithms

Abstract

This thesis is devoted to the development and analysis of greedy reconstruction (GR) algorithms. These procedures allow the design of optimized control functions that facilitate the accurate and efficient identification of unknown operators in dynamical systems. The approach is based on an offline/online decomposition of the reconstruction process, and on an ansatz for the unknown operator defined by a given family of operators. The first part of this thesis focuses on linear dynamical systems. A detailed analysis demonstrates that the controls computed by the GR algorithm make the quadratic online reconstruction problem strictly convex. Based on these results, an optimized greedy strategy (OGR) is introduced that additionally optimizes the ansatz for the unknown operator. In the second part, more general nonlinear systems are considered. Based on the linearization of these systems, a new greedy algorithm (LGR) is developed. It is shown that the controls computed by LGR lead to the local convergence of the classical Gauss-Newton method applied to the nonlinear online reconstruction problem. This result is extended to the controls obtained by the original GR algorithm applied directly to the nonlinear system. Numerical experiments on dynamical systems with linear and bilinear control structures confirm the effectiveness of the greedy algorithms. The third part of this thesis considers the reconstruction of a non-trivial joint probability distribution for two Hamiltonian parameters in Nuclear Magnetic Resonance. While the corresponding spin dynamics can be represented by a bilinear dynamical system, the online reconstruction problem is fully quadratic. A rigorous analysis proves that the controls generated by the GR algorithm ensure strict convexity of this reconstruction problem. These findings are confirmed by numerical experiments that highlight the efficiency of the OGR algorithm. In the final part of this work, the GR algorithms are applied to general function approximation problems. In the case of polynomial interpolation, the original GR algorithm is shown to compute exactly the (tensor-product) Leja points. Additionally, an equivalence between OGR and the well-established Empirical Interpolation Method is revealed. Finally, a new class of greedy algorithms is developed, that aim to select the smallest subset of a given data set, while simultaneously optimizing the structure of the approximation ansatz, within a given family of approximation functions. Extensive numerical tests on function approximation by neural networks demonstrate the efficiency of the new algorithms.