CBMS-2018-08

题目来源：[[做题/文字版题库/CBMS/2018#Question 8|2018#Question 8]] 日期：2024-07-27 题目主题: CS-Algorithms-Matrix Analysis

Solution

1. Positive Eigenvalues and Normalized Eigenvectors of ${\mathbf{A}}^T\mathbf{A}$

Given the singular value decomposition (SVD) of $\mathbf{A}$ as $\mathbf{A}=\mathbf{U\Sigma }{\mathbf{V}}^T$, we can express ${\mathbf{A}}^T\mathbf{A}$ as follows:

$${\mathbf{A}}^T\mathbf{A}=(\mathbf{U\Sigma }{\mathbf{V}}^T{)}^T(\mathbf{U\Sigma }{\mathbf{V}}^T)=\mathbf{V}{\mathbf{\Sigma }}^T{\mathbf{U}}^T\mathbf{U\Sigma }{\mathbf{V}}^T=\mathbf{V}{\mathbf{\Sigma }}^2{\mathbf{V}}^T$$

The matrix ${\mathbf{\Sigma }}^2$ is diagonal with the diagonal elements ${\sigma }_k^2$ ($k=1,\dots ,r$). Thus, the positive eigenvalues of ${\mathbf{A}}^T\mathbf{A}$ are exactly the ${\sigma }_k^2$, and the associated normalized eigenvectors are the columns of $\mathbf{V}$.

2. Surjectivity and Injectivity of $T_{\mathbf{A}}$

Surjective (onto): The mapping $T_{\mathbf{A}}:{\mathbb{R}}^m\to {\mathbb{R}}^n$ is surjective if the range of $\mathbf{A}$ spans ${\mathbb{R}}^n$, i.e., $\mathbf{A}$ has full row rank. This occurs when $r=n\le m$.

Injective (one-to-one): The mapping $T_{\mathbf{A}}$ is injective if the kernel of $\mathbf{A}$ contains only the zero vector, i.e., $\mathbf{A}$ has full column rank. This occurs when $r=m\le n$.

3. Image of $T_{\mathbf{B}}$ and Kernel of $T_{\mathbf{A}}$

The pseudoinverse ${\mathbf{A}}^{+}$ is defined as ${\mathbf{A}}^{+}=\mathbf{V}{\mathbf{\Sigma }}^{-1}{\mathbf{U}}^T$. Consider $\mathbf{B}={\mathbf{I}}_m-{\mathbf{A}}^{+}\mathbf{A}$.

We need to show that $\mathrm{Im}(T_{\mathbf{B}})$ is isomorphic to $\mathrm{Ker}(T_{\mathbf{A}})$. Observe the following:

$$\mathbf{BA}=({\mathbf{I}}_m-{\mathbf{A}}^{+}\mathbf{A})\mathbf{A}=\mathbf{A}-{\mathbf{A}}^{+}\mathbf{AA}=\mathbf{A}-\mathbf{A}=0$$

Thus, $\mathrm{Im}(\mathbf{B})\subseteq \mathrm{Ker}(\mathbf{A})$.

Now, consider $\mathbf{x}\in \mathrm{Ker}(\mathbf{A})$. Then $\mathbf{Ax}=0$, and

$$\mathbf{Bx}=({\mathbf{I}}_m-{\mathbf{A}}^{+}\mathbf{A})\mathbf{x}=\mathbf{x}$$

Thus, $\mathbf{x}\in \mathrm{Im}(\mathbf{B})$. Therefore, $\mathrm{Im}(\mathbf{B})=\mathrm{Ker}(\mathbf{A})$.

4. Orthogonal Decomposition

Given $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_2$ where ${\mathbf{x}}_1=\mathbf{Bx}$ and ${\mathbf{x}}_2=\mathbf{x}-{\mathbf{x}}_1$:

$${\mathbf{x}}_2=\mathbf{x}-\mathbf{Bx}=\mathbf{x}-({\mathbf{I}}_m-{\mathbf{A}}^{+}\mathbf{A})\mathbf{x}={\mathbf{A}}^{+}\mathbf{Ax}$$

To show orthogonality:

$${\mathbf{x}}_1^T{\mathbf{x}}_2=(\mathbf{Bx}{)}^T({\mathbf{A}}^{+}\mathbf{Ax})={\mathbf{x}}^T{\mathbf{B}}^T{\mathbf{A}}^{+}\mathbf{Ax}$$

Since $\mathbf{B}$ is symmetric ($\mathbf{B}={\mathbf{I}}_m-{\mathbf{A}}^{+}\mathbf{A}$):

$${\mathbf{x}}^T({\mathbf{I}}_m-{\mathbf{A}}^{+}\mathbf{A}){\mathbf{A}}^{+}\mathbf{Ax}={\mathbf{x}}^T({\mathbf{A}}^{+}\mathbf{A}-{\mathbf{A}}^{+}\mathbf{A})\mathbf{x}=0$$

Thus, ${\mathbf{x}}_1$ and ${\mathbf{x}}_2$ are orthogonal.

5. Minimizing $(\mathbf{Ax}-\mathbf{b}{)}^T(\mathbf{Ax}-\mathbf{b})$

Let ${\mathbf{x}}_0={\mathbf{A}}^{+}\mathbf{b}$. We need to show that $\mathbf{x}={\mathbf{x}}_0$ minimizes the expression.

Consider the error:

$$\mathbf{Ax}-\mathbf{b}=\mathbf{A}(\mathbf{x}-{\mathbf{x}}_0)+(\mathbf{A}{\mathbf{x}}_0-\mathbf{b})$$

Since ${\mathbf{x}}_0={\mathbf{A}}^{+}\mathbf{b}$, we have $\mathbf{A}{\mathbf{x}}_0=\mathbf{b}$, thus:

$$\mathbf{Ax}-\mathbf{b}=\mathbf{A}(\mathbf{x}-{\mathbf{x}}_0)$$

The norm to be minimized is:

$$(\mathbf{Ax}-\mathbf{b}{)}^T(\mathbf{Ax}-\mathbf{b})=(\mathbf{A}(\mathbf{x}-{\mathbf{x}}_0){)}^T(\mathbf{A}(\mathbf{x}-{\mathbf{x}}_0))$$

This is minimized when $\mathbf{x}={\mathbf{x}}_0$ since $\mathbf{A}{\mathbf{x}}_0=\mathbf{b}$ and $\mathbf{A}(\mathbf{x}-{\mathbf{x}}_0)=0$.

知识点

奇异值分解线性映射广义逆矩阵正交分解线性代数

重点词汇

• singular value decomposition (SVD) 奇异值分解
• pseudoinverse 广义逆
• surjective 满射
• injective 单射
• orthogonal decomposition 正交分解

参考资料

1. “Linear Algebra and Its Applications” by Gilbert Strang, Chapter 7: The Singular Value Decomposition (SVD)
2. “Matrix Computations” by Gene H. Golub and Charles F. Van Loan, Chapter 2: Matrix Analysis