Question

Consider the linear least squares problem of minimizing \(\|\mathbf{b}-A \mathbf{x}\|_{2}\), where \(A\) is an \(m \times n\) \((m>n)\) matrix of \(\operatorname{rank} n .\) (a) Use the SVD to show that \(A^{T} A\) is nonsingular. (b) Given an \(m \times n\) matrix \(A\) that has full column rank, show that \(A\left(A^{T} A\right)^{-1} A^{T}\) is a projector which is also symmetric. Such operators are known as orthogonal projectors. (c) Show the solution of the linear least squares problem satisfies $$ \mathbf{r}=\mathbf{b}-A \mathbf{x}=P \mathbf{b} $$ where \(P\) is an orthogonal projector. Express the projector \(P\) in terms of \(A\). (d) Let \(Q\) and \(R\) be the matrices associated with the QR decomposition of \(A\). Express the matrix \(P\) in terms of \(Q\) and \(R\). Simplify your result as much as possible. (e) With \(\mathbf{r}\) defined as usual as the residual, consider replacing \(\mathbf{b}\) by \(\hat{\mathbf{b}}=\mathbf{b}+\alpha \mathbf{r}\) for some scalar \(\alpha\). Show that we will get the same least squares solution to \(\min _{\mathbf{x}}\|A \mathbf{x}-\hat{\mathbf{b}}\|_{2}\) regardless of the value of \(\alpha\).

Short answer

Question: Prove that \(A^TA\) is nonsingular using SVD and show that the expression \(A(A^TA)^{-1}AT\) is a symmetric projector. Express the residual vector in terms of an orthogonal projector and the matrix A, and express the projector P using the QR decomposition of matrix A. Show that the solution is independent of the parameter \(\alpha\). Answer: Using the Singular Value Decomposition (SVD), we find that \(A^TA = V\Sigma^2 V^T\), making it positive definite and nonsingular. The expression \(A(A^TA)^{-1}AT\) is a symmetric projector, as shown by computing its transpose and square. The residual vector \(\mathbf{r} = \mathbf{b} - A\mathbf{x}\) can be expressed as \(P\mathbf{b}\), where \(P = (I - A(A^TA)^{-1}A^T)\) is an orthogonal projector in terms of matrix A. Using the QR decomposition, the matrix P can be expressed as \(P = I - QQ^T\). The least squares solution is independent of the parameter \(\alpha\) since the norm of the residual is proportional to the residual itself and minimization problems only depend on the norm.

Step-by-step solution

(a) Prove that \(A^TA\) is nonsingular using SVD

First, perform singular value decomposition (SVD) on the matrix \(A\). $$ A = U\Sigma V^T $$ Now, let's compute \(A^TA\): $$ A^TA = (U\Sigma V^T)^T(U\Sigma V^T) = V\Sigma^TU^TU\Sigma V^T = V\Sigma^2 V^T $$ Since \(\Sigma\) is a diagonal matrix with positive diagonal elements (singular values) and \(V\) is orthogonal, it follows that \(A^TA\) is positive definite, and hence nonsingular.

(b) Show that \(A(A^TA)^{-1}AT\) is a symmetric projector

Let \(P = A(A^T A)^{-1} A^T\). We need to show that \(P\) is symmetric and a projector. First, let's show that \(P\) is symmetric: $$ P^T = (A(A^T A)^{-1} A^T)^T = A((A^T A)^{-1})^T A^T = A(A^TA)^{-1} A^T = P $$ Now, we need to show that \(P\) is a projector. A matrix is a projector if \(P^2 = P\): $$ P^2 = A(A^TA)^{-1}A^TA(A^TA)^{-1}A^T = A(I_n)(A^TA)^{-1}A^T = A(A^TA)^{-1}A^T = P $$ Therefore, we can conclude that \(P\) is a symmetric projector.

(c) Express the residual in terms of the orthogonal projector P

Using the property of orthogonal projectors, we have: $$ \mathbf{r} = \mathbf{b} - A\mathbf{x} = (I - A(A^TA)^{-1}A^T)\mathbf{b} = P\mathbf{b} $$ Where \(P = (I - A(A^TA)^{-1}A^T)\) is the orthogonal projector in terms of \(A\).

(d) Express matrix P in terms of the QR decomposition of A

Given the QR decomposition of \(A=QR\), we can express \(P\) as follows: $$ P = I - A(A^TA)^{-1}A^T = I - QR(R^TQ^TQR)^{-1}(QR)^T = I - QR(R^TQ^TQR)^{-1}R^TQ^T $$ Now, we know that \(R^TQ^TQ = R^T\), hence: $$ P = I - QR((R^TR)^{-1})R^TQ^T = I - QR(R^{-1}(R^T)^{-1})R^TQ^T = I - QQQ^T = I - QQ^T $$ Therefore, the matrix \(P\) is expressed in terms of the QR decomposition matrices \(Q\) and \(R\).

(e) Prove that the solution is independent of the parameter \(\alpha\)

Given that \(\hat{\mathbf{b}} = \mathbf{b}+\alpha\mathbf{r}\), we want to show that \(\min_{\mathbf{x}} \|A\mathbf{x}-\hat{\mathbf{b}}\|_{2}\) is independent of \(\alpha\). The residual of this problem is given by: $$ \hat{\mathbf{r}} = \hat{\mathbf{b}} - A\mathbf{x} = (\mathbf{b}+\alpha\mathbf{r}) - A\mathbf{x} = \mathbf{r} + \alpha\mathbf{r} = (1+\alpha)\mathbf{r} $$ The norm of the residual is proportional to the residual itself since it's a scalar multiple: $$ \|\hat{\mathbf{r}}\|_{2} = |(1+\alpha)|\|\mathbf{r}\|_{2} $$ Since \(|(1+\alpha)|\) is a positive scalar, the minimization problem is equivalent to minimizing \(\|\mathbf{r}\|_{2}\), thus the least squares solution is independent of \(\alpha\).

Key concepts

Singular Value Decomposition (SVD)

Singular Value Decomposition, or SVD, is a method to factorize a matrix into three other matrices, defined as \( A = U\Sigma V^T \). This technique is very useful in linear algebra for reasons such as understanding the properties of a matrix or solving linear least squares problems.

Here, \( U \) and \( V \) are orthogonal matrices and \( \Sigma \) is a diagonal matrix containing the singular values of \( A \). The singular values are non-negative and appear in descending order. An important property of SVD is that it can tell us about the rank of the matrix \( A \). Since \( V \) is orthogonal and \( \Sigma \) is diagonal with positive elements, the matrix \( A^TA \) is not only invertible (nonsingular) but also positive definite.

In the context of least squares problems, using SVD can be a stable method for finding solutions even if the data is ill-conditioned or noisy.

QR Decomposition

QR Decomposition is another matrix factorization technique that writes a matrix \( A \) as the product of an orthogonal matrix \( Q \) and an upper triangular matrix \( R \). This is particularly useful in linear least squares and numerical calculations because it makes calculations numerically stable and efficient.

The process of decomposing a matrix into QR components is essential for solving systems of linear equations, particularly those involved in least squares problems. When you have the QR decomposition of a matrix, you can express a lot of matrix operations in simpler forms.

In the exercise, the QR decomposition helped express the orthogonal projector \( P \). By using the properties of orthogonal matrices, it simplifies the projector to \( I - QQ^T \), highlighting that operations on orthogonal matrices require less computational complexity.

Orthogonal Projectors

Orthogonal Projectors are special linear transformations that map vectors onto a subspace, providing the least error possible. The projection matrix, \( P \), is orthogonal because it is both symmetric and idempotent, meaning \( P^2 = P \).
For a given matrix \( A \) with full column rank, the projector is expressed as \( A(A^TA)^{-1}A^T \). Such projectors are extremely useful in linear regression and least squares as they enable the calculation of the best approximate solutions in an efficient way.

In the exercise, we saw that the residual vector, \( \mathbf{r} = \mathbf{b} - A\mathbf{x} \), can be expressed in terms of \( P \). This shows that the projection minimizes the distances from the data points to the subspace, providing an optimal solution to the least squares problems.

Symmetric Matrices

Symmetric matrices are square matrices that are equal to their transpose, \( A = A^T \). This property is significant in many areas of mathematics and engineering. In the context of the linear least squares exercise, symmetric matrices appear naturally in forms like \( A^TA \) and projection matrices like \( P \).

The symmetry ensures that these matrices have real eigenvalues and orthogonal eigenvectors, which simplifies many calculations, including those in numerical linear algebra. Inverting symmetric matrices is easier and often leads to stable numerical computations.

Moreover, symmetric matrices are associated with several important decompositions, like the spectral decomposition, further aiding efficient computation and error minimization in least squares solutions.