4.5: Вправи

Вправа 4.1

Переконайтеся\(A\), що для будь-якої\(m \times n\) матриці має наступне:

\[\frac{1}{\sqrt{n}}\|A\|_{1} \leq\|A\|_{2} \leq \sqrt{m}\|A\|_{\infty}.\nonumber\]

Вправа 4.2

Припустимо\(A^{\prime} = A\). Знайти точне співвідношення між власними значеннями і сингулярними значеннями\(A\). Чи тримається це\(A\), якщо не сполучений симетричний?

Вправа 4.3

Покажіть, що якщо\(rank(A) = 1\), то,\(\|A\|_{F}=\|A\|_{2}\)

Вправа 4.4

Ця проблема веде вас через аргумент існування SVD, використовуючи ітераційну конструкцію. Показуючи\(A = U \Sigma V^{\prime}\), що де\(U\) і\(V\) є унітарні матриці еквівалентно тому, щоб показати, що\(U^{\prime}AV = \Sigma\).

а) Аргументуйте з визначення\(\|A\|_{2}\), що існують одиничні вектори (вимірюються в 2-нормі)\(x \in C^{n}\) і\(y \in C^{m}\) такі\(Ax = \sigma y\), що, де\(\sigma= \|A\|_{2}\).

б) Ми можемо розширити обидва\(x\) і\(y\) вище до ортонормальних основ, тобто ми можемо знайти унітарні матриці\(V_{1}\) і\(U_{1}\) чиї перші стовпці\(x\) і\(y\) відповідно:

\[V_{1}=\left[x \tilde{V}_{1}\right], \quad U_{1}=\left[y \tilde{U}_{1}\right]\nonumber\]

Покажіть, що один із способів зробити це - це перетворення домовласника, наступним чином:

\[V_{1}=I-2 \frac{h h^{\prime}}{h^{\prime} h}, \quad h=x-[1,0, \ldots, 0]^{\prime}\nonumber\]

і так само для\(U_{1}\).

в)) Тепер визначте\(A_{1}=U_{1}^{\prime} A V_{1}\). Чому це\(\|A_{1}\|_{2}=\|A\|_{2}\)?

г) Зауважте, що

\ [A_ {1} =\ лівий (\ початок {масив} {cc}
y^ {\ прайм} A x & y^ {\ прайм} A\ тильда {V} _ {1}\
\ тильда {U} _ {1} ^ {\ прайм} A x &\ tilde {U} _ {1} ^ {\ прайм} A\ тильда {V} _ {1} масив}
\ праворуч) =\ лівий (\ begin {масив} {cc}
\ сигма & w^ {\ прайм}\\
0 & B
\ end {масив}\ право)\ nonumber\]

Яке обґрунтування того, що нижній лівий елемент у наведеній вище матриці дорівнює 0?

д) Тепер покажіть, що

\ [\ лівий\ |A_ {1}\ лівий (\ begin {масив} {c}
\ сигма\\
w
\ кінець {масив}\ праворуч)\ праворуч\ |_ {2}\ geq\ сигма^ {2} +w^ {\ прайм} w\ nonumber\]

і об'єднати це з тим, що\(\|A_{1}\|_{2}=\|A\|_{2}= \sigma\) вивести\(w = 0\), так

\ [A_ {1} =\ left (\ begin {масив} {cc}
\ сигма & 0\\
0 & B
\ end {масив}\ праворуч)\ nonumber\]

На наступній ітерації ми застосовуємо вищевказану процедуру до\(B\), і так далі. Коли ітерації закінчуються, ми маємо SVD.

[Причина того, що це лише доказ існування, а не алгоритм, полягає в тому, що він починається з виклику існування\(x\) і\(y\), але не показує, як їх обчислити. Дуже хороші алгоритми існують для обчислення SVD - див. Класика Голуба та Ван Лоана, Матричні обчислення, Johns Hopkins Press, 1989. SVD є наріжним каменем числових обчислень у безлічі додатків.]

Вправа 4.5

Припустимо\(A\),\(m \times n\) матриця розкладається у вигляді

\ [A=U\ left (\ begin {масив} {ll}
\ Сигма & 0\\
0 & 0
\ end {масив}\ праворуч) V^ {\ правий}\ nonumber\]

де\(U\) і\(V\) є унітарними матрицями, і\(\Sigma\) є оборотною\(r \times r\) матрицею (- СВД міг бути використаний для отримання такого розкладання). Тоді «Мур-Пенроуз обернений», або псевдоінверс e of\(A\), позначається\(A^{+}\), може бути визначена як\(n \times m\) матриця

\ [A^ {+} =V\ лівий (\ begin {масив} {cc}
\ сигма^ {-1} & 0\
0 & 0
\ кінець {масив}\ праворуч) U^ {\ правий}\ nonumber\]

(Ви можете викликати його в Matlab за допомогою\(pinv(A)\).)

а) Покажіть, що\(A^{+}A\) і\(AA^{+}\) симетричні, і що\(AA^{+}A=A\) і\(A^{+}AA^{+}=A^{+}\). (Ці чотири умови насправді являють собою альтернативне визначення псевдо-зворотного.)

б) Покажіть, що коли\(A\) має повний ранг стовпця тоді\(A^{+}=\left(A^{\prime} A\right)^{-1} A^{\prime}\), і що коли\(A\) має повний рядок рангу тоді\(A^{+}= A^{\prime} \left(A^{\prime} A\right)^{-1}\).

в) Покажіть, що з усіх,\(x\) що мінімізують\(\|y-A x\|_{2}\) (і їх буде багато, якщо\(A\) не має повного рангу стовпця), той з найменшою довжиною\(\|x\|_{2}\) задається\(\hat{x} = A^{+} y\)

Вправа 4.6

Всі матриці в цій задачі реальні. Припустимо

\ [Y=Q\ лівий (\ begin {масив} {l}
R\\
0
\ end {масив}\ праворуч)\ nonumber\]

з\(Q\)\(m \times m\) ортогональною матрицею і\(R\)\(n \times n\) оборотною матрицею. (Нагадаємо, що таке розкладання існує для будь-якої матриці\(A\), яка має повний ранг стовпця.) Також нехай\(Y\) буде\(m \times p\) матриця форми

\ [Y=Q\ left (\ begin {масив} {l}
Y_ {1}\\
Y_ {2}
\ кінець {масив}\ праворуч)\ nonumber\]

де розбиття у виразі for\(Y\) узгоджується з розділом для\(A\)

(а) Який вибір\(n \times p\) матриці\(\hat{X}\)\(X\) мінімізує норму Фробеніуса, або еквівалентно нормі Фробеніуса у квадраті\(Y - AX\)? Іншими словами, знайти

\[\hat{X}=\operatorname{argmin}\|Y-A X\|_{F}^{2}\nonumber\]

Також визначте значення\(\|Y-A X\|_{F}^{2}\). (Ваші відповіді повинні бути виражені в терміні матриць\(Q\)\(R\),\(Y_{1}\) і\(Y_{2}\).)

(b) Чи може ваш\(\hat{X}\) в (а) також бути записаний як\(\left(A^{\prime} A\right)^{-1} A^{\prime}Y\)? Чи можна записати так\(A^{+} Y\), де\(A^{+}\) позначає (Мур-Пенроуз) псевдо-інверс A?

(c) Тепер отримати вираз для вибору\(X\), який\(\bar{X}\) мінімізує

\[\|Y-A X\|_{F}^{2} + \|Z-B X\|_{F}^{2}\nonumber\]

де\(Z\) і\(B\) задані матриці відповідних розмірів. (Ваша відповідь може бути виражена\(A\) термінами\(B\),\(Y\), і\(Z\).)

Вправа 4.7 Структуровані сингулярні значення

Задано складну квадратну матрицю\(A\), визначте структуровану функцію сингулярного значення наступним чином.

\[\mu_\underline{\Delta}(A)=\frac{1}{\min _{\Delta \in \Delta}\left\{\sigma_{\max }(\Delta) \mid \operatorname{det}(I-\Delta A)=0\right\}} \nonumber\]

\(\underline{\Delta}\)де деякий набір матриць.

а) Якщо\(\underline{\Delta}=\{\alpha I: \alpha \in \mathbb{C}\}\), показати\(\mu_\underline{\Delta}(A)=\rho(A)\), що, де\(\rho\) спектральний радіус\(A\), визначається як:\(\rho(A)=\max _{i}\left|\lambda_{i}\right|\) і ті\(\lambda_{i}\) є власними значеннями\(A\).

б) Якщо\(\underline{\Delta}=\left\{\Delta \in \mathbb{C}^{n \times n}\right\}\), показати, що\(\mu_{\underline{\Delta}}(A)=\sigma_{\max }(A)\)

в) Якщо\(\underline{\Delta}=\left\{\operatorname{diag}\left(\alpha_{1}, \cdots, \alpha_{n}\right) \mid \alpha_{i} \in \mathbb{C}\right\}\), показати, що

\[\rho(A) \leq \mu_\underline{\Delta}(A)=\mu_\underline{\Delta}\left(D^{-1} A D\right) \leq \sigma_{\max }\left(D^{-1} A D\right)\nonumber\]

де

\[D \in\left\{\operatorname{diag}\left(d_{1}, \cdots, d_{n}\right) \mid d_{i}>0\right\} \nonumber\]

Вправа 4.8

Розглянемо ще раз структуровану функцію сингулярних значень складної квадратної матриці,\(A\) визначеної в попередній задачі. Якщо\(A\) має більшу структуру, іноді можна\(\mu_\underline{\Delta}\left(A_{ }\right)\) точно обчислити. У цій задачі, припустимо,\(A\) це матриця першого рангу, так що ми можемо записати\(A = uv^{\prime}\) де\(u\) і\(v\) є складними векторами розмірності\(n\). Обчислюйте\(\mu_\underline{\Delta}\left(A_{ }\right)\), коли

(а)\(\underline{\Delta}=\operatorname{diag}\left(\delta_{1}, \ldots, \delta_{n}\right), \quad \delta_{i} \in \mathbb{C}\).

(б)\(\underline{\Delta}=\operatorname{diag}\left(\delta_{1}, \ldots, \delta_{n}\right), \quad \delta_{i} \in \mathbb{R}\).

Щоб спростити обчислення, мінімізуйте норму Фробеніуса при визначенні\(\Delta\)\(\mu_\underline{\Delta}\left(A_{ }\right).\)