QR Factorization

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.

(QR and Cholesky Factorizations). Let \(A\) be a nonsingular square matrix and let \(A = QR\) and \(A^*A = U^*U\) be the QR factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj}, u_{jj} > 0\) are in effect. Is it true or false that \(R = U\)? Justify your answer with mathematical details.

(QR and Cholesky Factorizations). Let \(A\) be a nonsingular square matrix and let \(A = QR\) and \(A^*A = U^*U\) be the QR factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj}, u_{jj} > 0\) are in effect. Is it true or false that \(R = U\)? Justify your answer with mathematical details.

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.

Matrix Factorizations

Let \(A\) be a nonsingular square real matrix and let \(A=QR\) and \(A^TA=H^TH\) be QR and Cholesky factorizations, respectively, with the usual normalizations \(r_{jj},h_{jj}>0\). Is it true or false that \(R=H\)? Justify your answer.

Hadamard’s inequality

Let \(A\in \mathbb {C}^{N\times N}\) be comprised of columns \(a_i\in \mathbb {C}^N\), \(i=1,\ldots ,N\). Prove that \[ |\det A|\le \prod _{i=1}^{N}\|a_i\|_2. \] You may use, for example, a QR decomposition/Gram-Schmidt argument.

Positive Definite Matrices The Cholesky decomposition of a (symmetric and) positive definite matrix is defined to be a factorization of the form \(A=LL^T\) where \(L\) is lower triangular. Show that the Cholesky decomposition exists. Discuss whether or not it is unique.

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\).

\(QR\) and Cholesky Factorizations

Let \(A\) be a nonsingular square matrix and let \(A=QR\) and \(A^*A=U^*U\) be the \(QR\) factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj},u_{jj}>0\) are in effect. Is it true or false that \(R=U\)? Justify your answer.

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. \]

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.

Householder Reflections A Householder Reflection \(H\) is an \(n\times n\) orthogonal matrix of the form \[ H=I-2uu^T \tag {1} \] where \[ \lVert u\rVert _2=1 \tag {2} \] and \(I\) is the \(n\times n\) identity matrix. Let \(a\in \mathbb {R}^n\) be a given (non-zero) vector. Show how to pick \(u\) in (1) such that \[ Ha=\lVert a\rVert _2 e_1 \tag {3} \] where \(e_1\) is the first unit vector. Describe how to use this technique to compute the \(QR\) factorization of an \(n\times n\) matrix \(A\).

Frobenius Norm The Frobenius Norm \(\lVert A\rVert _F\) of an \(n\times n\) matrix \(A\) is defined by \[ \lVert A\rVert _F= \sqrt {\sum _{i=1}^n\sum _{j=1}^n a_{ij}^2}. \tag {4} \] Let \(H=I-2uu^T\) be a Householder reflection as in the preceding problem and compute the Frobenius Norm of \(H\).

The \(QR\) factorization Describe the \(QR\) factorization of an \(m\times n\) matrix \(A\), how to compute it, and what it can be used for.

The QR Algorithm Outline the basic ingredients of the \(QR\) algorithm for solving eigenvalue problems.

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 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.

Given a set of linearly independent vectors \(u_1,u_2,\ldots ,u_n\)

1. Describe the Gram-Schmidt procedure to produce an orthogonal set of vectors from the original set.
2. Suppose \(U\) is a matrix with linearly independent columns. Describe the \(QR\) factorization of \(U\) using Householder transformations.
3. In what sense are these two procedures equivalent? Prove your answer.

The QR Factorization. Let \(A\) be an \(m\times n\) matrix, where \(m\ge n\). What is the QR factorization of \(A\)? How do you compute it? What do you use it for?

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.

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.