Сингулярное разложение обычно выводят из спектральной теоремы для симметричной матрицы A^T A

МЕНЮ


Главная страница

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



У этого классического пути есть педагогический недостаток: он уводит нас от исходного геометрического смысла отображения в алгебру квадратичных форм и характеристических многочленов. Между тем геометрическое утверждение SVD предельно наглядно и просто:

Для любого линейного отображения из R^n в R^m

существует ортонормированный базис во входном пространстве, образы векторов которого попарно ортогональны.

Возникает естественный вопрос: можно ли доказать существование такого базиса напрямую — без собственных значений, без определителей, без спектральной теоремы и без производных?

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

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

Начнём с простого случая: пусть v и w — два ортонормированных вектора в ??. После действия матрицы A они переходят в векторы Av и Aw из ??. Их образы в общем случае не обязаны быть ортогональными: скалярное произведение ?Av, Aw? может быть ненулевым.

Повернём пару (v, w) на угол ? в порождённой ею плоскости:

v_? = cos ? · v + sin ? · w

w_? = ?sin ? · v + cos ? · w

Пара (v_?, w_?) остаётся ортонормированной и задаёт ту же плоскость при любом ?.

Посмотрим, как от угла ? зависит скалярное произведение образов:

f(?) = ?A v_?, A w_??

= ?cos ? · Av + sin ? · Aw, ?sin ? · Av + cos ? · Aw?.

Раскроем скалярное произведение:

f(?) = ?cos ? sin ? · ?Av?? + cos? ? · ?Av, Aw?

sin? ? · ?Av, Aw? + sin ? cos ? · ?Aw??

= (cos? ? ? sin? ?) · ?Av, Aw?

+ sin ? cos ? · (?Aw?? ? ?Av??).

Используем формулы двойного угла:

cos? ? ? sin? ? = cos 2?,

2 sin ? cos ? = sin 2?.

Получаем:

f(?) = ? cos 2? + ? sin 2?,

где ? = ?Av, Aw?, а ? = ?(?Aw?? ? ?Av??).

Наша цель — найти угол ?, при котором f(?) = 0.

1. Если ? = 0 и ? = 0, то f(?) = 0 при любом ?. Образы уже ортогональны, поэтому поворачивать векторы не нужно: достаточно взять ? = 0.

2. Если хотя бы один коэффициент отличен от нуля, положим:

R = ?(?? + ??) > 0.

Вектор (?/R, ?/R) лежит на единичной окружности, поскольку

(?/R)? + (?/R)? = 1.

Значит, найдётся вспомогательный угол ? ? [0, 2?), для которого

sin ? = ?/R,

cos ? = ?/R.

Подставим ? = R sin ? и ? = R cos ? в формулу для f(?):

f(?) = R(sin ? · cos 2? + cos ? · sin 2?)

= R sin(2? + ?).

Теперь достаточно сделать аргумент синуса равным нулю:

2.* + ? = 0,

откуда ?* = ??/2.

При таком угле образы повернутых векторов ортогональны:

A v_?*, A w_?*? = 0.

Итак, решение есть всегда: если ? = ? = 0, берём ? = 0; в остальных случаях подходит ?* = ??/2. Это работает и тогда, когда один или оба образа нулевые.

На первый взгляд, задача решена: раз любую пару векторов можно ортогонализовать, будем обрабатывать пары по очереди.

Возьмём пару (v?, v?) и повернём её так, чтобы ?Av?, Av?? = 0. Затем возьмём (v?, v?) и повернём эту пару, добившись ?Av?, Av?? = 0.

Но здесь возникает классическая ловушка линейной алгебры. Поворачивая пару (v?, v?), мы заменяем v? линейной комбинацией:

v?? = cos ? · v? + sin ? · v?.

Что станет с уже исправленным скалярным произведением первых двух образов?

Av?, Av???

= cos ? · ?Av?, Av?? + sin ? · ?Av?, Av??

= sin ? · ?Av?, Av??,

поскольку ?Av?, Av?? = 0.

Если Av? не ортогонален Av? и sin ? ? 0, новое скалярное произведение снова станет ненулевым. Исправляя одну связь, мы можем нарушить соседнюю. Попарный перебор рискует превратиться в бесконечную погоню за ортогональностью.

Что же делать?

Мера неортогональности и тождество сохранения

Вместо того чтобы исправлять пары по одной, будем оценивать весь базис сразу. Для любого ортонормированного базиса V = (v?, …, v?) пространства ?? определим функционал, который измеряет суммарную неортогональность образов:

(V) = ??? ? i < j ? n? ?Av?, Av???.

У величины ?(V) есть три важных свойства:

• ?(V) ? 0, потому что это сумма квадратов вещественных чисел.

• ?(V) = 0 тогда и только тогда, когда ?Av?, Av?? = 0 для всех пар i < j. Именно это условие нам нужно для построения SVD.

• Суммируем только по парам i < j, поэтому каждая неупорядоченная пара учитывается ровно один раз.

Теперь выберем пару индексов (i, j) и повернём только два соответствующих вектора на угол ?, оставив остальные n ? 2 вектора без изменений. Как изменится ?(V)?

Разобьём слагаемые в сумме на три группы:

1. Пара (i, j). Её вклад равен ?Av?, Av???.

2. Пары, в которые не входят ни i, ни j. Их векторы не меняются, поэтому и скалярные произведения остаются прежними.

3. Пары, связывающие поворачиваемые векторы с третьим вектором. Для каждого индекса k ? i, j есть два таких слагаемых:

Av?, Av??? + ?Av?, Av???.

Для краткости обозначим:

a? = ?Av?, Av??,

b? = ?Av?, Av??,

c = cos ?,?s = sin ?.

После поворота векторы примут вид:

v?? = c · v? + s · v?,

v?? = ?s · v? + c · v?.

По линейности новые скалярные произведения с неизменным вектором Av? равны:

Av??, Av?? = c a? + s b?,

Av??, Av?? = ?s a? + c b?.

Достижение минимума: переход к пределу

Итак, функционал ?(V) неотрицателен: ?(V) ? 0.

Множество всех ортонормированных базисов в ?? непусто: например, в него входит стандартный базис. Поэтому множество значений ?(V) тоже непусто и ограничено снизу нулём. Значит, у него есть точная нижняя грань — инфимум:

= inf_V ?(V) ? 0.

Теперь нужно показать, что ? — не просто абстрактная нижняя грань, а значение функционала на некотором ортонормированном базисе V*:

(V*) = ?.

В курсе анализа здесь можно было бы сослаться на компактность ортогональной группы O(n), непрерывность функции и теорему Вейерштрасса. Но мы не будем прятать суть за топологическими терминами, а разберём этот шаг явно — через деление отрезков пополам, как в доказательстве теоремы Больцано—Вейерштрасса.

Строгое доказательство достижения минимума

По определению инфимума для каждого k = 1, 2, … можно выбрать ортонормированный базис

= (v????, …, v????),

для которого

?(??) < ? + 1/k.

Каждый вектор v???? имеет единичную длину в ??, поэтому каждая его координата лежит в отрезке [?1, 1]. Весь базис задаётся n ? n = n? вещественными числами.

Рассмотрим первую координату первого вектора. При изменении k она образует последовательность чисел из [?1, 1]. Разделим этот отрезок пополам: хотя бы в одной половине окажется бесконечно много членов последовательности.

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

Затем проделаем то же самое для второй координаты, каждый раз уточняя уже выбранную подпоследовательность. Всего координат n?, поэтому после конечного числа шагов получим одну подпоследовательность индексов k?, вдоль которой сходятся координаты всех векторов:

v????? ? v?* для каждого i = 1, …, n.

Проверим, что предельные векторы v?*, …, v?* образуют ортонормированный базис.

Скалярное произведение — конечная сумма произведений координат, поэтому при предельном переходе оно сохраняется:

v?*, v?*?

= lim??? ?v?????, v??????

= lim??? ???

= ???.

Здесь ??? = 1, если i = j, и ??? = 0, если i ? j. Значит, предельные векторы ортонормированы. А любые n ортонормированных векторов в ?? автоматически образуют базис.

Функционал ? — многочлен степени не выше четырёх от координат базисных векторов. Поэтому предельный переход совместим с его вычислением:

(V*) = lim??? ?(V??) = ?.

Итак, минимум действительно достигается: существует ортонормированный базис V* = (v?, …, v?), для которого ?(V*) = ?.

Пока мы не утверждаем, что ? = 0. Мы доказали лишь, что ни на каком другом базисе значение ? не может быть строго меньше ?.

Почему минимум не может быть положительным

Предположим, что минимум положителен: ? > 0.

Поскольку ?(V*) = ?, сумма квадратов в определении функционала положительна. Значит, хотя бы одно слагаемое в ней ненулевое. Следовательно, найдутся индексы i < j, для которых

= ?Av?, Av?? ? 0.

Применим к паре (v?, v?) двумерную лемму. Выберем угол ?* = ??/2, при котором образы повёрнутых векторов ортогональны:

Av??, Av??? = 0.

Составим новый базис V?: заменим в V* векторы v? и v? на повёрнутые v?? и v??, а остальные n ? 2 векторов оставим без изменений. Новый базис по-прежнему ортонормирован.

Как изменится функционал ?(V?)?

1. Вклады пар, не содержащих i и j, не изменятся.

2. Для каждого k ? i, j сумма вкладов двух пар с вектором v? сохранится — по доказанному ранее тождеству:

Av??, Av??? + ?Av??, Av???

= ?Av?, Av??? + ?Av?, Av???.

3. Вклад пары (i, j) уменьшится с ?? до нуля.

Значит, суммарная неортогональность нового базиса равна:

(V?) = ?(V*) ? ?? = ? ? ??.

Так как ? ? 0, получаем ?(V?) < ?.

Но ? — минимальное значение функционала среди всех ортонормированных базисов. Мы построили базис, на котором значение ещё меньше, и получили противоречие. Значит, предположение ? > 0 неверно.

Итак, ? = 0.

Минимум достигается на базисе V*, поэтому

(V*) = ??? ? i < j ? n? ?Av?, Av??? = 0.

Все слагаемые — неотрицательные числа. Значит, каждое из них равно нулю:

Av?, Av?? = 0 для всех 1 ? i < j ? n.

Таким образом, образы векторов базиса V* попарно ортогональны.

Сборка прямоугольного SVD

Теперь соберём итоговые матрицы для матрицы A размера m ? n.

Пусть V* = (v?, …, v?) — найденный ортонормированный базис ??, образы которого попарно ортогональны. Некоторые образы могут быть нулевыми, например, если матрица вырождена или n > m.

1. Упорядочим векторы базиса так, чтобы длины их образов не возрастали:

Av?? ? ?Av?? ? … ? ?Av?? > 0 = ?Av???? = … = ?Av??.

Число ненулевых образов r совпадает с размерностью im A, то есть с рангом матрицы:

r = rank A ? min(m, n).

Если A = 0, то r = 0 и все образы нулевые. А если n = 1, сумма ? изначально не содержит слагаемых, поэтому сразу равна нулю.

2. Сингулярные числа

Для каждого i = 1, …, r положим:

= ?Av?? > 0.

3. Базис выходного пространства

Определим первые r векторов в ??, нормировав образы:

u? = Av? / ??,?1 ? i ? r.

Поскольку образы Av? попарно ортогональны, векторы u?, …, u? образуют ортонормированную систему в ??. Дополним её до полного ортонормированного базиса (u?, …, u?), например, процедурой Грама—Шмидта.

Если n > m, векторы u? с индексами i > m не строим: выходное пространство имеет размерность m.

4. Матричная запись

Запишем базисные векторы столбцами матриц:

V = (v? v? … v?) ? ????,

U = (u? u? … u?) ? ????.

Обе матрицы составлены из ортонормированных базисов, поэтому они ортогональны:

V?V = I?,?U?U = I?.

Их определитель может быть равен ?1, поэтому матрицы могут задавать отражение. Требования быть только вращениями нет.

Теперь определим матрицу ? размера m ? n: на диагональных позициях (i, i) при 1 ? i ? r поставим числа ??, а все остальные элементы сделаем равными нулю.

Проверим произведение AV: его i-й столбец — это Av?.

Если i ? r, то Av? = ??u?. Если i > r, то Av? = 0. Именно такие столбцы получаются при умножении U?. Значит,

AV = U?.

Умножим обе части справа на V?. Поскольку VV? = I?, получим:

A = U?V?.

Сингулярное разложение построено.

8. Исторический контекст и связь с вычислениями

Идея использовать сумму квадратов неортогональности связана с классическим методом вращений Якоби, который применяют для диагонализации симметричных матриц.

В 1981 году математик Герберт Уилф (Herbert S. Wilf) опубликовал короткую двухстраничную заметку. В ней он предложил доказывать спектральную теорему для симметричных матриц через минимум суммы квадратов внедиагональных элементов.

Связь этого доказательства с подходом Уилфа видна, если рассмотреть матрицу Грама векторов (Av?, …, Av?):

G = V?(A?A)V.

Её элементы — это скалярные произведения:

g?? = ?Av?, Av??.

Сумма квадратов всех внедиагональных элементов G равна:

Od(G) = ??? ? ?? g???

= 2 · ??? ? i < j ? n? ?Av?, Av???

= 2?(V).

Уилф минимизировал сумму квадратов внедиагональных элементов Od(G) для произвольной симметричной матрицы. Мы применили ту же идею напрямую к исходному отображению A: не стали строить матрицу A?A и опираться на спектральную теорию.

С этим подходом связан практический численный алгоритм — односторонний метод Якоби для SVD (one-sided Jacobi SVD). В нём последовательно ортогонализуют пары столбцов матрицы AV, накапливая повороты в матрице V. На практике вычисления останавливают, когда скалярные произведения столбцов становятся достаточно малы по сравнению с их нормами.

Само доказательство через минимум не устанавливает сходимость произвольного порядка поворотов. Продуманная реализация метода может точно вычислять малые сингулярные числа, но качество результата зависит и от матрицы, и от реализации.

Например, документация LAPACK для DGESVJ отдельно оговаривает условия точности и критерий остановки [3].

Схема доказательства в одном предложении

Существует базис V*, на котором достигается минимум ? ? при повороте пары векторов сумма квадратов её вкладов с третьими векторами сохраняется ? если предположить, что ? > 0, поворот уменьшит ? на ?? ? получаем противоречие, значит, ? = 0 ? образы Av? попарно ортогональны ? нормируем ненулевые образы, дополняем их до базиса и получаем A = U?V?.

Источники

1. Herbert S. Wilf. An Algorithm-Inspired Proof of the Spectral Theorem in E?. The American Mathematical Monthly, vol. 88, no. 1 (1981), pp. 49–50. PDF на странице автора:

https://www2.math.upenn.edu/~wilf/website/Spectral theorem.pdf

2. Robert van de Geijn, Margaret Myers. Advanced Linear Algebra: Foundations to Frontiers, §11.3.3, “Jacobi’s method for computing the Singular Value Decomposition”. Материалы курса:

https://www.cs.utexas.edu/~flame/laff/alaff/chapter11-one-sided-Jacobi-method.html

3. LAPACK. Документация DGESVJ: односторонний метод Якоби, условия относительной точности и критерий остановки. Описание процедуры:

https://www.netlib.org/lapack/explore-html/d9/deb/group__gesvj_ga7aec05d2a1523bbeee77ece21b12187c.html


Телеграм: t.me/ainewsline

Источник: www.netlib.org

Комментарии: