Сингулярные числа и вектора
Сингулярные числа и вектора
Сингулярными числами $\sigma_1, \dots, \sigma_r$ матрицы $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ называются
неотрицательные вещественные числа $\sigma_i = \sqrt{\lambda_i}$, где $\lambda_i$ являются ненулевые
собственные числа соответствующей матрицы Грама $\boldsymbol{K} = \boldsymbol{A}^T \boldsymbol{A}$.
Ассоциированные собственные вектора матрицы Грама $\boldsymbol{K}$ называются сингулярными векторами.
Свойства
Сингулярные числа являются косвенным обобщением собственных чисел на случай прямоугольных матриц.
Сингулярные числа сортируются в убывающую последовательность: $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_r > 0$;
Число $r$ является рангом матриц $\boldsymbol{A}$ и $\boldsymbol{K}$.
Теорема о сингулярном разложении
Матрица $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ ранга $r > 0$ может быть предствлена в виде разложения
\begin{equation*}
\boldsymbol{A} = \boldsymbol{P} \boldsymbol{\Sigma} \boldsymbol{Q}^T,
\end{equation*}
где $\boldsymbol{P} \in \mathbb{R}^{m \times r}$ и $\boldsymbol{Q} \in \mathbb{R}^{r \times n}$ – ортонормальные матрицы
($\boldsymbol{P}^T \boldsymbol{P} = \boldsymbol{E}$ и $\boldsymbol{Q}^T \boldsymbol{Q} = \boldsymbol{E}$), а
$\boldsymbol{\Sigma} \in \mathbb{R}^{r \times r}$ – диагональная матрица, на диагонали которой расположены
сингулярные числа $\sigma_1, \dots, \sigma_r$.
Столбцы матрицы $\boldsymbol{Q}$ являются сингулярными векторами матрицы $\boldsymbol{A}$.
Столбцы матрицы $\boldsymbol{P}$ являются сингулярными векторами матрицы $\boldsymbol{A}^T$, и
$i$-й столбец матрицы $\boldsymbol{P}$ может быть найден по следующей формуле:
\begin{equation*}
\boldsymbol{p}_i = \frac{1}{\sigma_i} \boldsymbol{A} \boldsymbol{q}_i, \quad i = 1, \dots, r,
\end{equation*}
где $\sigma_i$ и $\boldsymbol{q}_i$ являются $i$-м сингулярным числом/вектором.
Сингулярное разложение позволяет найти псевдообратную матрицу / обратную Мура–Пенроуза
(обобщение обратных матриц на случай прямоугольных матриц):
$$
\boldsymbol{A}^{+} = \boldsymbol{Q} \boldsymbol{\Sigma}^{-1} \boldsymbol{P}^T.
$$
Лемма
Пусть матрица $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ имеет ранг $n$.
Тогда
\begin{equation*}
\boldsymbol{A}^{+} = (\boldsymbol{A}^T \boldsymbol{A})^{-1} \boldsymbol{A}^T.
\end{equation*}
Доказательство
Метод наименьших квадратов для СЛАУ
Множество методов решения СЛАУ строится на минимизации нормы вектора невязки.
Вектор невязки
Пусть $\boldsymbol{x^*} \in \mathbb{R}^n$ является приближением к точному решению СЛАУ $\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}$.
Тогда вектором невязки называется $\boldsymbol{r} = \boldsymbol{b} - \boldsymbol{A} \boldsymbol{x^*}$.
Решение СЛАУ можно найти как решение задачи метода наименьших квадратов:
$$
\boldsymbol{x} = \argmin_{\boldsymbol{x^*}} ||\boldsymbol{r}||_2^2 = \argmin_{\boldsymbol{x^*}} ||\boldsymbol{b} - \boldsymbol{A} \boldsymbol{x^*}||_2^2.
$$
Псевдообратная матрица позволяет найти аппроксимацию решения даже для случая несовместных СЛАУ.
Теорема о решении задачи МНК для СЛАУ
Пусть дана СЛАУ $\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}$.
Тогда $\boldsymbol{x^*} = \boldsymbol{A}^+ \boldsymbol{b}$, где $\boldsymbol{A}^+$ является псевдообратной матрицей для
$\boldsymbol{A}$, является решением задачи метода наименьших квадратов для СЛАУ:
$$
\boldsymbol{x^*} = \argmin_{\boldsymbol{x}} ||\boldsymbol{b} - \boldsymbol{A} \boldsymbol{x^*}||_2^2.
$$
Доказательство
Приближение матрицей меньшего ранга
Сингулярное разложение позволяет найти оптимальную в среднеквадратичном смысле аппроксимацию матрицы $\boldsymbol{A}$ другой матрицей
меньшего ранга $\boldsymbol{A_k}$.
Теорема об оптимальном приближении матрицей меньшего ранга
Пусть матрица $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ имеет ранг $r$ и сингулярное разложение
$\boldsymbol{A} = \boldsymbol{P} \boldsymbol{\Sigma} \boldsymbol{Q}^T$.
Пусть дано число $k$, $1 \leq k \leq r$ и $\boldsymbol{\Sigma}_k$ обозначает левую верхнюю диагональную подматрицу $\boldsymbol{\Sigma}$
размерности $k \times k$, которая содержит наибольшие $k$ сингулярных чисел.
Пусть $\boldsymbol{Q}_k \in \mathbb{R}^{n \times k}$ и $\boldsymbol{P}_k \in \mathbb{R}^{m \times k}$ обозначают
матрицы, сформированные из $k$ первых столбцов $\boldsymbol{Q}$ и $\boldsymbol{P}$ соответственно.
Тогда матрица $\boldsymbol{A}_k = \boldsymbol{P}_k \boldsymbol{\Sigma}_k \boldsymbol{Q}_k^T$ имеет размерность
$m \times n$, ранг $k$ и является решением следующей задачи минимизации:
$$
\boldsymbol{A_k} = \argmin_{\boldsymbol{B}, \text{rank}(\boldsymbol{B})=k} ||\boldsymbol{A} - \boldsymbol{B}||_2.
$$
Сжатие данных
Метод главных компонент
Матрица данных $\boldsymbol{X} \in \mathbb{R}^{m \times n}$
Вектор выборочных средних показаний измерений:
$$
\bar{\boldsymbol{x}} = \frac{1}{m} \boldsymbol{e}^T \boldsymbol{X},
$$
где $\boldsymbol{e}$ обозначает единичный вектор.
Матрица центрированных данных $\boldsymbol{A}$
Рассмотрим отклонения данных от средних значений, т.е. $a_{ij} = x_{ij} - \bar{x}_{j}$.
Это дает матрицу центрированных данных $\boldsymbol{A}$:
$$
\boldsymbol{A} = \boldsymbol{X} - \boldsymbol{e} \bar{\boldsymbol{x}} = \left( \boldsymbol{E} - \frac{1}{m} \boldsymbol{e}\boldsymbol{e}^T \right) \boldsymbol{X},
$$
где $\boldsymbol{e}\boldsymbol{e}^T$ – матрица единиц.
Коэффициент $\nu$ – зависит от выбора оценки ковариации (по умолчанию $\nu = 1/(m-1)$).
Элементы этой матрицы $k_{ij}$ являюся ковариациями $i$-х и $j$-х показаний
Ковариационная матрица при этом является матрицей Грама, т.е. положительно полуопределенной (линейная зависимость между
столбцами матрицы может наблюдаться только в очень редких случаях).
Формируют ортонормальный базис, состоящий из векторов, ассоциированных с наибольшими выборочными дисперсиями.
Первая главная компонента является направлением, вдоль которого выборочная дисперсия максимальна.
Вторая главная компонента является направлением, ортогональным первой главной компоненте, вдоль которого выборочная дисперсия максимальна.
... и так далее
Формируют ортонормальный базис, в котором межкоординатные коэффициенты корреляции равны нулю.
Теорема о главных компонентах
Главными компонентнами матрицы центрированных данных $\boldsymbol{A}$ являются ее сингулярные вектора, при этом
$j$-я главная компонента соответствует $j$-му сингулярному вектору $\boldsymbol{q}_j$ и стандратному отклонению $\sqrt{\nu} \sigma_j$,
где $\sigma_j$ является $j$-м сингулярным числом.
Понижение размерности данных