⇔ левые сингулярные векторы
⇔ диагональная матрица сингулярных значений
⇔ правые сингулярные значения
- ортогональные матрицы
Разложение SVD обобщает понятие собственных значений на прямоугольные матрицы, где напрямую собственные значения не найти.
Применения: Поиск информации; веб-поиск; обработка сигналов; анализ больших данных; аппроксимация матриц низкого ранга; минимизация методом наименьших квадратов; псевдообратная матрица и т.д.
Численными методами:
1. Находим
2. Находим собственные значения и вектора у (QR-алг)
3. Находим сингулярные значения , составляем
4. Вычисляем сингулярные векторы:
V = собственные вектора
U =
Пример разложения в презентации слайд 340
47. Плотные и разреженные матрицы, способы хранения разреженных матриц.
Плотные матрицы - матрицы, где бо́льшая часть элементов ненулевая
Разреженные матрицы - матрицы, где бо́льшая часть элементов нулевая
* Нет четкого количества ненулевых элементов, что делает матрицу разрежённой
Т.к. бо́льшая часть разрежённой матрицы - нули, их можно игнорировать, тем самым сэкономив место и ускорив их последующую обработку.
Форматы хранения:
* Coordinate Format (COO)
Хранит ненулевые элементы в виде трёх массивов:
values — значения ненулевых элементов,
row_indices — номера строк,
col_indices — номера столбцов.
Плюсы: Простота добавления элементов.
Минусы: Неэффективен для арифметических операций.
* Compressed Sparse Row (CSR)
Оптимизирован для строк.
Использует три массива:
values — ненулевые элементы,
col_indices — индексы столбцов,
row_ptr — указатели на начало строк в values и col_indices.
Плюсы: Эффективен для умножения матрицы на вектор.
Минусы: Долго добавлять элементы. (Если добавить новый элемент в строку i, то все indptr[j] для j > i нужно увеличить на 1. Это O(N) операция (где N — число строк).)
* Compressed Sparse Column (CSC)
Аналог CSR, но для столбцов.
Три массива:
values — ненулевые элементы,
row_indices — индексы строк,
col_ptr — указатели на начало столбцов.
Плюсы: Эффективен для операций по столбцам.
Минусы: Долго добавлять элементы (аналогично CSR)
* Diagonal Storage (DIA)
Используется для матриц с диагональной структурой.
Хранит ненулевые элементы вдоль диагоналей.
Плюсы: Эффективен для СЛАУ с диагональным преобладанием.
Минусы: Не подходит для произвольных разреженных матриц.
* ELLPACK (ELL) (LIL в scipy)
Хранит ненулевые элементы в двумерном массиве, дополняя короткие строки.
Плюсы: Хорош для GPU-оптимизаций.
Минусы: Неэффективен при сильном разбросе длины строк.