La forma más rápida de comprobar si un vector aumenta el rango de matriz

Dada una matriz A de n por m, con la garantía de que n> m = rango (A), y dada una columna n por 1 v, qué es la manera más rápida de verificar si [A v] tiene un rango estrictamente más grande que A?La forma más rápida de comprobar si un vector aumenta el rango de matriz

Para mi aplicación, A es escaso, n es aproximadamente 2^12, y m está en cualquier lugar en 1: n-1. Comparar el rango (completo ([A v])) lleva aproximadamente un segundo en mi máquina, y tengo que hacerlo decenas de miles de veces, por lo que estaría encantado de descubrir una forma más rápida.

Fuente

2012-02-01 Ian Hincks

Dice que necesita hacer esto 10k veces. ¿Qué cambia de ejecución a ejecución? P.ej. ¿'A' es siempre el mismo y se compara con muchos vectores' v'? ¿O son 'A' y' v' diferentes para cada ejecución? –

@FlorianBrucker Empiezo con A teniendo relativamente pocas columnas, y luego tengo un bucle que se ejecuta ~ 20K veces, cada vez generando una nueva v de alguna manera específica, comprobando si es linealmente independiente del espacio de columna de A, y si es así, añádalo a A. –

La solución más rápida puede ser usar el espacio nulo como una restricción para crear nuevos vectores 'v'. – Jonas

Quizás puedas intentar resolver el sistema A*x=v, si tiene una solución que signifique que el rango no aumenta.

x=(B\A)'; 
norm(A*x-B) %% if this is small then the rank does not increase

Fuente

2012-02-01 15:16:10 Oli

Buena sugerencia, pero parece ser un poco más intensivo que el rango de llamadas ([lleno (A) v]) con mis casos de prueba: alrededor de 4 segundos en comparación con 1 segundo. –

No hay necesidad de hacer solucio- nes repetidas SI puede permitirse hacer UN cálculo del espacio nulo. Solo una llamada a null será suficiente. Dado un nuevo vector V, si el producto escalar con V y la base de espacio nulo no es cero, entonces V aumentará el rango de la matriz. Por ejemplo, supongamos que tenemos la matriz M, que por supuesto tiene un rango de 2.

M = [1 1;2 2;3 1;4 2]; 
nullM = null(M')';

Será un nuevo vector de columna [1; 1; 1; 1] aumentar el rango si anexó a M?

nullM*[1;1;1;1] 
ans = 
     -0.0321573705742971 
     -0.602164651199413

Sí, ya que tiene un no-cero proyección sobre al menos uno de los vectores de la base en nullM.

¿Qué hay de este vector:

nullM*[0;0;1;1] 
ans = 
     1.11022302462516e-16 
     2.22044604925031e-16

En este caso, ambos números son esencialmente cero, por lo que el vector en cuestión no habría aumentado el rango de M.

El punto es, sólo la multiplicación simple matriz-vector es necesaria una vez que se ha generado la base del espacio nulo. Si su matriz es demasiado grande (y la matriz casi de rango completo) que una llamada a nulo fallará aquí, entonces tendrá que hacer más trabajo. Sin embargo, n = 4096 no es excesivamente grande siempre que la matriz no tenga demasiadas columnas.

Una alternativa si null es demasiado es una llamada a svds, para encontrar esos vectores singulares que son esencialmente cero. Estos formarán la base de espacio nulo que necesitamos.

Fuente

2012-02-01 16:12:24

Gracias! Eso es lo que intenté, excepto que mi LinAlg-fu no es tan fuerte como el tuyo. – Jonas

Gracias, este es un muy buen consejo para soluciones repetidas. –

Yo usaría sprank para matrices dispersas. Compruébalo, podría ser más rápido que cualquier otro método.

Editar: Como se señala correctamente por @IanHincks, no es el rango. Dejo la respuesta aquí, por si acaso alguien más la necesitará en el futuro.

Fuente

2012-02-01 16:30:04

Definitivamente es mucho más rápido, pero no devuelve el rango, solo un límite en el rango (la documentación lo llama el rango estructural). –

La forma más rápida de comprobar si un vector aumenta el rango de matriz

Respuesta

Cuestiones relacionadas