5.3: Пертурабції, виміряні в нормі Фробенія
- Page ID
- 33329
Зараз ми продемонструємо, що для випадків мультиплікативного та адитивного збурень, коли ми мінімізували індуковану 2-норму, ми також мінімізували норму Фробеніуса.
Нехай\(A \in C^{m \times n}\), і нехай\(rank(A) = r\).
\[\|A\|_{F} \triangleq\left(\sum_{j=1}^{n} \sum_{i=1}^{m}\left|a_{i j}\right|^{2}\right)^{\frac{1}{2}} \ \tag{5.8}\]
\[=\left(\operatorname{trace}\left(A^{\prime} A\right)\right)^{\frac{1}{2}} \ \tag{5.9}\]
\[=(\Sigma_{i=1}^{r} \sigma_{i}^{2})^{\frac{1}{2}} (\text{the trace of a matrix is the sum of its eigenvalues}) \ \tag{5.10}\]
\[\geq \sigma_{1}(A) \ \tag{5.11}\]
Тому,
\[\|A\|_{F} \geq\|A\|_{2} \ \tag{5.12}\]
що є корисною нерівністю.
В обох задачах збурень, які ми розглядали раніше, ми знайшли рішення рангу, або діаду, для\(\Delta\):
\[\Delta=\alpha u v^{\prime} \ \tag{5.13}\]
де\(\alpha \in \mathbb{C}\)\(u \in \mathbb{C}^{n}\),\(v \in \mathbb{C}^{n}\) такий що\(\|u\|_{2}=\|v\|_{2}=1\). Легко показати, що норма Фробеніуса і індукована 2-норма рівні для матриць рангу одного виду в Рівнянні (5.13). З цього випливає,\(\Delta\) що мінімізує індуковану 2-норму також мінімізує норму Фробеніуса, для розглянутих нами адитивних і мультиплікативних випадків збурень. Однак загалом мінімізація індукованої 2-норми матриці не означає, що норма Фробеніуса зведена до мінімуму (або навпаки.)
Приклад 5.1
Цей приклад покликаний проілюструвати використання декомпозиції сингулярних значень та норм Фробеніуса у розв'язанні задачі мінімальної відстані.
Рішення
Припустимо\(A \in \mathbb{C}^{n \times n}\), у нас є матриця, і ми зацікавлені в пошуку найближчої матриці до\(A\) виду,\(cW\) де\(c\) є комплексне число і\(W\) є унітарною матрицею. Відстань вимірюється нормою Фробеніуса. Цю проблему можна сформулювати як
\[\min _{c \in \mathbb{C}, W \in \mathbb{C}^{n \times n}}\|A-c W\|_{F}\nonumber\]
де\(W^{\prime}W = I\). Ми можемо написати
\ [\ почати {вирівняний}
\ |A-C W\ |_ {F} ^ {2} &=\ ім'я оператора {Tr}\ ліворуч ((A-c W) ^ {\ prime} (A-c W)\ праворуч)\\
&=\ ім'я оператора {Tr}\ ліворуч (A^ {\ правий} A\ правий) -c ^ {\ правий}\ ім'я оператора {Tr}\ left (W^ {\ правий} ^ {\ prime} A\ праворуч) -c\ ім'я оператора {Tr}\ ліворуч (A^ {\ prime} W\ праворуч) +|c | ^ {2}\ ім'я оператора {Tr}\ left (W^ {\\ простий} W\ правий)
\ кінець {вирівняний}\ nonumber\]
Зауважте, що\(\operatorname{Tr}(W^{\prime}W) = \operatorname{Tr}(I) = n\). Тому у нас є
\[\|A-c W\|_{F}^{2}=\|A\|_{F}^{2}-2 \operatorname{Re}\left(c^{\prime} \operatorname{Tr}\left(W^{\prime} A\right)\right)+n|c|^{2} \ \tag{5.14}\]
і приймаючи
\[c=\frac{1}{n} \operatorname{Tr}\left(W^{\prime} A\right)\nonumber\]
права частина Рівняння (5.14) буде зведена до мінімуму. Тому ми маємо це
\[\|A-c W\|_{F}^{2} \geq\|A\|_{F}^{2}-\frac{1}{n}\left|\operatorname{Tr}\left(W^{\prime} A\right)\right|^{2}\nonumber\]
Тепер ми повинні мінімізувати праву сторону щодо\(W\), що еквівалентно максимізації\(\left|\operatorname{Tr}\left(W^{\prime} A\right)\right|\). Для цього ми використовуємо декомпозицію сингулярних значень\(A\) as\(U \Sigma V^{\prime}\), що дає
\ [\ почати {вирівняний}
\ ліворуч |\ ім'я оператора {Tr}\ ліворуч (W^ {\ правий} A\ правий)\ праворуч | ^ {2} &=\ ліворуч |\ ім'я оператора {Tr}\ ліворуч (W^ {\ prime} U\ Sigma V^ {\ прайм}\ праворуч | ^ {2}\
&=\ ліворуч |\ ім'я оператора {Tr}\ ліворуч (V^ {\ прайм} W^ {\ прайм} U\ сигма\ праворуч)\ праворуч |^ {2}
\ кінець {вирівняний}\ номер\]
Матриця\(Z = V^{\prime} W^{\prime} U\) задовольняє
\ [\ почати {вирівняний}
Z Z ^ {\ прайм} &=V^ {\ прайм} W^ {\ прайм} U ^ {\ прайм} W V\\
&= I
\ кінець {вирівняний}\ nonumber\]
Тому,
\[|\operatorname{Tr}(Z \Sigma)|^{2}=\left|\sum_{i=1}^{n} \sigma_{i} z_{i i}\right|^{2} \leq\left(\sum_{i=1}^{n} \sigma_{i}\right)^{2}\nonumber\]
означає, що
\[\min _{c, W}\|A-c W\|_{F}^{2} \geq\|A\|_{F}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n} \sigma_{i}\right)^{2} \ \tag{5.15}\]
Для завершення цього прикладу ми покажемо, що нижня межа в Рівнянні (5.15) насправді може бути досягнута за допомогою конкретного вибору\(W\). Зауважте, що
\[\operatorname{Tr}\left(W^{\prime} U \Sigma V^{\prime}\right)=\operatorname{Tr}\left(W^{\prime} U V^{\prime} \Sigma\right)\nonumber\]
і дозволяючи\(W^{\prime}= V U^{\prime}\) нам отримати
\[\operatorname{Tr}\left(W^{\prime} A\right)=\operatorname{Tr}(\Sigma)=\sum_{i=1}^{n} \sigma_{i}\nonumber\]
і
\[c=\frac{1}{n} \sum_{i=1}^{n} \sigma_{i}\nonumber\]
Склавши всі шматки воєдино, отримуємо, що
\[\min _{c, W}\|A-c W\|_{F}^{2}=\sum_{i=1}^{n} \sigma_{i}^{2}-\frac{1}{n}\left(\sum_{i=1}^{n} \sigma_{i}^{2}\right)^{2}\nonumber\]
і мінімізація унітарної матриці задається
\[c W=\frac{1}{n}\left(\sum_{i=1}^{n} \sigma_{i}\right) U V^{\prime}\nonumber\]
Зрозуміло також, що для того, щоб матриця була точно представлена як комплексна кратна унітарної матриці, всі її сингулярні значення повинні бути рівними.