스파스 푸리에 변환

스파스 푸리에 변환(SFT)은 빅데이터 신호 처리를 위한 이산 푸리에 변환(DFT)의 일종이다.특히 GPS 동기화, 스펙트럼 감지 및 아날로그-디지털 변환기에 사용된다.^[1]

FFT(Fast Fourier Transform, FFT)는 특히 신호 처리에서 많은 과학 영역에서 필수적인 역할을 한다.20세기 10대 알고리즘 중 하나이다.^[2]하지만 빅데이터 시대가 도래하면서 더 많은 컴퓨팅 파워를 절약하기 위해서는 여전히 FFT의 개선이 필요하다.최근 희소성 푸리에 변환(SFT)은 신호 성분이 거의 없는 긴 데이터 시퀀스 분석 성능이 뛰어나 상당한 주목을 받고 있다.

정의

복잡한 숫자의 순서 x를_n 생각해 보아라.푸리에 시리즈에 의해 x는_n 다음과 같이 쓰여질 수 있다.

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

마찬가지로 X는_k 다음과 같이 나타낼 수 있다.

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

따라서 위의 방정식에서 매핑은 $F{\displaystyle }$: ${\displaystyle {}^{}}$ N${\displaystyle {}^{}}$→ ${\displaystyle {}^{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\$ \mathb {C} $^{N}}}$이다$.$

단일 주파수 복구

시퀀스에 단일 주파수만 존재한다고 가정하십시오.시퀀스로부터 이 주파수를 회복하기 위해서는 시퀀스의 인접 지점들 사이의 관계를 이용하는 것이 적당하다.

위상 인코딩

위상 k는 시퀀스의 인접 지점을 분할하여 얻을 수 있다.바꾸어 말하면, 환언하면

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

${\displaystyle {}^{}}$ n$math$ C N$${\$displaystyle x_{n}\in$\mathb ${C} ^{N}}$에 주목하십시오$.$

앨리어싱 기반 검색

탐색 단계 k는 중국의 나머지 정리(CRT)에 의해 이루어질 수 있다.^[3]

예를$$ 들어 $k{\displaystyle }$= ${\displaystyle \mathrm{104,134}}$ ${\displaystyle k=104{,}134}$을(를) 예로 들어보자.자, 우리는 100, 101, 103의 비교적 주요한 정수를 세 개 가지고 있다.따라서 방정식은 다음과 같이 설명할 수 있다.

${\displaystyle k=c={,}put\equiv \left\{\bmod{1}{rl}34&{\\bmod{1}1}00,\3&\bmod{1}1}1}{\1&\bmod}{1}}}}}}{\bmod {1}}}}}}}}}03.\end{array}\오른쪽.}$

CRT에 의해, 우리는

${\displaystyle k=sn1}s{,}mod{{}bmod{{}100\cdot 101\cdot 103)=mod{,}mod{1}{,}040{,}300}$

무작위 바이닝 주파수

이제 우리는 단일 주파수 대신 다중 주파수의 경우를 탐구하고자 한다.인접 주파수는 스케일링 c와 변조 b 속성으로 분리할 수 있다.즉, c와 b의 모수를 임의로 선택함으로써 모든 주파수의 분포는 거의 동일한 분포가 될 수 있다.그림 모든 주파수 확산은 임의의 빈도수를 통해 나타나며, 우리는 단일 주파수 회수를 이용하여 주요 구성요소를 찾을 수 있다.

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

여기서 c는 스케일링 속성이고 b는 변조 속성이다.

무작위로 c와 b를 선택함으로써 전체 스펙트럼은 균일한 분포처럼 보일 수 있다.그런 다음 이들을 필터 뱅크로 가져가면 가우시안,^[4] 지표 기능,^[5][6] 스파이크 트레인,^{[7][8][9][10]} 돌프-체비셰프 필터 등 모든 주파수를 분리할 수 있다.^[11]각 은행은 하나의 주파수만 가지고 있다.

표준 SFT

일반적으로 모든 SFT는 세 단계를^[1] 따른다.

주파수 식별

무작위 빈도를 측정함으로써 모든 구성요소를 분리할 수 있다.그런 다음 이들을 필터 뱅크로 가져가 각 대역은 하나의 주파수만 포함하고 있다.이 신호 주파수를 복구하기 위해 우리가 언급한 방법을 사용하는 것이 편리하다.

계수 추정

주파수를 식별한 후에 우리는 많은 주파수 성분을 갖게 될 것이다.우리는 푸리에 변환을 사용하여 그들의 계수를 추정할 수 있다.

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

반복

마지막으로, 이 두 단계를 반복하면 원래의 신호에서 가장 중요한 요소들을 추출할 수 있다.

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

이산형 설정의 스파스 푸리에 변환

2012년 Hassanieh, Indyk, Katabi, Price는 $O{\displaystyle (k}$ ${\displaystyle \log \mathrm{nn}}$ ${\displaystyle \log }$log ${\displaystyle (n}$ /${\displaystyle k}$ $){\displaystyle O(k\log n\log(n/k))}$개의 샘플을$$ 채취하여 동일한 런닝타임에 실행하는 알고리즘을 제안했다.

고차원 환경에서 스파스 푸리에 변환

2014년에, Indyk과 Kapralov[12]. 2016년에서, Kapralov[13]2O(d2)k로그 ⁡와 로그 ⁡ 로그⁡ n{\displaysty 선형적이기 때문의 샘플을 사용합니다 알고리즘을 제안했다, n{n\displaystyle}에 거의 선형 시간을 흐르고 있어 2O(d로그 ⁡ d)k로그⁡ n{\displaystyle 2^{O(d\log d)}k\log n}샘플을 택하는 알고리즘을 제안했다.르 2^{O($d^{2})}k\log n\log \log n}$ and sublinear decoding time ${\displaystyle k\log ^{O(d)}n}$. In 2019, Nakos, Song, and Wang ^[14] introduced a new algorithm which uses nearly optimal samples ${\displaystyle O(k\log n\log k)}$ and requires nearly linear time decoding time.

연속 설정에서 스파스 푸리에 변환

이산 설정을 연속 설정으로 일반화하는 것에 관한 몇 가지 작업이 있다.^[15][16]

구현

MIT, MSU, ETH를 소재로 한 작품들이 여럿 있다.또한, 그들은 온라인에서 무료다.

• MSU 구현
• ETH 구현
• MIT 구현
• 깃헙

추가 읽기

Hassanieh, Haitham (2018). The Sparse Fourier Transform: Theory and Practice. Association for Computing Machinery and Morgan & Claypool. ISBN 978-1-94748-707-9.

Price, Eric (2013). Sparse Recovery and Fourier Sampling. MIT.

참조