Singular Value Decomposition

[suan123]

พี่ๆคับ ช่วยดูสองข้อนี้ให้หน่อยคับ

1. Using the SVD, prove that any matrix in $\mathbb{C}^{m\times n}$ os the limit of a sequence of matrices of full rank. On other word, prove that the set of full rank matrices is a dense subset of $\mathbb{C}^{m\times n} $. Use the2-norm for your proof.

2. Suppose that $A\in\mathbb{C}^{m\times n}$ has $SVD$ : $A=U\Sigma V^{*}$. Find the eigenvalue decomposition of the $2m\times2m$ hermitian matrix

$$ \left[\begin{array}{cc}
0 & A^{*}\\
A & 0
\end{array}\right]. $$

[nooonuii]

SVD คืออะไรเหรอครับ ผมไม่เคยใช้มาก่อน

[suan123]

Singular Value Decomposition ครับ

[nooonuii]

ข้อความเดิมเขียนโดยคุณ suan123

พี่ๆคับ ช่วยดูสองข้อนี้ให้หน่อยคับ

1. Using the SVD, prove that any matrix in $\mathbb{C}^{m\times n}$ os the limit of a sequence of matrices of full rank. On other word, prove that the set of full rank matrices is a dense subset of $\mathbb{C}^{m\times n} $. Use the2-norm for your proof.

คิดว่าเป็นแบบนี้ครับ สมมติ $A=U\Sigma V^{*}$

โดยที่ $\Sigma=\text{diag}(a_1,a_2,...,a_k,0,...,0)$ เมื่อ $a_1\geq a_2\geq\cdots\geq a_k>0$

โดย Archimedean property จะมี $N$ ซึ่ง $a_k>\dfrac{1}{N}$

ต่อไปสร้าง $\Sigma_t=\text{diag}(a_1,...,a_k,\dfrac{1}{N+t},\dfrac{1}{N+t},...,\dfrac{1}{N+t})$ เมื่อ $t\in\mathbb{N}$

และให้ $A_t=U\Sigma_t V^{*}$ จะเห็นว่า $A_t$ มี full rank ทุก $t$ เพราะว่า $\text{rank}(A_t)=\text{rank}(\Sigma_t)$

และ $A_t\to A$ เมื่อ $t\to\infty$ เพราะว่า $\Sigma_t\to \Sigma$ เมื่อ $t\to\infty$

[nooonuii]

ข้อ $2$ ยังไม่เคยใช้พวกนี้ก็เลย no idea ครับ

[suan123]

ดูเหมือนไม่ต้องใช้ 2-norm ตามที่โจทย์สั่งเลยอะครับ
ผมงงตรง
$$ \Sigma_{t}=dig(a_{1,...}a_{k},\frac{1}{N+t},\frac{1}{N+t},...\frac{1}{N+t}) $$
มายังไงครับ

[nooonuii]

ใช้ 2-norm ตอนเขียนแจกแจงรายละเอียดการพิสูจน์ครับ

จริงๆแล้วใช้ norm ตัวไหนก็ได้ครับ

แต่ผมก็ยังเห็นว่าไม่น่าจะถูกเพราะเมื่อ $\Sigma_t$ เปลี่ยนไป $U,V$ จะต้องเปลี่ยนตาม

จึงควรเขียนเป็น $U_t,V_t$ แทน แต่รายละเอียดส่วนนี้ผมก็ยังไม่ค่อยเข้าใจครับ

[Anarist]

ข้อ 1 ไอเดียหลักๆ เหมือนของคุณ nooonuii แหละครับ
ให้ $A = U \Sigma V^*$ ไว้ก่อน โดย SVD

แต่ $\Sigma$ เนี่ยมัน m-by-n diagonal (rectangular diagonal) with nonnegative entries
เวลาเขียน diagonal ก็เลยจะงงๆหน่อย
โดยไม่เสียนัยก็เรียงมากไปน้อยจากบนลงล่าง $a_1 , ... , a_k , ... , a_d$ โดย $d= min(m,n)$
สมมติมันไม่ full rank ก็คือ $a_{k+1} = ... = a_d = 0$ และ $a_k > 0$

ทริกคือหา $A_\epsilon$ ที่จะเข้าหา $A$ โดยใช้ $U,V$ เดิม
แต่เปลี่ยน $\Sigma$ เป็น $\Sigma_\epsilon$โดยเติมตรง $a_{k+1} , ... , a_d$ ที่เป็น 0 ด้วย $\epsilon$ น่ะครับ
จะได้ $A_\epsilon - A = U (\Sigma_\epsilon - \Sigma) V^*$
เช็คได้ว่า 2-norm ของอันนี้เป็น $\epsilon$ (จริงๆ ที่ใช้ 2-norm ง่ายสุดเพราะมันก็คือค่ามากสุดของสมาชิกใน $\Sigma$ นั่นเอง)

ข้อ 2 block matrix อันนั้นไม่ใช่ (m+n)-by-(m+n) เหรอครับ
แต่ถ้าเอาตามนั้นลองคูณเข้าทางซ้ายขวาด้วย block ที่มี $U,V,U^*,V^*$ ดูครับ
(สลับกันให้ถูก ให้สุดท้ายเหลือแต่ $\Sigma , \Sigma^*$ แล้วก็ต้องสลับที่นิดหน่อย)

[suan123]

Let A to be an arbitrary matrix. We need to find the full-rank matrix $A_{k}$ for $k=1,2,3,...$ such that $$lim_{k\rightarrow\infty}A_{k}=A.$$

Consider $$A=U\Sigma V^{H}=\Sigma_{i=1}^{n}u_{i}v_{i}^{H}\sigma_{i},$$


since we need $A_{k}$ to be full rank, all of singular values of $A_{k}$ must be greater than 0.
Let $$A_{k}=\Sigma_{i=1}^{n}u_{i}v_{i}^{H}\left(\sigma_{i}+\frac{1}{k}\right),$$
then the singular values $$\sigma_{i}+\frac{1}{k}>0, \forall {i} $$

$$lim_{k\rightarrow0}A_{k} =\Sigma_{i=1}^{n}u_{i}v_{i}^{H}\left(\sigma_{i}+lim_{k\rightarrow0}\frac{1}{k}\right)
=\Sigma_{i=1}^{n}u_{i}v_{i}^{H}\sigma_{i}
=A.$$

อ่านแล้วงงไหมครับ

[suan123]

ช่วยอธิบายข้อ 2 อีกนิดได้มั๊ยครับ

[kongp]

สมัยแรกๆ ผมก็งง SVD , Eigen Value . ต่อมาก็รู้ว่าไม่มีอะไรมาก นอกจากหาตัวแทนของเมตริกซ์สำหรับในเชิงเขียนโปรแกรมหาผลลัพธ์ บางคนก็ว่าซับซ้อนอีกระดับ ซึ่งซับซ้อนมากกว่านี้ก็มี ช่วยๆ กันพัฒนาและศึกษานะครับ (เมตริกซ์แยกออกแบบเวกเตอร์ในระนาบสี่แกน)

[suan123]

ในสาย Applied Mathematics, Eigenvalues problem นี้เป็นปัญหาใหญ่มากๆเลยครับ ทุกวันนี้ก็ยังไม่มีวิธีการหาที่ดีที่สุด ถ้าคนที่เคยใช้ Matlab จะรู้ว่า command \ เป็น function มหัศจรรย์เลยละครับ

ผมเป็นมือใหม่ ยังดีที่ได้พี่ๆในบอร์ดช่วยชี้แนะครับ ไม่งั้นอาจจะเรียนไม่จบเอาได้

[kongp]

จบไม่จบเป็นไปตามสังคมครับ แนะให้เข้ากลุ่ม ไม่ต้องหวังผลเลอเลิศเกินไป

[suan123]

SVD ต่ออีกสักข้อครับ

Use $SVD$ to show that if $A$ belongs to $\mathcal{R}^{m\times n}$ with $m\geq n,$ then there exists $Q\in\mathcal{R}^{m\times n}$ such that $Q^{T}Q=I$ and $P\in\mathcal{R}^{m\times n}$ a positive semi-definite matrix such that $A=QP$.

This is called the the polar decomposition. Also show that if $A$ is invertible, then the polar decomposition is unique.