Null-space dari matriks padat persegi panjang

16

Diberi matriks padat apa cara terbaik untuk menemukan basis ruang-nol dalam beberapa toleransi ?

ARm×n,m>>n;max(m)100000
ϵ

Berdasarkan pada dasar itu dapatkah saya mengatakan bahwa col tertentu tergantung linear dalam ? Dengan kata lain, memiliki basis ruang nol dihitung, kolom apa yang harus dihilangkan untuk mendapatkan matriks nonsingular?ϵA

Referensi dihargai.

Alexander
sumber

Jawaban:

12

Metode standar untuk menentukan ruang nol dari sebuah matriks adalah dengan menggunakan dekomposisi QR atau SVD. Jika akurasi adalah yang terpenting, SVD lebih disukai; dekomposisi QR lebih cepat.

A=UΣVHVΣmax(m,n)εε

Menggunakan dekomposisi QR, jika , dan pangkat adalah , maka kolom terakhir dari membentuk ruang nol dari , dengan asumsi bahwa dekomposisi QR adalah peringkat yang terbuka. Untuk menentukan , hitung jumlah entri pada diagonal utama yang besarnya melebihi toleransi (mirip dengan yang digunakan dalam pendekatan SVD).AT=QRArnrQArR

Jangan gunakan dekomposisi LU. Dalam aritmatika yang tepat, ini adalah pendekatan yang layak, tetapi dengan aritmatika titik apung, akumulasi kesalahan numerik membuatnya tidak akurat.

Wikipedia membahas topik-topik ini di sini .

Geoff Oxberry
sumber
Geoff, berbicara dalam hal QR, seandainya saya memiliki dekomposisi, bagaimana saya kemudian menghubungkan basis ruang nol dan kolom dalam matriks asli? Dengan kata lain, kolom apa yang harus saya hapus dari untuk menghilangkan ruang kosong? Intinya di sini adalah bekerja dengan sendiri dan bukan dengan dekomposisi. AA
Alexander
Rutinitas yang menghitung dekomposisi QR biasanya menyertakan opsi untuk mengembalikan vektor permutasi yang menunjukkan bagaimana kolom diijinkan untuk mendapatkan faktorisasi QR. Entri terakhir dari vektor permutasi akan sesuai dengan baris (kolom ) yang ada di ruang nol. Entri pertama dari vektor tersebut berhubungan dengan kolom yang bebas linear. Saya tidak yakin apa yang Anda maksud dengan "singkirkan ruang kosong". Maksud Anda ingin menghapus kolom untuk mendapatkan matriks nonsingular? A A T r A T AnrAATrATA
Geoff Oxberry
Ya, maksud saya itu. Saya akan melihat permutasi, terima kasih.
Alexander
Itu pertanyaan yang berbeda. Apa yang Anda kemudian akan lakukan malah menghitung QR dekomposisi (atau SVD) dari . Jika Anda menghitung dekomposisi QR dari A , Anda dapat menghitung peringkat A seperti pada jawaban di atas (tidak perlu mengubah urutan matriks), dan kemudian r entri pertama (di mana r adalah pangkat A ) dari vektor permutasi yang sesuai ke kolom independen A . Algoritma yang sama berlaku untuk SVD; jika Anda dapat mengembalikan vektor permutasi bersama dengan dekomposisi, itu akan memberikan informasi yang diperlukan. AAArrAA
Geoff Oxberry
8

Jika , sebagai pertanyaan Anda menunjukkan, Anda dapat menyimpan beberapa pekerjaan dengan terlebih dahulu memilih indeks set I dari p 5 n (katakanlah) baris acak dan menggunakan faktorisasi ortogonal A T I : = Q R . (The QR-faktorisasi adalah satu di mana Q adalah sqare dan R adalah persegi panjang dari peringkat r , dan sisanya n - r kolom R adalah nol Menggunakan permutasi QR faktorisasi akan meningkatkan stabilitas; permutasi kemudian harus diperhitungkan dalam. resep lebih detail.)mnIp5nAI:T=QRQRrnrR

Biasanya, ini akan memberi Anda ruang bagian yang jauh lebih rendah dimensi direntang oleh kolom , yang terakhir n - r kolom Q . Subspace ini berisi ruang nol dari A . Sekarang memilih lain, menguraikan acak indeks set dan menghitung QR faktorisasi ( A I : N ) T . Lipat gandakan ruang nol yang dihasilkan di sebelah kiri oleh N untuk mendapatkan N yang lebih baik dari dimensi yang mungkin lebih rendah. Ulangi sampai dimensi N tidak lagi berkurang. Maka Anda mungkin memiliki ruang nol yang benar dan dapat memeriksa dengan menghitung A NNnrQA(AI:N)TNNNAN. Jika ini belum dapat diabaikan, lakukan iterasi lebih lanjut dengan baris paling signifikan.

Edit: Setelah Anda memiliki , Anda dapat menemukan satu set maksimal J kolom bebas linear dari A oleh faktorisasi ortogonal N T = Q R dengan berputar. Memang, himpunan indeks J yang tidak dipilih sebagai pivot akan memiliki properti ini.NJANT=QRJ

Arnold Neumaier
sumber
+1 untuk cara yang efisien untuk menentukan ruang nol dari matriks besar. Saya harus ingat untuk berkonsultasi jawaban ini nanti ketika saya membutuhkannya.
Geoff Oxberry
Memang, kedengarannya masuk akal, namun matriks saya masuk ke dalam 16 GB RAM, jadi saya akan tetap dengan qr matlab standar.
Alexander
Neumaier, saya telah memutuskan untuk menguji algoritma itu, tetapi saya tidak mengerti persis apa itu dan apa artinya "menghitung faktorisasi QR dari ( A I : N ) T "? Bisakah Anda jelaskan sedikit lebih banyak. N(AI:N)T
Alexander,
Saya mengedit jawaban saya sedikit. dihitung dengan resep Geoff Oxberry. N
Arnold Neumaier
Terima kasih. Saya menerapkannya. Namun, sejauh yang saya lihat, algoritma ini tidak memungkinkan untuk mendefinisikan saya satu set kolom bebas linear (karena kita membusuk A T I : bukan A I : ), tetapi hanya membantu untuk memperkirakan nul dasar itu sendiri? AAI:TAI:
Alexander