Eu gostaria de gerar matrizes de tamanhomxn e classificarr, com elementos provenientes de um conjunto finito especificado, e.{0,1} ou{1,2,3,4,5}. Eu quero que eles sejam "aleatórios" em algum sentido muito frouxo dessa palavra, ou seja, eu quero obter uma variedade de saídas possíveis do algoritmo com distribuição vagamente semelhante à distribuição de todas as matrizes sobre esse conjunto de elementos com a classificação especificada.

Na verdade, eu realmente não me importo que tenha classificaçãor, só que éperto para uma matriz de classificaçãor (medido pela norma Frobenius).

Quando o conjunto em questão é o real, venho fazendo o seguinte, que é perfeitamente adequado para as minhas necessidades: gerar matrizesU de tamanhomxr eV donxr, com elementos independentemente amostrados de, e. Normal (0, 2) EntãoU V' é ummxn matriz de classificaçãor (bem,<= r, mas eu acho que ér com alta probabilidade).

Se eu fizer isso e depois passar para binário / 1-5, a classificação aumenta.

Também é possível obter uma aproximação de classificação mais baixa para uma matriz fazendo um SVD e obtendo o primeiror valores singulares. Esses valores, no entanto, não estarão no conjunto desejado, e arredondá-los aumentará novamente a classificação.

Essa questão está relacionado, mas a resposta aceita não é "aleatória", e a outra resposta sugere SVD, o que não funciona aqui como observado.

Uma possibilidade que eu pensei é fazerr vetores de linha ou coluna linearmente independentes do conjunto e depois obter o restante da matriz por combinações lineares desses. Não estou muito claro, no entanto, em como obter vetores lineares aleatórios "aleatórios" ou como combiná-los de maneira quase aleatória depois disso.

(Não que seja super relevante, mas estou fazendo isso numpy.)

Atualizar: Eu tentei a abordagem sugerida pelo EMS nos comentários, com esta implementação simples:

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

Funciona rapidamente para pequenas matrizes, mas desmorona por ex. 10x10 - parece ficar preso no rank 6 ou 7, pelo menos por centenas de milhares de iterações.

Parece que isso pode funcionar melhor com uma função objetiva melhor (ou seja, menos plana), mas não sei o que isso seria.

Eu também tentei um método simples de rejeição para construir a matriz:

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

Isso funciona bem, por exemplo, Matrizes binárias 10x10 com qualquer classificação, mas não para matrizes 0-4 ou binários muito maiores com classificação inferior. (Por exemplo, obter uma matriz binária de 20x20 de nível 15 me deu 42.000 rejeições; com 20x20 de classificação 10, foram necessários 1,2 milhão.)

Isto é claramente porque o espaço ocupado pela primeirar linhas é uma parte muito pequena do espaço do qual estou amostrando, por exemplo{0,1}^10, nesses casos.

Queremos a intersecção do espaço do primeiror linhas com o conjunto de valores válidos. Assim, poderíamos tentar amostragem a partir do intervalo e procurar por valores válidos, mas como o intervalo envolve coeficientes reais que nunca nos encontrarão vetores válidos (mesmo se normalizarmos de modo que, por exemplo, o primeiro componente esteja no conjunto válido).

Talvez isso possa ser formulado como um problema de programação inteira, ou algo assim?