Linear least squares

Let $\mathcal{U}$ represent a subspace of the linear space $\mathbb {R}^{m}$ of all $m$-dimensional column vectors. Take $\mathcal{M}$ to be the subspace of $\mathbb {R}^{m \times n}$ defined by $\mathbf{W} \in \mathcal{M}$ if and only if $\mathbf{W} = (\mathbf{w}_{1}, \ldots , \mathbf{w}_{n})$ for some vectors $\mathbf{w}_{1}, \ldots , \mathbf{w}_{n}$ in $\mathcal{U}$. Let $\mathbf{Z}$ represent the projection (with respect to the usual inner product) of an $m \times n$ matrix $\mathbf{Y}$ on $\mathcal{M}$, and let $\mathbf{X}$ represent any $m \times p$ matrix whose columns span $\mathcal{U}$. Show that $\mathbf{Z} = \mathbf{X}\mathbf{B}^{*}$ for any solution $\mathbf{B}^{*}$ to the linear system

Let $\mathbf{X}$ represent any $n \times p$ matrix. If a $p \times n$ matrix $\mathbf{B}^{*}$ is a solution to the linear system $\mathbf{X}'\mathbf{X}\mathbf{B} = \mathbf{X}'$ (in $\mathbf{B}$), then $\mathbf{B}^{*}$ is a generalized inverse of $\mathbf{X}$ and $\mathbf{X}\mathbf{B}^{*}$ is symmetric. Show that, conversely, if a $p \times n$ matrix $\mathbf{G}$ is a generalized inverse of $\mathbf{X}$ and if $\mathbf{X}\mathbf{G}$ is symmetric, then $\mathbf{X}'\mathbf{X}\mathbf{G} = \mathbf{X}'$ (i.e., $\mathbf{G}$ is a solution to $\mathbf{X}'\mathbf{X}\mathbf{B} = \mathbf{X}'$).

Let the physical quantities $x$ and $y$ be related by an unknown linear relationship $y = a x+b$. As a result of $n$ measurements, the following pairs of values were obtained with some error: $\left(x_{1} ; y_{1}\right)$, $\left(x_{2} ; y_{2}\right), \ldots ,\left(x_{n} ; y_{n}\right)$. According to the principle of least squares, the most probable values of the coefficients $a$ and $b$ are those for which

attains its smallest value. Find the most probable values $\bar{a}, \bar{b}$ for the coefficients $a$ and $b$.

Let $A\mathrm{x} = \mathrm{b}$ be an arbitrary system of linear equations. Prove that the system of equations $\left(A^{T} A\right) \mathbf{x} = A^{T} \mathbf{b}$ is consistent.

Using the method of least squares, solve the overdetermined system of linear equations:

Let $f(x) = \sin \pi x$ on $[0, 1]$. The object of this problem is to determine the coefficients $\alpha_{i}$ of the cubic polynomial

that is as close to $f(x)$ as possible in the sense that

is as small as possible.

Perform the following calculations using the matrices:

Hooke's law says that the displacement $y$ of an ideal spring is proportional to the force $x$ that is applied — i.e., $y = kx$ for some constant $k$. Consider a spring in which $k$ is unknown. Various masses are attached, and the resulting displacements shown below are observed. Using these observations, determine the least squares estimate for $k$.

Figure 4.6.6

Show that the slope of the line that passes through the origin in $\mathbb {R}^{2}$ and comes closest in the least squares sense to passing through the points $\left\{ (x_1, y_1), (x_2, y_2), \ldots , (x_n, y_n)\right\}$ is given by $m = \sum_i x_i y_i / \sum_i x_i^2$.

A small company has been in business for three years and has recorded annual profits (in thousands of dollars) as follows.

Assuming that there is a linear trend in the declining profits, predict the year and the month in which the company begins to lose money.

An economist hypothesizes that the change (in dollars) in the price of a loaf of bread is primarily a linear combination of the change in the price of a bushel of wheat and the change in the minimum wage. That is, if $B$ is the change in bread prices, $W$ is the change in wheat prices, and $M$ is the change in the minimum wage, then $B = \alpha W + \beta M$. Suppose that for three consecutive years the change in bread prices, wheat prices, and the minimum wage are as shown below.

Use the theory of least squares to estimate the change in the price of bread in Year 4 if wheat prices and the minimum wage each fall by $1.

Suppose that a researcher hypothesizes that the weight loss of a pint of ice cream during storage is primarily a linear function of time. That is,

where $y =$ the weight loss in grams, $t =$ the storage time in weeks, and $\varepsilon$ is a random error function whose mean value is $0$. Suppose that an experiment is conducted, and the following data is obtained.

After studying a certain type of cancer, a researcher hypothesizes that in the short run the number ($y$) of malignant cells in a particular tissue grows exponentially with time ($t$). That is, $y = \alpha_0 e^{\alpha_1 t}$. Determine least squares estimates for the parameters $\alpha_0$ and $\alpha_1$ from the researcher's observed data given below.

Using least squares techniques, fit the following data

with a line $y = \alpha_0 + \alpha_1 x$ and then fit the data with a quadratic $y = \alpha_0 + \alpha_1 x + \alpha_2 x^2$. Determine which of these two curves best fits the data by computing the sum of the squares of the errors in each case.

Consider the time ($T$) it takes for a runner to complete a marathon (26 miles and 385 yards). Many factors such as height, weight, age, previous training, etc.can influence an athlete's performance, but experience has shown that the following three factors are particularly important:

A linear model hypothesizes that the time $T$ (in minutes) is given by $T = \alpha_0 + \alpha_1 x_1 + \alpha_2 x_2 + \alpha_3 x_3 + \varepsilon$, where $\varepsilon$ is a random function accounting for all other factors and whose mean value is assumed to be zero. On the basis of the five observations given below, estimate the expected marathon time for a 43-year-old runner of height 74 in., weight 180 lbs., who has run 450 miles during the previous eight weeks.

What is your personal predicted mean marathon time?

For $\mathbf{A} \in \mathbb {R}^{m \times n}$ and $\overrightarrow {b} \in \mathbb {R}^{m}$, prove that $\overrightarrow {x}_2$ is a least squares solution for $\mathbf{A}\overrightarrow {x} = \overrightarrow {b}$ if and only if $\overrightarrow {x}_2$ is part of a solution to the larger system

In many least squares applications, the underlying data matrix $\mathbf{A}_{m \times n}$ does not have independent columns — i.e., $\operatorname {rk}\left(\mathbf{A}\right) < n$ — so the corresponding system of normal equations $\mathbf{A}^T \mathbf{A}\overrightarrow {x} = \mathbf{A}^T \overrightarrow {b}$ will fail to have a unique solution. This means that in an associated linear estimation problem of the form

there will be infinitely many least squares estimates for the parameters $\alpha_i$, and hence there will be infinitely many estimates for the mean value of $y$ at any given point $(t_1, t_2, \ldots , t_n)$ — which is clearly undesirable. In order to remedy this problem, we restrict ourselves to making estimates only at those points $(t_1, t_2, \ldots , t_n)$ that are in the row space of $\mathbf{A}$. If

is any least squares solution (i.e., $\mathbf{A}^T \mathbf{A}\overrightarrow {x} = \mathbf{A}^T \overrightarrow {b}$), prove that the estimate defined by

is unique in the sense that $\hat{y}$ is independent of which least squares solution $\overrightarrow {x}$ is used.

For matrix $A$ in Exercise 5.11.8, and for $b = \begin{pmatrix} -12& 3& -9 \end{pmatrix}^{T}$, find the solution of $Ax=b$ that has minimum euclidean norm.

Explain why $\hat{x}$ is a least squares solution for $Ax=b$ if and only if $\left\| A\hat{x}-b\right\|_{2} = \left\| P_{\mathcal{N}(A^{T})}b\right\|_{2}$.

Prove that if $\varepsilon = A\hat{x}-b$, where $\hat{x}$ is a least squares solution for $Ax=b$, then $\left\| \varepsilon \right\|_{2}^{2} = \left\| b\right\|_{2}^{2} - \left\| P_{\mathcal{R}(A)}b\right\|_{2}^{2}$.

Let $A = \begin{pmatrix} 1 & 0 & -1 \\ 1 & 2 & 1 \\ 1 & 1 & -3 \\ 0 & 1 & 1 \end{pmatrix}$ and $b = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}$.

Use Householder reduction to compute the least squares solution for $Ax=b$, where $A = \begin{pmatrix} 4 & -3 & 4 \\ 2 & -14 & -3 \\ -2 & 14 & 0 \\ 1 & -7 & 15 \end{pmatrix}$ and $b = \begin{pmatrix} 5 \\ -15 \\ 0 \\ 30 \end{pmatrix}$.

Prove that a pseudosolution can be found as the solution of a new inhomogeneous system of equations formed using the Gram matrix $G\left(a_{1}, a_{2}, \ldots , a_{n}\right)$:

What is the geometric meaning of the constants $x_{1}, x_{2}, \ldots , x_{n}$ found in this way?

Using the method of least squares, find the pseudosolution of the following inconsistent systems of linear equations:

Prove that the solution $L_{m}^{f}(x)$ of the least-squares interpolation problem in the space $V_{n+1}$ exists and is unique, and that the coefficients $a_{i}, i = 0, \ldots , m$, are found from the system of inhomogeneous linear equations

where $G\left(\varphi_{0}, \varphi_{1}, \ldots , \varphi_{m}\right)$ is the Gram matrix of the system of functions $\varphi_{0}(x), \ldots \ldots , \varphi_{m}(x)$ in the Euclidean space $V_{n+1}$.

Using the method of least squares, find the interpolation (best mean-square approximation) of the function $f$ given by the values $f(0) = 1, f(1) = 2, f(2) = 3, f(3) = 5$:

Using the method of least squares, find, in the Euclidean space of continuously differentiable functions with the inner product

the interpolation (best mean-square approximation) of a continuously differentiable function $f$ using the system of functions $\varphi_{0}(x) = 1, \varphi_{1}(x) = \cos x, \varphi_{2}(x) = \sin x$.

Prove that the set of pseudosolutions of the system $A x = b$ forms an affine subspace (linear manifold)

in $\mathbb {R}^{n}$ ($x^{\prime }$ is some pseudosolution).

Let $P = x^{\prime }+\operatorname {Ker} A$ be the affine subspace of pseudosolutions of the system $A x = b$, and let $x^{\prime \prime } \in P$ be some pseudosolution. Prove that the following statements are equivalent:

Consider the system $A x = b$, where $A$ is the matrix of the operator $\mathrm{A}: \mathbb {R}^{n} \rightarrow \mathbb {R}^{m}$. The spaces $\mathbb {R}^{n}$ and $\mathbb {R}^{m}$ are equipped with the standard scalar products. Let $e_{1}, e_{2}, \ldots , e_{n}$ be the canonical basis of the nonnegative self-adjoint operator $\mathbf{A}^{*} \mathbf{A}$, and let $\lambda_{1}, \lambda_{2}, \ldots , \lambda_{r}$ be its positive (i.e. nonzero) eigenvalues, corresponding to the eigenvectors $e_{1}, e_{2}, \ldots , e_{r}$ respectively. Prove that the general pseudosolution $x^{\prime }$ of the system $A x = b$ has the form

moreover the normal pseudosolution

If we have an inconsistent system $A x = b$ of linear inhomogeneous equations, then from the point of view of the theory of linear operators this is a situation in which the operator $\mathbf{A}$ is not invertible, and the vector $b$ does not lie in its image Im A. With the help of the scalar product it is possible to define the so-called pseudoinverse operator $\mathbf{A}^{+}$, which will "in the best way replace" the nonexistent inverse operator $\mathbf{A}^{-1}$.

Let the matrix $A$ of a system of equations define some linear map $\mathbf{A}: \mathbb {R}^{n} \rightarrow \mathbb {R}^{m}$. The spaces $\mathbb {R}^{n}$ and $\mathbb {R}^{m}$ may be regarded as Euclidean, by equipping them with corresponding (e.g. standard) scalar products. Define the pseudoinverse operator $\mathrm{A}^{+}$as follows:

where $\widetilde{A} = \left.\mathrm{A}\right|_{(\operatorname {Ker} \mathbf{A})^{\perp }}$ is the operator constructed in the previous problem. Prove that:

Let $\mathrm{A}: \mathbb {R}^{n} \rightarrow \mathbb {R}^{m}$ be a linear map of Euclidean spaces given by the matrix $A$. Define the map $\mathbf{B}: \mathbb {R}^{m} \rightarrow \mathbb {R}^{n}$ as follows: let $y \in \mathbb {R}^{m}$, then define the value $B(y) \in \mathbb {R}^{n}$ as the (unique) normal pseudosolution of the system $A x = y$. Prove that:

Prove that the matrix $A^{+}$ of the pseudoinverse operator $\mathbf{A}^{+}$ (defined with respect to the standard scalar product) equals the normal pseudosolution of the matrix equation $A X = E$ (considered as an inhomogeneous system of linear equations with $n m$ unknowns).

Let $A$ be an $m \times n$ matrix over $\mathbb {C}$. The Moore-Penrose pseudo inverse matrix $A^{+}$ is the unique $n \times m$ matrix which satisfies

We also have that

is the shortest length least square solution to the problem $A\overrightarrow {x} = \overrightarrow {b}$.

Show that the curve fitting problem

by a quadratic polynomial of the form $p(t) = a_{2} t^{2}+a_{1} t+a_{0}$ leads to an overdetermined linear system.

Consider the overdetermined linear system $A\overrightarrow {x} = \overrightarrow {b}$. Find an $\hat{\overrightarrow {x}}$ such that

with the residual vector $\overrightarrow {r}(\overrightarrow {x}) := \overrightarrow {b}-A\overrightarrow {x}$ and $\left\| \cdot \right\|_{2}$ denotes the Euclidean norm.

Consider the overdetermined linear system $A\overrightarrow {x} = \overrightarrow {b}$ with

Solve this linear system in the least squares sense (see the previous problem) by the normal equations method.

An underdetermined linear system is either inconsistent or has infinitely many solutions. Consider the underdetermined linear system $H\overrightarrow {x} = \overrightarrow {y}$, where $H$ is an $n \times m$ matrix with $m>n$ and

Assume that $H\overrightarrow {x} = \overrightarrow {y}$ has infinitely many solutions. Let $Q$ be the $n \times m$ matrix

We define $\hat{\overrightarrow {x}} := Q\overrightarrow {x}$. Find

subject to the constraint $\left\| H\overrightarrow {x}-\overrightarrow {y}\right\|_{2}^{2} = 0$. Assume that $(\lambda H^{T} H+Q^{T} Q)^{-1}$ exists for all $\lambda >0$. Apply the Lagrange multiplier method.