计算科学 - 对角矩阵的最小二乘 - 吾爱随笔录

计算科学线性代数线性求解器矩阵线性系统

2021-12-24 11:43:37

这是我更详细地询问的另一个问题的后续行动。

为了 $v\in\mathbb{R}^n$ , 表示 $D_v\in\mathbb{R}^n$ 作为具有元素的对角矩阵 $v$ . 给定一个“高”矩阵 $B\in\mathbb{R}^{n\times m}$ ，我想解决以下优化问题：

min_{v \in R^{n}} ‖ X - B^{⊤} D_{v} B ‖_{F r o}^{2}

$\min_{v\in\mathbb{R}^n} \|X-B^\top D_v B\|_{\mathrm{Fro}}^2$ 假设我计算得当，一阶最优性给出线性系统

(B B^{⊤} \circ B B^{⊤}) v = (B X \circ B) 1

$(BB^\top\circ BB^\top)v=(BX\circ B)\mathbb{1}$ ，其中

\circ

$\circ$ 表示逐元素（Hadamard）乘积和

1 \in R^{n}

$\mathbb{1}\in\mathbb{R}^n$ 是所有的向量。我已经检查过这个系统对于我的应用程序是可逆的。

问题是，矩阵 $BB^\top\circ BB^\top$ 相对于 $B$ 的大小非常大。我有能力采用 $B$ 的 SVD （和 $X$ 的 SVD ），但不能构建这个大而密集的矩阵。

我有什么办法可以直接解决这个系统而不使用迭代求解器？如果我必须迭代地进行，那么对于来自这个最小二乘问题的系统来说，最快的迭代是什么？

1个回答

通过将问题投影到 B 所跨越的空间中，可以获得封闭形式的解决方案。要看到这一点，请注意我们有

min_{v \in R^{n}} ‖ X - B D_{v} B^{T} ‖_{F},

$\min_{v\in\mathbb{R}^{n}}\|X-BD_{v}B^{T}\|_{F},$ 但是如果我们引入使得，则优化减少显然我们能做的最好的事情是设置，其中“diag”运算符隔离其输入矩阵的对角线。

\tilde{X}

$\tilde{X}$

X = B \tilde{X} B^{T}

$X=B\tilde{X}B^{T}$

\arg min_{v \in R^{n}} ‖ B \tilde{X} B^{T} - B D_{v} B^{T} ‖_{F} \equiv \arg min_{v \in R^{n}} ‖ \tilde{X} - D_{v} ‖_{F},

$\arg\min_{v\in\mathbb{R}^{n}}\|B\tilde{X}B^{T}-BD_{v}B^{T}\|_{F}\equiv\arg\min_{v\in\mathbb{R}^{n}}\|\tilde{X}-D_{v}\|_{F},$

v = d i a g (\tilde{X})

$v=\mathrm{diag}(\tilde{X})$

现在，要获得，假设的范围空间上执行投影即可，证明是通过替换获得的（检查这个）。如果是奇异的，则使用伪逆。结合起来，我们证明了以下结果。 $\tilde{X}$ $B$ $B$

\tilde{X} = (B^{T} B)^{- 1} B^{T} X B (B^{T} B)^{- 1} .

$\tilde{X}=(B^{T}B)^{-1}B^{T}XB(B^{T}B)^{-1}.$

X = B \tilde{X} B^{T}

$X=B\tilde{X}B^{T}$

B^{T} B

$B^TB$

定理 1.优化有以下闭式解

$v = d i a g [(B^{T} B)^{- 1} B^{T} X B (B^{T} B)^{- 1}] .$ $v=\mathrm{diag}[(B^{T}B)^{-1}B^{T}XB(B^{T}B)^{-1}].$

最后，值得注意的是，如果计算负载是一个问题，您不应该明确地形成矩阵。相反，您应该对进行cholesky 分解，执行一种大小的矩阵-矩阵乘积，然后隐式计算对角线。 $X$

其它你可能感兴趣的问题