Преобразования

Матричные разложения. Спектральное разложение. Сингулярное разложение.

Полный обзор разложений

Спектральное разложение - разложение матрицы \(A\) вида \(A = VLV^{−1}\) или \(AV = VL\), где \(V\) - матрица, в столбцах которой стоят собственные векторы, \(L\) - диагональная матрица, на диагонали которой стоят собственные значения. Зачем это делать - хочется для удобства разложить матрицы на более простые объекты (аналог -- разложение числа на простые множители).\ Норма вектора:

\[\left\|x \right\| = \left(\sum _{i}\left|x_{i}\right|^{2} \right)^{\frac{1}{2}}\]

Норма матрицы:

\[\left\|A\right\| = \max_{1\le j\le n} \sum_{i=1}^{m} \left|a_{ij}\right|\]

Норма Фробениуса для матриц:

\[\left\|A\right\|_{F} = \left\|A\right\|_{2} = \sqrt{ \sum_{ij} \left|a_{ij}\right|^2} = \sqrt{Tr A^\intercal{A}}\]

Метод главных компонент - это метод выбора подпространства меньшей размерности с минимальной потерей данных. А сингулярное разложение (Singular Value Decomposition) - метод, который используется для такого выбора. У нас есть множество данных, представим их как точки в пространстве, наша задача - найти такое подпростанство, «проекция на которое» сохранит максимальный разброс точек. Потом приблизим эту «проекцию» эллипсом, в который попадут максимальное количество точек. Остальные точки воспринимаем как «шум».\ Алгоритм SVD-разложения матрицы \(A_{m×n}\):

1. Составляем матрицу \(A^\intercal{A}\) и находим её собственные значения \(\lambda_{1} ... \lambda_{n}\), находим ненулевые сингулярные числа \(\sigma_{i} = \sqrt{\lambda_{i}}\) и составляем из них диагональную матрицу \(\Sigma\).

2. Находим собственные векторы \(v_{i}, i \in (1, \cdots, n)\) , соответствующие значениям \(\lambda_{i}\), производим нормирование каждого вектора. Ставим их как столбцы в матрицу \(V\) и находим \(V^\intercal\) .

3. Строим векторы \(u_{i} = \frac{Av_{i}}{\sigma_{i}}\) и дополняем любыми векторами до ортонормированного базиса \(u_{i}, i \in (1, \cdots, m )\). Ставим их как столбцы в матрицу \(U\).

4. Записываем разложение \(A = U\Sigma V^\intercal\) .

Преобразование Фурье. Вейвлет-преобразование. Оконные функции.

Исторически задача появилась, когда надо было понять характер поведения закреплённой колеблющейся струны. Возникает проблема: как описать более сложные формы, можно ли более сложные формы представить как сумму простейших, в нашем случае - синусоидальных кривых.

Период - это длина \(T\) промежутка времени, через которое наша функция \(f(x)\) начинает принимать те же значения: \(f(x − T) = f(x) = f(x + T)\).

Частота - количество повторений в единицу времени. В нашем случае под частотой будем понимать \(\omega = \frac{2\pi}{T}\)

Фаза - это «сдвиг функции» от нулевого значения, или координата пересечения оси \(x\) с графиком функции: \(\phi = \omega t + \phi\).

Амплитуда - длина максимального смещения вдоль оси \(y\) от среднего положения.

Далее все выводы и доказательства можно посмотреть в ее отдельном файле по преобразованию Фурье.

Первое представление разложения функции \(f(x)\) в ряд Фурье:

\[f(t) = \sum\limits_{k=0}^{\infty}\Big(a_k cos(k\omega t) + b_k sin(k\omega t)\Big)\]

\[a_k = \frac{2}{T}\int\limits_0^T f(t)cos(k \omega t)dt \;\;\;\; b_k = \frac{2}{T}\int\limits_0^T f(t)sin(k \omega t)dt\]

Второе представление разложения функции \(f(x)\) в ряд Фурье(просто преобразуем некоторым образом коэффициенты из первого разложения):

\[f(t) = \sum\limits_{k=0}^{\infty} A_k cos(k \omega t - \phi_k)\]

Здесь \(A_k = \sqrt{a_k^2 + b_k^2}\) - амплитуда, \(\phi_k = arctg \frac{b_k}{a_k}\) - фаза. Множество амплитуд \(\{A_k\}\) называется спектром сигнала и показывает распределение энергии сигнала по частотам.

Это представление даёт возможность построить график зависимости амплитуды сигнала от частоты. На примере разложения мелодии по нотам частота - это ноты или те клавиши, на которые мы нажимаем, а амплитуда - сила, с которой мы нажимаем на каждую клавишу.

График амплитуды в зависимости от времени

Спектр волны

Пойдём дальше и вспомним формулу Эйлера - представление экспоненты через синус и косинус: \(e^{i \alpha} = cos \alpha + i sin\alpha\)

\[e^{ik \omega t} = cos(k \omega t) + isin(k \omega t) \;\;\; e^{−ik \omega t} = cos(k \omega t) − isin(k \omega t)\]

Третье представление разложения \(f(x)\) в ряд Фурье:

\[f(x) = \sum\limits_{-\infty}^{\infty} c_k e^{ik \omega t}\]

Всё, что мы делали ранее, относилось к периодическим функциям. Для непериодических функций логично совершить предельный переход \(T \rightarrow \infty\) или \(\omega \rightarrow 0\), тогда параметр \(k\) теряет смысл, и разумнее перейти к новой частоте \(\omega_1 = k\omega\):

\[F(w_1) = \int\limits_{-\infty}^{\infty} f(t) e^{-i w_1 t} dt\]

На практике нельзя получить сигнал на бесконечном интервале, так как нет возможности узнать, какой был сигнал до включения устройства и какой он будет в будущем. Для моделирования сигнала как в реальной жизни ограничим интервала анализа, что равносильно произведению исходного сигнала на оконную функцию. Таким образом, результатом оконного преобразования Фурье является не спектр исходного сигнала, а спектр произведения сигнала и оконной функции.

Оконная функция - это математическая функция, которая имеет нулевое значение за пределами некоторого выбранного интервала, обычно симметричная вокруг середины интервала, близкая к максимуму в середине и сужающаяся от середины.

Оконное преобразование Фурье - это разновидность преобразования Фурье, определяемая следующим образом:

\[F(t,\omega )=\int \limits_{-\infty }^{\infty }f(\tau)W(\tau -t)e^{-i\omega \tau}d\tau\]

где \(W(\tau - t)\) - некоторая оконная функция. В случае дискретного преобразования оконная функция используется аналогично:

\[F(m,\omega) = \sum\limits_{-\infty}^\infty f[n] w[n-m] e^{-i\omega n}d\tau\]

Ещё один выход для избежания проблем, возникающих при преобразовании Фурье, - вместо разложения по синусам и косинусам взять другие системы ортогональных функций, самые известные: вейвлет "Хаара" и вейвлет "Мексиканская шляпа".

Вейвлет-преобразование - это его представление в виде обобщенного ряда или интеграла Фурье по системе базисных функций. Вейвлет-преобразование переводит сигнал из временного представления в частотно-временное. Это способ преобразования функции (или сигнала) в форму, которая или делает некоторые величины исходного сигнала более поддающимися изучению, или позволяет сжать исходный набор данных.

Польза Вейвлет-преобразования заключается в том, что в заданном сигнале мы можем находить функции, похожие на вейвлеты: если при заданном масштабе и сдвига получаем большое значение вейвлета, то в заданном сигнале будет похожий участок.

В отличие от преобразования Фурье вейвлет-преобразование дает двумерную развертку одномерного процесса, при этом частота и время рассматриваются как независимые переменные. В результате появляется возможность анализировать свойства процесса одновременно во временной и частотной областях.