IS CS-2021W-04

题目来源：Problem 4 日期：2024-07-24 题目主题：CS-算法-最优化问题与线性代数

解题思路

这道题目涉及通过拉格朗日乘数法解决带有约束条件的优化问题，并利用奇异值分解（SVD）简化表达式。主要步骤包括：

1. 使用拉格朗日乘数法解约束优化问题。
2. 使用奇异值分解简化矩阵表达式。
3. 根据优化问题的 KKT 条件表达解的形式。

Solution

Question 1: Express $\mathbf{X}{\mathbf{X}}^{-}\mathbf{X}$ using only $\mathbf{X}$

Given:

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

we can write:

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

where

$${\mathbf{\Lambda }}^{-}=\left(\begin{array}{ccccc}\frac{1}{{\lambda }_1}& 0& \cdots & 0& 0\\ 0& \frac{1}{{\lambda }_2}& \cdots & 0& 0\\ 0& 0& \ddots & 0& 0\\ 0& 0& \cdots & \frac{1}{{\lambda }_n}& 0\end{array}\right).$$

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

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

Notice:

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

therefore:

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

Thus,

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

Question 2: Express $\mathbf{X}{\mathbf{X}}^{\top }$ using only $\mathbf{U}$ and ${\lambda }_i$ ($i=1,\dots ,n$)

Given:

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

we have:

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

Since $\mathbf{\Lambda }$ is an $n\times d$ matrix with singular values ${\lambda }_1,{\lambda }_2,\dots ,{\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,\dots ,{\lambda }_n^2).$$

Therefore,

$$\mathbf{X}{\mathbf{X}}^{\top }=\mathbf{U}\left(\begin{array}{cccc}{\lambda }_1^2& 0& \cdots & 0\\ 0& {\lambda }_2^2& \cdots & 0\\ 0& 0& \ddots & 0\\ 0& 0& \cdots & {\lambda }_n^2\end{array}\right){\mathbf{U}}^{\top }.$$

Thus,

$$\boxed{\mathbf{X}{\mathbf{X}}^{\top }=\mathbf{U}\mathrm{diag}({\lambda }_1^2,{\lambda }_2^2,\dots ,{\lambda }_n^2){\mathbf{U}}^{\top }}.$$

Question 3: Express the stationary points of $L(\mathbf{w},\mathbf{\mu })$ in the form of $\mathbf{w}=\mathbf{Ay}$ and $\mathbf{\mu }=\mathbf{By}$

To solve the optimization problem using Lagrange multipliers:

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

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

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

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

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

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

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

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

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

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

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

Then,

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

Therefore,

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

Thus,

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

Question 4: Express $\mathbf{A}$ using only ${\mathbf{X}}^{-}$

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 }}^{-}{\mathbf{U}}^{\top },$$

we know:

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

Therefore:

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

Another way to see this is to use the given SVD of $\mathbf{X}$ and $\mathbf{X}{\mathbf{X}}^{\top }$ from Question 2:

$$\mathbf{X}=\mathbf{U\Lambda }{\mathbf{V}}^{\top },$$ $$\mathbf{X}{\mathbf{X}}^{\top }=\mathbf{U}\mathrm{diag}({\lambda }_1^2,{\lambda }_2^2,\dots ,{\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,\dots ,{\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},\dots ,{\lambda }_n^{-2}){\mathbf{U}}^{\top }$$ $$=\mathbf{V}{\mathbf{\Lambda }}^{\top }\mathrm{diag}({\lambda }_1^{-2},{\lambda }_2^{-2},\dots ,{\lambda }_n^{-2}){\mathbf{U}}^{\top }$$ $$=\mathbf{V}\left(\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ 0& 0& \ddots & 0\\ 0& 0& \cdots & {\lambda }_n\\ 0& 0& \cdots & 0\\ ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0\end{array}\right)\left(\begin{array}{cccc}{\lambda }_1^{-2}& 0& \cdots & 0\\ 0& {\lambda }_2^{-2}& \cdots & 0\\ 0& 0& \ddots & 0\\ 0& 0& \cdots & {\lambda }_n^{-2}\end{array}\right){\mathbf{U}}^{\top }$$ $$=\mathbf{V}\left(\begin{array}{cccc}{\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\\ ⋮& ⋮& & ⋮\\ 0& 0& \cdots & 0\end{array}\right){\mathbf{U}}^{\top }={\mathbf{X}}^{-}.$$

Thus,

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

知识点

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

难点思路

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

解题技巧和信息

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

重点词汇

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

参考资料

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