東京大学 情報理工学系研究科 コンピュータ科学専攻 2021年2月実施 問題4

标签：

• 东京大学
• 奇异值分解
• 摩尔–彭罗斯广义逆
• 约束最优化

Author

zephyr, 祭音Myyura

Description

Let $n$ and $d$ ($n < d$) be natural numbers and $\mathbb{R}$ be the set of real numbers. Denote by $\top$ the transposition operator of a vector and a matrix. Define the inner product of two column vectors $\mathbf{x_1}, \mathbf{x_2} \in \mathbb{R}^d$ as $\mathbf{x_1}^\top \mathbf{x_2} \in \mathbb{R}$. Let $\mathbf{w} = (w_1, w_2, \ldots, w_d)^\top \in \mathbb{R}^d$ be a $d$-dimensional column vector, $\mathbf{X} \in \mathbb{R}^{n \times d}$ an $n \times d$ matrix where $\mathbf{X} \mathbf{X}^\top$ is invertible, and $\mathbf{y} \in \mathbb{R}^n$ an $n$-dimensional column vector. Consider solving the following optimization problem by using the Lagrange multipliers method:

$$\min_{\mathbf{w}} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{subject to} \quad \mathbf{y} = \mathbf{Xw},$$

where $\|\mathbf{w}\| = \sqrt{w_1^2 + w_2^2 + \ldots + w_d^2}$. The Lagrange function is given by

$$L(\mathbf{w}, \boldsymbol{\mu}) = \frac{1}{2} \|\mathbf{w}\|^2 + \boldsymbol{\mu}^\top (\mathbf{y} - \mathbf{Xw}),$$

where $\boldsymbol{\mu} \in \mathbb{R}^n$ is the Lagrange multipliers.

Let $\lambda_1, \lambda_2, \ldots, \lambda_n$ be positive real values. The sets of column vectors $\{\mathbf{u_i} \in \mathbb{R}^n\}_{i=1}^{n}$ and $\{\mathbf{v_j} \in \mathbb{R}^d\}_{j=1}^{d}$ form an orthonormal basis of $\mathbb{R}^n$ and $\mathbb{R}^d$, respectively; that is, they are all unit vectors and orthogonal to each other. Suppose that the singular value decomposition of $\mathbf{X}$ is

$$\mathbf{X} = \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top,$$

where $\mathbf{U}$ is an $n \times n$ matrix, $\mathbf{\Lambda}$ is an $n \times d$ matrix, and $\mathbf{V}$ is a $d \times d$ matrix given by

$$\mathbf{U} = (\mathbf{u_1}, \mathbf{u_2}, \ldots, \mathbf{u_n}), \quad \mathbf{\Lambda} = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 & 0 & & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n & 0 & \cdots & 0\\ \end{pmatrix}, \quad \mathbf{V}^\top = \begin{pmatrix} \mathbf{v_1}^\top \\ \mathbf{v_2}^\top \\ \vdots \\ \mathbf{v_d}^\top \\ \end{pmatrix}.$$

Moreover, define

$$\mathbf{X^-} = \mathbf{V} (\mathbf{\Lambda}^-)^{\top} \mathbf{U}^\top, \quad \text{where} \quad \mathbf{\Lambda}^- = \begin{pmatrix} \frac{1}{\lambda_1} & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \frac{1}{\lambda_2} & \cdots & 0 & 0 & & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \frac{1}{\lambda_n} & 0 & \cdots & 0\\ \end{pmatrix}.$$

Answer the following questions. Describe not only an answer but also the derivation process.

(1) Express $\mathbf{XX^-X}$ using only $\mathbf{X}$.

(2) Express $\mathbf{XX^\top}$ using only $\mathbf{U}$ and $\lambda_i$ ($i = 1, \ldots, n$).

(3) Suppose we wish to express the stationary points of $L(\mathbf{w}, \boldsymbol{\mu})$ in the form of $\mathbf{w} = \mathbf{A} \mathbf{y}$ and $\boldsymbol{\mu} = \mathbf{B} \mathbf{y}$. Express the matrices $\mathbf{A} \in \mathbb{R}^{d \times n}$ and $\mathbf{B} \in \mathbb{R}^{n \times n}$ using only $\mathbf{X}$.

(4) Express $\mathbf{A}$ in question (3) using only $\mathbf{X^-}$.

---

设 $n$ 和 $d$ ($n < d$) 为自然数，$\mathbb{R}$ 为实数集。记 $\top$ 为向量和矩阵的转置算子。定义两个列向量 $\mathbf{x_1}, \mathbf{x_2} \in \mathbb{R}^d$ 的内积为 $\mathbf{x_1}^\top \mathbf{x_2} \in \mathbb{R}$。设 $\mathbf{w} = (w_1, w_2, \ldots, w_d)^\top \in \mathbb{R}^d$ 为一个 $d$ 维列向量，$\mathbf{X} \in \mathbb{R}^{n \times d}$ 是一个 $n \times d$ 矩阵，其中 $\mathbf{X} \mathbf{X}^\top$ 可逆，$\mathbf{y} \in \mathbb{R}^n$ 是一个 $n$ 维列向量。考虑使用拉格朗日乘子法求解以下优化问题：

$$\min_{\mathbf{w}} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{subject to} \quad \mathbf{y} = \mathbf{Xw},$$

其中 $\|\mathbf{w}\| = \sqrt{w_1^2 + w_2^2 + \ldots + w_d^2}$。拉格朗日函数为

$$L(\mathbf{w}, \boldsymbol{\mu}) = \frac{1}{2} \|\mathbf{w}\|^2 + \boldsymbol{\mu}^\top (\mathbf{y} - \mathbf{Xw}),$$

其中 $\boldsymbol{\mu} \in \mathbb{R}^n$ 是拉格朗日乘子。

设 $\lambda_1, \lambda_2, \ldots, \lambda_n$ 为正实数。列向量集合 $\{\mathbf{u_i} \in \mathbb{R}^n\}_{i=1}^{n}$ 和 $\{\mathbf{v_j} \in \mathbb{R}^d\}_{j=1}^{d}$ 分别构成 $\mathbb{R}^n$ 和 $\mathbb{R}^d$ 的正交基；即它们都是单位向量且彼此正交。假设 $\mathbf{X}$ 的奇异值分解为

$$\mathbf{X} = \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top,$$

其中 $\mathbf{U}$ 是一个 $n \times n$ 矩阵，$\mathbf{\Lambda}$ 是一个 $n \times d$ 矩阵，$\mathbf{V}$ 是一个 $d \times d$ 矩阵，给出如下

$$\mathbf{U} = (\mathbf{u_1}, \mathbf{u_2}, \ldots, \mathbf{u_n}), \quad \mathbf{\Lambda} = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 & 0 & & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \lambda_n & 0 & \cdots & 0\\ \end{pmatrix}, \quad \mathbf{V}^\top = \begin{pmatrix} \mathbf{v_1}^\top \\ \mathbf{v_2}^\top \\ \vdots \\ \mathbf{v_d}^\top \\ \end{pmatrix}.$$

此外，定义

$$\mathbf{X^-} = \mathbf{V} (\mathbf{\Lambda}^-)^{\top} \mathbf{U}^\top, \quad \text{where} \quad \mathbf{\Lambda}^- = \begin{pmatrix} \frac{1}{\lambda_1} & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \frac{1}{\lambda_2} & \cdots & 0 & 0 & & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \frac{1}{\lambda_n} & 0 & \cdots & 0\\ \end{pmatrix}.$$

回答以下问题。描述答案的同时也要给出推导过程。

(1) 使用仅 $\mathbf{X}$ 表示 $\mathbf{XX^-X}$。

(2) 使用仅 $\mathbf{U}$ 和 $\lambda_i$ ($i = 1, \ldots, n$) 表示 $\mathbf{XX^\top}$。

(3) 假设我们希望用 $\mathbf{w} = \mathbf{A} \mathbf{y}$ 和 $\boldsymbol{\mu} = \mathbf{B} \mathbf{y}$ 表示 $L(\mathbf{w}, \boldsymbol{\mu})$ 的驻点。使用仅 $\mathbf{X}$ 表示矩阵 $\mathbf{A} \in \mathbb{R}^{d \times n}$ 和 $\mathbf{B} \in \mathbb{R}^{n \times n}$。

(4) 使用仅 $\mathbf{X^-}$ 表示问题 (3) 中的 $\mathbf{A}$。

题目描述

设自然数 $n<d$， $\boldsymbol{w}\in\mathbb R^d$、 $X\in\mathbb R^{n\times d}$、 $\boldsymbol{y}\in\mathbb R^n$，并假定 $XX^{\mathsf T}$ 可逆。用拉格朗日乘子法求解

$$\min_{\boldsymbol{w}}\frac12\|\boldsymbol{w}\|^2 \quad\text{满足}\quad \boldsymbol{y}=X\boldsymbol{w},$$

其拉格朗日函数为

$$L(\boldsymbol{w},\boldsymbol{\mu}) =\frac12\|\boldsymbol{w}\|^2 +\boldsymbol{\mu}^{\mathsf T} (\boldsymbol{y}-X\boldsymbol{w}), \qquad \boldsymbol{\mu}\in\mathbb R^n.$$

设 $X$ 的奇异值分解为 $X=U\Lambda V^{\mathsf T}$，其中 $U,V$ 的列分别构成 $\mathbb R^n,\mathbb R^d$ 的标准正交基， $\Lambda\in\mathbb R^{n\times d}$ 的前 $n$ 个对角元为正数 $\lambda_1,\ldots,\lambda_n$，其余为零。将这些非零奇异值取倒数形成 $\Lambda^-$，并定义

$$X^-=V(\Lambda^-)^{\mathsf T}U^{\mathsf T}.$$

各问除答案外还须给出推导。

（1）仅用 $X$ 表示 $XX^-X$。

（2）仅用 $U$ 和 $\lambda_i\ (i=1,\ldots,n)$ 表示 $XX^{\mathsf T}$。

（3）将 $L$ 的驻点写成 $\boldsymbol{w}=A\boldsymbol{y}$、 $\boldsymbol{\mu}=B\boldsymbol{y}$，仅用 $X$ 表示 $A\in\mathbb R^{d\times n}$ 与 $B\in\mathbb R^{n\times n}$。

（4）仅用 $X^-$ 表示第（3）问中的 $A$。

Kai

(1)

Given:

$$\mathbf{X} = \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top,$$

$$\mathbf{X^-} = \mathbf{V} (\mathbf{\Lambda}^-)^\top \mathbf{U}^\top,$$

we can write:

$$\mathbf{X^-} = \mathbf{V} ((\mathbf{\Lambda}^-)^\top) \mathbf{U}^\top,$$

where

$$\mathbf{\Lambda}^- = \begin{pmatrix} \frac{1}{\lambda_1} & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \frac{1}{\lambda_2} & \cdots & 0 & 0 & & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & \frac{1}{\lambda_n} & 0 & \cdots & 0\\ \end{pmatrix}.$$

To find $\mathbf{XX^-X}$:

$$\mathbf{XX^-X} = (\mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top)(\mathbf{V} (\mathbf{\Lambda}^-)^\top \mathbf{U}^\top)(\mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top).$$

Notice:

$$\mathbf{V}^\top \mathbf{V} = \mathbf{I}_d, \quad \mathbf{U}^\top \mathbf{U} = \mathbf{I}_n,$$

therefore:

$$\begin{aligned} \mathbf{XX^-X} &= \mathbf{U} \mathbf{\Lambda} (\mathbf{V}^\top \mathbf{V}) (\mathbf{\Lambda}^-)^\top \mathbf{U}^\top \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top \\ &= \mathbf{U} \mathbf{\Lambda} (\mathbf{\Lambda}^-)^\top \mathbf{\Lambda} \mathbf{V}^\top \\ &= \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top = \mathbf{X}. \end{aligned}$$

Thus,

$$\boxed{\mathbf{XX^-X} = \mathbf{X}}.$$

(2)

Given:

$$\mathbf{X} = \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top,$$

we have:

$$\mathbf{XX^\top} = (\mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top)(\mathbf{V} \mathbf{\Lambda}^\top \mathbf{U}^\top) = \mathbf{U} \mathbf{\Lambda} \mathbf{\Lambda}^\top \mathbf{U}^\top.$$

Since $\mathbf{\Lambda}$ is an $n \times d$ matrix with singular values $\lambda_1, \lambda_2, \ldots, \lambda_n$ on the diagonal, $\mathbf{\Lambda} \mathbf{\Lambda}^\top$ is an $n \times n$ diagonal matrix:

$$\mathbf{\Lambda} \mathbf{\Lambda}^\top = \mathrm{diag}(\lambda_1^2, \lambda_2^2, \ldots, \lambda_n^2).$$

Therefore,

$$\mathbf{XX^\top} = \mathbf{U} \begin{pmatrix} \lambda_1^2 & 0 & \cdots & 0 \\ 0 & \lambda_2^2 & \cdots & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & \cdots & \lambda_n^2 \\ \end{pmatrix} \mathbf{U}^\top.$$

Thus,

$$\boxed{\mathbf{XX^\top} = \mathbf{U} \mathrm{diag}(\lambda_1^2, \lambda_2^2, \ldots, \lambda_n^2) \mathbf{U}^\top}.$$

(3)

To solve the optimization problem using Lagrange multipliers:

$$L(\mathbf{w}, \boldsymbol{\mu}) = \frac{1}{2} \|\mathbf{w}\|^2 + \boldsymbol{\mu}^\top (\mathbf{y} - \mathbf{Xw}),$$

we need to find $\mathbf{w}$ and $\boldsymbol{\mu}$ such that:

$$\frac{\partial L}{\partial \mathbf{w}} = 0 \quad \text{and} \quad \frac{\partial L}{\partial \boldsymbol{\mu}} = 0.$$

First, compute $\frac{\partial L}{\partial \mathbf{w}}$:

$$\frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \mathbf{X}^\top \boldsymbol{\mu} = 0 \implies \mathbf{w} = \mathbf{X}^\top \boldsymbol{\mu}.$$

Next, compute $\frac{\partial L}{\partial \boldsymbol{\mu}}$:

$$\frac{\partial L}{\partial \boldsymbol{\mu}} = \mathbf{y} - \mathbf{Xw} = 0 \implies \mathbf{y} = \mathbf{Xw}.$$

Substituting $\mathbf{w} = \mathbf{X}^\top \boldsymbol{\mu}$ into $\mathbf{y} = \mathbf{Xw}$:

$$\mathbf{y} = \mathbf{X} (\mathbf{X}^\top \boldsymbol{\mu}) \implies \mathbf{y} = (\mathbf{X} \mathbf{X}^\top) \boldsymbol{\mu}.$$

Since $\mathbf{X} \mathbf{X}^\top$ is invertible,

$$\boldsymbol{\mu} = (\mathbf{X} \mathbf{X}^\top)^{-1} \mathbf{y}.$$

Then,

$$\mathbf{w} = \mathbf{X}^\top \boldsymbol{\mu} = \mathbf{X}^\top (\mathbf{X} \mathbf{X}^\top)^{-1} \mathbf{y}.$$

Therefore,

$$\mathbf{A} = \mathbf{X}^\top (\mathbf{X} \mathbf{X}^\top)^{-1}, \quad \mathbf{B} = (\mathbf{X} \mathbf{X}^\top)^{-1}.$$

Thus,

$$\boxed{\mathbf{w} = \mathbf{X}^\top (\mathbf{X} \mathbf{X}^\top)^{-1} \mathbf{y}, \quad \boldsymbol{\mu} = (\mathbf{X} \mathbf{X}^\top)^{-1} \mathbf{y}}.$$

(4)

From question 3, we have:

$$\mathbf{A} = \mathbf{X}^\top (\mathbf{X} \mathbf{X}^\top)^{-1}.$$

Using $\mathbf{X^-}$:

$$\mathbf{X^-} = \mathbf{V} (\mathbf{\Lambda}^-)^\top \mathbf{U}^\top,$$

we know:

$$\mathbf{X} \mathbf{X}^- = \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top \mathbf{V} (\mathbf{\Lambda}^-)^\top \mathbf{U}^\top = \mathbf{U} \mathbf{\Lambda} (\mathbf{\Lambda}^-)^\top\mathbf{U}^\top = \mathbf{U} \mathbf{I}_n \mathbf{U}^\top = \mathbf{I}_n.$$

This identity alone does not determine a right inverse uniquely. It remains to show that

$$\mathbf{X}^\top (\mathbf{X} \mathbf{X}^\top)^{-1} = \mathbf{X^-}.$$

To see this, use the given SVD of $\mathbf{X}$ and $\mathbf{X}\mathbf{X}^\top$ from Question 2:

$$\mathbf{X} = \mathbf{U} \mathbf{\Lambda} \mathbf{V}^\top,$$

$$\mathbf{X}\mathbf{X}^\top = \mathbf{U} \mathrm{diag}(\lambda_1^2, \lambda_2^2, \ldots, \lambda_n^2) \mathbf{U}^\top.$$

Then,

$$\mathbf A = \mathbf{X}^\top (\mathbf{X} \mathbf{X}^\top)^{-1}$$

$$= \mathbf{V} \mathbf{\Lambda}^\top \mathbf{U}^\top (\mathbf{U} \mathrm{diag}(\lambda_1^2, \lambda_2^2, \ldots, \lambda_n^2) \mathbf{U}^\top)^{-1}$$

$$= \mathbf{V} \mathbf{\Lambda}^\top \mathbf{U}^\top \mathbf{U} \mathrm{diag}(\lambda_1^{-2}, \lambda_2^{-2}, \ldots, \lambda_n^{-2}) \mathbf{U}^\top$$

$$= \mathbf{V} \mathbf{\Lambda}^\top \mathrm{diag}(\lambda_1^{-2}, \lambda_2^{-2}, \ldots, \lambda_n^{-2}) \mathbf{U}^\top$$

$$= \mathbf{V} \begin{pmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & \cdots & \lambda_n \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix} \begin{pmatrix} \lambda_1^{-2} & 0 & \cdots & 0 \\ 0 & \lambda_2^{-2} & \cdots & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & \cdots & \lambda_n^{-2} \\ \end{pmatrix} \mathbf{U}^\top$$

$$= \mathbf{V} \begin{pmatrix} \lambda_1^{-1} & 0 & \cdots & 0 \\ 0 & \lambda_2^{-1} & \cdots & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & \cdots & \lambda_n^{-1} \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix} \mathbf{U}^\top = \mathbf{V}(\mathbf{\Lambda}^-)^\top\mathbf{U}^\top = \mathbf{X^-}.$$

Thus,

$$\boxed{\mathbf{A} = \mathbf{X^-}}.$$

Knowledge

最优化 奇异值分解 线性代数 拉格朗日乘数法

难点思路

这道题目涉及多个知识点的综合运用，特别是拉格朗日乘数法和奇异值分解的结合使用。重点在于理解矩阵运算和变换的基本性质。

解题技巧和信息

• 拉格朗日乘数法：在求解带有约束的最优化问题时非常有用。
• 奇异值分解：帮助简化矩阵运算，特别是对于逆矩阵和伪逆矩阵的计算。

重点词汇

• inner product 内积
• transpose 转置
• Lagrange multipliers 拉格朗日乘数
• singular value decomposition 奇异值分解
• orthonormal basis 正交归一基

参考资料

1. 《线性代数及其应用》David C. Lay，第四章：奇异值分解
2. 《最优化理论》Edwin K. P. Chong and Stanislaw H. Zak，第三章：拉格朗日乘数法