On the solution of rank deficient least squares problems

Abstract

In this thesis, we introduce a new method for solving minimum norm least squares problems. This method involves a QR decomposition followed by a Cholesky decomposition (QC). The existing methods in the literature are the Complete Orthogonal Factorization which involves two QR decompositions, and the SVD method. We compare the computational requirements of our method to the Complete Orthogonal Factorization method and show that QC requires fewer ops as long as the matrix is rank deficient. We also compare the sensitivity of the solution obtained by our method and the Complete Orthogonal Factorization method to parameter perturbations for generic matrices. A Kolmogorov-Smirnov test was run on the results of numerical experiments using normally distributed parameter perturbations. The results showed that the Null Hypothesis that the solutions by both algorithms have the same continuous underlying distribution cannot be rejected to a significance level of 0.05. The same numerical experiments showed that for the full rank case, the normal equation method using a Cholesky decomposition is significantly computationally faster than the QR method.