Espaço nulo de uma matriz densa retangular

Dada uma matriz densa Qual é a melhor maneira de encontrar sua base de espaço nulo com alguma tolerância ?

A \in R^{m \times n}, m >> n; m a x (m) \approx 100000

$A \in R^{m \times n}, m >> n; max(m) \approx 100000$

ϵ

$\epsilon$

Com base nessa base, posso dizer que determinadas colunas são linearmente dependentes em $\epsilon$ ? Em outras palavras, tendo a base de espaço nulo calculada, quais colunas de $A$ precisam ser removidas para obter uma matriz não singular?

Referências são apreciadas.

linear-algebra Alexander
fonte

Respostas:

Os métodos padrão para determinar o espaço nulo de uma matriz são usar uma decomposição QR ou um SVD. Se a precisão é primordial, o SVD é o preferido; a decomposição do QR é mais rápida.

Usando o SVD, se $A = U\Sigma V^{H}$ , as colunas de $V$ correspondentes a pequenos valores singulares (ou seja, pequenas entradas diagonais de $\Sigma$ ) formam a base para o espaço nulo. A tolerância relevante aqui é o que se considera um valor singular "pequeno". O MATLAB, por exemplo, é pequeno para $\max(m,n) \cdot \varepsilon$ , onde $\varepsilon$ está relacionado à precisão da máquina (veja aqui na documentação do MATLAB ).

Usando a decomposição QR, se , e a classificação de for , as últimas colunas de formam o espaço nulo de , assumindo que a decomposição QR seja reveladora da classificação. Para determinar , calcule o número de entradas na diagonal principal de cuja magnitude excede uma tolerância (semelhante à usada na abordagem SVD). $A^{T} = QR$ $A$ $r$ $n-r$ $Q$ $A$ $r$ $R$

Não use a decomposição da LU. Na aritmética exata, é uma abordagem viável, mas com a aritmética de ponto flutuante, o acúmulo de erros numéricos a torna imprecisa.

A Wikipedia cobre esses tópicos aqui .

Geoff Oxberry
fonte

Geoff, falando em termos de QR, suponha que eu tenha a decomposição, como relaciono a base de espaço nulo e as colunas na matriz original? Em outras palavras, quais colunas devo remover de para livrar-se do espaço nulo? O objetivo aqui é trabalhar com o próprio e não com sua decomposição.

A

$A$

A

$A$

Alexander

As rotinas que calculam a decomposição do QR normalmente incluem uma opção para retornar um vetor de permutação, indicando como as colunas são permutadas para obter a fatoração do QR. As últimas entradas desse vetor de permutação corresponderiam às linhas de (colunas de ) que estão no espaço nulo. As primeiras entradas desse vetor correspondem às colunas de que são linearmente independentes. Não sei ao certo o que você quer dizer com "livrar-se do espaço nulo". Você quer dizer que deseja remover as colunas de para obter uma matriz não singular?

n - r

$n-r$

A

$A$

A^{T}

$A^{T}$

r

$r$

A^{T}

$A^{T}$

A

$A$

precisa

Sim, eu quis dizer isso. Vou olhar para a permutação, obrigado.

Alexander

Essa é uma pergunta diferente. O que você deve então fazer em vez disso é calcular a decomposição QR (ou SVD) de . Se você calcular a decomposição QR de , poderá calcular a classificação de como na resposta acima (não há necessidade de transpor a matriz) e, em seguida, as primeiras entradas (onde é a classificação de ) do vetor de permutação correspondem para as colunas independentes de . O mesmo tipo de algoritmo se aplica ao SVD; se você pode retornar um vetor de permutação junto com a decomposição, isso deve fornecer as informações necessárias.

A

$A$

A

$A$

A

$A$

r

$r$

r

$r$

A

$A$

A

$A$

precisa

Se , como indica sua pergunta, você pode economizar algum trabalho escolhendo primeiro um conjunto de índices de (digamos) linhas aleatórias e usando a fatoração ortogonal . (A fatoração QR é aquela em que é quadrado e é retangular na classificação , e as colunas restantes de são zero. O uso de uma fatoração QR permutada aumentará a estabilidade; a permutação deve ser contabilizada de forma mais detalhada receita.) $m\gg n$ $I$ $p\approx 5n$ $A_{I:}^T=QR$ $Q$ $R$ $r$ $n-r$ $R$

Normalmente, isso vai lhe dar um subespaço muito menor dimensional gerado por colunas de , a última colunas de . Este subespaço contém o espaço nulo de . Agora escolher outro, disjuntos conjunto índice aleatório e calcular a fatoração QR de . Multiplique o espaço nulo resultante à esquerda por para obter um aprimorado de dimensão provavelmente ainda mais baixa. Itere até que a dimensão de não diminua mais. Então você provavelmente tem o espaço nulo correto e pode verificar computando . Se isso ainda não for insignificante, faça iterações adicionais com as linhas mais significativas. $N$ $n-r$ $Q$ $A$ $(A_{I:}N)^T$ $N$ $N$ $N$ $AN$

Edit: Depois de ter , você pode encontrar um conjunto máximo de colunas linearmente independentes de por uma fatoração ortogonal de com pivô. De fato, o conjunto de índices não escolhidos como pivôs terá essa propriedade. $N$ $J$ $A$ $N^T=QR$ $J$

Arnold Neumaier
fonte

+1 para uma maneira eficiente de determinar o espaço nulo de uma matriz grande. Vou ter que lembrar de consultar esta resposta mais tarde, quando precisar.

precisa

Na verdade, parece razoável, no entanto, minhas matrizes cabem em 16 GB de RAM, então eu ficaria com o matlab qr padrão.

Alexander

Prof. Neumaier, decidi testar esse algoritmo, mas não entendo exatamente o que é

e o que significa "calcular a fatoração QR de

"? Poderia explicar um pouco mais.

N

$N$

(A_{I :} N)^{T}

$(A_{I:}N)^T$

Alexander

Eu editei minha resposta um pouco.

é calculado pela receita de Geoff Oxberry.

N

$N$

Arnold Neumaier

Obrigado. Eu implementei. No entanto, tanto quanto eu ver, este algoritmo não permite-me definir um conjunto de colunas linearmente independentes de

(uma vez que se decompõem

em vez de

), mas apenas ajuda a estimar base espaço nulo em si?

A

$A$

A_{I :}^{T}

$A_{I:}^T$

A_{I :}

$A_{I:}$

Alexander