Разреженное преобразование Фурье

Разреженное преобразование Фурье ( SFT ) — это разновидность дискретного преобразования Фурье (DFT) для обработки сигналов больших данных . В частности, он используется в GPS- синхронизации, распознавании спектра и аналого-цифровых преобразователях .: ^[1]

Быстрое преобразование Фурье (БПФ) играет незаменимую роль во многих научных областях, особенно в обработке сигналов. Это один из 10 лучших алгоритмов двадцатого века. ^[2] Однако с наступлением эры больших данных БПФ все еще нуждается в улучшении, чтобы сэкономить больше вычислительной мощности. В последнее время разреженное преобразование Фурье (SFT) привлекло значительное внимание, поскольку оно хорошо работает при анализе длинной последовательности данных с небольшим количеством компонентов сигнала.

Определение

Рассмотрим последовательность x _n комплексных чисел . Рядом Фурье n x _как можно записать

x_{n}=(F^{*}X)_{n}=\sum _{k=0}^{N-1}X_{k}e^{j{\frac {2\pi }{N}}kn}.

Аналогично X _k можно представить как

X_{k}={\frac {1}{N}}(Fx)_{k}={\frac {1}{N}}\sum _{n=0}^{N-1}x_{n}e^{-j{\frac {2\pi }{N}}kn}.

Следовательно, из приведенных выше уравнений отображение имеет вид $F:\mathbb {C} ^{N}\to \mathbb {C} ^{N}$ .

Одночастотное восстановление

Предположим, что в последовательности существует только одна частота. Чтобы восстановить эту частоту из последовательности, разумно использовать связь между соседними точками последовательности.

Фазовое кодирование

Фазу k можно получить путем деления соседних точек последовательности. Другими словами,

{\frac {x_{n+1}}{x_{n}}}=e^{j{\frac {2\pi }{N}}k}=\cos \left({\frac {2\pi k}{N}}\right)+j\sin \left({\frac {2\pi k}{N}}\right).

Обратите внимание, что $x_{n}\in \mathbb {C} ^{N}$ .

Поиск на основе псевдонимов

Поиск фазы k можно осуществить с помощью китайской теоремы об остатках (CRT). ^[3]

Брать $k=104{,}134$ для примера. Теперь у нас есть три относительно простых целых числа: 100, 101 и 103. Таким образом, уравнение можно описать как

k=104{,}134\equiv \left\{{\begin{array}{rl}34&{\bmod {1}}00,\\3&{\bmod {1}}01,\\1&{\bmod {1}}03.\end{array}}\right.

По ЭЛТ мы имеем

k=104{,}134{\bmod {(}}100\cdot 101\cdot 103)=104{,}134{\bmod {1}}{,}040{,}300

Случайное биннинг частот

Теперь мы хотим изучить случай нескольких частот, а не одной частоты. Соседние частоты могут быть разделены свойствами масштабирования c и модуляции b . А именно, при случайном выборе параметров c и b распределение всех частот может быть почти равномерным. На рисунке «Распределение всех частот» показано случайное объединение частот. Мы можем использовать восстановление одной частоты для поиска основных компонентов.

x_{n}'=X_{k}e^{j{\frac {2\pi }{N}}(c\cdot k+b)},

где c — свойство масштабирования, а b — свойство модуляции.

Случайным образом выбрав c и b , весь спектр можно будет представить как равномерное распределение . Затем, объединив их в банки фильтров, можно разделить все частоты, включая гауссианы. ^[4] индикаторные функции, ^[5]^[6] шипованные поезда, ^[7]^[8]^[9]^[10] и фильтры Дольфа-Чебышева. ^[11] Каждый банк содержит только одну частоту.

Прототип SFT

Как правило, все SFT проходят три этапа. ^[1]

Определение частот

Путем случайного объединения частот все компоненты можно разделить. Затем их объединяют в банки фильтров, чтобы каждая полоса содержала только одну частоту. Для восстановления частоты этого сигнала удобно использовать упомянутые нами методы.

Оценочные коэффициенты

После определения частот у нас будет множество частотных составляющих. Мы можем использовать преобразование Фурье для оценки их коэффициентов.

X_{k}'={\frac {1}{L}}\sum _{l=1}^{L}x_{n}'e^{-j{\frac {2\pi }{N}}n'\ell }

Повторение

Наконец, повторив эти два этапа, мы можем извлечь наиболее важные компоненты из исходного сигнала.

x_{n}-\sum _{k'=1}^{k}X_{k}'e^{j{\frac {2\pi }{N}}k'n}

Разреженное преобразование Фурье в дискретной ситуации

В 2012 году Хассания, Индик, Катаби и Прайс ^[11] предложил алгоритм, который принимает $O(k\log n\log(n/k))$ образцы и прогоны за одно и то же время работы.

Разреженное преобразование Фурье в условиях большой размерности

В 2014 году Индик и Капралов ^[12] предложил алгоритм, который принимает $2^{O(d\log d)}k\log n$ отбирает образцы и работает практически за линейное время в $n$ . И 2016, Капрал ^[13] предложил алгоритм, использующий сублинейные выборки $2^{O(d^{2})}k\log n\log \log n$ и время сублинейного декодирования $k\log ^{O(d)}n$ . В 2019 году Накос, Сун и Ван ^[14] представил новый алгоритм, который использует почти оптимальные образцы $O(k\log n\log k)$ и требует почти линейного времени декодирования. Алгоритм с приращением измерений был предложен Поттсом, Фолькмером. ^[15] на основе выборки по решеткам ранга 1.

Разреженное преобразование Фурье в непрерывном случае

Есть несколько работ об обобщении дискретной ситуации в непрерывную. ^[16]^[17]

Реализации

Есть несколько работ, основанных на MIT , MSU , ETH и Технологическом университете Хемница [TUC]. Кроме того, они бесплатны онлайн.

Дальнейшее чтение

Хассания, Хайсам (2018). Разреженное преобразование Фурье: теория и практика . Ассоциация вычислительной техники и Morgan & Claypool. ISBN 978-1-94748-707-9 .

Прайс, Эрик (2013). Разреженное восстановление и выборка Фурье . Массачусетский технологический институт.

Ссылки

^ Jump up to: ^а ^б Гилберт, Анна С.; Индик, Петр; Ивен, Марк; Шмидт, Людвиг (2014). «Последние разработки в области разреженного преобразования Фурье: сжатое преобразование Фурье для больших данных» (PDF) . Журнал обработки сигналов IEEE . 31 (5): 91–100. Бибкод : 2014ISPM...31...91G . дои : 10.1109/MSP.2014.2329131 . hdl : 1721.1/113828 . S2CID 14585685 .
^ Ципра, Барри А. (2000). «Лучшее 20-го века: редакторы называют 10 лучших алгоритмов». СИАМ Новости . 33 (4).
^ Ивен, Массачусетс (5 января 2010 г.). «Комбинаторные алгоритмы Фурье с сублинейным временем». Основы вычислительной математики . 10 (3): 303–338. дои : 10.1007/s10208-009-9057-1 . S2CID 1631513 .
^ Хайсам Хассания; Петр Индик; Дина Катаби; Эрик Прайс (2012). Простой и практичный алгоритм разреженного преобразования Фурье . стр. 1183–1194. дои : 10.1137/1.9781611973099.93 . hdl : 1721.1/73474 . ISBN 978-1-61197-210-8 .
^ AC Гилберт (2002). «Почти оптимальное разреженное представление Фурье посредством выборки». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . С. Гуха, П. Индик, С. Мутукришнан , М. Штраус. стр. 152–161. дои : 10.1145/509907.509933 . ISBN 1581134959 . S2CID 14320243 .
^ AC Гилберт; С. Мутукришнан ; М. Штраус (21 сентября 2005 г.). «Улучшенные временные ограничения для почти оптимальных разреженных представлений Фурье». В Пападакисе, Манос; Лейн, Эндрю Ф; Унсер, Майкл А. (ред.). Вейвлеты XI . Труды SPIE. Том. 5914. стр. 59141А. Бибкод : 2005SPIE.5914..398G . дои : 10.1117/12.615931 . S2CID 12622592 .
^ Гази, Бадих; Хассания, Хайсам; Индик, Петр; Катаби, Дина; Прайс, Эрик; Лисинь Ши (2013). «Разреженное преобразование Фурье в среднем оптимальном для выборки в двух измерениях». 2013 51-я ежегодная конференция Allerton по связи, управлению и вычислениям (Allerton) . стр. 1258–1265. arXiv : 1303.1209 . дои : 10.1109/Allerton.2013.6736670 . ISBN 978-1-4799-3410-2 . S2CID 6151728 .
^ Ивен, Массачусетс (5 января 2010 г.). «Комбинаторные алгоритмы Фурье с сублинейным временем». Основы вычислительной математики . 10 (3): 303–338. дои : 10.1007/s10208-009-9057-1 . S2CID 1631513 .
^ Марк А.Ивен (01 января 2013 г.). «Улучшенные гарантии аппроксимации для алгоритмов Фурье с сублинейным временем». Прикладной и вычислительный гармонический анализ . 34 (1): 57–82. arXiv : 1010.0014 . дои : 10.1016/j.acha.2012.03.007 . ISSN 1063-5203 . S2CID 16808450 .
^ Павар, Самир; Рамчандран, Каннан (2013). «Вычисление дискретного преобразования Фурье k-разреженной длины n с использованием не более 4 тыс. выборок и сложности O (k log k)». Международный симпозиум IEEE по теории информации , 2013 г. стр. 464–468. дои : 10.1109/ISIT.2013.6620269 . ISBN 978-1-4799-0446-4 . S2CID 601496 .
^ Jump up to: ^а ^б Хассания, Хайсам; Индик, Петр; Катаби, Дина; Прайс, Эрик (2012). «Почти оптимальное разреженное преобразование Фурье» . Материалы сорок четвертого ежегодного симпозиума ACM по теории вычислений . СТОК'12. АКМ. стр. 563–578. arXiv : 1201.2501 . дои : 10.1145/2213977.2214029 . ISBN 9781450312455 . S2CID 3760962 .
^ Индик, Петр; Капралов, Михаил (2014). «Оптимальная выборка Фурье в любом постоянном измерении» . Ежегодный симпозиум по основам информатики . ФОКС'14: 514–523. arXiv : 1403.5804 .
^ Капралов, Михаил (2016). «Разреженное преобразование Фурье в любом постоянном измерении с почти оптимальной сложностью выборки за сублинейное время». Материалы сорок восьмого ежегодного симпозиума ACM по теории вычислений . СТОК'16. стр. 264–277. arXiv : 1604.00845 . дои : 10.1145/2897518.2897650 . ISBN 9781450341325 . S2CID 11847086 .
^ Накос, Василейос; Сун, Чжао; Ван, Чжэнъюй (2019). «(Почти) оптимальное для выборки разреженное преобразование Фурье в любом измерении; без RIP и без фильтров». Ежегодный симпозиум по основам информатики . ФОКС'19. arXiv : 1909.11123 .
^ Поттс, Дэниел; Волкмер, Тони (2016). «Разреженное многомерное БПФ на основе решетчатой выборки ранга 1». Прикладной и вычислительный гармонический анализ . 41 (3): 713–748. дои : 10.1016/j.acha.2015.05.002 .
^ Прайс, Эрик; Сун, Чжао (2015). «Надежное разреженное преобразование Фурье в непрерывной ситуации». Ежегодный симпозиум по основам информатики . ФОКС'15: 583–600. arXiv : 1609.00896 .
^ Чен, Сюэ; Кейн, Дэниел М.; Прайс, Эрик; Сун, Чжао (2016). «Фурье-разреженная интерполяция без частотного зазора» . Ежегодный симпозиум по основам информатики . ФОКС'16: 741–750. arXiv : 1609.01361 .

[auto-1] Jump up to: ^а ^б Гилберт, Анна С.; Индик, Петр; Ивен, Марк; Шмидт, Людвиг (2014). «Последние разработки в области разреженного преобразования Фурье: сжатое преобразование Фурье для больших данных» (PDF) . Журнал обработки сигналов IEEE . 31 (5): 91–100. Бибкод : 2014ISPM...31...91G . дои : 10.1109/MSP.2014.2329131 . hdl : 1721.1/113828 . S2CID 14585685 .

[2] Ципра, Барри А. (2000). «Лучшее 20-го века: редакторы называют 10 лучших алгоритмов». СИАМ Новости . 33 (4).

[3] Ивен, Массачусетс (5 января 2010 г.). «Комбинаторные алгоритмы Фурье с сублинейным временем». Основы вычислительной математики . 10 (3): 303–338. дои : 10.1007/s10208-009-9057-1 . S2CID 1631513 .

[4] Хайсам Хассания; Петр Индик; Дина Катаби; Эрик Прайс (2012). Простой и практичный алгоритм разреженного преобразования Фурье . стр. 1183–1194. дои : 10.1137/1.9781611973099.93 . hdl : 1721.1/73474 . ISBN 978-1-61197-210-8 .

[5] AC Гилберт (2002). «Почти оптимальное разреженное представление Фурье посредством выборки». Материалы тридцать четвертого ежегодного симпозиума ACM по теории вычислений . С. Гуха, П. Индик, С. Мутукришнан , М. Штраус. стр. 152–161. дои : 10.1145/509907.509933 . ISBN 1581134959 . S2CID 14320243 .

[6] AC Гилберт; С. Мутукришнан ; М. Штраус (21 сентября 2005 г.). «Улучшенные временные ограничения для почти оптимальных разреженных представлений Фурье». В Пападакисе, Манос; Лейн, Эндрю Ф; Унсер, Майкл А. (ред.). Вейвлеты XI . Труды SPIE. Том. 5914. стр. 59141А. Бибкод : 2005SPIE.5914..398G . дои : 10.1117/12.615931 . S2CID 12622592 .

[7] Гази, Бадих; Хассания, Хайсам; Индик, Петр; Катаби, Дина; Прайс, Эрик; Лисинь Ши (2013). «Разреженное преобразование Фурье в среднем оптимальном для выборки в двух измерениях». 2013 51-я ежегодная конференция Allerton по связи, управлению и вычислениям (Allerton) . стр. 1258–1265. arXiv : 1303.1209 . дои : 10.1109/Allerton.2013.6736670 . ISBN 978-1-4799-3410-2 . S2CID 6151728 .

[8] Ивен, Массачусетс (5 января 2010 г.). «Комбинаторные алгоритмы Фурье с сублинейным временем». Основы вычислительной математики . 10 (3): 303–338. дои : 10.1007/s10208-009-9057-1 . S2CID 1631513 .

[9] Марк А.Ивен (01 января 2013 г.). «Улучшенные гарантии аппроксимации для алгоритмов Фурье с сублинейным временем». Прикладной и вычислительный гармонический анализ . 34 (1): 57–82. arXiv : 1010.0014 . дои : 10.1016/j.acha.2012.03.007 . ISSN 1063-5203 . S2CID 16808450 .

[10] Павар, Самир; Рамчандран, Каннан (2013). «Вычисление дискретного преобразования Фурье k-разреженной длины n с использованием не более 4 тыс. выборок и сложности O (k log k)». Международный симпозиум IEEE по теории информации , 2013 г. стр. 464–468. дои : 10.1109/ISIT.2013.6620269 . ISBN 978-1-4799-0446-4 . S2CID 601496 .

[hikp12stoc-11] Jump up to: ^а ^б Хассания, Хайсам; Индик, Петр; Катаби, Дина; Прайс, Эрик (2012). «Почти оптимальное разреженное преобразование Фурье» . Материалы сорок четвертого ежегодного симпозиума ACM по теории вычислений . СТОК'12. АКМ. стр. 563–578. arXiv : 1201.2501 . дои : 10.1145/2213977.2214029 . ISBN 9781450312455 . S2CID 3760962 .

[12] Индик, Петр; Капралов, Михаил (2014). «Оптимальная выборка Фурье в любом постоянном измерении» . Ежегодный симпозиум по основам информатики . ФОКС'14: 514–523. arXiv : 1403.5804 .

[13] Капралов, Михаил (2016). «Разреженное преобразование Фурье в любом постоянном измерении с почти оптимальной сложностью выборки за сублинейное время». Материалы сорок восьмого ежегодного симпозиума ACM по теории вычислений . СТОК'16. стр. 264–277. arXiv : 1604.00845 . дои : 10.1145/2897518.2897650 . ISBN 9781450341325 . S2CID 11847086 .

[14] Накос, Василейос; Сун, Чжао; Ван, Чжэнъюй (2019). «(Почти) оптимальное для выборки разреженное преобразование Фурье в любом измерении; без RIP и без фильтров». Ежегодный симпозиум по основам информатики . ФОКС'19. arXiv : 1909.11123 .

[15] Поттс, Дэниел; Волкмер, Тони (2016). «Разреженное многомерное БПФ на основе решетчатой выборки ранга 1». Прикладной и вычислительный гармонический анализ . 41 (3): 713–748. дои : 10.1016/j.acha.2015.05.002 .

[16] Прайс, Эрик; Сун, Чжао (2015). «Надежное разреженное преобразование Фурье в непрерывной ситуации». Ежегодный симпозиум по основам информатики . ФОКС'15: 583–600. arXiv : 1609.00896 .

[17] Чен, Сюэ; Кейн, Дэниел М.; Прайс, Эрик; Сун, Чжао (2016). «Фурье-разреженная интерполяция без частотного зазора» . Ежегодный симпозиум по основам информатики . ФОКС'16: 741–750. arXiv : 1609.01361 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]