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

Question

Я пытаюсь реализовать SVD в C в течение последних нескольких недель, и в настоящее время я использую алгоритм 6, найденный here, и из моего понимания этот алгоритм будет работать вовремя O (n^5), потому что есть две петли (одна из петель не идет от 0 до n, я знаю, но n^5 работает как грубая граница), и внутри внутренней матрицы цикла необходимо умножить умножение, которое является n^3.

Однако, согласно this website, для матрицы n на n SVD можно вычислить в O (2n^3). Кто-нибудь знает, где я могу найти алгоритм для этой временной сложности?

Answer 1

В случае, если кто-либо ищет ответ на этот вопрос в будущем, алгоритм вычисления SVD в O (n^3), если матрица является квадратной матрицей, является методом вращения Якоби.

Для получения дополнительной информации о конкретном алгоритме вы можете посмотреть алгоритм 7 на this website.

Нотация на веб-сайте немного запутанна из-за опечаток, но на этапе определения значений d1, d2, c и č (извините, что ближе всего я мог добраться до c с шляпой на top), что они означают, что c = cos (theta), s = sin (theta), č = cos (phi) и š = sin (phi).

Вы можете рассчитать эти значения theta и phi путем исключения и замены или вы можете проверить this StackExchange post, чтобы узнать, как их вычислить.

После этого он просто следует этому алгоритму.