python — Быстрые методы аппроксимации трех старших собственных значений и собственных векторов большой симметричной матрицы
Я пишу код для вычисления Классическое многомерное масштабирование (сокращенно MDS) очень большого n от n матрица, n = 500,000 в моем примере.
В одном шаге MDS мне нужно вычислить три старших собственные значения и соответствующие им собственные векторы из n от n матрица. Эта матрица называется B матрица. Мне нужны только эти три собственных вектора и собственные значения. Обычные методы вычисления собственных векторов и собственных значений большой матрицы занимают много времени, и мне не требуется очень точный ответ, поэтому я ищу оценку собственных векторов и собственных значений.
Некоторые параметры:
-
Bматрица симметричный, реальный, и довольно плотный - Разложение по собственным значениям
Bв теории всегда должны давать реальные цифры. - Мне не нужна абсолютно точная оценка, просто быстрая. Мне нужно было бы завершить это через несколько часов.
- Я пишу на python и C ++
Мой вопрос: существуют ли быстрые методы оценки трех старших собственных векторов и собственных значений такого большого B матрица?
Мой прогресс: я нашел метод аппроксимации наибольшего собственного значения матрицы, но я не знаю, смогу ли я обобщить это до старшей тройки. Я также нашел эта статья написана в 1996 году, но это очень технический и трудно для меня, чтобы прочитать.
Решение
Матричные вычисления Г. Голуба и К. Ф. Ван Лоана, 2-й в главе 9, утверждают, что алгоритмы Ланцоша являются одним из вариантов для этого (за исключением того, что в идеале матрица должна быть разреженной — она явно работает и для не разреженных)
Другие решения
Вы можете получить самый высокий собственный вектор B а затем преобразовать данные в B' используя этот собственный вектор. Затем поп первый столбец B' и получить B'' так что вы можете получить самый высокий собственный вектор B'': достаточно информации, чтобы составить вероятный второй по величине собственный вектор для B, А потом уже третий.
О скорости: вы можете случайно выбрать этот огромный набор данных, чтобы он был только набором данных N Предметы. Если вы получаете только три измерения, я надеюсь, что вы также можете избавиться от большинства данных, чтобы получить представление о собственных векторах. Вы можете назвать это: «избирательный опрос». Я не могу помочь вам измерить частоту появления ошибок, но я попытаюсь сделать выборку из 1 тыс. Элементов несколько раз и посмотреть, будут ли результаты более или менее одинаковыми.
Теперь вы можете получить среднее значение нескольких «опросов», чтобы построить «прогноз».
Посмотрите на предложения в этой теме
Наибольшие собственные значения (и соответствующие собственные векторы) в C ++
Как и предполагалось, вы можете использовать пакет ARPACK, который имеет интерфейс C ++.
detector