设 A 和 B 是中的稀疏矩阵，密度（大致）相同。我想有效地计算一个矩阵在某种意义上是“最接近”同时仍然具有密度。“最接近”可能意味着“最小化 ”，但我对其他解释持开放态度。$\mathbb{R}^{m\times m}$$p$$C$$AB$$p$$||C - AB||_F$

如果是 A 中非零条目的数量（= B 中非零条目的数量），则主要计算要求是操作应该只需要内存。$\textrm{nnz}$$O(\textrm{nnz})$

问题1：这似乎是一个已经有很多研究的问题，但我没有找到很多。谷歌搜索时我可以使用任何参考/关键字吗？

我天真的想法：

1. 做一个稀疏的 matmul 而不实际将结果条目写入内存。相反，将它们输入在线订单选择算法以选择输出流中的 'th最大范数元素。$\textrm{nnz}$
2. 重新执行稀疏 matmul，但仅记录范数大于或等于步骤 1 中找到的阈值的条目。

这似乎直接最小化了 Frobenius 范数，但也有点低效：对于糟糕的稀疏模式，渐近运行时间仍然可以是，实际上，我们实际上是在进行两次乘法运算。$O(m^2)$

此外，还不清楚如何处理非零条目都相同的矩阵。也许只取第一个条目？但这使分析变得更加困难。$nnz$

问题2：对此有什么明显的改进吗？

问题 3：在所有非零条目都是不同的假设下，该算法的动态行为是什么？例如，让是这个保持密度的乘法，而是稀疏矩阵。我们能说一下吗？可能不适用于病理情况，但是如果是 iid 随机稀疏矩阵呢？$\odot$$M_i$$||(M_1 M_2 \ldots M_n) - (M_1 \odot M_2 \odot \ldots \odot M_n)||_F$$M_i$