从稀疏矩阵中随机选择一个非零元素

Question

我有一个稀疏逻辑矩阵，它非常大。我希望能够从中随机提取非零元素，而不需要将所有非零元素存储在单独的向量中(例如通过使用查找命令)。有没有简单的方法可以实现这个功能？

目前，我正在实现拒绝抽样(rejection sampling)，即随机选择一个元素并检查它是否为非零。但当非零元素比例较小时，效率不高。

- user1210230

---

我认为如果您担心的是稀疏矩阵，那么“find（查找）”已经进行了相当优化。 - Andrey Rubshtein

我担心内存而不是运行时间。但是，即使从运行时间的角度来看，如果你只想采样几个项目，使用find操作也并不那么高效。 - user1210230

使用nonzeros应该比find稍微更节省一些内存，因为您不需要存储行和列的索引。 - Richie Cotton

Answer 1

如果你想要选择随机位置，那么一个稀疏逻辑矩阵并不是一个非常实用的数据表示方式。在我看来，拒绝抽样和find是唯一有意义的两种方法。以下是如何高效地执行它们（假设你想要获取4个随机位置）：

%# using find
idx = find(S);
%# draw 4 without replacement
fourRandomIdx = idx(randperm(length(idx),4));
%# draw 4 with replacement
fourRandomIdx = idx(randi(1,length(idx),4));
%# get row, column values
[row,col] = ind2sub(size(S),fourRandomIdx);



%# using rejection sampling
density = nnz(S)/prod(size(S));
%# estimate how many samples you need to get at least 4 hits
%# and multiply by 2 (or 3)
n = ceil( 1 / (1-(1-density)^4) ) * 2;
%# random indices w/ replacement
randIdx = randi(1,n,prod(size(S)));
%# identify the first four non-zero elements
[row,col] = find(S(randIdx),4,'first');

- Jonas

Answer 2

一个有 nnz 个非零元素的 n x m 矩阵需要 nnz + n + 1 个整数来存储其非零条目的位置。对于逻辑矩阵，没有必要存储非零条目的值：这些都是 true。因此，最好将逻辑稀疏矩阵转换为其非零条目的线性索引列表，以及 n 和 m，这只需要 nnz + 2 个整数的存储空间。从这些（和 ind2sub），您可以轻松地重建出与任意随机选择的非零条目相对应的下标，可以使用 randi 在范围 1..nnz 上进行选择。

- lsfinn

---

我的应用程序需要从零条目进行采样。因此，我维护稀疏矩阵以便能够检查随机条目的值。使用您的索引解决方案，采样零元素将是不可能的。 - user1210230

你能澄清一下你的目标吗？在你的原始帖子中，你表示想要绘制“随机非零元素”；然而，在你的评论中，似乎你也想从零条目中进行抽取。你能澄清一下吗？即，当你从矩阵中进行随机抽取时，你是从所有条目中进行抽取，还是只从某些条目中进行抽取（如果是这样，是哪些条目）？当你进行抽取时，你想要什么（例如，索引、索引和元素值等）？最后，矩阵是作为随机矩阵传递给你的，还是它是从其他东西构建的，以便你可以控制其表示？ - lsfinn

Answer 3

find 是获取稀疏矩阵中非零元素的标准接口。请在这里查看 http://www.mathworks.se/help/techdoc/math/f6-9182.html#f6-13040

[i,j,s] = find(S)

find函数返回向量i中非零值的行索引，向量j中的列索引以及向量s中的非零值本身。

不需要获取向量s。只需在i、j中随机选择一个索引即可。

- Johan Lundberg

---

也许我的观点没有表达清楚。我不想使用find函数，因为这样我就必须在一个单独的向量中存储索引（例如你的示例中的i和j），这将非常占用内存。与稀疏矩阵本身相比，它是一个稀疏逻辑矩阵。 - user1210230

Answer 4

通过以3列格式表示条目，即坐标列表（i，j，value），您可以简单地从列表中选择项目。要做到这一点，您可以使用创建稀疏矩阵的原始方法（即sparse()的前身），或使用find命令，例如[i，j，s] = find(S); 如果您不需要条目，似乎确实如此，您只需提取i和j。

如果由于某种原因，您的矩阵非常庞大，而且RAM限制非常严格，您可以将矩阵分成区域，并让选择给定子矩阵的概率与该子矩阵中非零元素的数量成比例。您甚至可以将矩阵分成单个列，其余计算是微不足道的。注意：通过对矩阵应用sum，您可以获得每列计数（假设您的条目只是1）。

通过这种方式，您甚至不必费心进行拒绝抽样（在这种情况下，似乎这样做毫无意义，因为Matlab知道所有非零条目的位置）。

- Iterator