Каковы эффективные алгоритмы для вычисления разложения по сингулярным числам (SVD)?

В статье Википедии об анализе основных компонентов говорится, что

Существуют эффективные алгоритмы для вычисления SVD без необходимости формирования матрицы , поэтому вычисление SVD теперь является стандартным способом вычисления анализа главных компонентов из матрицы данных, если только не требуется лишь несколько компонентов.$X$$X^TX$

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

Основной рабочей лошадкой для расчета SVD является алгоритм QR . Сказав , что существует множество различных алгоритмов для вычисления сингулярного разложения родового матрицы с размерностью матрицы . Отличная схема по проблеме, доступной здесь (из документации Intel MKL ), выглядит следующим образом:$M$$N$$A$

Как вы видите, в зависимости от вашего варианта использования существуют разные подходы (обычные соглашения об именах можно найти здесь ). Это связано с тем, что, например, существуют матричные формы, где сокращение домохозяев может быть более дорогим, чем ротация Гивенса (чтобы назвать два «очевидных» способа получения QR). Стандартным справочником по этому вопросу являются Матричные вычисления Голуба и Ван Лоана (я бы предложил использовать по крайней мере 3-е издание). Я также нашел Å. Бьорк в Численные методы наименьших квадратов проблем очень хороший ресурс по этому вопросу; Хотя СВД не является основной темой книги, она помогает контекстуализировать ее использование.

Если я должен дать вам один общий совет по этому вопросу , не пытайтесь писать свои собственные алгоритмы SVD, если вы уже не успешно прошли пару классов по числовой линейной алгебре и не знаете, что делаете. Я знаю, это звучит нелогично, но на самом деле, существует масса вещей, которые могут пойти не так, и вы в конечном итоге получите (в лучшем случае) неоптимальные реализации (если не ошибаюсь). Есть несколько очень хороших бесплатных наборов по этому вопросу (например, Eigen , Armadillo и Trilinos ).