MATH566 Lesson 12: Nonlinear least squares approximation

Overview

Motivation: data points might be affected by errors. The interpolation criterion $y_i=f\left(x_i\right)=g\left(x_i\right)$, i.e., exactly recover the function values is not appropriate, and linear combination of basis functions is not appropriate

• Approximants with nonlinear dependence on parameters

• Gradient descent

Linear versus nonlinear dependence on parameters

• Problem: approximate $f:[a,b]\to ℝ$ by $g:[a,b]\to ℝ$, $f\left(t\right)\cong g(t;c)$, $c$ are approximant parameters

• Type of approximant dependence on parameters.

  • linear: $g=c_1{g}_2+\cdots +c_n{g}_n$, typically arising from unknown behavior.

  • nonlinear: $g(t;c)$, typically arising from known behavior. Examples:

    • Chemical reaction rate given by Arrhenius equation (linearizable)

      ${\displaystyle k\left(T\right)=A\exp [-\frac{E}{RT}]}$

      Data $𝒟=\{(T_i,k_i),i=1,\dots ,m\}$, $A,E$ are parameters, $R$ is a constant.

    • Statistical model parameters, e.g., bimodal model

      ${\displaystyle g(x;c)=A_1\exp [-\frac{(x-{\mu }_1)}{{\sigma }_1^2}]+A_2\exp [-\frac{(x-{\mu }_2)}{{\sigma }_2^2}]}$

      $𝒟=\{(x_i,g_i),i=1,\dots ,m\}$, parameters: $𝒄={\left[\begin{array}{llllll}{A}_1& A_2& {\mu }_1& {\mu }_2& {\sigma }_1& {\sigma }_2\end{array}\right]}^T$

Linearizable least sqaures

• Chemical reaction rate given by Arrhenius equation (linearizable)

  ${\displaystyle k\left(T\right)=A\exp [-\frac{E}{RT}]}$

  Data $𝒟=\{(T_i,k_i),i=1,\dots ,m\}$, $A,E$ are parameters, $R$ is a constant.

• Take logarithm

  ${\displaystyle y=\log k=c_1-c_{2}x,x=\frac{1}{T},c_1=\log A,c_2=E/R}$ ${\displaystyle ℒ=\{(x_i,y_i),i=1,\dots ,m\}}$

• Obtain linear dependence on parameters, apply projection technique (Lesson11)

Truly nonlinear least squares problems

• Bimodal distribution

  ${\displaystyle g(x;c)=A_1\exp [-\frac{(x-{\mu }_1)}{{\sigma }_1^2}]+A_2\exp [-\frac{(x-{\mu }_2)}{{\sigma }_2^2}]}$

  $𝒟=\{(x_i,y_i=g(x_i;c)),i=1,\dots ,m\}$, parameters: $𝒄={\left[\begin{array}{llllll}{A}_1& A_2& {\mu }_1& {\mu }_2& {\sigma }_1& {\sigma }_2\end{array}\right]}^T$

• Taking logarithms does not lead to a linear system

• Form squared error in 2-norm

  ${\displaystyle f\left(𝒄\right)={\epsilon }^2={||g(𝒙;𝒄)-𝒚||}_2^2}$

• Solve minimization problem

  ${\displaystyle {min}_{𝒄\in {ℝ}^n}f\left(𝒄\right)}$

Gradient descent

• To solve ${min}_{𝒄\in {ℝ}^n}f\left(𝒄\right)$, $f:{ℝ}^n\to ℝ$, $f>0$, $f\mathrm{convex}$ recall that the gradient defines direction of maximal inrease of $f$

• Gradient descent. Construct a sequence of parameter approximants ${\left\{{𝒄}_k\right\}}_{k\in \mathbb{N}}$

• Starting from some previous approximation ${𝒄}_k$, new estimate of the parameters obtained by

  ${\displaystyle {𝒄}_{k+1}={𝒄}_k-{\lambda }_k\mathrm{grad}f\left({𝒄}_k\right)}$

• Distance to travel in direction of gradient typically determined by orthogonality to next gradient

  ${\displaystyle \mathrm{grad}f\left({𝒄}_k\right)\cdot \mathrm{grad}\left[f\left({𝒄}_{k+1}\right)\right]=0\Rightarrow \mathrm{equation}\mathrm{forspace}{\lambda }_k}$

• Topic pursued further during solution of root finding.