Nomor kondisi formulasi A'A dan AA

9

Ditampilkan (Yousef Saad, metode berulang untuk sistem linier yang jarang , hal. 260) yang $cond(A'A) \approx cond(A)^2$

Apakah ini juga berlaku untuk ? $AA'$

Dalam kasus adalah dengan , saya amati bahwa $A$ $N\times M$ $N \ll M$ $cond(A'A) \gg cond(AA')$

Apakah itu berarti formulasi dalam hal lebih disukai dalam kasus ini? $AA'$

linear-algebra condition-number Alexander
sumber

2

Anda membandingkan angka kondisi dua matriks dengan ukuran yang sangat berbeda. Tanpa penjelasan mengapa, sepertinya perbandingan itu mungkin tidak bermakna. Tentu saja, jika Anda dapat mencapai apa yang Anda butuhkan dengan menggunakan matriks yang jauh lebih kecil, Anda harus (bahkan jika kondisinya mirip).

David Ketcheson

1

Jawaban baru oleh Stefano M di bawah ini benar. Silakan baca dan pilih itu.

David Ketcheson

6

Jika dengan , maka sehingga tidak bisa peringkat penuh, yaitu singular. $A\in\mathbb{R}^{N\times M}$ $N<M$

r a n k (A^{T} A) = r a n k (A A^{T}) = r a n k (A) \leq N < M

$\mathop{\mathrm{rank}}(A^TA) = \mathop{\mathrm{rank}}(AA^T) = \mathop{\mathrm{rank}}(A) \leq N < M$

A^{T} A \in R^{M \times M}

$A^TA \in \mathbb{R}^{M\times M}$

Dengan demikian nomor kondisi adalah . Karena aritmatika presisi terbatas, jika Anda menghitung dalam matlab Anda mendapatkan jumlah besar, tidak . $\kappa_2(A^TA)=\infty$ cond(A'A)Inf

Stefano M
sumber

@OscarB: nilai singular

hanya

, tidak ada yang namanya nilai singular ke-

! Derivasi Anda benar, tetapi harap dicatat bahwa jika

,

adalah sv untuk

, maka

, sedangkan

A

$A$

N

$N$

M

$M$

σ_{i}

$\sigma_i$

i = 1 \dots N

$i=1\dots N$

A

$A$

S S^{T} = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2})

$SS^T=\mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2)$

dengan

trailing nol.

S^{T} S = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2}, 0, \dots, 0)

$S^TS = \mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2, 0, \dots, 0)$

M - N

$M-N$

Stefano M

8

Nah, lihat mari mengapa memiliki sekitar jumlah kondisi kuadrat . Dengan menggunakan dekomposisi SVD dari , dengan , , , kita dapat menyatakan sebagai $A^TA$ $A$ $A=USV^T$ $U \in \mathbb{R}^{N \times N}$ $S \in \mathbb{R}^{N \times M}$ $V \in \mathbb{R}^{M \times M}$ $A^T A$

$A^T A=(USV^T)^T USV^T=VS^T U^T U S V^T=V S^T S V^T$

Yang kita tiba di dengan mencatat bahwa adalah ortonormal, sehingga . Lebih lanjut kita perhatikan bahwa adalah matriks diagonal, sehingga dekomposisi akhir dapat dinyatakan sebagai , dengan berarti , menghasilkan matriks diagonal dengan nilai singular N pertama dari kuadrat di diagonal. Ini berarti bahwa karena jumlah kondisi adalah rasio yang pertama dan nilai singular terakhir, $U$ $U^T U=I$ $S$ $A^TA$ $V S^2 V^T$ $S^2$ $S^T S$ $S$ untuk, $cond(A)=\frac{s_1}{s_N}$ $A \in \mathbb{R}^{N \times M}$

$cond(A^T A)=\frac{s_1^2}{s_M^2}=(\frac{s_1}{s_M})^2=cond(A)^2$

Sekarang, kita dapat melakukan latihan yang sama dengan : $AA^T$

$AA^T=USV^T (USV^T)^T=USV^T V S^T U^T=U S^2 U^T$

Yang berarti bahwa kita mendapatkan hasil , karenasini berarti, perbedaan yang halus dari notasi di atas. $cond(AA^T)=\frac{s_1^2}{s_N^2}$ $S^2$ $SS^T$

Tetapi perhatikan perbedaan yang halus itu! Untuk , nomor kondisi memiliki nilai tunggal M'th dalam penyebut, sedangkan memiliki nilai tunggal N'th. Hal ini menjelaskan mengapa Anda melihat perbedaan yang signifikan dalam jumlah kondisi - memang akan “lebih baik AC” dari . $A^TA$ $AA^T$ $AA^T$ $A^TA$

Namun, David Ketcheson benar - Anda membandingkan angka kondisi antara dua matriks yang sangat berbeda. Secara khusus, apa yang dapat Anda capai dengan tidak akan sama dengan apa yang dapat Anda capai dengan . $A^TA$ $AA^T$

OscarB
sumber

Itu penjelasan yang bagus! Saya melihat perbedaannya dengan jelas sekarang. Matriks A digunakan untuk membangun persamaan normal dan dengan sedikit perubahan Anda juga dapat merumuskan sebagai

, bukan klasik

. Bisakah Anda memberi tahu juga apakah menguntungkan untuk menggunakan pemecah seperti LSQR daripada memecahkan persamaan normal? Karena LSQR tidak perlu membuat produk ini sama sekali.

A A^{'}

$AA'$

A^{'} A

$A'A$

Alexander

Senang itu masuk akal. Secara umum, Anda perlu mempertimbangkan pengondisian masalah. Tetapi, jika itu bukan masalah, Anda bisa menggunakan persamaan normal / faktorisasi-QR (dari A) / LSQR, tergantung pada ukuran masalah (di antara hal-hal lain). Kecuali masalah Anda besar atau tidak terkondisi, saya mungkin akan menerapkan QR-faktorisasi, tetapi tanpa lebih banyak pengetahuan tentang masalah yang Anda coba selesaikan, sulit untuk mengatakannya. Saya yakin orang lain yang lebih berpengalaman bisa memberikan saran yang lebih rinci.

OscarB

A itu sendiri tidak terkondisi (dengan nomor kondisi

), padat dan besar. QR bukan opsi. Karena itu kondisi buruk, saya harus menambahkan beberapa regularisasi. Sekarang regularisasi Tikhonov yang sederhana tampaknya sudah cukup. Intinya adalah bahwa jika

(untuk kasus saya dengan

\approx 10^{7}

$\approx 10^7$

c o n d (A) < c o n d (A A^{T}) < c o n d (A^{T} A)

$cond(A) < cond(AA^T) < cond(A^T A)$

N < M

$N < M$ ) kemudian menggunakan LSQR tampaknya selalu lebih disukai karena Anda tidak perlu membentuk produk sama sekali. Pertanyaannya adalah apakah solusi yang diperoleh dengan persamaan normal dan LSQR identik?

Alexander

Yah, seperti yang saya mengerti, LSQR akan memberikan solusi yang identik dengan persamaan normal setelah "iterations tak terhingga" dalam presisi yang tepat. Namun, untuk masalah keliru, solusi persamaan normal bukanlah yang Anda inginkan. Sebaliknya, Anda ingin menggunakan LSQR untuk beralih sampai semi-konvergensi tercapai. Namun, mengendalikan algoritma iteratif dalam masalah-masalah keliru adalah permainan bola lainnya. Juga, tergantung pada biaya produk matriks-vektor Anda dan jumlah iterasi (dan dengan demikian matvec) diperlukan, solusi tikhonov langsung dengan bidiagonisasi mungkin lebih baik.

OscarB

Penjelasan luar biasa. +1 untuk Anda, Tuan!

meawoppl

2

Klaim bahwa (untuk matriks kuadrat) ~~dalam pertanyaan dan~~ [Sunting: Saya salah membaca] dalam jawaban Artan adalah omong kosong. Contoh tandingan $\DeclareMathOperator{\cond}{cond} \cond A^2 \approx \cond A^T A$

SEBUAH = (\begin{matrix} ϵ & 1 \\ 0 & ϵ \end{matrix}), ϵ ≪ 1

$\newcommand\bigO{\mathcal{O}}A = \begin{pmatrix} \epsilon & 1 \\ 0 & \epsilon \end{pmatrix}, \quad \epsilon \ll 1$

di mana Anda dapat dengan mudah memeriksa sementara . $\cond A^T A = \bigO(\epsilon^{-4})$ $\cond A^2 = \bigO(\epsilon^{-2})$

Jed Brown
sumber

OK untuk menekankan bahwa

dan

secara umum sangat berbeda dengan apa yang berkaitan dengan eigs, svds, cond number: tetapi menurut saya klaim pertanyaannya adalah tentang

.

A^{2}

$A^2$

A^{T} A

$A^T A$

[c o n d (A)]^{2}

$[\mathrm{cond}(A)]^2$

Stefano M

@StefanoM Terima kasih, sepertinya saya salah membaca, meskipun dari diskusi, bukan satu-satunya.

Jed Brown

1

Dalam cond aritmatika yang tepat (A ^ 2) = cond (A'A) = cond (AA '), lihat misalnya. Golub dan van Loan, edisi ketiga, p70. Ini tidak benar dalam aritmatika floating point jika A hampir kekurangan peringkat. Saran terbaik adalah mengikuti resep buku di atas ketika memecahkan masalah kuadrat terkecil, pendekatan SVD teraman, p257. Gunakan \ varepsilon-rank sebagai gantinya saat menghitung SVD, di mana \ varepsilon adalah resolusi data matriks Anda.

Artan
sumber

Maaf, saya melihat Golub dan Van Loan 3rd ed p. 70, dan tidak dapat menemukan apa pun yang mendukung pernyataan cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T). Bisakah Anda lebih spesifik dengan referensi Anda?

OscarB

Tidak ada pernyataan di sana, tetapi Anda dapat berasal dari teorema 2.5.2 dan pseudoinverse, bagian 5.5.4 yang cond (AA ') = cond (A'A). Alasan saya mengambil pseudoinverse adalah bahwa inilah yang penting untuk masalah kuadrat terkecil di tangan. Kesetaraan setelah cond (A ^ 2) harus \ approx, maaf atas kesalahan ketik.

Artan

Tidak, jawaban ini sama sekali salah. Lihat contoh tandingan saya.

Jed Brown

Saad pasti telah membuat titik seperti itu dengan konteks tertentu. Apa yang relevan untuk pertanyaan yang ada adalah argumen yang melanjutkan.

Artan

Nomor kondisi formulasi A'A dan AA

Jawaban: