Least-Squares Problems

This notebook is based on the book Numerical optimization [1].

[1] J. Nocedal and S. J. Wright. Numerical optimization. en. 2nd ed. Springer series in operations research. OCLC: ocm68629100. New York: Springer, 2006. isbn: 978-0-387-30303-1.

Definition

Least-squares problems are defined, e.g. by Nocedal and Wright [1], as

\[\begin{equation*}%\label{equ:leastSqaureProblem} \min_{x\in\mathbb{R}^n} f(x) \qquad \text{with } f: \mathbb{R}^n \rightarrow \mathbb{R}, \ \ f(x)=\frac{1}{2}\sum\limits_{j=1}^m r_j^2(x)=\frac{1}{2}\|r(x)\|_2^2 \end{equation*}\]

where the summands \(r_j:\mathbb{R}^n \rightarrow \mathbb{R}\) are smooth functions, called residuals, and \(\|\cdot\|_2\) denotes the Euclidean norm. If the residuals are linear, the problem is referred to as a linear least-squares problem.

Least-Squares Problems in Model Fitting

Least-squares problems can be used to describe the challenge of fitting a model function \(\Phi\) to data points \((y_j,t_j)\). In this case, the residuals represent the discrepancy between the measured values and the corresponding predicted values \(\Phi(x,t_j)\). The parameters \(x=(x_1,\ldots,x_n)\) of the model serve as an input for the residuals:

\[\begin{align*} r_j(x)=\Phi(x,t_j)-y_j \quad \text{ for } j=1,\ldots, m \end{align*}\]

To determine the parameters \(x_i\) of the model, the sum of squared residuals (SSR) is minimized:

(1)\[\begin{align} \min_{x\in\mathbb{R}^n} \ \frac{1}{2}\sum\limits_{j=1}^m \bigl(\Phi(x,t_j)-y_j\bigr)^2 \end{align}\]