Алгоритм Рыбицкого Пресса

Расширенная разреженная матрица, возникающая из $10\times 10$ полуразделимая матрица, полуразделимый ранг которой равен $4$.

Алгоритм Рыбицкого – Пресса — это быстрый алгоритм обращения матрицы , элементы которой имеют вид $A(i,j)=\exp(-a\vert t_{i}-t_{j}\vert )$, где $a\in \mathbb {R}$ и где $t_{i}$ сортируются по порядку. Ключевое наблюдение, лежащее в основе наблюдения Рыбицкого-Пресса, заключается в том, что матрица, обратная такой матрице, всегда представляет собой трехдиагональную матрицу (матрица с ненулевыми элементами только на главной диагонали и двух соседних), и трехдиагональные системы уравнений могут быть эффективно решены. (точнее, в линейном времени). Это вычислительная оптимизация общего набора статистических методов, разработанных для определения того, являются ли два зашумленных набора данных с нерегулярной выборкой фактически смещенными по размерности представлениями одной и той же базовой функции. Наиболее распространенное использование алгоритма - обнаружение периодичности в астрономических наблюдениях. , например, для обнаружения квазаров .

Метод был расширен до обобщенного алгоритма Рыбицкого-Пресса для обращения матриц с элементами вида $A(i,j)=\sum _{k=1}^{p}a_{k}\exp(-\beta _{k}\vert t_{i}-t_{j}\vert )$. Ключевое наблюдение в алгоритме Обобщенного Рыбицкого-Пресса (GRP) заключается в том, что матрица $A$ является полуразделимой матрицей ранга $p$ (то есть матрица, верхняя половина которой, не включая главную диагональ, является матрицей некоторой матрицы с матричным рангом $p$ и чья нижняя половина также принадлежит к какому-то, возможно, другому рангу $p$ матрица ) и поэтому может быть встроен в ленточную матрицу большего размера (см. рисунок справа), структуру разреженности которой можно использовать для уменьшения вычислительной сложности. В качестве матрицы $A\in \mathbb {R} ^{n\times n}$ имеет полусепарабельный ранг $p$, вычислительная сложность решения линейной системы $Ax=b$ или вычисления определителя матрицы $A$ масштабируется как ${\mathcal {O}}\left(p^{2}n\right)$, что делает его привлекательным для больших матриц.

Тот факт, что матрица $A$ представляет собой полуразборную матрицу, также образующую основу целерита библиотека, которая представляет собой библиотеку для быстрой и масштабируемой регрессии гауссовского процесса в одном измерении. с реализациями на C++ , Python и Julia . Целеритовый метод также предоставляет алгоритм для создания выборок из многомерного распределения. Метод нашел интересное применение в самых разных областях. особенно в анализе астрономических данных.

См. также

• Обратимая матрица
• Разложение матрицы
• Многомерная обработка сигналов
• Система линейных уравнений

Внешние ссылки

• Реализация обобщенного алгоритма Рыбицкого Пресса
• библиотека Celerite на GitHub