计算科学 - 不对称矩阵的 SVD 的 Nystrom 近似 - 吾爱随笔录

计算科学线性代数特征值本征系统 svd

2021-12-08 14:20:26

假设我有一个对称矩阵 $K$ . 细分 $K$ 成碎片作为

K = (\begin{matrix} K_{11} & K_{12} \\ K_{21} & K_{22} \end{matrix}),

$K=\begin{pmatrix} K_{11} & K_{12} \\ K_{21} & K_{22}\end{pmatrix},$ 在哪里

K_{21} = K_{12}^{⊤}

$K_{21}=K_{12}^\top$ . 然后，Nystrom 近似

K

$K$ 替换

K_{22}

$K_{22}$ 与近似

K_{22} \approx K_{12}^{⊤} K_{11}^{- 1} K_{12} .

$K_{22}\approx K_{12}^\top K_{11}^{-1}K_{12}.$ 参见例如这篇论文的介绍。

现在，假设 $K$ 是不对称的。这是我的问题： 如果我们细分 $K$ 如上所述，是否存在“尼斯特罗姆式”近似 $K_{22}$ ?

我可以假设 $K_{11}$ 如果有帮助，则选择为正方形和可逆的。天真地认为我可以使用完全相同的公式 $K$ 不是正方形的，但是 Nystrom 近似的证明当然不再成立；我假设必须用 SVD 替换特征值参数。

1个回答

Nemtsov、Averbuchm 和 Schclar 的“使用 Nyström 方法的矩阵压缩”（2016 年）似乎相关：

Nyström 方法通常用于核矩阵的样本外扩展。我们描述了如何应用这种方法来找到一般矩阵的奇异值分解 (SVD) 和方阵的特征值分解 (EVD)。[...] 我们的算法适用于一般矩阵，而之前的方法专注于核矩阵。

特别是，他们表明一个矩阵

M = [\begin{matrix} A_{M} & B_{M} \\ F_{M} & C_{M} \end{matrix}]

$M= \begin{bmatrix} A_M & B_M \\ F_M & C_M \end{bmatrix}$

可以近似为：

\hat{M} = [\begin{matrix} A_{M} & B_{M} \\ F_{M} & F_{M} A_{M}^{+} B_{M} \end{matrix}]

$\hat M = \begin{bmatrix} A_M & B_M \\ F_M & F_M A_M^+ B_M \end{bmatrix}$

在哪里 $A_M^+$ 表示的伪逆 $A_M$ .

Kumar 和 Schneider 看似彻底的“关于矩阵低秩近似的文献调查”（2016 年）提供了 Nyström 方法误差估计、集成方法和自适应采样技术的方便参考书目。上述是它引用的唯一一篇将 Nyström 应用于一般矩阵的论文。

其它你可能感兴趣的问题