Genera una matriz "aleatoria" de cierto rango sobre un conjunto fijo de elementos

Me gustaría generar matrices de tamaño.mxn y rangor, con elementos que provienen de un conjunto finito específico, p. ej.{0,1} o{1,2,3,4,5}. Quiero que sean "aleatorios" en un sentido muy vago de esa palabra, es decir, quiero obtener una variedad de resultados posibles del algoritmo con una distribución vagamente similar a la distribución de todas las matrices sobre ese conjunto de elementos con el rango especificado.

De hecho, en realidad no me importa que tenga rango.r, solo que escerrar a una matriz de rangor (Medido por la norma de Frobenius).

Cuando el conjunto a la mano es el real, he estado haciendo lo siguiente, que es perfectamente adecuado para mis necesidades: generar matricesU de tamañomxr yV denxr, con elementos muestreados independientemente, p. ej. Normal (0, 2). EntoncesU V' es unmxn matriz de rangor (bien,<= r, pero creo que esr con alta probabilidad).

Si solo hago eso y luego redondeo a binario / 1-5, el rango aumenta.

También es posible obtener una aproximación de rango inferior a una matriz haciendo una SVD y tomando la primerar valores singulares. Sin embargo, esos valores no estarán en el conjunto deseado, y al redondearlos aumentará nuevamente el rango.

Esta pregunta está relacionado, pero la respuesta aceptada no es "aleatoria", y la otra respuesta sugiere SVD, que no funciona aquí como se indica.

Una posibilidad que he pensado es hacerr Los vectores de fila o columna linealmente independientes del conjunto y luego obtienen el resto de la matriz mediante combinaciones lineales de esos. Sin embargo, no estoy realmente claro, ni sobre cómo obtener vectores linealmente independientes lineales, o cómo combinarlos de forma casi aleatoria después de eso.

(No es que sea súper relevante, pero estoy haciendo esto en gran medida).

Actualizar: He intentado el enfoque sugerido por EMS en los comentarios, con esta sencilla implementación:

<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 rápidamente para matrices pequeñas, pero se desmorona, por ejemplo. 10x10: parece atascarse en el rango 6 o 7, al menos para cientos de miles de iteraciones.

Parece que esto podría funcionar mejor con una función objetivo mejor (es decir, menos plana), pero no sé qué sería eso.

También he intentado un método de rechazo simple para construir la 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>

Esto funciona bien, por ejemplo. Matrices binarias 10x10 con cualquier rango, pero no para matrices 0-4 o binarios mucho más grandes con rango más bajo. (Por ejemplo, obtener una matriz binaria de 20x20 de rango 15 me llevó 42,000 rechazos; con 20x20 de rango 10, tomó 1.2 millones).

Esto es claramente porque el espacio que abarca la primerar filas es una porción muy pequeña del espacio del que estoy muestreando, por ejemplo,{0,1}^10, en estos casos.

Queremos la intersección del tramo de la primera.r Filas con el conjunto de valores válidos. Así que podríamos intentar muestrear el intervalo y buscar valores válidos, pero como el intervalo involucra coeficientes de valores reales, nunca nos encontrará vectores válidos (incluso si lo normalizamos, por ejemplo, el primer componente está en el conjunto válido).

Tal vez esto puede ser formulado como un problema de programación de enteros, o algo así?

Respuestas a la pregunta(3)

Su respuesta a la pregunta