9

mサイズxnとランクの行列を生成したいと思います。r要素は指定された有限集合（{0,1}または）から取得されます{1,2,3,4,5}。私はそれらをその単語の非常に緩い意味で「ランダム」にしたい、つまり、指定されたランクの要素のセット全体のすべての行列の分布に漠然と似た分布で、アルゴリズムからさまざまな可能な出力を取得したい。

実際、私はそれがランクを持っていることを実際には気にしませんr、ただそれがランクの行列（フロベニウスノルムによって測定される）に近いということだけです。r

手元のセットが実数である場合、私は次のことを行っています。これは私のニーズに完全に適しています。たとえば、Normal（0、2）から独立してサンプリングされた要素を使用して、サイズUxおよびxの行列をm生成rします。次に、ランクのx行列です（まあ、、、しかし私はそれが高い確率であると思います）。VnrU V'mnr<= rr

ただし、それを実行してから2進数/ 1-5に丸めると、ランクが上がります。

rSVDを実行し、最初の特異値を取得することにより、行列の低ランク近似を取得することもできます。ただし、これらの値は目的のセットには含まれず、丸めるとランクが再び上がります。

この質問は関連していますが、受け入れられた回答は「ランダム」ではなく、他の回答はSVDを示唆しています。これは、前述のようにここでは機能しません。

私が考えた1つの可能性はr、セットから線形独立の行または列ベクトルを作成し、それらの線形結合によって行列の残りの部分を取得することです。ただし、「ランダムな」線形独立ベクトルを取得する方法、またはその後に準ランダムな方法でそれらを組み合わせる方法については、はっきりしていません。

（それは非常に関連性があるというわけではありませんが、私はこれをnumpyでやっています。）

更新：コメントでEMSによって提案されたアプローチを、この単純な実装で試しました。

real = np.dot(np.random.normal(0, 1, (10, 3)), np.random.normal(0, 1, (3, 10)))
bin = (real > .5).astype(int)
rank = np.linalg.matrix_rank(bin)
niter = 0

while rank > des_rank:
    cand_changes = np.zeros((21, 5))
    for n in range(20):
        i, j = random.randrange(5), random.randrange(5)
        v = 1 - bin[i,j]
        x = bin.copy()
        x[i, j] = v
        x_rank = np.linalg.matrix_rank(x)
        cand_changes[n,:] = (i, j, v, x_rank, max((rank + 1e-4) - x_rank, 0))
    cand_changes[-1,:] = (0, 0, bin[0,0], rank, 1e-4)

    cdf = np.cumsum(cand_changes[:,-1])
    cdf /= cdf[-1]
    i, j, v, rank, score = cand_changes[np.searchsorted(cdf, random.random()), :]
    bin[i, j] = v
    niter += 1
    if niter % 1000 == 0:
        print(niter, rank)

小さなマトリックスではすぐに機能しますが、たとえば10x10ではバラバラになります。少なくとも数十万回の反復では、ランク6または7でスタックしているようです。

これは、より良い（つまり、平坦度の低い）目的関数でうまく機能するようですが、それがどうなるかはわかりません。

また、マトリックスを構築するための簡単な棄却法を試しました。

def fill_matrix(m, n, r, vals):
    assert m >= r and n >= r
    trans = False
    if m > n: # more columns than rows I think is better
        m, n = n, m
        trans = True

    get_vec = lambda: np.array([random.choice(vals) for i in range(n)])

    vecs = []
    n_rejects = 0

    # fill in r linearly independent rows
    while len(vecs) < r:
        v = get_vec()
        if np.linalg.matrix_rank(np.vstack(vecs + [v])) > len(vecs):
            vecs.append(v)
        else:
            n_rejects += 1
    print("have {} independent ({} rejects)".format(r, n_rejects))

    # fill in the rest of the dependent rows
    while len(vecs) < m:
        v = get_vec()
        if np.linalg.matrix_rank(np.vstack(vecs + [v])) > len(vecs):
            n_rejects += 1
            if n_rejects % 1000 == 0:
                print(n_rejects)
        else:
            vecs.append(v)
    print("done ({} total rejects)".format(n_rejects))

    m = np.vstack(vecs)
    return m.T if trans else m

これは、たとえば、任意のランクの10x10バイナリ行列では問題なく機能しますが、0〜4の行列、またはランクの低いはるかに大きなバイナリでは機能しません。（たとえば、ランク15の20x20バイナリマトリックスを取得すると、42,000の拒否が発生しました。ランク10の20x20では、120万が必要でした。）

これは明らかに、最初の行にまたがるスペースが、たとえばこれらの場合にrサンプリングしているスペースの一部として小さすぎるためです。{0,1}^10

最初の行のスパンとr有効な値のセットの共通部分が必要です。したがって、スパンからサンプリングして有効な値を探すこともできますが、スパンには実数値の係数が含まれているため、有効なベクトルを見つけることはできません（たとえば、最初のコンポーネントが有効なセットに含まれるように正規化した場合でも）。

多分これは整数計画問題か何かとして定式化することができますか？

4

3 に答える 3

2

上でコメントした私の友人、ダニエル・ジョンソンはアイデアを思いつきましたが、彼はそれを投稿しなかったようです. あまり肉付けされていませんが、適応できる可能性があります。

がAmB行 r 列かつ が r 行 n 列で、両方がランク r の場合、ランク r になりABます。ここで、指定されたセットにのみ値を持つAなどBを選択する必要があります。AB最も単純なケースはS = {0,1,2,...,j}.

1つの選択肢はA、正しいランクを保証する適切な行/列の合計でバイナリを作成Bし、列の合計が を超えないjようにして（積の各項が入るようにするS）、行の合計を選択してランクを発生させるr（または少なくとも奨励する）ことです。拒否として使用できます）。

A2 つの独立したサンプリング スキームを考え出すことができB、マトリックス全体を一度に攻撃しようとするよりも複雑ではなく、迅速であると思います。残念ながら、マトリックス サンプリング コードはすべて別のコンピューターにあります。{0,1}(つまり)よりも大きなセットのエントリを許可するように簡単に一般化できることはわかってSいますが、計算が でどのようにスケーリングされたかは思い出せませんm*n。

于 2012-04-14T00:29:17.307 に答える