Kompleksitas menemukan matriks pseudoinverse

Berapa banyak operasi aritmatika yang diperlukan untuk menemukan matriks pseudoinverse Moore-Penrose dari bidang arbitrer?

Jika matriksnya tidak dapat dibalik dan dinilai kompleks, maka itu hanyalah kebalikannya. Menemukan invers membutuhkan waktu, di mana adalah konstanta pengali matriks. Teorema 28.2 dalam Pengantar Algoritma Edisi ke-3. $O(n^\omega)$ $\omega$

Jika matriks memiliki baris atau kolom yang independen secara linier dan bernilai kompleks, maka matriks pseudoinverse dapat dihitung dengan atau berurutan, di mana adalah konjugat transpose dari . Secara khusus, ini menyiratkan waktu untuk menemukan pseudoinverse dari . $A$ $A^*(A A^*)^{-1}$ $(A A^*)^{-1}A^*$ $A^*$ $A$ $O(n^\omega)$ $A$

Untuk matriks umum, algoritma yang saya lihat menggunakan dekomposisi QR atau SVD, yang tampaknya mengambil operasi aritmatika dalam kasus terburuk. Apakah ada algoritma yang menggunakan lebih sedikit operasi? $O(n^3)$

algorithms linear-algebra Chao Xu
sumber

Saya memiliki tindak lanjut, Mungkin terlalu dasar tetapi dapat Anda silahkan confirm apa yang n di sini dalam persamaan kompleksitas. Apakah ini dimensi dari sebuah matriks dan bagaimana jika matriks tersebut bukan persegi.?

Mike Pomp

Dalam klaim bahwa invers dapat ditemukan dalam waktu

memang merupakan dimensi dari matriks kuadrat; jika matriksnya tidak persegi, Anda mungkin dapat mengambil

menjadi dimensi yang lebih besar.

O (n^{ω})

$O(n^\omega)$

n

$n$

n

$n$

David Richerby

Karena ini adalah pertanyaan yang mudah, saya sudah menjawabnya di sini. Namun, jika Anda memiliki pertanyaan lebih lanjut, silakan tanyakan pada mereka sebagai halaman sendiri menggunakan tombol "ajukan pertanyaan" di bagian atas halaman. Anda dapat menautkan kembali ke halaman ini untuk memberikan konteks. Situs ini hanya diatur untuk satu pertanyaan per halaman: tidak ada threading dan posting bergerak sesuai dengan suara yang mereka peroleh, sehingga semuanya menjadi sangat berantakan dengan lebih dari satu pertanyaan pada halaman. Ada informasi lebih lanjut di tur singkat kami dan di pusat bantuan kami .

David Richerby

Jawaban:

Pertama-tama, orang cenderung lupa bahwa adalah infinite. Setiap kali kita menulis , kita sebenarnya bermaksud untuk semua , ada algoritma yang berjalan dalam waktu . $\omega$ $O(n^\omega)$ $\gamma > \omega$ $O_\gamma(n^\gamma)$

Keller-Gehrig menunjukkan (antara lain) bagaimana menyajikan matriks dalam bentuk normal dalam waktu . Jika memiliki peringkat , maka bentuk normal peringkat adalah untuk beberapa terbalik dari dimensi yang sesuai; lihat juga Teori Kompleksitas Aljabar, Proposisi 16.13 pada halaman 435. $A$ $O(n^\omega)$ $A$ $r$ $A$

S (\begin{matrix} I_{r} & 0 \\ 0 & 0 \end{matrix}) T

$S \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} T$

S, T

$S,T$

$A = XY$ $X$ $r$ $Y$ $r$ $X$ $r$ $S$ $Y$ $r$ $T$ $O(n^\omega)$

Yuval Filmus
sumber

Terima kasih atas jawabannya! Saya mendapatkan kertas dan ternyata saya tidak memiliki latar belakang. Apakah ada pengantar / survei yang bagus tentang hasil seperti ini? Saya tahu buku Teori Kompleksitas Aljabar adalah buku yang bagus tapi saat ini sudah keluar dari perpustakaan ...

Chao Xu

Mungkin ada catatan kuliah yang relevan, meskipun mungkin yang terbaik untuk melihat buku itu. CLRS (Pengantar Algoritma) juga mengandung beberapa materi yang relevan, seperti kesetaraan antara perkalian matriks dan invers matriks.

Yuval Filmus

O (n^{ω})

$O(n^ω)$

w

$w$

ω

$\omega$

ω < 2.3728639

$\omega < 2.3728639$

ω = 2

$\omega = 2$