Приближенный спектр большой матрицы

14

Я хочу вычислить спектр ( все собственные значения) большой разреженной матрицы (сотни тысяч строк). Это трудно.

Я готов согласиться на приближение. Существуют ли методы приближения для этого?

Хотя я надеюсь получить общий ответ на этот вопрос, я также был бы удовлетворен ответом в следующем конкретном случае. Моя матрица - нормализованный лапласиан большого графа. Собственные значения будут в диапазоне от 0 до 2 с большим количеством их сгруппированы около 1.

MRocklin
источник
Матрица разреженная или плотная?
Арон Ахмадиа
Матрица редкая. Я отредактировал вопрос, чтобы отразить это.
MRocklin
Почему вы хотите все собственные значения? Это почти всегда плохо, когда у вас есть разреженная или структурированная матрица, поэтому важно знать, как вы планируете ее использовать.
Джед Браун
Спектр графического лапласиана несет некоторую важную информацию, которую я хотел бы проверить. Я не нуждаюсь в них всех, мне просто нужно примерно знать, где они.
MRocklin

Ответы:

15

Если ваш график ненаправленный (как я подозреваю), матрица симметрична, и вы не можете сделать ничего лучше, чем алгоритм Ланцоша (с выборочной реортогонализацией, если это необходимо для устойчивости). Поскольку полный спектр состоит из 100000 чисел, я думаю, вы в основном заинтересованы в спектральной плотности.

Чтобы получить приблизительную спектральную плотность, возьмите спектр ведущего подпространства Крылова размера 100 или около того и замените его дискретную плотность сглаженным вариантом.

Ведущий спектр Крылова будет иметь почти разрешенные хорошо изолированные собственные значения (если они существуют), аппроксимирует собственные значения в конце неизолированного спектра и является несколько случайным промежуточным, с распределением, совокупная функция распределения которого напоминает распределение истинного спектра. , Он будет сходиться к нему в точной арифметике, если размерность будет расти. (Если бы ваш оператор был бесконечномерным, это все равно было бы так, и вы бы получили интеграл от истинной функции спектральной плотности по непрерывному спектру.)

Арнольд Ноймайер
источник
Разве спектр ведущих подпространств Крылова не будет 100 самыми большими собственными значениями? Я также заинтересован в распределении умеренных и наименьших собственных значений.
MRocklin
1
@MRocklin: Нет. Я дополнил свой ответ, чтобы дать больше деталей.
Арнольд Ноймайер
6

Ответ Арнольда Ноймайера обсуждается более подробно в разделе 3.2 статьи «Приближение спектральных плотностей больших матриц» Лин Лин, Юсеф Саад и Чао Янг ​​(2016) .

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

А. Ван Верде
источник
4

Если вы не против думать о вещах, которые не являются собственными значениями, а функциями, которые в некотором смысле все еще говорят вам что-то о спектре, то я думаю, что вам стоит проверить некоторые работы Марка Эмбри в Университете Райса.

Вольфганг Бангерт
источник
2

Вот еще один способ охарактеризовать спектр.

Avk=λkvkA

S(ω)=kπ1σσ2+(λkω)2=σπTr[σ2+(ωA)2]1
S(ω)=σπzT[σ2+(ωA)2]1z
z+11σω[σ2+(ω-A)2]-1Z[ω+яσ-A]-1[ω-яσ-A]-1чтобы минимизировать заполнение. Это позволяет оценитьS(ω)также для больших матриц. На практике кажется, что CG-решение не обязательно должно быть очень точным, и при вычислении среднего не требуется много векторов. Это может зависеть от проблемы.

Вышеуказанное, по-видимому, взвешивает части спектра более равномерно, чем аналогично смазанная спектральная плотность Крылова - попробуйте diag (linspace (0, 1, 150000)) - хотя, возможно, есть способ исправить это? Это несколько похоже на псевдоспектральный подход, но результат указывает (размытое) число собственных значений в окрестности точкиω, а не обратное расстояние до ближайшего собственного значения.

РЕДАКТИРОВАТЬ : Лучшая альтернатива для вычисления вышеупомянутой величины состоит в том, чтобы вычислить чебышевские моменты (с помощью стохастической оценки, подобной описанной выше), а затем восстановить спектральную плотность из них. Это не требует ни матричных инверсий, ни отдельных вычислений для каждогоω. See http://theorie2.physik.uni-greifswald.de/downloads/publications/LNP_chapter19.pdf and references therein.

pv.
источник
0

See the paper "On Sampling-based Approximate Spectral Decomposition" by Sanjiv Kumar, Mehryar Mohri & Ameet Talwalkar (ICML 2009.). It uses sampling of columns of your matrix.

Since your matrix is symmetric you should do the following:

Let A be your n*n matrix. You want to reduce the computation of the eigenvalues of an n*n matrix to the computation of the eigenvalues of an k*k matrix. First choose your value of k. Let's say you choose k=500, since you can easily compute the eigenvalues of a 500*500 matrix. Then, randomly choose k columns of the matrix A. Contruct the matrix B that keeps only these columns, and the corresponding rows.

B = A(x,x) for a random set of k indexes x

B is now a k*k matrix. Compute the eigenvalues of B, and multiply them by (n/k). You now have k values which are approximately distributed like the n eigenvalues of A. Note that you get only k values, not n, but their distribution will be correct (up to the fact that they are an approximation).

Jérôme Kunegis
источник
-1

You can always use the Gershgorin circle Theorem bounds to approximate the eigenvalues.

If the off-diagonal terms are small, the diagonal itself is a good approximation of the spectrum. Otherwise if you end up with an approximation of the eigenspace (by other methods) you could try to express the diagonal entries in this system. This will lead to a matrix with smaller off-diagonal terms and the new diagonal will be a better approximation of the spectrum.

FKaria
источник
Gerschgoring gives no aprroximations but error bounds, so is irrelevant here. Moreover, using your method on a sparse matrix would require a dense eigenvector matrix, which is impossible to store for the OPs problem.
Arnold Neumaier
As I said, the diagonal is itself an approximation of the spectrum with the error bounds given by the Gershgorin circle theorem, of course Gershgorin error bounds are not approximations. The diagonal will be a good approximation if the off-diagonal terms are small, wich I believe is the case since OP said that matrix is sparse.
FKaria
5
Most sparse matrices arising in practice have some significant off-diagonal elements in each row and column, which makes the diagonal very poor approximations (e.g., for a Laplacian of a regular graph the diagonal is constant), and the error bounds useless.
Arnold Neumaier