Řídká Fourierova transformace - Sparse Fourier transform

The řídká Fourierova transformace (SFT) je druh diskrétní Fourierova transformace (DFT) pro manipulaci velká data signály. Konkrétně se používá v GPS synchronizace, snímání spektra a analogově-digitální převaděče.:^[1]

The rychlá Fourierova transformace (FFT) hraje nepostradatelnou roli v mnoha vědeckých doménách, zejména při zpracování signálu. Je to jeden z top 10 algoritmů ve dvacátém století ^[2]. S příchodem éry velkých dat však musí být FFT ještě vylepšen, aby se ušetřil více výpočetního výkonu. V poslední době si řídká Fourierova transformace (SFT) získala značnou pozornost, protože funguje dobře při analýze dlouhé sekvence dat s několika složkami signálu.

Definice

Zvažte sekvenci X_n z komplexní čísla. Podle Fourierova řada, X_n lze psát jako

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

Podobně, X_k lze reprezentovat jako

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

Z výše uvedených rovnic tedy je mapování ${ displaystyle F: mathbb {C} ^ {N} do mathbb {C} ^ {N}}$.

Obnova jedné frekvence

Předpokládejme, že v sekvenci existuje pouze jedna frekvence. Aby bylo možné tuto frekvenci obnovit ze sekvence, je slušné využít vztah mezi sousedními body sekvence.

Fázové kódování

Fáze k lze získat dělením sousedních bodů posloupnosti. Jinými slovy,

${ displaystyle { frac {x_ {n + 1}} {x_ {n}}} = e ^ {j { frac {2 pi} {N}} k} = cos left ({ frac { 2 pi k} {N}} vpravo) + j sin vlevo ({ frac {2 pi k} {N}} vpravo).}$

Všimněte si toho ${ displaystyle x_ {n} in mathbb {C} ^ {N}}$.

Hledání založené na aliasingu

Hledání založené na aliasingu

Fáze hledání k lze provést pomocí Čínská věta o zbytku (CRT).^[3]

Vzít ${ displaystyle k = 104 {,} 134}$ například. Nyní máme tři relativně prvočísla 100, 101 a 103. Rovnici lze tedy popsat jako

${ displaystyle k = 104 {,} 134 equiv left {{ begin {array} {rl} 34 & { bmod {1}} 00, 3 & { bmod {1}} 01, 1 & { bmod {1}} 03. end {pole}} vpravo.}$

CRT, máme

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

Náhodně binovací frekvence

Rozložte všechny frekvence

Nyní si přejeme prozkoumat případ více frekvencí namísto jedné frekvence. Sousední frekvence lze oddělit podle měřítka C a modulace b vlastnosti. Jmenovitě náhodným výběrem parametrů C a b, rozdělení všech frekvencí může být téměř rovnoměrné rozdělení. Postava Rozložte všechny frekvence odhaluje náhodným kombinačním kmitočtem, můžeme použít obnovu jedné frekvence k hledání hlavních komponent.

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

kde C je měřítko vlastnictví a b je vlastnost modulace.

Náhodným výběrem C a b, může vypadat celé spektrum rovnoměrné rozdělení. Pak je vezmeme filtrovat banky dokáže oddělit všechny frekvence, včetně Gaussianů,^[4] funkce indikátorů,^[5][6] špice vlaky,^{[7][8][9][10]} a Dolph-Chebyshev filtry.^[11] Každá banka obsahuje pouze jednu frekvenci.

Prototyp SFT

Obecně platí, že všechny SFT sledují tři fáze^[1]

Identifikace frekvencí

Náhodně vázanými frekvencemi lze oddělit všechny komponenty. Poté je vezmeme do bank filtrů, takže každé pásmo obsahuje pouze jednu frekvenci. Je vhodné použít metody, které jsme zmínili, k obnovení frekvence tohoto signálu.

Odhad koeficientů

Po identifikaci frekvencí budeme mít mnoho frekvenčních složek. Můžeme použít Fourierovu transformaci k odhadu jejich koeficientů.

${ displaystyle X_ {k} '= { frac {1} {L}} součet _ {l = 1} ^ {L} x_ {n}' e ^ {- j { frac {2 pi} { N}} n ' ell}}$

Opakování

Nakonec opakováním těchto dvou fází můžeme extrahovat nejdůležitější složky z původního signálu.

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

Řídká Fourierova transformace v diskrétním nastavení

V roce 2012 Hassanieh, Indyk, Katabi a Price ^[11] navrhl algoritmus, který trvá ${ displaystyle O (k log n log (n / k))}$ vzorky a běží ve stejné době běhu.

Řídká Fourierova transformace ve vysoko dimenzionálním prostředí

V roce 2014 Indyk a Kapralov ^[12] navrhl algoritmus, který trvá ${ displaystyle 2 ^ {O (d log d)} k log n}$ vzorky a běží v téměř lineárním čase v ${ displaystyle n}$. V roce 2016 Kapralov ^[13] navrhl algoritmus, který používá sublearní vzorky ${ displaystyle 2 ^ {O (d ^ {2})} k log n log log n}$ a sublearní čas dekódování ${ displaystyle k log ^ {O (d)} n}$. V roce 2019 Nakos, Song a Wang ^[14] představil nový algoritmus, který využívá téměř optimální vzorky ${ displaystyle O (k log n log k)}$ a vyžaduje téměř lineární čas dekódování času.

Řídká Fourierova transformace v kontinuálním nastavení

Existuje několik prací o zobecnění diskrétního nastavení na kontinuální nastavení ^{[15] [16]}.

Implementace

Existuje několik prací založených na MIT, MSU, a ETH. Jsou také zdarma online.

• Implementace MSU
• Implementace ETH
• Implementace MIT
• GitHub

Další čtení

Hassanieh, Haitham (2018). Řídká Fourierova transformace: teorie a praxe. Sdružení pro výpočetní techniku ​​a Morgan & Claypool. ISBN  978-1-94748-707-9.

Cena, Eric (2013). Řídké zotavení a Fourierovo vzorkování. MIT. Citovat má prázdný neznámý parametr: |1= (Pomoc)

Reference