Preconditioned gradient methods for solving nonlinear underdetermined least-squares problems

This thesis is devoted to the theoretical and numerical investigation of preconditioning methods for gradient schemes for solving underdetermined nonlinear least-squares problems. In particular, problems with zero residual are considered, which are equivalent to the problem of solving underdetermined nonlinear systems of equations. These problems arise in several fields such as nonlinear eigenvalue problems, partial differential equations, and in the context of data fitting. A specific example from the latter class is the supervised training of overparameterised artificial neural networks. In this case, a large number of parameters and a complex problem structure make solving these problems challenging, and the development of efficient methods with guaranteed convergence is of paramount importance. In this thesis, the relation between solutions of nonlinear least-squares problems and nonlinear systems of equations is explained. Further, a result on the existence of solutions that is based on the existence of a point with sufficiently small value of the residual function and a full rank assumption on the Jacobian of the residual function around this point is presented. This theoretical framework is discussed in the context of quadratic data fitting problems and supervised training problems. However, in some cases a full rank property is not at hand, and regularisation techniques are required for guaranteeing existence of solutions and convergence of iterative schemes. For this purpose, two regularisation schemes based on the minimisation of a least-squares objective function with a regularised residual are introduced. These schemes preserve the underdetermined structure of the problem and the corresponding Jacobians satisfy the full rank property. Further, it is established that a sequence of solutions of the regularised problems converges to a solution of the original problem if the regularisation parameter decreases to zero. To compute solutions of the considered underdetermined nonlinear least-squares problems, preconditioning approaches for gradient-based schemes are investigated. To this end, the standard gradient method, which serves as a basis for the proposed preconditioning approaches, is discussed. Specifically, a semi-local convergence result is presented, where, in contrast to local convergence theorems, the existence of a solution is not assumed a priori but follows from the convergence of a sequence obtained by this gradient scheme. The assumptions for this convergence result are transferred to the case of quadratic data fitting problems and supervised training problems. Moreover, the application of the gradient method to minimise the underdetermined regularised least-squares objective function that appear in both regularisation strategies is investigated. It is proven that the sequence of solutions obtained by the gradient method for regularised problems with varying regularisation parameter converges to a solution of the original problem if the regularisation parameter tends to zero. Results of numerical experiments illustrate this property. Preconditioning approaches with fixed transformation matrices are introduced. Motivated from the linear case, these schemes are classified as left, right, and split preconditioning methods depending on the space in which the transformation is applied. A convergence result for a left preconditioning method is proven. Further, flexible preconditioning schemes where the transformation matrix is allowed to vary during the gradient iteration are addressed. For nonlinear least-squares problems, a left preconditioning scheme with fixed transformation matrix based on a random subspace embedding is designed. A relation of the condition number of the Jacobian of the transformed residual function to the distortion of the subspace embedding is established. Results from numerical experiments on supervised learning problems are shown, which demonstrate a striking improvement of the convergence rate of the randomised preconditioned method compared to the standard gradient method. Inspired by spectral multigrid preconditioners, a flexible right preconditioning scheme is defined using the eigendecomposition of the Hessian of the least-squares objective function that complements the gradient method. Based on the resemblance to algebraic multigrid schemes, an approach to compute a similar transformation matrix with less computational effort is suggested. Additionally, the combination of this gradient and coarse-level correction scheme with the randomised left preconditioning approach is analysed. The resulting scheme gives a flexible split preconditioned gradient method. A numerical investigation of these flexible right and split preconditioning schemes is included. These results demonstrate that the combination of the gradient method with a coarse-level correction leads to a faster reduction of the least-squares objective function in terms of iterations compared to the standard gradient method, and that the split preconditioned gradient scheme converges even faster. Another efficient method for solving nonlinear systems of equations is the class of quasi-Newton methods, which represent flexible left preconditioned gradient schemes. In this context, an update formula for the Moore-Penrose inverse of the Jacobian approximations obtained by the Broyden update for underdetermined problems is developed. A semi-local convergence result for general quasi-Newton methods is proven. Sufficient conditions for the convergence of the quasi-Newton scheme resulting from the developed new updating procedure based on the Broyden update are given. These conditions are transferred to the context of quadratic data fitting problems and the supervised training of shallow neural networks. Further, for the considered regularised problems, it is established that the sequence of solutions obtained by the proposed quasi-Newton scheme applied to find a zero of the regularised residual functions converges to a solution of the original problem if the regularisation parameters decrease to zero. Results of numerical experiments on quadratic data fitting problems, eigenvalue problems, and supervised training problems are included to support the theoretical findings. A description of the problems' settings, the specifications of the applied algorithms, and the Python program used for the numerical experiments is included.