Gauss-Newton Trust Region Search Optimization Method for Least Squares Problems with Singular Hessian

Summary Although the Gauss-Newton trust-region sub-problem (GNTRS) solver using inverse-quadratic model (GNTRS-IQ) performs more efficiently than other direct solvers using matrix factorization and more robustly than available iterative solvers, it cannot compute the desired GN search step for many least-squares problems in which the Hessian is (near) singular. A popular approach to handle a singular matrix is to apply singular-value-decomposition (SVD). However, it is quite expensive to compute the SVD of a large matrix. In this paper, we developed an integrated GNTRS solver by combining different methods together. For problems with a positive-definite Hessian, the GN search step is computed by solving a linear equation with N=min(Nd,Nm) unknowns, where Nd is the number of data and Nm the number of unknown parameters. Otherwise, we apply a linear transformation to reduce the dimension from Nm to r (the rank of Hessian) and then compute the GN step by solving a linear equation with r unknowns. When r=Nd< Nm, we use the sensitivity matrix J as the transformation matrix. When r is smaller than min(ND,Nm), we first compute the compact-SVD of J and then use the compact form of the right-singular matrix as the transformation matrix. For performance comparison, we also developed two GNTRS solvers using the traditional-SVD and compact-SVD formulation. The three GNTRS solvers are validated and their performances are benchmarked on three sets of synthetic test problems. Each set contains 500 problems with different number of parameters and observed data. For small-scale and intermediate-scale problems, the solutions obtained by the three solvers have comparable accuracy. However, for large-scale problems, the solutions obtained by the solver using the traditional-SVD deviate from the solutions obtained by other solvers with unacceptably large errors. The integrated GNTRS solver performs most efficiently, and it can reduce the CPU time by a factor ranging from 1 to 173 and from 1 to 14585 when compared to the two solvers using the compact- and traditional-SVD. Our numerical tests confirm that the integrated GNTRS solver is efficient, robust, and applicable to least squares problems with singular Hessian. Finally, we applied the newly developed GN trust region search optimization method using the integrated GNTRS solver to a Gaussian-Mixture-Model (GMM) fitting problem. Compared with the one using the old version GNTRS-IQ solver, the new optimizer can reduce the CPU time used to construct an acceptable GMM by a factor of 8.