在 numpy/scipy 中有效地计算两个（密集）向量的外部总和的稀疏子集

Question

假设我在 R^n 中有两个密集向量 a 和 b。我正在尝试计算定义为

的以下矩阵 S

S[i,j] = a[i]+b[j] for (i,j) in P,

S[i,j] = 0 否则，

其中 P 是 [0, ..., n]^2 中的稀疏子集。现在，我当然可以计算完整的外积，然后使用稀疏子集 P 来形成 S，但是我想知道是否有一种方法可以仅在需要时计算 S 的条目，即如果有在实际计算条目之前输入集合 P 的方法，以避免计算 n^2 总和。我尝试寻找解决此问题的方法，但没有找到任何东西。

提前致谢！

Answer 1

如果 P 是稀疏的，这很容易。

>>> import numpy as np
>>> import scipy.sparse as sps
>>> v1 = np.random.rand(10)
>>> v2 = np.random.rand(10)
>>> P = sps.csr_matrix(np.random.rand(10,10) < 0.1)

>>> P
<10x10 sparse matrix of type '<class 'numpy.bool_'>'
    with 20 stored elements in Compressed Sparse Row format>

现在只需获取非零索引并用它们索引你的向量：

>>> v1_idx, v2_idx = P.nonzero()
>>> OP = sps.csr_matrix((v1[v1_idx] + v2[v2_idx], (v1_idx, v2_idx)), shape=P.shape)

这将为您提供一个稀疏矩阵，其中仅填充了您需要的向量值

>>> OP
<10x10 sparse matrix of type '<class 'numpy.float64'>'
    with 20 stored elements in Compressed Sparse Row format>

在 numpy/scipy 中有效地计算两个（密集）向量的外部总和的稀疏子集

Computing a sparse subset of the outer sum of two (dense) vectors efficiently in numpy/scipy

python

numpy

scipy

sparse-matrix