Быстрые методы аппроксимации наивысшие 3 собственных значений и собственных векторов большой симметричной матрицы

Question

Я пишу код для вычисления Classical Multidimensional Scaling (сокращенно МДС) в очень большой n по n матрицы, n = 500,000 в моем примере.

За один шаг MDS, мне нужно вычислить самые высокие три цифры n на n матрицы. Эта матрица называется матрицей B. Мне нужны только эти три собственных вектора и собственные значения. Общие методы вычисления собственных векторов и собственных значений большой матрицы занимают много времени, и я не требую очень точного ответа, поэтому я ищу оценку собственных векторов и собственных значений.

Некоторые параметры:

1. B матрица symmetric, real и довольно dense
2. Собственное разложение B в теории всегда должны производить действительные числа.
3. Мне не нужна абсолютно точная оценка, просто быстрая. Мне нужно, чтобы он завершился через несколько часов.
4. Я пишу в Python и C++

Мой вопрос: Есть ли быстрые методы оценки трех высших собственных векторов и собственных значений такого большого B матрицы?

Прогресс: Я нашел method of approximating the highest eigenvalue of a matrix, но не знаю, могу ли я обобщить его на самые высокие три. Я также нашел this paper written in 1996, но для меня это чрезвычайно технично и трудно.

Answer 1

Г. Голубы и CF Ван заем Матричные вычисления 2-й в главе 9 состояния, Ланцош алгоритмы один выбор для этого (кроме того, что матрица в идеале должна быть редкой - это явно работает неразреженные те, а)

https://en.wikipedia.org/wiki/Lanczos_algorithm

Answer 2

Вы можете получить высокий собственный вектор B, а затем преобразовать данные в B' используя этот собственный вектор. Затем поместите первый столбец B' и получите B'', чтобы получить самый высокий собственный вектор B'': достаточно информации, чтобы составить правдоподобный второй самый старший вектор для B. А потом третий.

О скорости: вы можете случайным образом опробовать этот огромный набор данных только для набора данных N элементов. Если вы получаете только три измерения, я надеюсь, вы также можете избавиться от большинства данных, чтобы получить обзор собственных векторов. Вы можете назвать это: «избирательный опрос». Я не могу помочь вам в измерении частоты ошибок, но я попытаюсь несколько раз опробовать элементы 1k и посмотреть, будут ли результаты более или менее одинаковыми.

Теперь вы можете получить среднее количество нескольких опросов, чтобы построить «предсказание».

Answer 3

Посмотрите предложения в этой теме

Largest eigenvalues (and corresponding eigenvectors) in C++

Как предложил там вы можете использовать ARPACK пакет, который имеет интерфейс C++.