Сложность нахождения собственного разложения * симметричной * матрицы

Это специализированная версия предыдущего вопроса: сложность нахождения собственного разложения матрицы .

Для симметричных матриц NxN известно, что времени O (N ^ 3) достаточно для вычисления собственного разложения. Вопрос в том, можем ли мы достичь субкубической сложности? Спасибо.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Лихонг Ли
источник

Это действительно нуждается в отдельном вопросе? Конечно, если бы кто-то знал ответ на этот особый случай, он бы сказал это в другом вопросе.

Уоррен Шуди

Я подчеркнул худший случай в своем вопросе, поэтому я думаю, что это справедливо ...

Лев Рейзин

Вы уверены в том, что O (N ^ 3) ограничено по времени? Смотрите мой связанный вопрос об исключении Гаусса.

Джефф

Похоже, с mathoverflow.net/questions/24287/… вы можете получить

O (n^{3})

$O(n^3)$ для приблизительного решения.

Лев Рейзин

Ответы:

На мой взгляд, этот частный случай не проще, чем общий случай. Чисто символически вы можете свести проблему нахождения разложения по сингулярным числам (SVD) к проблеме диагонализации симметричной матрицы. Можно прочитать SVD для M из собственных векторов и собственных значений M * M. Заметим, что сокращение включает только умножение матриц для вычисления M * M. Похоже, не должно быть каких-либо серьезных числовых проблем.

источник