Conditioning and Regularization

Large least-squares problems can be sensitive to perturbations in the data, which can either be due to model approximation or superimposed errors (noise). These unwanted perturbations in the data can lead to substantial errors in the solution which numerical analysts have been trying to estimate and control in the past decades, resulting in a body of knowledge called numerical linear algebra. One basic characterization of sensitivity to noise in the data is an index called numerical conditioning. In this chapter we discuss the numerical conditioning of linear least-squares problems and relate it to a more general characterization of conditioning of linear inverse problems of which linear least squares is just a particular example. There are two main avenues to attack ill-conditioned linear least-squares problems, both based on the idea of regularization—one based on quadratic regularization and the other based on non-smooth regularization, called the Lasso. We briefly discuss the merits of these two techniques and conclude with a summary of a third regularization technique based on local regression via local polynomial expansion using splines.