Есть ли БПФ, которое использует логарифмическое деление частоты?

Question

Википедия Вейвлет-статья содержит этот текст:

Дискретное вейвлет-преобразование также менее вычислительно сложное, занимая O (N) по сравнению с O (N log N) для быстрого преобразования Фурье . Это вычислительное преимущество не присуще преобразованию, но отражает выбор логарифмического деления частоты, в отличие от равноотстоящих делений частоты БПФ.

Означает ли это, что существует также алгоритм, подобный БПФ, который использует логарифмическое деление частоты вместо линейного? Это тоже O (N)? Это, очевидно, было бы предпочтительным для многих приложений.

Answer 1

Да. Да. Нет.

Это называется логарифмическим преобразованием Фурье. У него есть O (n) время. Однако это полезно для функций, которые медленно распадаются с увеличением области / абсциссы.

Возвращаясь к статье в википедии:

Основное отличие в том, что вейвлеты локализованы как во времени, так и частота, тогда как стандарт Фурье преобразование только локализовано в частота.

Так что, если вы можете быть локализованы только во времени (или в пространстве, выберите свою интерпретацию абсциссы), то вейвлеты (или дискретное косинусное преобразование) являются разумным подходом. Но если вам нужно продолжать и продолжать, вам нужно преобразование Фурье.

Узнайте больше о LFT на http://homepages.dias.ie/~ajones/publications/28.pdf

Вот реферат:

"Мы представляем точное и аналитическое выражение для преобразования Фурье функции, которая была выбрана логарифмически. Процедура значительно более эффективна в вычислительном отношении, чем быстрое преобразование Фурье (БПФ) для преобразования функций или измеренных откликов, которые медленно затухают с увеличением значение абсциссы. Мы иллюстрируем предложенный метод на примере электромагнитной геофизики, где масштабирование часто таково, что следует применять наше логарифмическое преобразование Фурье (LFT). Для выбранного примера мы можем получить результаты, которые согласуются с результатами из БПФ с точностью до 0,5% за время, которое в 1,0 э2 короче. Потенциальные применения нашего LFT в геофизике включают преобразование широкополосных электромагнитных частотных откликов в переходные отклики, ледниковую нагрузку и разгрузку, проблемы пополнения водоносных горизонтов, исследования нормального режима и приливов в сейсмологии, а также моделирование импульсных ударных волн. "

Answer 2

Чтобы делать то, что вы хотите, вам нужно измерять разное время Windows, что означает, что более низкие частоты обновляются реже (обратно пропорционально степени 2).

Проверьте FPPO здесь: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf

Это означает, что более высокие частоты будут обновляться чаще, но вы всегда усредняете (скользящее среднее - это хорошо), но вы также можете позволить ему двигаться быстрее. Конечно, если вы планируете использовать обратное БПФ, вам этого не нужно. Кроме того, чтобы иметь более высокую точность (меньшую пропускную способность) на более низких частотах, это означает, что они должны обновляться гораздо медленнее, например, 16k Windows (1/3 м / с).

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

Я думаю, что ссылка, которую я предоставлю, прояснит некоторые ваши варианты ... К сожалению, через 7 лет после того, как вы задали вопрос.

Answer 3

РЕДАКТИРОВАТЬ: После прочтения этого, я думаю, что этот алгоритм не очень полезен для этого вопроса, я все равно дам описание для других читателей.

Существует также алгоритм Филона метод, основанный на квадратуре Филона, который можно найти в Числовые рецепты в этой [кандидатской диссертации] [1]. Временная шкала логарифмическая, как и результирующая шкала частот.

Этот алгоритм используется для данных / функций, которые упали до 0 в наблюдаемом интервале времени (что, вероятно, не ваш случай), типичным простым примером будет экспоненциальный спад.

Если ваши данные отмечены точками (x_0, y_0), (x_1, y_1) ... (x_i, y_i) и вы хотите вычислить спектр A (f), где f - частота, скажем, f_min = От 1 / x_max до f_max = 1 / x_min журнал разнесен. Действительная часть для каждой частоты f затем рассчитывается по формуле:

A (f) = сумма из i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * [cos (2 * pi * f * t_i + 1) - cos (2 * pi * f * t_i)] / ((2 * pi * f) ^ 2)}

Мнимая часть:

A (f) = y_0 / (2 * pi * f) + сумма из i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * [sin (2 * pi * f * t_i + 1) - sin (2 * pi * f * t_i)] / ((2 * pi * f) ^ 2)}

[1] Блохович, Томас: Широкополосная диэлектрическая спектроскопия в чистых и бинарных молекулярных стеклах. Университет Байройта, 2003, глава 3.2.3