计算科学 - 哪些是计算两个矩阵之间相似度的好算法和启发式方法？ - 吾爱随笔录

哪些是计算两个矩阵之间相似度的好算法和启发式方法？

计算科学算法矩阵近似

2021-12-19 11:33:07

假设我有一个这样的矩阵：

[\begin{matrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix}]

$\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix}$

和这个：

[\begin{matrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix}]

$\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}$

这两个矩阵之间的差异是 12 中的 2 个元素，即 16.67%。所以，我可以说它们有 83,33% 的相似性。有哪些好的算法或启发式方法（我不需要比 +- 5% 更高的精度）来获得这个数字（本例中的 83,33%）比遍历两个矩阵并使用嵌套循环结构比较每个元素的天真的算法？

1个回答

简短的回答是：“这取决于”。

但是从问题中不完全清楚的第一个问题是两个矩阵之间相似性的定义。从技术上讲，有一个术语Matrixsimilarity，但它与您所要求的内容之间肯定没有共同之处。

为了证明对相似性定义的询问是正确的，请考虑三个矩阵：

A_{1} = [\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array}], A_{2} = [\begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array}], A_{3} = [\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}]

$A_1=\left[\begin{array}{ccc} 1 &0 &0 \\ 1 &1 & 0 \\ 1 & 1 & 1 \end{array}\right], \quad A_2=\left[\begin{array}{ccc} 1 &1 &1 \\ 0 &1 & 1 \\ 0 & 0 & 1 \end{array}\right],\quad A_3=\left[\begin{array}{ccc} 1 &0 &0 \\ 0 &1 & 0 \\ 0 & 0 & 1 \end{array}\right]$ 这里，。但是，根据您提出的元素相似性定义，它们之间的差异将是巨大的：2/3。此外，单位矩阵的差异较小，仅为 1/3。

A_{1} = A_{2}^{T}

$A_1 = A_2^T$

A_{3} = I_{3}

$A_3=I_3$

可以显示展示两个矩阵之间更复杂的相似性/差异的其他示例。

尽管如此，让我们假设我们只对在两个矩阵中执行严格的元素到元素感兴趣。一个自然的度量标准是nicoguaro建议的：这里对应不同的矩阵范数（1-范数，2-范数，Frobenius范数，等）不幸的是，范数的计算至少需要浏览矩阵的所有元素。在不知道矩阵来自哪里的情况下，要加快计算速度并不容易。 $\left|\left| A_1-A_2 \right|\right|_{1,2,F,\ldots}$ $1,2,F,\ldots$ $A_1-A_2$

提供一些信息，有多种算法可以估计您的规范：

2007 年9 月 13 日至 15 日，英国伯明翰，第一次 IMA 数值线性代数和优化国际会议，无矩阵、无转置范数估计器- 需要矩阵向量乘积。
A. Heldring、E. Ubeda、JM Rius，“ACA 收敛准则中 Frobenius 范数的随机估计”，IEEE 天线传播。, 卷。63，没有。3，第 1155-1158 页，2015 年 3 月。 - 使用自适应交叉近似，如果您的矩阵一开始是低秩的，这将是有效的。

但我认为这一切都是矫枉过正。目前，没有理由解释为什么计算矩阵的范数的朴素算法是不够的。因为，即使矩阵的大小很大，您还是将它们存储在内存中；因此，您当然至少可以计算 Frobenius 范数。 $A_1-A_2$

其它你可能感兴趣的问题

上一篇什么是H12(ΓG)H12(Γg) 下一篇四阶龙格-库塔和谐波振荡器