Неравномерное дискретное преобразование Фурье

В прикладной математике неоднородное дискретное преобразование Фурье ( NUDFT или NDFT ) сигнала — это тип преобразования Фурье , связанный с дискретным преобразованием Фурье или дискретным временным преобразованием Фурье , но в котором входной сигнал не дискретизируется в равноотстоящих точках или частотах (или и то, и другое). Это обобщение смещенного DFT . Оно имеет важные приложения в обработке сигналов, ^[1] магнитно-резонансной томографии , ^[2] и численном решении уравнений с частными производными. ^[3]

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

Определение

Неравномерное дискретное преобразование Фурье преобразует последовательность комплексных чисел в другую последовательность комплексных чисел, определяемую формулой ${\displaystyle N}$ ${\displaystyle x_{0},\ldots ,x_{N-1}}$ ${\displaystyle X_{0},\ldots ,X_{N-1}}$

где — точки выборки, а — частоты. Обратите внимание, что если и , то уравнение ( 1 ) сводится к дискретному преобразованию Фурье . Существует три типа NUDFT. ^[4] Обратите внимание, что эти типы не являются универсальными, и разные авторы будут ссылаться на разные типы разными числами. ${\displaystyle p_{0},\ldots ,p_{N-1}\in [0,1]}$ ${\displaystyle f_{0},\ldots ,f_{N-1}\in [0,N]}$ ${\displaystyle p_{n}=n/N}$ ${\displaystyle f_{k}=k}$

• Неравномерное дискретное преобразование Фурье типа I (NUDFT-I) использует равномерные точки выборки , но неравномерные (т.е. нецелые) частоты . Это соответствует оценке обобщенного ряда Фурье в равноотстоящих точках. Оно также известно как NDFT ^[5] или прямое NDFT ^{[6] [7]} ${\displaystyle p_{n}=n/N}$ ${\displaystyle f_{k}}$
• Неравномерное дискретное преобразование Фурье типа II (NUDFT-II) использует равномерные (т.е. целые) частоты, но неравномерные точки выборки . Это соответствует оценке ряда Фурье в неравномерно расположенных точках. Оно также известно как сопряженное NDFT. ^{[7] [6]} ${\displaystyle f_{k}=k}$ ${\displaystyle p_{n}}$
• Неравномерное дискретное преобразование Фурье типа III (NUDFT-III) использует как неравномерные точки выборки , так и неравномерные частоты . Это соответствует оценке обобщенного ряда Фурье в неравномерно расположенных точках. Оно также известно как NNDFT. ${\displaystyle p_{n}}$ ${\displaystyle f_{k}}$

Аналогичный набор NUDFT можно определить, подставив в уравнение ( 1 ). Однако, в отличие от однородного случая, эта подстановка не связана с обратным преобразованием Фурье. Обращение NUDFT является отдельной проблемой, обсуждаемой ниже. ${\displaystyle -i}$ ${\displaystyle +i}$

Многомерный NUDFT

Многомерный NUDFT преобразует -мерный массив комплексных чисел в другой -мерный массив комплексных чисел, определяемый формулой ${\displaystyle d}$ ${\displaystyle x_{\mathbf {n} }}$ ${\displaystyle d}$ ${\displaystyle X_{\mathbf {k} }}$

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}x_{\mathbf {n} }e^{-2\pi i\mathbf {p} _{\mathbf {n} }\cdot {\boldsymbol {f}}_{\mathbf {k} }}}$

где — точки выборки, — частоты, а и — -мерные векторы индексов от 0 до . Многомерные NUDFT типов I, II и III определяются аналогично одномерному случаю. ^[4] ${\displaystyle \mathbf {p} _{\mathbf {n} }\in [0,1]^{d}}$ ${\displaystyle {\boldsymbol {f}}_{\mathbf {k} }\in [0,N_{1}]\times [0,N_{2}]\times \cdots \times [0,N_{d}]}$ ${\displaystyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{d})}$ ${\displaystyle \mathbf {k} =(k_{1},k_{2},\ldots ,k_{d})}$ ${\displaystyle d}$ ${\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\ldots ,N_{d}-1)}$

Связь с Z-преобразованием

NUDFT-I можно выразить как Z-преобразование . ^[8] NUDFT-I последовательности длины равно ${\displaystyle x[n]}$ ${\displaystyle N}$

${\displaystyle X(z_{k})=X(z)|_{z=z_{k}}=\sum _{n=0}^{N-1}x[n]z_{k}^{-n},\quad k=0,1,...,N-1,}$

где — Z-преобразование , а — произвольно различные точки в z-плоскости. Обратите внимание, что NUDFT сводится к DFT, когда точки выборки расположены на единичной окружности под равноотстоящими углами. ${\displaystyle X(z)}$ ${\displaystyle x[n]}$ ${\displaystyle \{z_{i}\}_{i=0,1,...,N-1}}$

Выражая вышесказанное в виде матрицы, получаем

${\displaystyle \mathbf {X} =\mathbf {D} \mathbf {x} }$

где

${\displaystyle \mathbf {X} ={\begin{bmatrix}X(z_{0})\\X(z_{1})\\\vdots \\X(z_{N-1})\end{bmatrix}},\quad \mathbf {x} ={\begin{bmatrix}x[0]\\x[1]\\\vdots \\x[N-1]\end{bmatrix}},{\text{ and}}\quad \mathbf {D} ={\begin{bmatrix}1&z_{0}^{-1}&z_{0}^{-2}&\cdots &z_{0}^{-(N-1)}\\1&z_{1}^{-1}&z_{1}^{-2}&\cdots &z_{1}^{-(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&z_{N-1}^{-1}&z_{N-1}^{-2}&\cdots &z_{N-1}^{-(N-1)}\end{bmatrix}}.}$

Прямая инверсия NUDFT-I

Как мы видим, NUDFT-I характеризуется и, следовательно, точками. Если мы далее факторизуем , то увидим, что является невырожденным при условии, что точки различны. Если является невырожденным, мы можем получить уникальное обратное NUDFT-I следующим образом: ${\displaystyle \mathbf {D} }$ ${\displaystyle N}$ ${\displaystyle {z_{k}}}$ ${\displaystyle \det(\mathbf {D} )}$ ${\displaystyle \mathbf {D} }$ ${\displaystyle N}$ ${\displaystyle {z_{k}}}$ ${\displaystyle \mathbf {D} }$

${\displaystyle \mathbf {x} =\mathbf {D^{-1}} \mathbf {X} }$.

Учитывая , мы можем использовать метод Гаусса для решения для . Однако сложность этого метода составляет . Чтобы решить эту задачу более эффективно, мы сначала определяем напрямую с помощью полиномиальной интерполяции: ${\displaystyle \mathbf {X} {\text{ and }}\mathbf {D} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle O(N^{3})}$ ${\displaystyle X(z)}$

${\displaystyle {\hat {X}}[k]=X(z_{k}),\quad k=0,1,...,N-1}$.

Тогда — коэффициенты указанного выше интерполяционного полинома. ${\displaystyle x[n]}$

Выражая в виде полинома Лагранжа порядка , получаем ${\displaystyle X(z)}$ ${\displaystyle N-1}$

${\displaystyle X(z)=\sum _{k=0}^{N-1}{\frac {L_{k}(z)}{L_{k}(z_{k})}}{\hat {X}}[k],}$

где — фундаментальные полиномы: ${\displaystyle \{L_{i}(z)\}_{i=0,1,...,N-1}}$

${\displaystyle L_{k}(z)=\prod _{i\neq k}(1-z_{i}z^{-1}),\quad k=0,1,...,N-1}$.

Выражая методом интерполяции Ньютона, получаем ${\displaystyle X(z)}$

${\displaystyle X(z)=c_{0}+c_{1}(1-z_{0}z^{-1})+c_{2}(1-z_{0}z^{-1})(1-z_{1}z^{-1})+\cdots +c_{N-1}\prod _{k=0}^{N-2}(1-z_{k}z^{-1}),}$

где - разделенная разность -го порядка относительно : ${\displaystyle c_{j}}$ ${\displaystyle j}$ ${\displaystyle {\hat {X}}[0],{\hat {X}}[1],...,{\hat {X}}[j]}$ ${\displaystyle z_{0},z_{1},...,z_{j}}$

${\displaystyle c_{0}={\hat {X}}[0],}$

${\displaystyle c_{1}={\frac {{\hat {X}}[1]-c_{0}}{1-z_{0}z_{1}^{-1}}},}$

${\displaystyle c_{2}={\frac {{\hat {X}}[2]-c_{0}-c_{1}(1-z_{0}z^{-1})}{(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})}},}$

${\displaystyle \vdots }$

Недостатком представления Лагранжа является то, что любая дополнительная точка, включенная в него, увеличит порядок интерполирующего полинома, что приведет к необходимости пересчета всех фундаментальных полиномов. Однако любая дополнительная точка, включенная в представление Ньютона, требует только добавления еще одного члена.

Для решения можно использовать нижнюю треугольную систему : ${\displaystyle \{c_{j}\}}$

${\displaystyle \mathbf {L} \mathbf {c} =\mathbf {X} }$

где

${\displaystyle \mathbf {X} ={\begin{bmatrix}{\hat {X}}[0]\\{\hat {X}}[1]\\\vdots \\{\hat {X}}[N-1]\end{bmatrix}},\quad \mathbf {c} ={\begin{bmatrix}c_{0}\\c_{1}\\\vdots \\c_{N-1}\end{bmatrix}},{\text{ and}}\quad \mathbf {L} ={\begin{bmatrix}1&0&0&\cdots &0\\1&(1-z_{0}z_{1}^{-1})&0&\cdots &0\\1&(1-z_{0}z_{2}^{-1})&(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&(1-z_{0}z_{N-1}^{-1})&(1-z_{0}z_{N-1}^{-1})(1-z_{1}z_{N-1}^{-1})&\cdots &\prod _{k=0}^{N-2}(1-z_{k}z_{N-1}^{-1})\end{bmatrix}}.}$

По приведенному выше уравнению можно вычислить в пределах операций. Таким образом, интерполяция Ньютона более эффективна, чем интерполяция Лагранжа, если только последняя не модифицирована ${\displaystyle \{c_{j}\}}$ ${\displaystyle O(N^{2})}$

${\displaystyle L_{k+1}(z)={\frac {(1-z_{k+1}z^{-1})}{(1-z_{k}z^{-1})}}L_{k}(z),\quad k=0,1,...,N-1}$.

Неравномерное быстрое преобразование Фурье

В то время как наивное применение уравнения ( 1 ) приводит к алгоритму вычисления NUDFT, существуют алгоритмы, основанные на быстром преобразовании Фурье (FFT). Такие алгоритмы называются NUFFT или NFFT и были разработаны на основе передискретизации и интерполяции, ^{[9] [10] [11] [12]} интерполяции min-max, ^[2] и аппроксимации с низким рангом. ^[13] В общем, NUFFT используют FFT, преобразуя неоднородную задачу в однородную задачу (или последовательность однородных задач), к которой можно применить FFT. ^[4] Библиотеки программного обеспечения для выполнения NUFFT доступны в 1D, 2D и 3D. ^{[7] [6] [14] [15] [16] [17]} ${\displaystyle O(N^{2})}$ ${\displaystyle O(N\log N)}$

Приложения

Приложения NUDFT включают в себя:

• Цифровая обработка сигнала
• Магнитно-резонансная томография
• Численные уравнения в частных производных
• Полулагранжевы схемы
• Спектральные методы
• Спектральный анализ
• Конструкция цифрового фильтра
• Конструкция антенной решетки
• Обнаружение и декодирование двухтональных многочастотных (DTMF) сигналов

Смотрите также

• Дискретное преобразование Фурье
• Быстрое преобразование Фурье
• Спектральный анализ методом наименьших квадратов
• Периодограмма Ломба–Скаргла
• Спектральная оценка
• Неравномерно распределенные временные ряды

Ссылки

1. Багчи, Сонали; Митра, Санджит К. (1999). Неравномерное дискретное преобразование Фурье и его применение в обработке сигналов . Бостон, Массачусетс: Springer US. ISBN 978-1-4615-4925-3.
2. Fessler, JA; Sutton, BP (февраль 2003 г.). "Неравномерные быстрые преобразования Фурье с использованием интерполяции минимума и максимума". IEEE Transactions on Signal Processing . 51 (2): 560–574. Bibcode : 2003ITSP...51..560F. doi : 10.1109/TSP.2002.807005. hdl : 2027.42/85840 .
3. Ли, Джун-Юб; Грингард, Лесли (июнь 2005 г.). «Неоднородное БПФ типа 3 и его приложения». Журнал вычислительной физики . 206 (1): 1–5. Bibcode :2005JCoPh.206....1L. doi :10.1016/j.jcp.2004.12.004.
4. Greengard, Leslie; Lee, June-Yub (январь 2004). «Ускорение неравномерного быстрого преобразования Фурье». SIAM Review . 46 (3): 443–454. Bibcode : 2004SIAMR..46..443G. CiteSeerX 10.1.1.227.3679 . doi : 10.1137/S003614450343200X. 
5. Плонка, Герлинд ; Поттс, Дэниел; Стейдл, Габриэле ; Таше, Манфред (2019). Численный анализ Фурье . Биркхойзер. дои : 10.1007/978-3-030-04306-3. ISBN 978-3-030-04306-3.
6. PyNUFFT Services. "Основное использование PyNUFFT — документация PyNUFFT 2023.2.2". pynufft.readthedocs.io . Получено 27 февраля 2024 г. .
7. Фонд Саймонса. "Математические определения преобразований — документация finufft 2.2.0". finufft.readthedocs.io . Получено 27 февраля 2024 г. .
8. Марвасти, Фарох (2001). Неравномерная выборка: теория и практика . Нью-Йорк: Springer. С. 325–360. ISBN 978-1-4615-1229-5.
9. Датт, Алок (май 1993 г.). Быстрые преобразования Фурье для неравноширинных данных (PDF) (PhD). Йельский университет.
10. Датт, Алок; Рохлин, Владимир (ноябрь 1993 г.). «Быстрые преобразования Фурье для неэквиспек-тированных данных». Журнал SIAM по научным вычислениям . 14 (6): 1368–1393. Bibcode : 1993SJSC...14.1368D. doi : 10.1137/0914081.
11. Поттс, Дэниел; Стейдл, Габриэль (январь 2003 г.). «Быстрое суммирование в неэквиспейсных узлах с помощью NFFT». Журнал SIAM по научным вычислениям . 24 (6): 2013–2037. Bibcode : 2003SJSC...24.2013P. doi : 10.1137/S1064827502400984.
12. Boyd, John P (декабрь 1992 г.). "Быстрый алгоритм для интерполяции Чебышева, Фурье и синусоидального уравнения на нерегулярной сетке" (PDF) . Journal of Computational Physics . 103 (2): 243–257. Bibcode :1992JCoPh.103..243B. doi :10.1016/0021-9991(92)90399-J. hdl : 2027.42/29694 .
13. Руис-Антолин, Диего; Таунсенд, Алекс (20 февраля 2018 г.). «Неравномерное быстрое преобразование Фурье на основе аппроксимации низкого ранга» (PDF) . Журнал SIAM по научным вычислениям . 40 (1): A529–A547. arXiv : 1701.04492 . Bibcode :2018SJSC...40A.529R. doi :10.1137/17M1134822. hdl :10902/13767.
14. "Страница NUFFT". cims.nyu.edu .
15. "NFFT". www.nfft.org .
16. "MikaelSlevinsky/FastTransforms.jl". GitHub . 2019-02-13.
17. "chebfun/chebfun". GitHub . 2019-02-07.

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

• Неравномерное преобразование Фурье: Учебное пособие.
• NFFT 3.0 – Учебное пособие
• Библиотека программного обеспечения NUFFT