Определение. Сингулярное разложение (SVD) для матрицы $A$ размера $m\times n$ это представление матрицы $A$ в виде произведения трех матриц: $A=U\cdot\Sigma\cdot V^{\dagger},$ где $U$ — ортогональная матрица размера $m\times m$, $\Sigma$ — диагональная матрица размера $m\times n$ с неотрицательными элементами на диагонали (сингулярными числами матрицы $A$), $V^{\dagger}$ — транспонированная ортогональная матрица размера $n\times n$.

Для произвольной матрицы $A$ размера $m\times n$ сингулярное разложение строится следующим образом:

• Элемент нумерованного списка
• Вычислить матрицу $A^{\dagger}\cdot A$ размера $n\times n$.
• Найти собственные значения и собственные векторы матрицы $A^{\dagger}\cdot A.$ Пусть собственные значения будут $\lambda_{1},\lambda_{2},...,\lambda_{k},$ где $k=\text{min}(m,n),$ а соответствующие им собственные векторы будут $v_{1},v_{2},...,v_{k}.$
• Нормализовать каждый из векторов $v_{i}$ так, чтобы его длина была равна 1: $v_{i}'=\frac{v_{i}}{|v_{i}|},$ где $|v_{i}|$ — длина вектора $v_{i}.$
• Сформировать матрицу $V$ размера $n\times k,$ состоящую из найденных собственных векторов $v'_{1},v'_{2},...,v'_{k}$. Если $k<n,$ то дополнить базис ортонормированными векторами $v'_{k+1},v'_{k+2},...,v'_{n}$. Построить из векторов $v'_{1},v'_{2},...,v'_{n}$ матрицу $V.$ Транспонированием и сопряжением матрицы $V$ построить $V^{\dagger}$.
• Найти сингулярные числа матрицы $A$ как корни из найденных собственных значений матрицы $A^{\dagger}\cdot A$: $\sigma_{i}=\sqrt{\lambda_{i}},$ где $i=1,\ldots,k.$ Сформировать диагональную матрицу $\Sigma$ размера $m\times n$ состоящую из найденных сингулярных значений $\sigma_{1}\geqslant\sigma_{2}\geqslant...\geqslant\sigma_{k}.$ Причём, если $m<n,$ то

$$\Sigma=\left(\begin{array}{cccccc} \sigma_{1} & 0 & \cdots & 0 & \cdots & 0\\ 0 & \sigma_{2} & \cdots & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & \sigma_{m} & \cdots & 0 \end{array}\right),$$ если $m>n,$то $$\Sigma=\left(\begin{array}{cccc} \sigma_{1} & 0 & \cdots & 0\\ 0 & \sigma_{2} & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & \sigma_{n}\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & 0 \end{array}\right).$$

• Построить вектора $u_{i}=\frac{1}{\sigma_{i}}Av'_{i}$. Если $m>n,$ то дополнить базис ортонормированными векторами $u_{n+1},...,u_{m}$. Построить из векторов $u_{1},...,u_{m}$ матрицу $U.$
• Таким образом, сингулярное разложение матрицы $A$ может быть представлено в виде $A=U\cdot\Sigma\cdot V^{\dagger}.$ Матрица $U$ будет ортогональной и размера $m\times n,$ матрица $\Sigma$ будет диагональной и размера $m\times n$, а матрица $V^{\dagger}$ будет ортогональной и размера $n\times n$.

Определение. Правое полярное разложение для матрицы $A$ размера $m\times n$ это представление матрицы $A$ в виде произведения двух матриц: $A=UP,$ где $U$ — ортогональная матрица размера $m\times m$, $P$ — неотрицательно определенная матрица размера $m\times n$.

Аналогичным образом можно определить левое полярное разложение $A=P'V,$где $P'$ — неотрицательно определенная матрица размера $m\times n$, а $V$ — ортогональная матрица размера $n\times n.$

В отличие от сингулярного разложения, полярное разложение не единственно, но, если матрица $A$ квадратная и не вырождена, то полярное разложение единственно и определяется как $A=UP,$ где $U$ — ортогональная матрица размера $m\times m$, а $P$ — симметричная положительно определенная матрица того–же размера, которая может быть интерпретирована как квадратный корень из матрицы $A^{\dagger}A$.

Если уже есть сингулярное разложение $A=U\cdot\Sigma\cdot V^{\dagger},$ то полярное получается из него просто $A=U\cdot\Sigma\cdot V^{\dagger}=U\cdot P=P'\cdot V^{\dagger}.$ Если его нет, то можно найти отдельно, например для квадратных матриц:

Алгоритм нахождения левого полярного разложения.

• Составляем матрицу $AA^{*}$.
• Вычисляем $P=\sqrt{AA^{*}}$, для этого сначала
• Элемент ненумерованного списка– находим спектр $AA^{*}$ в виде $\lambda_{1},\ldots,\lambda_{m}$;
• находим ОНБ из собственных векторов, в котором $AA^{*}$ имеет диагональный вид $D$, $T$ — матрица перехода к этому базису;
• вычисляем $P=T\sqrt{D}T^{-1}$.
• ищем матрицу $V$ такую, чтобы $A=PV$. Если $\det A\neq0$, то $V=P^{-1}A.$

Алгоритм нахождения правого полярного разложения получается из алгоритма левого полярного разложения заменой $AA^{*}$ на $A^{*}A$, а $V=P^{-1}A$ на $U=AP^{-1}$.