疎行列から無作為な非ゼロ要素を描く

Question

私は非常に大きい疎な論理行列を持っています。ゼロ以外の要素を別のベクトルに格納せずに、ランダムな非ゼロ要素を描画したいと思います（たとえば、findコマンドを使用して）。これを行う簡単な方法はありますか？

現在、私は拒否サンプリングを実装しています。これは、ランダム要素を描画し、それが非ゼロであるかどうかをチェックしています。しかし、非ゼロ要素の比率が小さい場合は効率的ではありません。

Answer 1

findは、疎行列の非ゼロ要素を取得するための標準インタフェースです。 http://www.mathworks.se/help/techdoc/math/f6-9182.html#f6-13040

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

ここを見て発見iは、ベクトルでベクトルjの列のインデックス、およびベクトルsでゼロ以外の値そのものを非ゼロ値の行インデックスを返します。

sを取得する必要はありません。 i、jでランダムなインデックスを選択するだけです。

Answer 2

疎な論理行列は、ランダムな場所を選択したい場合、データをあまり実用的ではありません。拒否サンプリングとfindは、私にとって意味をなさない唯一の2つの方法です。

%# 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'); 

Answer 3

NNZ非ゼロ要素を持つn×mの行列が非ゼロの位置を保存するためにNNZ + N + 1の整数を必要とします。ここでは、それらを効率的に行うことができます方法です（あなたが4つのランダムな位置を取得したいと仮定した場合）エントリ。論理行列の場合、非ゼロのエントリの値を格納する必要はありません。これらはすべて真です。これに対応して、論理的な疎行列を、nnz + 2の整数の記憶域しか必要としないnとmと一緒に、非ゼロの項目の線形インデックスのリストに変換するのが最善です。これらの（およびind2sub）から、範囲外でランダムに選択した任意の非ゼロ項目に対応する添え字を簡単に再構成することができます。1.nnz

Answer 4

3つの列形式、 （i、j、value）を使用すると、リストから項目を選択することができます。これを取得するには、（sparse()にすなわち前駆体）スパース行列を作成するためにあなたの元のメソッドを使用するか、または、ラfindコマンドを使用するか[i,j,s] = find(S);

あなたはエントリーを必要としない、そしてそれはあなたが思われる場合しないでください、あなたはiとjを抽出することができます。

何らかの理由でマトリクスが大量にあり、RAMの制限が厳しい場合は、単にマトリクスを領域に分割し、特定のサブマトリクスを選択する確率を非ゼロの数に比例させることができますその部分行列内の要素（nnzを使用）を使用します。行列を個々の列に分割することができ、残りの計算は簡単です。注：マトリックスにsumを適用すると、列ごとの数を得ることができます（エントリが1だけであると仮定します）。

このようにして、拒否サンプリングをする必要はありません（Matlabはゼロ以外のエントリがどこにあるかを知っているので、私には無意味です）。