Least Squares and Normal Equations

Least Squares Problems. Let \(A \in \mathbb {R}^{m \times n}\) with \(m > n\) have rank \(n\) and \(b \in \mathbb {R}^m\). The Least Squares problem is to find \(x \in \mathbb {R}^n\) which makes \(\|Ax - b\|_2\) as small as possible.

1. Show that \(x\) solves this Least Squares problem if and only if \(A^T Ax = A^T b\).
2. What is meant by the QR factorization of matrix \(A\)?
3. Show how to use the QR factorization of \(A\) to solve the Least Squares problem.

Least Squares Problems. Let \(A \in \mathbb {R}^{m \times n}\) with \(m > n\) have rank \(n\) and \(b \in \mathbb {R}^m\). The Least Squares problem is to find \(x \in \mathbb {R}^n\) which makes \(\|Ax - b\|_2\) as small as possible.

1. Show that \(x\) solves this Least Squares problem if and only if \(A^T Ax = A^T b\).
2. What is meant by the QR factorization of matrix \(A\)?
3. Show how to use the QR factorization of \(A\) to solve the Least Squares problem.

Overdetermined Linear System

Solve the following overdetermined linear system in the sense of the least squares: \[ z+y=1,\qquad z-y=2,\qquad 4z+2y=4.8. \]

Suppose \(A\) is an \(m\times n\) real matrix with \(m>n\), and \(b\in \mathbb {R}^m\). For any vector \(v\in \mathbb {R}^m\), let \[ \|v\|_2=\sqrt {\sum _{i=1}^m v_i^2} \] as usual. Describe how to solve the Least Squares Problem \[ \|Ax-b\|_2=\min \] using the \(QR\) factorization of \(A\). Briefly state how you would compute the \(QR\) factorization.

1. Describe the Gram-Schmidt orthogonalization procedure for a set of \(n\)-vectors \(\{u_1,u_2,\ldots ,u_k\}\).
2. Suppose \(k<n\) and that the vectors \(\{u_1,u_2,\ldots ,u_k\}\) are linearly independent. Show that the Gram-Schmidt procedure is equivalent to factoring the matrix \(U\) with column vectors \(\{u_1,u_2,\ldots ,u_k\}\) as \(U=QR\) where \(R\) is triangular. What is the structure of \(Q\)?
3. Use this factorization of \(U\) to find the least-squares solution of \(Ux=b\).

This problem examines features of the differential operator \[ Lu=u'' \] subject to boundary conditions \(u(-1)+u(1)=0\) and \(u'(-1)=u'(1)\).

1. What is the adjoint of this operator? Is it self-adjoint?
2. What is the nullspace of the operator and what is the nullspace of the adjoint operator?
3. Under what conditions on \(f\), \(a\), and \(b\) does the boundary value problem \[ u''=f,\qquad u(-1)+u(1)=a,\qquad u'(-1)-u'(1)=b \] have a solution?
4. Find the smallest least squares solution for the boundary value problem \[ u''=1,\qquad u(-1)+u(1)=1,\qquad u'(-1)-u'(1)=1. \] What equation does this least squares solution satisfy?

1. The least squares psuedo-inverse of \(A\) is a matrix \(B\) which satisfies what two properties?
2. Find the pseudoinverse of the matrix \[ A= \begin {pmatrix} 1 & 2\\ 1 & 2 \end {pmatrix}. \]

QR factorization Show how to compute the QR factorization of a real \(m\times n\) matrix \(A\) (with \(m\geq n\)) using Householder reflections, and describe how to use the QR factorization to solve the Least Squares problem \[ \|Ax-b\|_2=\min . \tag {1} \]

Least Squares

Suppose \(A\in \mathbb {R}^{m\times n}\) has linearly independent columns, and \(C\in \mathbb {R}^{\ell \times n}\) has linearly independent rows. Let \(d\in \mathbb {R}^\ell \) and \(b\in \mathbb {R}^m\). Show how two full-rank QR factorizations can be used to solve the linearly constrained least squares problem: \[ \text {Find } x^*\in \{x\in \mathbb {R}^n:Cx=d\} \text { which minimizes } \|b-Ax^*\|_2. \]

Suppose that \(L\) is a bounded linear operator in a Hilbert space \(H\) with closed range.

1. Prove the Fredholm alternative theorem for solutions of the inhomogeneous equation \(Lu=f\) with \(u,f\in H\).
2. Suppose that \(L\) is invertible and has a complete orthonormal set of eigenfunctions \(\phi _n\), integer \(n\). Solve the inhomogeneous equation of part (a) using an eigenfunction expansion.
3. Suppose that the adjoint operator \(L^*\) has a nontrivial nullspace \(\mathcal {N}(L^*)\) spanned by the functions \(\psi _i\), \(i=1,\ldots ,m\) and \(f\) does not lie in the orthogonal complement of \(\mathcal {N}(L^*)\). Let \(L\) have a nullspace spanned by the functions \(\phi _i\), \(i=1,\ldots ,m\). Explain the construction of the smallest least squares solution.

Let \(A\in \mathbb {R}^{n\times m}\), \(B\in \mathbb {R}^{r\times m}\), and \(b\in \mathbb {R}^n\) be given. Assume \(R(B^*)=N(A)\). For fixed \(\mu \ge 0\), consider the problem \[ \min _{x\in \mathbb {R}^m} \|Ax-b\|_2^2+\mu \|Bx\|_2^2. \]

1. Find the necessary conditions (analogous to the normal equations for the standard least-squares problem) and prove that the necessary conditions have a solution when \(\mu =0\).
2. Prove that the necessary conditions have a unique solution if \(\mu >0\).

Linear Least Squares The Linear Least Squares problem for an \(m\times n\) real matrix \(A\) and \(b\in \mathbb {R}^m\) is the problem:

Find \(x\in \mathbb {R}^n\) such that \(\lVert Ax-b\rVert _2\) is minimized.

a) Suppose that you have data \(\{(t_j,y_j)\}\), \(j=1,2,\ldots ,m\) that you wish to approximate by an expansion \[ p(t)=\sum _{k=1}^n x_k\phi _k(t). \] Here, the functions \(\phi _k(t)\) are given functions. Which norm on the difference between the approximation function \(p\) and the data gives rise to a linear least squares problem for the unknown expansion coefficients \(x_k\)? What is the matrix \(A\) in this case, and what is the vector \(b\)?

b) Suppose that \(A\) is a real \(m\times n\) matrix of full rank and let \(b\in \mathbb {R}^m\). Show that the Least Squares problem has a unique solution and describe the geometry of the Least Squares problem (in terms of vectors and/or subspaces of \(\mathbb {R}^m\) and/or \(\mathbb {R}^n\)).

c) For the matrix \(A\) and vector \(b\) of part b), answer the following questions: What are the ‘normal equations’ for the Least Squares problem? How can they be used to solve the Least Squares problem? What is the QR factorization of \(A\) and how can it be used to solve the Least Squares problem? Compare and contrast these approaches for numerically solving the Least Square problem.

LS Problems and SVD Let \(A\) be a real \(m\times n\) matrix \((m>n)\) of full rank and let \(b\in \mathbb {R}^m\), the least square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

a) (13%) Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) singular value decomposition (SVD). Discuss briefly the advantages and disadvantages of each approach. In particular, give a geometric interpretation of the normal equation approach, and explain why it is often to be avoided.

b) (7%) In addition to minimizing the above norm, we impose the constraint: \(\lVert x\rVert _2\le \beta \), for some constant \(\beta >0\). This is a constrained LS problem. Use SVD to formulate and solve this problem, notice that there are different cases where a Lagrange multiplier may be needed.

The “best” least squares solution of the boundary value problem \(u''+u=0\), \(u(0)=\alpha \), \(u(\pi )=0\) is the unique exact solution of what problem?

Linear Least Squares and Singular Value Decomposition Let \(A\) be a real \(m\times n\) matrix \((m>n)\) of full rank and let \(b\in \mathbb {R}^m\), the least square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) singular value decomposition (SVD). Discuss briefly the advantages and disadvantages of each approach. In particular, give a geometric interpretation of the normal equation approach, and explain why it is often to be avoided. Characterize the difficulties in a rank-deficient least square problem and make a suggestion about which method you should use.

Linear Least Squares The Linear Least Squares problem for an \(m\times n\) real matrix \(A\) and \(b\in \mathbb {R}^m\) is the problem: \[ \text {Find }x\in \mathbb {R}^n\text { such that }\lVert Ax-b\rVert _2\text { is minimized.} \]

a) Suppose that you have data \(\{(t_j,y_j)\}\), \(j=1,2,\ldots ,m\) that you wish to approximate by an expansion \[ p(t)=\sum _{k=1}^n x_k\phi _k(t). \] Here, the functions \(\phi _k(t)\) are given functions. Which norm on the difference between the approximation function \(p\) and the data gives rise to a linear least squares problem for the unknown expansion coefficients \(x_k\)? What is the matrix \(A\) in this case, and what is the vector \(b\)?

b) Suppose that \(A\) is a real \(m\times n\) matrix of full rank and let \(b\in \mathbb {R}^m\). Show that the Least Squares problem has a unique solution and describe the geometry of the Least Squares problem (in terms of vectors and/or subspaces of \(\mathbb {R}^m\) and/or \(\mathbb {R}^n\)).

c) For the matrix \(A\) and vector \(b\) of part b), answer the following questions: What are the ‘normal equations’ for the Least Squares problem? How can they be used to solve the Least Squares problem? What is the QR factorization of \(A\) and how can it be used to solve the Least Squares problem? Compare and contrast these approaches for numerically solving the Least Square problem.

1. Describe the Gram-Schmidt orthogonalization procedure for a set of \(n\)-vectors \(\{u_1,u_2,\ldots ,u_k\}\).
2. Suppose \(k<n\) and that the vectors \(\{u_1,u_2,\ldots ,u_k\}\) are linearly independent. Show that the Gram-Schmidt procedure is equivalent to factoring the matrix \(U\) with column vectors \(\{u_1,u_2,\ldots ,u_k\}\) as \(U=QR\) where \(R\) is triangular. What is the structure of \(Q\)?
3. Use this factorization of \(U\) to find the least-squares solution of \(Ux=b\).

Linear Least Squares Let \(A\) be a real \(m\times n\) matrix of full rank \((m>n)\) and let \(b\in \mathbb {R}^m\). The Least Square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) Singular Value Decomposition (SVD). Discuss briefly the advantages and disadvantages of these approaches. In particular, give a geometric interpretation of the normal equation approach and explain why it is not often used?

Linear Least Squares The Linear Least Squares problem for an \(m\times n\) real matrix \(A\) and \(b\in \mathbb {R}^m\) is the problem: \[ \text {Find }x\in \mathbb {R}^n\text { such that }\lVert Ax-b\rVert _2\text { is minimized.} \]

a) Suppose that you have data \(\{(t_j,y_j)\}\), \(j=1,2,\ldots ,m\) that you wish to approximate by an expansion \[ p(t)=\sum _{k=1}^n x_k\phi _k(t). \] Here, the functions \(\phi _k(t)\) are given functions. Which norm on the difference between the approximation function \(p\) and the data gives rise to a linear least squares problem for the unknown expansion coefficients \(x_k\)? What is the matrix \(A\) in this case, and what is the vector \(b\)?

b) Suppose that \(A\) is a real \(m\times n\) matrix of full rank and let \(b\in \mathbb {R}^m\). Show that the Least Squares problem has a unique solution and describe the geometry of the Least Squares problem (in terms of vectors and/or subspaces of \(\mathbb {R}^m\) and/or \(\mathbb {R}^n\)).

c) For the matrix \(A\) and vector \(b\) of part b), answer the following questions: What are the ‘normal equations’ for the Least Squares problem? How can they be used to solve the Least Squares problem? What is the QR factorization of \(A\) and how can it be used to solve the Least Squares problem? How can the SVD of \(A\) be used to solve the Least Squares problem? Compare and contrast these approaches for numerically solving the Least Square problem.

Linear Least Squares The Linear Least Squares problem for an \(m\times n\) real matrix \(A\) and \(b\in \mathbb {R}^m\) is the problem: \[ \text {Find }x\in \mathbb {R}^n\text { such that }\lVert Ax-b\rVert _2\text { is minimized.} \]

a) Suppose that you have data \(\{(t_j,y_j)\}\), \(j=1,2,\ldots ,m\) that you wish to approximate by an expansion \[ p(t)=\sum _{k=1}^n x_k\phi _k(t). \] Here, the functions \(\phi _k(t)\) are given functions. Which norm on the difference between the approximation function \(p\) and the data gives rise to a linear least squares problem for the unknown expansion coefficients \(x_k\)? What is the matrix \(A\) in this case, and what is the vector \(b\)?

b) Suppose that \(A\) is a real \(m\times n\) matrix of full rank and let \(b\in \mathbb {R}^m\). What are the ‘normal equations’ for the Least Squares problem? How can they be used to solve the Least Squares problem? What is the QR factorization of \(A\) and how can it be used to solve the Least Squares problem? Compare and contrast these approaches for numerically solving the Least Square problem.

Use a Green’s function to find the representation of a possible solution to \[ y''+\omega ^2y=f(x),\qquad y(0)=y'(1)=0 \] for arbitrary values of the parameter \(\omega \). For what values of \(\omega \) does the solution exist? If the solution does not exist find the least square solution. Explain the meaning of the least square solution.

Let \(A\) be an \(m\times n\) matrix and let the \(n\times m\) matrix \(A'\) denote the Least Square Pseudo-Inverse of \(A\).

1. State the conditions that define \(A'\).
2. Show that \(A'\) always exists.
3. Construct \(A'\) explicitly for the \(2\times 2\) matrix \[ A=\begin {pmatrix} 1 & 1\\ 0.5 & 0.5 \end {pmatrix}. \]

Least Squares. Describe in general the problem of approximating a given function in the Least Squares sense by a linear combination of certain basis functions. Discuss the significance of orthogonal basis functions. If you have a basis that is not orthogonal, how can you obtain an orthogonal basis that spans the same space?

Linear Least Squares Let \(A\) be a real \(m\times n\) matrix of full rank and let \(b\in \mathbb {R}^m\) and consider the Least Squares problem: \[ \text {Find }x\in \mathbb {R}^n\text { such that }\lVert Ax-b\rVert _2\text { is minimized.} \] What are the ‘normal equations’ for the Least Squares problem? How can they be used to solve the Least Squares problem? What is the QR factorization of \(A\) and how can it be used to solve the Least Squares problem? What is the Singular Value Decomposition (SVD) of \(A\) and how can it be used to solve the Least Squares problem? Compare and contrast these approaches for numerically solving the Least Square problem.

Let \(A\) be a real \(m\times n\) matrix.

1. Define the Least Square Pseudo-Inverse \(A'\).
2. Show how Gaussian Elimination can be used to compute \(A'\).

a) What is the best least squares approximation to \(f(x)=\cos 3x\) by functions of the form \[ a_0+a_1\cos x+a_2\cos ^2 x+b_1\sin x+b_2\sin ^2 x \] with the inner product given by \[ (v,w)_C=\frac {1}{2\pi }\int _0^{2\pi }v(x)\overline {w(x)}\,dx \]

b) What if the inner product is \[ (v,w)_D=\frac {1}{J}\sum _{j=0}^{J-1}v(x_j)\overline {w(x_j)} \] with \(x_j=jh\), \(h=2\pi /J\).

c) Briefly discuss the normal equations (do they form a well- or ill-conditioned system?), the Gram-Schmidt process, QR factorization in the context of parts a) and b). Observe the connection with problem #2.

Let \(A\) be an \(m\times n\) matrix and let the \(n\times m\) matrix \(A'\) denote the Least Square Pseudo-Inverse of \(A\).

1. State the conditions that define \(A'\).
2. Show that \(A'\) always exists.
3. Construct \(A'\) explicitly for the \(2\times 2\) matrix \[ A=\begin {pmatrix} 1 & 1\\ 0 & 0 \end {pmatrix}. \]

Find the adjoint operator, its domain and the least squares solution of the problem \(Lu\equiv 4u''+u=e^x\) for \(0\le x\le \pi /2\) if \(u(0)=\alpha \) and \(u(\pi /2)=\beta \).