SVD для нахождения наибольшего собственного значения матрицы 50x50 - я трачу много времени?

У меня есть программа, которая вычисляет наибольшее собственное значение из многих вещественных симметричных матриц 50x50, выполняя разложения по сингулярным числам для всех из них. SVD является узким местом в программе.

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

linear-algebra eigensystem Анна
источник

Не могли бы вы дать больше информации о ваших матрицах, например, если что-то известно об их структуре, диапазоне их собственных значений или их сходстве друг с другом?

Педро

Это ковариационная матрица (

). Тестирование показывает, что все, кроме 5 или около того, собственных значений близки к нулю, и что наибольшее собственное значение по меньшей мере на ~ 20% больше, чем второе по величине. Поскольку есть много собственных значений, близких к нулю, я полагаю, диапазон не важен? Это может быть изменено на любой диапазон. Масштаб, который я использую в настоящее время, дает диапазон от 150 до 200.

X X^{T}

$XX^T$

Анна

Кроме того, матрица не очень тесно сингулярна, поэтому проблема SVD хорошо обусловлена.

Анна

Поскольку

является симметричным и положительным (полу) определенным, вы можете использовать факторизацию Холецкого вместо SVD. Факторизация Холецкого требует гораздо меньше флопов, чем SVD, но точный метод все равно требует

флопов.

X X^{T}

$XX^T$

O (n^{3})

$O(n^3)$

Кен

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

Педро

Ответы:

В зависимости от точности, требуемой для наибольшего собственного значения, вы можете попробовать использовать Power Iteration .

Для вашего конкретного примера я бы зашел так далеко, что явно не формировал , а вычислял в каждой итерации. Вычисление потребует операций, тогда как произведение матрицы на вектор требует только $A=XX^\mathsf{T}$ $x \leftarrow X(X^\mathsf{T}x)$ $A$ $\mathcal O(n^3)$ $\mathcal O(n^2)$ .

Скорость сходимости зависит от разделения между двумя самыми большими собственными значениями, поэтому это не может быть хорошим решением во всех случаях,

Pedro
источник

Если наибольшее собственное значение на 20% больше, чем следующее, итерация мощности должна сходиться довольно быстро (все остальные собственные значения уменьшаются в 5/6 раз на каждой итерации, поэтому вы получаете одну цифру на каждые 13 итераций.

Вольфганг Бангерт,

Методы подпространства Крылова строго лучше, чем степенные, поскольку они содержат вектор из степенной итерации с тем же числом итераций.

Джек Полсон

@JackPoulson: Да, но каждая итерация обходится дороже ... Разве она того стоит для такой маленькой проблемы?

Педро

@Pedro: конечно, matvecs требуют квадратичной работы, и частное Рэлея eigensolve и последующее расширение тривиально по сравнению.

Джек Полсон

Код расхода? Поскольку @JackPoulson затронул эту проблему, Б. Парлетт и др. (1982) («Об оценке наибольшего собственного значения с помощью алгоритма Ланцоша») сравнивают силовой метод, силовой метод + ускорение Айткена и приложение Ланцоша, нацеленное на наибольшее собственное значение реального симметричный (или эрмитовский) поз. отсроченный матрица. Они приходят к выводу, что метод Ланцоша более эффективен, если требуется даже скромная точность (первого собственного значения относительно второго), и лучше избегает неправильного схождения.

hardmath

$X(X^Tx)$

Арнольд Ноймайер
источник

B = T = I

$B = T = I$

Нет; Я имел в виду стандартный алгоритм Lanczsos, но на скорую руку написал CG. Сейчас исправлено.

Арнольд Ноймайер

$A = XX^T$ $\mu$ $A - \mu I$ $A$ .

$||Ax||/||x||$ $\lambda_1$ $[0,\frac{5}{6} \lambda_1]$ $A - \frac{5}{12} \lambda_1 I$ $\frac{7}{12} \lambda_1$ $[\frac{-5}{12} \lambda_1, \frac{5}{12} \lambda_1]$

$A - \mu I$ is found to sufficient accuracy, $\lambda_1$ is estimated by adding back the shift $\mu$ that had been taken away.

Note that you need not explicitly form $A - \mu I$ because $(A - \mu I)x = X(X^Tx) - \mu x$ can still be computed with $O(n^2)$ усилия.

hardmath
источник

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

Педро

@Pedro: применение итерации со смещенной мощностью требует только оценки наибольшего собственного значения

λ_{1}

$\lambda_1$ , but as with the unshifted power method, analysis shows the rate of convergence depends on

| λ_{2} | / | λ_{1} |

$|\lambda_2|/|\lambda_1|$ (throwing in abs. values that are unnecessary for the pos. semi-definite case at hand). In turn observed rates of convergence can be used to estimate

| λ_{2} | / | λ_{1} |

$|\lambda_2|/|\lambda_1|$ , and hence the size of

λ_{2}

$\lambda_2$ relative to

λ_{1}

$\lambda_1$ if desired. I was suggesting what benefit you'd see in a case such as Anna describes in her comments below the Question.

hardmath