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

Я пишу код для вычисления классического многомерного масштабирования (сокращенно MDS) очень большого n по n матрице, n = 500,000 в моем примере.

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

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

  1. Матрица B является симметричной, настоящие и довольно плотные
  2. Теоретически разложение по собственным значениям B всегда должно давать действительные числа.
  3. Я не требую абсолютно точной оценки, только быстрой. Мне нужно, чтобы это было сделано за несколько часов.
  4. Пишу на питоне и с++

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

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


python c++ algorithm matrix eigenvalue
person Paul Terwilliger    schedule 25.11.2016    source источник
comment
Матрица такого размера потребует более терабайта памяти с учетом 64-битных записей с плавающей запятой. Забудьте о собственных векторах — даже одно умножение матрицы на вектор выглядит болезненно.   -  person David Eisenstat    schedule 30.11.2016
comment
Но нет необходимости хранить исходную матрицу! Это косвенно указано в алгоритме MDS, и вы можете использовать его для выполнения умножения матрицы на вектор без предварительного вычисления матрицы.   -  person Hans Olsson    schedule 01.12.2016
comment
Вы смотрели примерные MDS, предназначенные для больших данных? Например. см. pike.cs.ucla.edu/~weiwang/paper/CIMCV06.pdf   -  person Gene    schedule 04.12.2016

Ответы (3)


arrow_upward
8
arrow_downward

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

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

person Hans Olsson    schedule 25.11.2016

arrow_upward
2
arrow_downward

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

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

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

person robermorales    schedule 28.11.2016

arrow_upward
0
arrow_downward

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

Наибольшие собственные значения (и соответствующие собственные векторы) в C++

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

person AdityaG    schedule 01.12.2016