Escasa base para el subespacio lineal

Question

Supongamos que tengo un subespacio lineal de algunos de espacio vectorial, por ejemplo, se describe como la columna espacio de algunos grandes de la matriz. Cómo iba yo a través de algoritmos encontrar una base del mismo subespacio donde la base de la matriz es dispersa, es decir, la mayoría de las entradas en la mayoría de los vectores de la base son iguales a cero? Entiendo que esto dependerá de la estructura de la matriz, por lo que es posible que prefiera para interpretar esto como "tantas entradas como sea posible son cero" en lugar de "la mayoría de las entradas son cero". Estoy interesada en soluciones prácticas, incluso si los resultados no son óptimos.

Answer 1

Supongamos que el subespacio $V$ es la columna espacio de la $m \times n$ matriz $M$ donde $M$ rango $n < m$. Elija cualquier subconjunto $S$ $\{1,\ldots, m\}$ de cardinalidad $n-1$, y considerar la $(n-1) \times n$ submatriz $M_S$ $M$ consta de las filas de las enumeradas en la $S$. Si $y$ es un vector distinto de cero en el espacio nulo de a$M_S$, $M y$ es un valor distinto de cero miembro de $V$ con ceros en las posiciones dadas por $S$. Hacer esto para $m$ elegido al azar subconjuntos $S$ y es probable que obtener suficiente tales vectores para abarcar $V$.

Por ejemplo, he probado el random $7 \times 4$ matriz $$ M = \left[ \begin {array}{cccc} -6&2&3&9\\ 0&5&-1&2 \\ 1&-2&-1&7\\ 8&1&3&-2 \\ 7&-4&7&-8\\ -1&-1&-6&9 \\ -6&-4&-6&-6\end {array} \right] $$

El uso de subconjuntos $[2, 3, 7], [4, 5, 7], [3, 5, 6], [3, 5, 7]$ tengo los vectores que consta de las columnas de $$\left[ \begin {array}{cccc} {\frac {780}{19}}&{\frac {3}{26}}&-{ \frac {289}{28}}&{\frac {681}{13}}\\ 0&-{\frac {80}{ 13}}&{\frac {471}{14}}&-{\frac {311}{26}}\\ 0&{ \frac {151}{13}}&0&0\\ -{\frac {468}{19}}&0&{\frac { 615}{14}}&-{\frac {755}{26}}\\ -{\frac {311}{19}}&0&0 &0\\ -4&{\frac {170}{13}}&0&-{\frac {415}{26}} \\ 0&0&-{\frac {415}{7}}&0\end {array} \right] $$

Dado que la matriz tiene rango $4$, estas columnas span $V$.

Answer 2

Sospecho que este es un problema difícil de resolver en una sola toma, pero aquí es una idea. Tengan paciencia conmigo que estoy pensando en voz alta. Supongamos que ya ha identificado a $a_1, \ldots, a_p \in V$ que son linealmente independientes. Construir $$ A := \begin{bmatrix} a_1 \cdots a_p \end{bmatrix}. $$ Supongamos, además, que $V$ puede ser descrito por el sistema lineal $Bx=d$. Una forma de encontrar un vector disperso en $V$ que es ortogonal a $a_1, \ldots, a_p$ es resolver el $\ell_1$ problema $$ \min_x \ \|x\|_1 \quad \text{objeto} \ Bx=d, \ A^T x = 0. $$ Esto puede ser transformado a un problema de programación lineal de la siguiente manera: \begin{align*} \min_{x,v} \quad & \sum_i v_i \\ \text{subject to} \quad & Bx = d, \\ & A^T x = 0, \\ & -v \leq x \leq v. \end{align*} Esto no está garantizado para encontrar el sparsest solución, pero en general es relativamente éxito en ese sentido. La idea es que el $\ell_1$ norma es el más cercano convexa de la norma para el llamado a $\ell_0$ norma, que en realidad no es una norma, sino simplemente cuenta el número de nonzeros de un vector.