modo più veloce per controllare se un vettore aumenta matrice rango

Dato un n-by-m matrice A, con essendo garantito che n> m = rango (A), e dato a n-by-1 colonna v, ciò è il modo più veloce per verificare se [A v] ha rango strettamente più grande di A?modo più veloce per controllare se un vettore aumenta matrice rango

Per la mia applicazione, A è sparsa, n è di circa 2^12, e m è ovunque in 1: n-1. Il confronto del rank (completo ([A v]) richiede circa un secondo sulla mia macchina, e ho bisogno di farlo decine di migliaia di volte, quindi sarei molto felice di scoprire un modo più veloce.

fonte

2012-02-01 Ian Hincks

Si dice che è necessario eseguire questa operazione 10 volte. Cosa cambia da correre a correre? Per esempio. è 'A' sempre uguale e controlli contro molti vettori' v'? O sono 'A' e' v' diversi per ogni corsa? –

@FlorianBrucker cominciare con la vista relativamente poche colonne, e quindi ho un ciclo che viene eseguito ~ 20K volte, ogni volta genera un nuovo v in qualche modo specifico, il controllo per vedere se linearmente indipendenti dello spazio colonna di A, e se lo è, aggiungendolo a A. –

La soluzione più veloce potrebbe essere quella di utilizzare lo spazio nullo come vincolo per la creazione di nuovi vettori 'v'. – Jonas

Forse si può provare a risolvere il sistema A*x=v, se ha una soluzione che significa che il rango non aumenta.

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

fonte

2012-02-01 15:16:10 Oli

Un buon suggerimento, ma sembra che richieda più tempo del call rank ([full (A) v]) con i miei casi di test - circa 4 secondi rispetto a 1 secondo. –

Non è necessario eseguire soluzioni ripetute SE è possibile effettuare un calcolo dello spazio nullo. Solo una chiamata a null sarà sufficiente. Dato un nuovo vettore V, se il prodotto punto con V e base null è diverso da zero, allora V aumenterà il rango della matrice. Ad esempio, supponiamo di avere la matrice M, che ovviamente ha un rango di 2.

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

Sarà un nuovo vettore colonna [1; 1; 1; 1] aumentare il rango se allegate a M?

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

Sì, poiché ha un non-zero proiezione su almeno uno dei vettori di base in nullM.

Che ne dite di questo vettore:

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

In questo caso, entrambi i numeri sono sostanzialmente pari a zero, in modo che il vettore in questione non avrebbe aumentato il rango di M.

Il punto è, a la moltiplicazione semplice del vettore matrice è necessaria una volta generata la base dello spazio nullo. Se la tua matrice è troppo grande (e la matrice quasi del rango completo) che una chiamata a null fallirà qui, allora dovrai fare più lavoro. Tuttavia, n = 4096 non è eccessivamente grande fintanto che la matrice non ha troppe colonne.

Un'alternativa se nulla è troppo è una chiamata a GNS, per trovare quei vettori singolari che sono essenzialmente zero. Questi formeranno la base nulla di cui abbiamo bisogno.

fonte

2012-02-01 16:12:24

Grazie! Questo è quello che ho tentato, tranne che il mio LinAlg-fu non è forte come il tuo. – Jonas

Grazie, questo è un ottimo consiglio per soluzioni ripetute. –

userei sprank per matrici sparse. Dai un'occhiata, potrebbe essere più veloce di qualsiasi altro metodo.

Modifica: Come sottolineato correttamente da @IanHincks, non è il grado. Lascio la risposta qui, nel caso in cui qualcun altro ne avesse bisogno in futuro.

fonte

2012-02-01 16:30:04

È decisamente molto più veloce, ma non restituisce il rango, solo un limite sul rango (la documentazione lo chiama rango strutturale). –

modo più veloce per controllare se un vettore aumenta matrice rango

risposta

Problemi correlati