Least Squares Problems
Finding the best approximate solution to an overdetermined system by minimizing the sum of squared residuals.
More equations than unknowns
When a linear system has more equations than unknowns, it usually has no exact solution. The least squares approach finds the solution that minimizes the sum of squared residuals, the squared length of the difference between the observed data and the model prediction. This is the foundation of data fitting, regression, and parameter estimation throughout science and engineering.
The normal equations and their pitfall
The minimizer satisfies the normal equations: A transposed times A, times the solution, equals A transposed times the data. These can be solved directly, but forming A transposed times A squares the condition number of the problem, amplifying rounding error. For well-conditioned problems the normal equations are fast and adequate; for ill-conditioned ones they lose accuracy and better methods are needed.
Stable methods
- QR factorization: factor A into orthogonal times triangular, then solve the triangular system; backward stable and the standard dense approach
- The SVD: the most robust choice, handling rank-deficient problems and giving the minimum-norm solution
- Iterative methods (LSQR, LSMR): Krylov methods for large sparse least squares, avoiding the normal equations
Regularization
When the problem is ill-posed or the data are noisy, the least squares solution can be wildly sensitive to the data. Regularization stabilizes it by adding a penalty. Tikhonov (ridge) regularization penalizes the solution's size, trading a little bias for a large reduction in variance; the SVD makes the effect transparent, damping the components associated with small singular values. Choosing the regularization strength balances fitting the data against controlling sensitivity.
Nonlinear least squares
When the model depends nonlinearly on the parameters, the problem becomes nonlinear least squares, solved by the Gauss-Newton or Levenberg-Marquardt methods, which repeatedly linearize and solve a linear least squares subproblem. These underlie curve fitting and the parameter estimation used to match simulation outputs to experimental data in plasma and materials modeling.