Ранняя история сингулярного разложения матриц

Историк численной линейной алгебры Дж. У. Стюарт (Университет Мэриленда) в 1993 году опубликовал в журнале SIAM Review (том 35, № 4, с. 551, 566) статью «О ранней истории сингулярного разложения», с шутливым посвящением «Джину Голубу на его 15-летие» (Голуб, один из создателей современных вычислительных алгоритмов для SVD, и посвящение, внутренняя шутка профессионального сообщества). Стюарт прослеживает, как без малого за 40 лет, с 1873 по 1912 год, пять математиков независимо друг от друга подходили к одной и той же конструкции и постепенно превратили её из локального учебного приёма в фундаментальный инструмент прикладной математики: Эудженио Бельтрами, Камиль Жордан, Джеймс Джозеф Сильвестр, Эрхард Шмидт и Герман Вейль.

Сингулярное разложение (SVD) представляет произвольную матрицу A в виде произведения A = UΣVᵀ, где U и V, ортогональные матрицы, а Σ, диагональная матрица неотрицательных чисел по убыванию (сингулярных значений). Стюарт называет разложение особенно ценным по четырём причинам: оно строится через ортогональные матрицы (удобно для геометрии n-мерного пространства), устойчиво к малым возмущениям, по диагонали Σ легко понять, насколько матрица близка к вырожденной, и, как следствие, даёт наилучшее приближение матрицы матрицей меньшего ранга. До 1873 года почти все классические матричные разложения возникали из работы с определителями, системами уравнений и билинейными или квадратичными формами, а не с матрицами как таковыми: свой вклад внесли Гаусс (метод исключения, впервые набросан в 1809 году, изложен в 1823-м), Коши (1829, свойства собственных чисел и векторов симметричной системы), Якоби (1846, алгоритм диагонализации симметричной матрицы, посмертная статья 1857 года о LU-разложении) и Вейерштрасс (1868, канонические формы для пар билинейных функций).

Первым разложение опубликовал итальянец Эудженио Бельтрами в 1873 году, в журнале для студентов итальянских университетов, с чисто учебной целью объяснить билинейные формы. Отправляясь от билинейной формы f(x,y) = xᵀAy, он показал, что подходящим выбором ортогональных замен переменных её можно свести к сумме σᵢξᵢηᵢ, и дал трёхшаговый алгоритм нахождения σᵢ и матриц U, V. Год спустя, независимо от Бельтрами, к тому же результату, но заметно строже и полнее, пришёл француз Камиль Жордан в статье «Mémoire sur les formes bilinéaires» («Мемуар о билинейных формах», 1874). Стюарт называет Бельтрами и Жордана «прародителями» разложения: Бельтрами, по праву первой публикации, Жордана, по полноте и изяществу изложения («в этой работе видна уверенная рука мастера: Жордан идёт от постановки задачи к решению экономно и изящно», пишет Стюарт). У Бельтрами метод работает только для невырожденных квадратных матриц с попарно различными сингулярными числами, и, по мнению Стюарта, по тексту заметно, что вырожденные случаи автор до конца не продумал. Жордан же использовал приём последовательного сведения задачи к задаче меньшего размера, позже это назовут «дефляцией»: по словам Стюарта, приём пролежал невостребованным, пока в 1917 году его не применил Иссай Шур для построения треугольной формы произвольной матрицы; вспомогательная блочная матрица вида [[0, A], [Aᵀ, 0]], возникающая в выводе Жордана, тоже стала широко используемым инструментом, во многом благодаря Виландту, а Корнелиус Ланцош в 1958 году с её помощью независимо переоткрыл само сингулярное разложение.

В 1889 году к теме, ничего не зная о работе Жордана, обратился Джеймс Джозеф Сильвестр, в сноске и двух статьях. Он предложил итеративный алгоритм постепенной диагонализации сначала квадратичной, а затем и билинейной формы бесконечной последовательностью «бесконечно малых» ортогональных замен, а также отдельное «правило» для прямого вычисления коэффициентов через миноры матрицы. Стюарт пишет об этих текстах без обиняков: «эти статьи нелегко читать: стиль тёмен, а Сильвестр изрекает истины, ничего не доказывая, и оставляет слишком много деталей читателю». Показательная деталь: заметку о своём результате Сильвестр отправил именно в Comptes Rendus, тот самый журнал, где Жордан анонсировал свой результат пятнадцатью годами ранее; судя по всему, Сильвестр не подозревал о существовании предшественника и придавал большое значение приоритету открытия. Сильвестр также не знал об алгоритме Якоби 1846 года для диагонализации квадратичных форм, его обобщение на сингулярное разложение позже сделал Когбетлианц. Даже сам Стюарт признаёт, что не берётся однозначно реконструировать замысел Сильвестра: неясно, сознательно ли тот отбрасывал члены второго порядка малости или представлял диагонализацию как результат бесконечной последовательности бесконечно малых шагов, ни одно из двух толкований не согласуется с текстом до конца.

В 1907 году сюжет переходит из линейной алгебры в интегральные уравнения, одну из главных тем математики начала XX века. Эрхард Шмидт (тот самый, чьим именем назван процесс Грама, Шмидта; ученик Гильберта) перенёс идею разложения в бесконечномерные пространства функций, разбирая интегральные уравнения с несимметричными ядрами. Но главное, Шмидт пошёл дальше простого доказательства существования разложения и доказал, что оно даёт наилучшее приближение оператора оператором ранга не выше k (по норме Фробениуса). Стюарт называет это «венцом работы Шмидта», результат, который «трудно даже сформулировать с нуля, не говоря о том, чтобы доказать», и «именно его по праву можно назвать фундаментальной теоремой сингулярного разложения». Так, подчёркивает Стюарт, Шмидт превратил разложение «из математического курьёза в важный теоретический и вычислительный инструмент». Однако три десятилетия спустя, в 1936 и 1939 годах, Карл Экарт и Гейл Янг распространили конструкцию на прямоугольные матрицы и заново открыли ту же теорему приближения, и именно за ней с тех пор закрепилось название «теорема Экарта, Янга», хотя, по словам Стюарта, называют её так часто, но ошибочно: настоящий приоритет принадлежит Шмидту, доказавшему её на тридцать лет раньше.

В 1912 году Герман Вейль дал куда более прозрачное, чем оригинал, доказательство теоремы Шмидта и по ходу дела построил теорию возмущений сингулярных значений. Его ключевой результат: если матрицу A ранга k немного исказить ошибкой E (получив Ã = A + E), то сумма квадратов последних n − k сингулярных чисел Ã не превышает квадрата нормы E, то есть по величине «хвостовых» сингулярных чисел можно судить, насколько зашумлённая матрица отличается от матрицы точного ранга k. Обобщая этот результат, Вейль показал, что сингулярные числа A и возмущённой Ã при естественном упорядочивании не могут отличаться больше, чем на спектральную норму возмущения E. Это не абстрактная деталь: именно на такой устойчивости сингулярных значений к возмущениям держится практическая, вычислительная сторона SVD, то, ради чего, по словам Стюарта, разложение стало рабочим инструментом благодаря «первопроходческим усилиям Джина Голуба» и созданным на их основе устойчивым алгоритмам: первый вычислительный алгоритм предложили Голуб и Кэхан (1965), а тот, что два следующих десятилетия оставался «рабочей лошадкой» вычислений, результат Голуба и Райнша (1970); позже Демель и Кэхан предложили ещё один, альтернативный алгоритм.

В заключительной части статьи, которую Стюарт озаглавил французским словом «Envoi» (буквально «послесловие»), он коротко намечает, что случилось с разложением после 1912 года, когда, по его словам, теория «созрела». Леон Отонн в 1913 году распространил разложение на комплексные матрицы; Экарт и Янг (1936, 1939), как уже сказано, на прямоугольные. Термин «сингулярное значение» пришёл из теории интегральных уравнений и лишь к 1937 году (у Фрэнка Смитиса) устоялся в современном смысле, до этого и ещё долго после (даже у самого Вейля в 1949-м, писавшего о «двух родах собственных чисел») для тех же чисел использовались другие названия. С разложением оказались связаны полярное разложение; выросшее из геометрических идей Жордана косинусно-синусное разложение пары ортогональных подматриц (Дэвис и Кэхан, 1970; сам Стюарт, 1977); обобщённое сингулярное разложение (Ван Лоан, 1975; в пересмотренном виде, Пейдж и Сондерс, 1981) и псевдообратная матрица Мура, Пенроуза, которая вычисляется через SVD. Фон Нейман в 1937 году связал унитарно инвариантные нормы матриц с симметричными функциями от сингулярных чисел, а Леон Мирский в 1960 году обобщил теорему приближения Шмидта на любую такую норму. В прикладной статистике та же математика лежит в основе метода главных компонент Гарольда Хотеллинга (1933) и его же канонических корреляций (1936), а также решения «проблемы Прокруста» в факторном анализе (Грин, 1952; Шёнеман, 1966).

Ключевые факты

Дж. У. Стюарт (SIAM Review, 1993, т. 35, № 4, с. 551, 566) прослеживает историю сингулярного разложения (SVD) через пять математиков, Бельтрами (1873), Жордана (1874), Сильвестра (1889), Шмидта (1907) и Вейля (1912), со статьёй, посвящённой «Джину Голубу на его 15-летие».
Бельтрами опубликовал разложение первым (1873, в студенческом журнале), но независимо работавший Жордан (1874) дал более строгий и полный вывод, включая приём «дефляции», который в 1917 году для построения треугольной формы матрицы применил Иссай Шур.
Сильвестр (1889) переоткрыл метод независимо, не зная о работе Жордана, хотя оба публиковались в одном и том же журнале, Comptes Rendus, с разницей в 15 лет; сам Стюарт называет статьи Сильвестра «нелёгкими для чтения», где автор «изрекает истины, ничего не доказывая».
Эрхард Шмидт (1907) перенёс разложение в бесконечномерные интегральные уравнения и доказал теорему о наилучшем приближении матрицы матрицей меньшего ранга, результат, который тридцать лет спустя (1936, 1939) переоткрыли Экарт и Янг, из-за чего теорему до сих пор часто (и, по Стюарту, ошибочно) называют «теоремой Экарта, Янга».
Герман Вейль (1912) дал изящное доказательство теоремы Шмидта и построил теорию возмущений сингулярных чисел, фундамент устойчивых вычислительных алгоритмов SVD (Голуб и Кэхан, 1965; Голуб и Райнш, 1970), которые легли в основу практических применений вроде метода главных компонент.

Почему это важно

Статья восстанавливает подлинную родословную одного из важнейших инструментов прикладной математики и объясняет, откуда вообще берутся «именные» теоремы, которыми пользуются, не задумываясь об авторстве. Главный сюжетный поворот: результат, который в учебниках почти повсеместно называют «теоремой Экарта, Янга» (о наилучшем приближении матрицы матрицей меньшего ранга, основа метода главных компонент, сжатия данных, рекомендательных систем, латентно-семантического анализа текстов), на самом деле доказал Эрхард Шмидт ещё в 1907 году, на тридцать лет раньше Экарта и Янга. Стюарт документально, по первоисточникам на четырёх языках, показывает, как разложение выросло из локального учебного примера у Бельтрами (1873) до фундаментального инструмента, и как по дороге растерялось и исказилось авторство.

Кому это важно

Тем, кто пользуется сингулярным разложением как чёрным ящиком, в анализе данных, машинном обучении (метод главных компонент, сжатие и понижение размерности, рекомендательные системы, латентно-семантический анализ текстов), численных методах и вычислительной технике, полезно знать, откуда взялась математика, на которой всё держится, и на чьё имя на самом деле стоит ссылаться. Историкам науки и преподавателям линейной алгебры статья даёт готовый, тщательно выверенный по первоисточникам конспект; тех же, кто интересуется историей математики без прикладного контекста, привлекает сам сюжет о потерянном и присвоенном не тем людям авторстве, это заметно и по реакции аудитории Hacker News: 115 баллов и 63 комментария меньше чем за сутки.

Как это применить

Практический вывод для тех, кто пишет о линейной алгебре или ссылается на неё в коде, статьях и презентациях, называть теорему о наилучшем приближении матрицы низкого ранга точнее: как минимум упоминать Шмидта (1907) рядом с Экартом и Янгом (1936, 1939), а в современной обобщённой форме, и Мирского (1960), распространившего её на любую унитарно инвариантную норму. Для тех, кто хочет разобраться в теме глубже, сама статья Стюарта (свободно доступный PDF) служит картой: она указывает, какой конкретно результат и в какой оригинальной статье искать (Бельтрами 1873, Жордан 1874, Сильвестр 1889, Шмидт 1907, Вейль 1912), избавляя от необходимости читать целиком тяжёлые оригиналы на французском, немецком и итальянском.

Можно ли доверять

Да, с высокой степенью уверенности: это рецензируемая статья в SIAM Review, одном из ведущих журналов по прикладной математике, написанная Дж. У. Стюартом, авторитетным специалистом по численной линейной алгебре, и опирающаяся на 66 первоисточников на английском, французском, немецком и итальянском языках, включая оригинальные статьи всех пяти героев повествования. Посвящение Джину Голубу не случайно: Голуб был одним из создателей практических вычислительных алгоритмов SVD, так что текст написан внутри профессионального сообщества, а не как популяризация со стороны. Оговорка: статье уже более 30 лет, и сам Стюарт честно отмечает места, где историческая реконструкция неоднозначна, например, не до конца ясно, что именно имел в виду Сильвестр в своих выкладках.

Риски и подводные камни

Стюарт сам предупреждает во введении: пересказ обязательно упрощает, «стараясь резюмировать всё, в итоге не скажешь ничего», и советует при необходимости обращаться к оригиналам. Термин «сингулярное значение» устоялся в современном понимании только к 1937 году: более ранние и даже некоторые более поздние тексты (вплоть до самого Вейля в 1949-м) использовали другие названия для тех же чисел, так что при чтении старых источников термины нельзя понимать буквально по сегодняшним конвенциям. Часть текстов, особенно статьи Сильвестра, написана настолько плотно и без доказательств, что даже сам Стюарт не берётся однозначно реконструировать замысел автора, то есть на некоторых участках это лучшая доступная историческая реконструкция, а не неоспоримый факт.

«Экарт и Янг (1936, 1939) распространили разложение на прямоугольные матрицы и заново открыли теорему приближения Шмидта, ту, которую часто (и ошибочно) называют теоремой Экарта, Янга.»

— Дж. У. Стюарт (G. W. Stewart), «Ранняя история сингулярного разложения» (SIAM Review, 1993)