Subconjunto máximo con rango$k$

Question

Estoy tratando de resolver el siguiente problema para un algoritmo estoy tratando de desarrollar y no pude encontrar nada útil en el erudito de google. Aquí está la pregunta:

Supongamos que tengo un conjunto de $N$ vectores $V=\{x_1,...,x_N\}$ y un entero positivo $k$. Me gustaría encontrar el mayor subconjunto de V (como muchos de los vectores como sea posible) que tiene dimensión $k$ (el rango de la matriz de los vectores se $k$).

Cualquier idea sobre cómo resolver esta redundancia problema? Yo estaba pensando en dinamizada QR o Interpolative de Descomposición, pero tengo un callejón sin salida.

Si esto ayuda, no me importa que en lugar de rango menor que $k$ me va a obtener una solución que da nuclear de norma menor que algún número positivo (es decir, la suma de los valores singulares).

Gracias, Gil

Answer 1

Este es un Pensamiento: en Primer lugar, vamos a poner todos sus vectores en un $M \times N$ matriz $A$ cuyas columnas son los dados los vectores (suponiendo, que se encuentran en $N$ dimensiones).

Hay varios aspectos a cualquier algoritmo que venir para arriba con. En términos generales, el algoritmo se puede dividir en dos partes

• $k$-rango de base: en Primer lugar, usted tiene que seleccionar un $k$-rango de la base. Hay $nC_k$ (combinatoria) las posibilidades de este. Esto puede ser prohibitivamente caro en computación.
• La ampliación del Conjunto: En general, para cada uno de los mencionados base posible, es necesario seleccionar algunos de los vectores de los demás, y ver la cardinalidad máxima posible. Es fácil ver que no debería ser $2^{n-k}$ de posibilidades de que para cada base elegida.

Si usted no puede hacerlo a través de la fuerza bruta (que es probablemente el caso), usted tendrá que recurrir a algún tipo de aproximación heurística. No tengo una estricta formal de argumentos para demostrar lo bueno que es (o para verificar que la materia).

• $k$-rango de base: Tomar la mejor $k$-rango de aproximación a la matriz $A$, se $A_K$. Ahora la forma de la matriz de proyección $P_K=A_K A_K^{\dagger}$ ($\dagger$ denota la pseudo-inversa). Ahora, encontrar $A_P=P_KA$. Calcular la norma de cada columna de $A_P$ y elegir los índices de la primera $k-$con los vectores de la norma suprema. Correspondiente a los mismos índices de este columnas, elija los correspondientes en el $A$. Este va a ser $\textit{most probably}$ un conjunto con $k$-rango. Ahora, forman la base de la matriz de $B_K$ con este vectores como columnas.

• La ampliación del conjunto: la Forma de la proyección ortogonal de la matriz $P_B=I-B_KB_K^{\dagger}$. Multiplicar todos los restantes $n-k$ vectores en $A$$P_B$, elija todos los vectores que son ceros cuando se multiplica por $P_B$ (que son cero, ya que no se encuentran en el intervalo de $B_K$, por lo que la adición de ellos a nuestro conjunto aumentará el rango).