Ich möchte Matrizen der Größe erzeugenmxn und Rangrmit Elementen, die aus einer bestimmten endlichen Menge stammen, z.{0,1} oder{1,2,3,4,5}. Ich möchte, dass sie in einem sehr losen Sinne des Wortes "zufällig" sind, d. H. Ich möchte eine Vielzahl möglicher Ausgaben des Algorithmus mit einer Verteilung erhalten, die der Verteilung aller Matrizen über diesen Satz von Elementen mit dem angegebenen Rang vage ähnlich ist.

In der Tat ist es mir eigentlich egal, dass es Rang hatr, nur dass es so istschließen zu einer Matrix von Rangr (gemessen nach der Frobenius-Norm).

Wenn es sich bei dem vorliegenden Set um den Real handelt, habe ich Folgendes getan, was für meine Bedürfnisse völlig ausreichend ist: Matrizen generierenU der Größemxr undV vonnxrmit Elementen, die unabhängig von z.B. Normal (0, 2). DannU V' ist einmxn Rangmatrixr (Gut,<= r, aber ich denke es istr mit hoher Wahrscheinlichkeit).

Wenn ich das einfach mache und dann auf binär / 1-5 runde, steigt der Rang.

Es ist auch möglich, eine niedrigere Annäherung an eine Matrix zu erhalten, indem Sie eine SVD durchführen und die erste nehmenr singuläre Werte. Diese Werte liegen jedoch nicht in der gewünschten Menge, und durch Runden wird der Rang erneut erhöht.

Diese Frage ist verwandt, aber die akzeptierte Antwort ist nicht "zufällig", und die andere Antwort schlägt SVD vor, was hier nicht wie angegeben funktioniert.

Eine Möglichkeit, über die ich nachgedacht habe, ist zu machenr linear unabhängige Zeilen- oder Spaltenvektoren aus der Menge und erhalten dann den Rest der Matrix durch lineare Kombinationen dieser. Mir ist jedoch nicht wirklich klar, wie man "zufällige" linear unabhängige Vektoren erhält oder wie man sie danach quasirandomartig kombiniert.

(Nicht, dass es überaus relevant wäre, aber ich mache das in Zahlen.)

Aktualisieren: Ich habe den von EMS in den Kommentaren vorgeschlagenen Ansatz mit dieser einfachen Implementierung ausprobiert:

<code>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)
</code>

Es funktioniert schnell für kleine Matrizen, zerfällt jedoch z.B. 10x10 - es scheint auf Rang 6 oder 7 hängen zu bleiben, zumindest für Hunderttausende von Iterationen.

Es scheint, als würde dies mit einer besseren (dh weniger flachen) Zielfunktion besser funktionieren, aber ich weiß nicht, was das wäre.

Ich habe auch eine einfache Ablehnungsmethode zum Erstellen der Matrix ausprobiert:

<code>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
</code>

Dies funktioniert z. 10x10-Binärmatrizen mit beliebigem Rang, jedoch nicht für 0-4-Matrizen oder viel größere Binärdateien mit niedrigerem Rang. (Wenn ich zum Beispiel eine 20x20-Binärmatrix mit Rang 15 erhalten habe, habe ich 42.000 Absagen erhalten. Bei 20x20 mit Rang 10 waren es 1,2 Millionen.)

Dies liegt eindeutig daran, dass der Raum von der ersten überspannt wirdr Zeilen ist ein zu kleiner Teil des Raums, aus dem ich eine Stichprobe mache, z.{0,1}^10, in diesen Fällen.

Wir wollen den Schnittpunkt der Spanne der erstenr Zeilen mit dem Satz gültiger Werte. Wir könnten also versuchen, eine Stichprobe aus der Spanne zu ziehen und nach gültigen Werten zu suchen, aber da die Spanne reelle Koeffizienten enthält, werden wir keine gültigen Vektoren finden (auch wenn wir normalisieren, so dass beispielsweise die erste Komponente in der gültigen Menge enthalten ist).

Vielleicht kann dies als ganzzahliges Programmierproblem formuliert werden oder so?