Сингулярное разложение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 2 участников)
Строка 4: Строка 4:
 
|author=Сингулярное разложение
 
|author=Сингулярное разложение
 
|statement=
 
|statement=
У любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение на матрицы <tex> U, \Sigma, V^T </tex>: <tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex>.<br/>
+
У любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение на матрицы <tex> U, \Sigma, V^T </tex>: <tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex>.
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.
+
При этом, матрицы <tex>U_{n \times n}</tex> и <tex>V_{m \times m}</tex> являются ортогональными, а матрица <tex>\Sigma_{n \times m} </tex> {{---}} диагональной.
}}
 
{{Определение
 
|definition=
 
'''SVD''' (англ. ''Singular Value Decomposition'') {{---}} у любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение на матрицы <tex> U, \Sigma, V^T </tex>: <tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex>.<br/>
 
 
}}
 
}}
 
  
 
== Свойства ==
 
== Свойства ==
  
Пусть <tex> F </tex> — <tex> l \times n </tex> матрица. Тогда <tex> F </tex> можно представить в следующем виде:
+
Пусть дана матрица <tex> F_{n \times m} </tex>. Тогда <tex> F </tex> можно представить в следующем виде:
  
<tex> F = V D U^T </tex>.
+
<tex> F_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex>.
  
 
Основные свойства сингулярного разложения:
 
Основные свойства сингулярного разложения:
  
* <tex> l \times n </tex>-матрица <tex> V = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>, <br> столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
+
* <tex> n \times n </tex>-матрица <tex> U = (v_1, \dots, v_n) </tex> ортогональна, <tex> V^T V = I_n </tex>,столбцы <tex> v_j </tex> — собственные векторы матрицы <tex> F F^T </tex>;
* <tex> n \times n </tex>-матрица <tex> U = (u_1, \dots, u_n) </tex> ортогональна, <tex> U^T U = I_n </tex>, <br> столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
+
* <tex> m \times m </tex>-матрица <tex> V = (u_1, \dots, u_m) </tex> ортогональна, <tex> U^T U = I_m </tex>,столбцы <tex> u_j </tex> — собственные векторы матриц <tex> F^T F </tex>;
* <tex> n \times n </tex>-матрица <tex> D </tex> диагональна, <tex> D = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <br> <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <br> <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.
+
* <tex> n \times m </tex>-матрица <tex> \Sigma_{n \times m}  </tex> {{---}} диагональная, <tex> \Sigma_{n \times m} = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) </tex>, <tex> \lambda_j \geq 0 </tex> — собственные значения матриц <tex> F^T F </tex> и <tex> F F^T </tex>, <br> <tex> \sqrt{ \lambda_j } </tex> — сингулярные числа матрицы <tex> F </tex>.
 +
 
 +
 
 +
Матрицы <tex> U, V </tex> ортогональные, <tex> \Sigma </tex> {{---}} диагональная:
 +
<tex> UU^T = I_n</tex>,<tex>VV^T = I_m</tex>, <tex> \Sigma = diag(\lambda_1,\dots,\lambda_{min(n, m)})</tex>, <tex>\lambda_1 \geq \dots \geq \lambda_{min(n, m)} \geq 0 </tex> .
 +
 
 +
=== Усеченное разложение ===
 +
Усеченное разложение  {{---}} когда из лямбд, остаются только первые <tex> d </tex> чисел, а остальные полагаются равными нулю.
 +
 
 +
<tex> \lambda_{d+1},\dots,\lambda_{min(n,m)} = 0 </tex>
 +
 
 +
Значит у матриц <tex> U </tex> и <tex> V </tex> остаются только первые <tex> d </tex> столбцов, а матрица <tex> \Sigma </tex> становится квадратной размером <tex> d \times d </tex>.
 +
 
 +
<tex> A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} </tex>.
 +
 
 +
Полученная матрица <tex> A'</tex> хорошо приближает исходную матрицу <tex> A</tex>. Более того, является наилучшим низкоранговым приближением с точки зрения средне-квадратичного отклонения.

Текущая версия на 19:40, 4 сентября 2022

Сингулярное разложение (англ. Singular Value Decomposition) — декомпозиция вещественной матрицы с целью ее приведения к каноническому виду.

Теорема (Сингулярное разложение):
У любой матрицы [math] A [/math] размера [math] n \times m [/math] существует разложение на матрицы [math] U, \Sigma, V^T [/math]: [math] A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} [/math]. При этом, матрицы [math]U_{n \times n}[/math] и [math]V_{m \times m}[/math] являются ортогональными, а матрица [math]\Sigma_{n \times m} [/math] — диагональной.

Свойства

Пусть дана матрица [math] F_{n \times m} [/math]. Тогда [math] F [/math] можно представить в следующем виде:

[math] F_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} [/math].

Основные свойства сингулярного разложения:

  • [math] n \times n [/math]-матрица [math] U = (v_1, \dots, v_n) [/math] ортогональна, [math] V^T V = I_n [/math],столбцы [math] v_j [/math] — собственные векторы матрицы [math] F F^T [/math];
  • [math] m \times m [/math]-матрица [math] V = (u_1, \dots, u_m) [/math] ортогональна, [math] U^T U = I_m [/math],столбцы [math] u_j [/math] — собственные векторы матриц [math] F^T F [/math];
  • [math] n \times m [/math]-матрица [math] \Sigma_{n \times m} [/math] — диагональная, [math] \Sigma_{n \times m} = diag(\sqrt{\lambda_1}, \dots, \sqrt{\lambda_n}) [/math], [math] \lambda_j \geq 0 [/math] — собственные значения матриц [math] F^T F [/math] и [math] F F^T [/math],
    [math] \sqrt{ \lambda_j } [/math] — сингулярные числа матрицы [math] F [/math].


Матрицы [math] U, V [/math] ортогональные, [math] \Sigma [/math] — диагональная: [math] UU^T = I_n[/math],[math]VV^T = I_m[/math], [math] \Sigma = diag(\lambda_1,\dots,\lambda_{min(n, m)})[/math], [math]\lambda_1 \geq \dots \geq \lambda_{min(n, m)} \geq 0 [/math] .

Усеченное разложение

Усеченное разложение — когда из лямбд, остаются только первые [math] d [/math] чисел, а остальные полагаются равными нулю.

[math] \lambda_{d+1},\dots,\lambda_{min(n,m)} = 0 [/math]

Значит у матриц [math] U [/math] и [math] V [/math] остаются только первые [math] d [/math] столбцов, а матрица [math] \Sigma [/math] становится квадратной размером [math] d \times d [/math].

[math] A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} [/math].

Полученная матрица [math] A'[/math] хорошо приближает исходную матрицу [math] A[/math]. Более того, является наилучшим низкоранговым приближением с точки зрения средне-квадратичного отклонения.