Nano Hash - криптовалюты, майнинг, программирование

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

Я пытаюсь решить проблему с python+numpy, в которой у меня есть некоторые функции типа < img src="https://i.stack.imgur.com/dlU2I.gif" alt="$f(x-x_i,y-y_i,z)$">, который мне нужно свернуть с другим функция $g(x,y,z,t)$. Чтобы оптимизировать код, я выполнил БПФ f и g, перемножил их, а затем выполнил обратное преобразование, чтобы получить результат.

В качестве дополнительной оптимизации я понял, что благодаря теореме сдвига я могу просто вычислить один раз fft f(x,y,z), а затем умножить его на фазовый коэффициент, который зависит от $(x_i, y_i)$ для получения fft $f(x-x_i,y-y_i,z)$. В частности, $\mathcal{F}(f(x-x_i,y-y_i,z)) = exp^{-2\pi j (x_i w_1 + y_i w_2)/N} \mathcal{F}( f(x,y,z))$, где N – длина x и y.

Я попытался реализовать эту простую формулу с помощью python + numpy, но по какой-то непонятной для меня причине она не работает, поэтому я прошу помощи сообщества SO, чтобы выяснить, что мне не хватает.

Я также привожу простой пример.

In [1]: import numpy as np
In [2]: x = np.arange(-10, 11)
In [3]: base = np.fft.fft(np.cos(x))
In [4]: shifted = np.fft.fft(np.cos(x-1))
In [5]: w = np.fft.fftfreq(x.size)
In [6]: phase = np.exp(-2*np.pi*1.0j*w/x.size)
In [7]: test = phase * base
In [8]: (test == shifted).all()
Out[8]: False
In [9]: shifted/base
Out[9]:
array([ 0.54030231 -0.j        ,  0.54030231 -0.23216322j,
        0.54030231 -0.47512034j,  0.54030231 -0.7417705j ,
        0.54030231 -1.05016033j,  0.54030231 -1.42919168j,
        0.54030231 -1.931478j  ,  0.54030231 -2.66788185j,
        0.54030231 -3.92462627j,  0.54030231 -6.74850534j,
        0.54030231-20.55390586j,  0.54030231+20.55390586j,
        0.54030231 +6.74850534j,  0.54030231 +3.92462627j,
        0.54030231 +2.66788185j,  0.54030231 +1.931478j  ,
        0.54030231 +1.42919168j,  0.54030231 +1.05016033j,
        0.54030231 +0.7417705j ,  0.54030231 +0.47512034j,
        0.54030231 +0.23216322j])
In [10]: np.abs(shifted/base)
Out[10]:
array([  0.54030231,   0.58807001,   0.71949004,   0.91768734,
         1.18100097,   1.52791212,   2.00562555,   2.72204338,
         3.96164334,   6.77009977,  20.56100612,  20.56100612,
         6.77009977,   3.96164334,   2.72204338,   2.00562555,
         1.52791212,   1.18100097,   0.91768734,   0.71949004,   0.58807001])

Я ожидаю, что с помощью shifted/base я смогу получить соответствующие значения фазового множителя, но, как видно, он не может быть фазовым множителем, так как его np.abs >= 1!

python numpy fft dft
27.04.2016

Ответы:


1

Проблема в моем коде заключалась как в строке ввода 6 из-за неправильной (по моей вине) интерпретации возвращаемого значения np.fft.fftfreq(), так и в необходимости дополнять массивы для получения хороших результатов.

Следующий код отлично работает и может быть расширен до многомерности.

In [1]: import numpy as np
In [2]: shift = 1
In [3]: dx = 0.5
In [4]: pad = 20
In [5]: x = np.arange(-10, 11, dx)
In [6]: y = np.cos(x)
In [7]: y = np.pad(y, (0,pad), 'constant')
In [8]: y_shift = np.cos(x-shift)
In [9]: y_fft = np.fft.fft(y)
In [10]: w = np.fft.fftfreq(y.size, dx)
In [11]: phase = np.exp(-2.0*np.pi*1.0j*w*shift)
In [12]: test = phase * y_fft
In [13]: # we use np.real since the resulting inverse fft has small imaginary part values that are zero
In [14]: inv_test = np.real(np.fft.ifft(test))
In [15]: np.allclose(y[:-pad-2],inv_test[2:-pad])
Out[15]: True
29.09.2017

2

Красиво, большое спасибо, что поделились! Я реализовал что-то в этих строках некоторое время назад, но не мог понять математику этого (я вслепую портировал технический документ, описывающий алгоритм). FWIW, вот оно: https://github.com/creaktive/flare/blob/master/nrf905_demod.c#L376

08.05.2018
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..