Chciałbym wygenerować macierze wielkościmxn i rangar, z elementami pochodzącymi z określonego zbioru skończonego, np.{0,1} lub{1,2,3,4,5}. Chcę, żeby były „losowe” w pewnym bardzo luźnym znaczeniu tego słowa, tj. Chcę uzyskać wiele możliwych wyników algorytmu z dystrybucją nieco podobną do rozkładu wszystkich macierzy na ten zestaw elementów o określonej randze.

Właściwie nie obchodzi mnie, że ma rangęr, tylko że to jestblisko do matrycy rangir (mierzone według normy Frobeniusa).

Kiedy zestaw jest pod ręką, robiłem co następuje, co jest całkowicie odpowiednie dla moich potrzeb: generowanie macierzyU wielkościowymxr iV znxr, z elementami niezależnie próbkowanymi np. z Normalny (0, 2). NastępnieU V' jestmxn macierz rangir (dobrze,<= r, ale myślę, że takr z dużym prawdopodobieństwem).

Jeśli to zrobię, a następnie zaokrąglisz do binarnego / 1-5, ranga wzrasta.

Możliwe jest również uzyskanie przybliżenia macierzy niższej rangi poprzez wykonanie SVD i wykonanie pierwszegor wartości pojedyncze. Te wartości nie będą jednak leżeć w pożądanym zestawie, a ich zaokrąglenie ponownie zwiększy rangę.

To pytanie jest spokrewniony, ale zaakceptowana odpowiedź nie jest „przypadkowa”, a druga odpowiedź sugeruje SVD, co nie działa tutaj, jak zauważono.

Jedną z możliwości, o których myślałem, jest zrobienier liniowo niezależne wektory rzędów lub kolumn z zestawu, a następnie pobierają resztę macierzy za pomocą ich kombinacji liniowych. Nie jestem jednak do końca pewien, jak uzyskać „losowe” liniowo niezależne wektory lub jak połączyć je w sposób quasirandom.

(Nie, że jest to bardzo istotne, ale robię to w liczbach.)

Aktualizacja: Próbowałem podejścia zaproponowanego przez EMS w komentarzach, z tą prostą implementacją:

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

Działa szybko dla małych matryc, ale rozpada się np. Na 10x10 - wydaje się, że utknął na poziomie 6 lub 7, przynajmniej dla setek tysięcy iteracji.

Wydaje się, że to może działać lepiej z lepszą (tj. Mniej płaską) funkcją celu, ale nie wiem, co to będzie.

Wypróbowałem także prostą metodę odrzucania w celu zbudowania macierzy:

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

Działa to dobrze np. 10x10 macierzy binarnych o dowolnej randze, ale nie dla macierzy 0-4 lub znacznie większych binarnych o niższej randze. (Na przykład otrzymanie macierzy binarnej 20x20 o randze 15 zajęło mi 42 000 odrzuceń; z 20 x 20 rangą 10 zajęło 1,2 mln).

Wynika to wyraźnie z tego, że przestrzeń rozciąga się na pierwsząr wiersze są zbyt małą częścią przestrzeni, z której próbuję, np.{0,1}^10, w tych przypadkach.

Chcemy przecięcia rozpiętości pierwszegor wiersze z zestawem poprawnych wartości. Możemy więc próbować z zakresu i szukać prawidłowych wartości, ale ponieważ zakres obejmuje współczynniki o wartościach rzeczywistych, które nigdy nie znajdą nam prawidłowych wektorów (nawet jeśli znormalizujemy tak, że np. Pierwszy komponent znajduje się w poprawnym zestawie).

Może to może być sformułowane jako problem z programowaniem całkowitym, czy coś?