Singular Value Decomposition

Singular Value Decomposition. Let \(A \in \mathbb {R}^{m \times n}\), with \(m \ge n\).

1. What is the singular value decomposition (SVD) of \(A\)? Does every such matrix \(A\) have an SVD? Prove that it does or show an example of a matrix \(A\) which does not have an SVD.
2. For any \(m \times n\) matrix \(A\) with an SVD and \(\epsilon > 0\), show that there is a full-rank matrix \(B\) for which \(\|A - B\|_2 < \epsilon \).
3. For \(m \times n\) matrix \(A\), give orthonormal bases for the subspaces \(\operatorname {range}(A)\), \(\operatorname {null}(A)\), \(\operatorname {range}(A^*)\), and \(\operatorname {null}(A^*)\).

(Properties via SVD).

1. Consider \(A \in \mathbb {C}^{m \times n}\). Define what we mean by the singular value decomposition of \(A\).
2. Show that the rank of \(A\) is \(r\), the number of nonzero singular values.
3. Show that the largest singular value of \(A\), call it here \(\sigma _{\max }(A)\), satisfies the relation (with \(x\) and \(y\) are being nonzero vectors below), \[ \sigma _{\max }(A) = \max _{y \in \mathbb {C}^m,\ x \in \mathbb {C}^n} \frac {|y^*Ax|}{\|x\|_2\|y\|_2}. \]

(Properties via SVD). Suppose \(A \in \mathbb {C}^{m \times n}\) has an SVD, \(A = U\Sigma V^*\), where \(u_j\) are the left singular vectors, \(U = \{u_j\}\), \(v_j\) are the right singular vectors, \(V = \{v_j\}\), and \(\sigma _j\) are the singular values. Assume rank of the matrix \(A\) is \(r\). For any \(\nu \) with \(0 \le \nu \le r\), define \[ A_\nu = \sum _{j=1}^{\nu }\sigma _j u_j v_j^*, \] (if \(\nu = p = \min \{m,n\}\), define \(\sigma _{\nu +1} = 0\)). Show that, \[ \|A - A_\nu \|_2 = \inf _{\substack {B \in \mathbb {C}^{m \times n}\\ \operatorname {rank}(B) \le \nu }} \|A - B\|_2 = \sigma _{\nu +1}. \]

(Properties via SVD). Suppose \(A \in \mathbb {C}^{m \times m}\) has an SVD, \(A = U\Sigma V^*\). Find an eigenvalue decomposition of the \(2m \times 2m\) hermitian matrix (using information about SVD for \(A\)), \[ \begin {bmatrix} 0 & A^* \\ A & 0 \end {bmatrix}. \]

Singular Value Decomposition. Let \(A \in \mathbb {R}^{m \times n}\), with \(m \ge n\).

1. What is the singular value decomposition (SVD) of \(A\)? Does every such matrix \(A\) have an SVD? Prove that it does or show an example of a matrix \(A\) which does not have an SVD.
2. For any \(m \times n\) matrix \(A\) with an SVD and \(\epsilon > 0\), show that there is a full-rank matrix \(B\) for which \(\|A - B\|_2 < \epsilon \).
3. For \(m \times n\) matrix \(A\), give orthonormal bases for the subspaces \(\operatorname {range}(A)\), \(\operatorname {null}(A)\), \(\operatorname {range}(A^*)\), and \(\operatorname {null}(A^*)\).

(Rank-One Perturbation of the Identity). If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B = I + uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1} = I + \beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

(Properties via SVD).

1. Consider \(A \in \mathbb {C}^{m \times n}\). Define what we mean by the singular value decomposition of \(A\).
2. Prove that any matrix in \(\mathbb {C}^{m \times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

(Rank-One Perturbation of the Identity). If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B = I + uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1} = I + \beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

(Properties via SVD).

1. Consider \(A \in \mathbb {C}^{m \times n}\). Define what we mean by the singular value decomposition of \(A\).
2. Show that the rank of \(A\) is \(r\), the number of nonzero singular values.
3. Show that the largest singular value of \(A\), call it here \(\sigma _{\max }(A)\), satisfies the relation \[ \sigma _{\max }(A) = \max _{y \in \mathbb {C}^m,\ x \in \mathbb {C}^n} \frac {|y^*Ax|}{\|x\|_2\|y\|_2}. \]

(Matrix properties) For each of the following statements, either prove that it is true, or show it’s false with a counterexample.

a. For \(A \in \mathbb {C}^{m \times n}\) any matrix, and \(U \in \mathbb {C}^{m \times m}\) any unitary matrix, then \(\|UA\|_2 = \|A\|_2\). b. For \(A \in \mathbb {C}^{n \times n}\) any matrix, if \(\rho (A) = 0\), then \(A = 0\). (Recall that \(\rho (A)\) is the spectral radius of \(A\), i.e., the maximum of the moduli of the eigenvalues of \(A\).)

c. For \(A \in \mathbb {C}^{m \times n}\) any matrix with \(m \ge n\), then the squared singular values of \(A\) equal the eigenvalues of \(A^*A\).

Rank-One Perturbation of the Identity

If \(x\) and \(y\) are \(m\)-vectors, the matrix \(A=I+xy^*\) is known as a rank-one perturbation of the identity. Show that if \(A\) is nonsingular, then its inverse has the form \(A^{-1}=I+\beta xy^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(x\) and \(y\) is \(A\) singular? If it is singular, what is \(\operatorname {null}(A)\)?

Properties via SVD 

Prove that any matrix in \(\mathbb {C}^{m\times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

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.

Rank-One Perturbation of the Identity

If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B=I+uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1}=I+\beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

Properties via SVD

Prove that any matrix in \(\mathbb {C}^{m\times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

Singular Value Decomposition

a) Consider \(A\in \mathbb {C}^{m\times n}\). Define what we mean by the singular value decomposition of \(A\).

b) Show that the rank of \(A\) is \(r\), the number of nonzero singular values.

Singular Value Decomposition (SVD)

a) Consider \(A\in \mathbb {C}^{m\times n}\). Define what we mean by the singular value decomposition of \(A\).

b) Consider \(A\in \mathbb {C}^{m\times m}\) and show that \[ \lvert \det (A)\rvert =\prod _{i=1}^m\sigma _i, \] where \(\{\sigma _i\}\) are the singular values of \(A\).

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.

Let \(A\) be an \(m\times n\) matrix where you may assume that \(m\geq n\). Define what is meant by the Singular Value Decomposition of \(A\). Then use it to show that if the rank of \(A\) is \(p\) then there exists an \(m\times p\) matrix \(X\) and an \(n\times p\) matrix \(Y\) such that \[ A=XY^T. \]

SVD Let \(A\) be an \(m\times n\) matrix. Define what we mean by the singular value decomposition of \(A\). Show that the singular value decomposition exists.

Singular Value Decomposition Let \(A\) be an \(m\times n\) matrix. You may assume that \(m\geq n\). Define what is meant by the singular value decomposition of \(A\) and show that every \(m\times n\) matrix has one.

Find a singular value decomposition and pseudoinverse of the matrix \[ A= \begin {pmatrix} 1 & 1\\ 2 & 2\\ 0 & 0 \end {pmatrix}. \]

Singular Value Decomposition Let \(A\) be a real \(m\times n\) matrix \((m>n)\) of full rank. We are interested in the singular value decomposition of \(A=U\Sigma V^T\). It is known that algorithms for SVD can be derived by turning the SVD problem into an eigenvalue problem. One such approach is to find the eigenvalue decomposition of the \((m+n)\times (m+n)\) symmetric matrix \[ \begin {bmatrix} 0 & A^T\\ A & 0 \end {bmatrix}. \] Establish the connections between the singular values, left and right singular vectors of \(A\) and the eigenvalues, eigenvectors of the above matrix. You should pay particular attention to the case \(m>n\). Comment on the advantages and disadvantages of this approach compared with an approach based on the eigendecomposition of \(A^TA\).

SVD Let \(A\) be a real \(m\times n\) matrix \((m\ge n)\) of full rank. We are interested in the singular value decomposition of \(A=U\Sigma V^T\). It is known that algorithms for SVD can be derived by turning the SVD problem into an eigenvalue problem. One such approach is to find the eigenvalue decomposition of the \((m+n)\times (m+n)\) symmetric matrix \[ \begin {bmatrix} 0 & A^T\\ A & 0 \end {bmatrix}. \] Establish the connections between the singular values, left and right singular vectors of \(A\) and the eigenvalues, eigenvectors of the above matrix. You should pay particular attention to the case \(m>n\). Comment on the advantages and disadvantages of this approach compared with an approach based on the eigendecomposition of \(A^T A\).

Sensitivity Consider a \(6\times 6\) symmetric positive definite matrix \(A\) with singular values \(\sigma _1=1000\), \(\sigma _2=500\), \(\sigma _3=300\), \(\sigma _4=20\), \(\sigma _5=1\), \(\sigma _6=0.01\).

a) Suppose you use a Cholesky factorization package on a computer with a machine epsilon \(10^{-14}\) to solve the system \(Ax=b\) for some nonzero vector \(b\). How many digits of accuracy do you expect in the computed solution? Justify your answer in terms of condition and stability. You may assume that the entries of \(A\) and \(b\) are exactly represented in the computer’s floating-point system.

b) Suppose that instead you use an iterative method to find an approximate solution to \(Ax=b\) and you stop iterating and accept iterate \(x^{(k)}\) when the residual \(r^{(k)}=Ax^{(k)}-b\) has 2-norm less than \(10^{-9}\). Give an estimate of the maximum size of the relative error in the final iterate? Justify your answer.

Singular Value Decomposition The singular value decomposition (SVD) of a real \(m\times n\) matrix \(A\) (you may assume \(m\ge n\)) is defined by \[ A=U\Sigma V^T \] where \(U\) is \(m\times m\) and orthogonal. \(\Sigma \) is \(m\times n\) and diagonal. \(V\) is \(n\times n\) and orthogonal.

a) Prove that every matrix \(A\) has an SVD.

b) Use the SVD of \(A\) to prove the famous result from linear algebra that the null space of \(A\) is the orthogonal complement of the range of \(A^T\) (the adjoint of \(A\)).

c) For a nonsingular \(m\times m\) matrix \(A\), the solution to the system \(Ax=b\) can be expressed in terms of \(A\)’s SVD. Write \(b=\sum _{j=1}^m c_j u_j\) where \(u_j\) is the \(j\)th column of \(U\). Then the solution \(x\) is \[ x=\sum _{j=1}^m \frac {c_j}{\sigma _j}v_j \] where \(v_j\) is the \(j\)th column of \(V\) and \(\sigma _j\) is the \(j\)th singular value. Verify this formula. Consider the special case \(b=u_1\). What perturbation \(\delta b\) in \(b\), with \(\lVert \delta b\rVert _2=1\), causes the largest change \(\delta x\) in the solution \(x\)?

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 Singular Value Decomposition Define the term “singular value decomposition” and show that every \(m\times n\) matrix \(A\) has a singular value decomposition.

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.

Singular Value Decomposition The singular value decomposition (SVD) of a real \(m\times n\) matrix \(A\) (you may assume \(m\ge n\)) is defined by \[ A=U\Sigma V^T \] where \(U\) is \(m\times m\) and orthogonal, \(\Sigma \) is \(m\times n\) and diagonal, \(V\) is \(n\times n\) and orthogonal.

a) Prove that every matrix \(A\) has an SVD.

b) Use the SVD of \(A\) to prove the famous result from linear algebra that the null space of \(A\) is the orthogonal complement of the range of \(A^T\) (the adjoint of \(A\)).

c) For a nonsingular \(m\times m\) matrix \(A\), the solution to the system \(Ax=b\) can be expressed in terms of \(A\)’s SVD. Write \(b=\sum _{j=1}^m c_j u_j\) where \(u_j\) is the \(j^{\text {th}}\) column of \(U\). Then the solution \(x\) is \[ x=\sum _{j=1}^m \frac {c_j}{\sigma _j}v_j \] where \(v_j\) is the \(j^{\text {th}}\) column of \(V\) and \(\sigma _j\) is the \(j^{\text {th}}\) singular value. Verify this formula. Consider the special case \(b=u_1\). What perturbation \(\delta b\) in \(b\), with \(\lVert \delta b\rVert _2=1\), causes the largest change \(\delta x\) in the solution \(x\)?

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?

Singular Value Decomposition Define the singular value decomposition of a real \(m\times n\) matrix with \(m\ge n\). Is the SVD unique for a given matrix \(A\)? How is an SVD problem connected with an eigendecomposition of a symmetric matrix? Sketch the general structure of algorithms for those imported from eigendecomposition, namely, how do you reduce \(A\) to some form more manageable? How do you obtain the information about the rank of \(A\) through the SVD of \(A\)? If \(A\) is square and nonsingular, how does the SVD of \(A\) help you determine the sensitivity of the solution \(x\) for \(Ax=b\)?

1. State the Singular Value Decomposition Theorem.
2. For any \(n\times m\) real matrices \(A\) and \(B\), show the \(\operatorname {Tr}(AB^*)=\operatorname {Tr}(BA^*)\).
3. Show that \(\lVert A\rVert =\sqrt {\operatorname {Tr}(AA^*)}\) is a norm.
4. Suppose \(A\) and \(B\) are \(n\times m\) real matrices. Find the orthogonal matrix \(Q\) that minimizes \(\lVert QA-B\rVert \) using the norm of part c.

Singular Value Decomposition Suppose that \(A\) is a real \(m\times n\) matrix, \(m\ge n\).

a) What is the singular value decomposition (SVD) of \(A\)? Does every matrix \(A\) of this type have an SVD? If your answer is yes, prove the assertion. If your answer is no, give an example of a matrix \(A\) which has no SVD.

b) For a matrix \(A\) which does have an SVD, how would having the SVD give easy access to information about the rank of \(A\)? If \(A\) were \(m\times m\) and nonsingular, how would knowing \(A\)’s SVD help you determine the sensitivity of the solution of a linear system of the following form \[ Ax=b? \]

c) For a nonsingular matrix \(A\) which does have an SVD, express the relative distance from \(A\) to the nearest rank deficient matrix in terms of \(A\)’s singular values.

Singular Value Decomposition Suppose that \(A\) is a real \(m\times n\) matrix with \(m\ge n\). What is the singular value decomposition (SVD) of \(A\)? Does every matrix \(A\) of this type have an SVD? If your answer is yes, prove the assertion. If your answer is no, give an example of a matrix \(A\) which has no SVD. For a matrix \(A\) which does have an SVD, how would having the SVD give easy access to information about the rank of \(A\)? If \(A\) were \(n\times n\) and nonsingular, how would knowing \(A\)’s SVD help you determine the sensitivity of the solution of a linear system of the following form \[ Ax=b? \]

Sensitivity of Solution of Linear System Suppose that \(A\) is a real non-singular \(n\times n\) matrix. Consider the family of linear systems \(Ax(\epsilon )=b+\epsilon c\), where \(b\) and \(c\) are given nonzero vectors in \(\mathbb {R}^n\), and \(\epsilon \) is a real parameter. Let \(x=x(0)\) be the solution for \(\epsilon =0\). Let \(\lVert \cdot \rVert _2\) denote the Euclidean vector norm.

a) Show that \[ \frac {\lVert x(\epsilon )-x\rVert _2}{\lVert x\rVert _2} \le \lVert A\rVert _2\lVert A^{-1}\rVert _2 \frac {\lVert \epsilon c\rVert _2}{\lVert b\rVert _2}. \] The expression \(\lVert A\rVert _2\lVert A^{-1}\rVert _2\) is the condition number of \(A\). Interpret the above inequality and explain its significance?

b) What is the Singular Value Decomposition (SVD) of \(A\)? Express the condition number above in terms of \(A\)’s singular values.

c) When the condition number is very large, the matrix is called ill-conditioned. Sometimes people say that an ill-conditioned matrix is ‘nearly-singular’. Make this precise by expressing the (relative) distance between \(A\) and the nearest singular matrix to \(A\) in terms of the condition number of \(A\).

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.