Низкоранговое приближение и псевдообратная

Матрица как сумма рангов-один

Перепишем SVD не как произведение трёх матриц, а как сумму:

$$A = \sum_{i=1}^{r} \htmlData{k=sig}{\sigma_i}\, \htmlData{k=outer}{\mathbf{u}_i \mathbf{v}_i^\top}$$

Каждое слагаемое — внешнее произведение, матрица ранга один, взятая с весом $\sigma_i$. Поскольку сингулярные значения упорядочены по убыванию, слагаемые идут от самого важного к самому незначительному.

Отбросим хвост, оставив первые $k$:

$A_k = \sum_{i=1}^{k} \sigma_i \mathbf{u}_i \mathbf{v}_i^\top$

Теорема Эккарта–Янга

Среди всех матриц ранга не выше $k$ матрица $A_k$ ближе всего к $A$ — и в норме Фробениуса, и в операторной. Ошибка равна в точности отброшенному хвосту:

$\|A - A_k\|_F^2 = \sum_{i>k} \sigma_i^2, \qquad \|A - A_k\|_2 = \sigma_{k+1}$

Это сильное утверждение. Не «хорошее приближение», а оптимальное: никакой другой алгоритм, никакая хитрая конструкция ранга $k$ не подберётся ближе. Доказательство мы пропускаем — важно уметь пользоваться формулировкой.

Потяните ранг и посмотрите на ошибку и на счётчик хранимых чисел. Обратите внимание, как быстро спадает спектр у гладких картинок и как медленно — у шума:

гладкаяградиентшахматнаяшум

исходная

приближение · k = 1

ранг k

1

спектр сингулярных значений

ошибка по Фробениусу

2.695

хранимых чисел

33 / 256

Шахматная картинка стоит отдельного взгляда: она выглядит самой «сложной», а ранг у неё равен единице. Ранг измеряет не изменчивость, а число независимых направлений.

Экономия

Матрица $m \times n$ — это $mn$ чисел. Её ранг-$k$ приближение хранится как $k$ столбцов $U$, $k$ столбцов $V$ и $k$ чисел:

$k(m + n + 1) \ \text{против}\ mn$

При $m = n = 1000$ и $k = 10$ это 20 тысяч чисел против миллиона — в пятьдесят раз меньше. Здесь же и ответ на вопрос, почему LoRA работает: поправка к матрице весов ищется в виде $BA$ с маленьким внутренним размером, то есть низкоранговой. Обучаемых параметров становится $k(m+n)$ вместо $mn$, и это ровно та же арифметика.

Псевдообратная матрица

Что делать, если $A$ необратима, а решить $A\mathbf{x} = \mathbf{b}$ надо? Псевдообратная (Мура–Пенроуза) определяется через SVD:

$A^{+} = V\Sigma^{+}U^\top$

где $\Sigma^{+}$ получается из $\Sigma$ обращением ненулевых элементов: $\sigma_i \mapsto 1/\sigma_i$, а нули остаются нулями. Последнее и есть весь фокус — деления на ноль не происходит, соответствующие направления просто игнорируются.

Что даёт $\mathbf{x} = A^{+}\mathbf{b}$:

• если решение существует и единственно — это оно;
• если решений много — из них выбирается с наименьшей нормой;
• если решений нет — выдаётся $\mathbf{x}$, минимизирующая $\|A\mathbf{x} - \mathbf{b}\|$, то есть решение задачи наименьших квадратов.

Одна операция закрывает все три случая из урока про ранг. Именно поэтому lstsq есть в каждой библиотеке, а inv использовать почти никогда не нужно.

Отсекать малые сингулярные значения при построении $\Sigma^{+}$ — стандартная практика (rcond в numpy). Причина в числе обусловленности: $1/\sigma$ при крошечном $\sigma$ усиливает шум до бессмыслицы. Приближение с отсечением честнее «точного» ответа, состоящего из шума.

След и определитель — рабочий минимум

Две скалярные характеристики, которые понадобятся дальше.

След — сумма диагональных элементов, и она же сумма собственных значений. Главное свойство:

$\operatorname{tr}(AB) = \operatorname{tr}(BA)$

Отсюда цикличность: $\operatorname{tr}(ABC) = \operatorname{tr}(CAB)$. Этим приёмом переставляют множители в выводах градиентов по матрицам — весь блок 2 будет им пользоваться. Ещё удобная запись: $\|A\|_F^2 = \operatorname{tr}(A^\top A) = \sum_i \sigma_i^2$.

Определитель — коэффициент изменения объёма и произведение собственных значений. Через SVD: $|\det A| = \prod_i \sigma_i$. Отрицательный определитель означает смену ориентации. Больше про определители в этом плане не нужно — миноры, правило Крамера и теория перестановок сознательно пропущены.