Grafik Fourier Dönüşümü - Graph Fourier Transform

Bu makale bir yetim, başka hiçbir makale olmadığı gibi ona bağlantı. Lütfen bağlantıları tanıtmak dan bu sayfaya İlgili Makaleler; dene Bağlantı bul aracı öneriler için. (Ağustos 2020)

İçinde matematik, grafik Fourier dönüşümü bir matematiksel dönüşüm hangi eigende kompoze Laplacian matrisi bir grafiğin içine Özdeğerler ve özvektörler. Benzer şekilde klasik Fourier Dönüşümü özdeğerler temsil eder frekanslar ve özvektörler grafik olarak bilinenleri oluşturur Fourier temeli.

Graph Fourier dönüşümü, spektral grafik teorisi. Son zamanlarda yapılan grafik yapılandırmasında yaygın olarak kullanılmaktadır. öğrenme algoritmaları yaygın olarak kullanılanlar gibi evrişimli ağlar.

Tanım

Verilen bir yönsüz ağırlıklı grafik ${ displaystyle G = (V, E)}$, nerede ${ displaystyle V}$ ile düğüm kümesidir ${ displaystyle | V | = N}$ (${ displaystyle N}$ düğüm sayısı) ve ${ displaystyle E}$ kenar kümesidir, bir grafik sinyalidir ${ displaystyle f: V rightarrow mathbb {R}}$ grafiğin köşelerinde tanımlanan bir fonksiyondur ${ displaystyle G}$. Sinyal ${ displaystyle f}$ her köşeyi eşler ${ displaystyle {v_ {i} } _ {i = 1, cdots, N}}$ bir gerçek Numara ${ displaystyle f (i)}$. Herhangi bir grafik sinyali, özvektörler of Laplacian matrisi ${ displaystyle L}$.^[1] İzin Vermek ${ displaystyle lambda _ {l}}$ ve ${ displaystyle mu _ {l}}$ ol ${ displaystyle l _ { text {th}}}$ özdeğer ve özvektör Laplacian matris ${ displaystyle L}$ (özdeğerler artan bir sırada sıralanır, yani, ${ displaystyle 0 = lambda _ {0} leq lambda _ {1} leq cdots leq lambda _ {N-1}}$^[2]), grafik Fourier dönüşümü (GFT) ${ displaystyle { şapka {f}}}$ bir grafik sinyalinin ${ displaystyle f}$ köşelerinde ${ displaystyle G}$ genişlemesi ${ displaystyle f}$ açısından özfonksiyonlar nın-nin ${ displaystyle L}$.^[3] Şu şekilde tanımlanır:^[1][4]

${ displaystyle { mathcal {GF}} [f] ( lambda _ {l}) = { hat {f}} sol ( lambda _ {l} sağ) = langle f, mu _ { l} rangle = toplam _ {i = 1} ^ {N} f (i) mu _ {l} ^ {*} (i),}$

nerede ${ displaystyle mu _ {l} ^ {*} = mu _ {l} ^ { text {T}}}$.

Dan beri ${ displaystyle L}$ bir gerçek simetrik matris, özvektörleri ${ displaystyle { mu _ {l} } _ {l = 0, cdots, N-1}}$ erkek için ortogonal temel. Bu nedenle bir ters grafik Fourier dönüşümü (IGFT) vardır ve şu şekilde yazılır:^[4]

${ displaystyle { mathcal {I}} { mathcal {G}} { mathcal {F}} [{ hat {f}}] (i) = f (i) = sum _ {l = 0} ^ {N-1} { hat {f}} left ( lambda _ {l} sağ) mu _ {l} (i)}$

Klasike benzer şekilde Fourier dönüşümü, grafik Fourier dönüşümü, bir sinyali iki farklı alanda temsil etmenin bir yolunu sağlar: köşe alanı ve grafik spektral alan. Grafik Fourier dönüşümü ve tersinin tanımının, mutlaka benzersiz olmayan Laplacian özvektörlerinin seçimine bağlı olduğuna dikkat edin.^[3] Normalleştirilmiş Laplacian matrisinin özvektörleri, aynı zamanda ileri ve ters grafik Fourier dönüşümünü tanımlamak için olası bir temeldir.

Özellikleri

Parseval'in Kimliği

Parseval ilişkisi Fourier dönüşümü grafiği için tutar,^[5] yani, herhangi biri için ${ displaystyle f, h in mathbb {R} ^ {N}}$

${ displaystyle langle f, h rangle = langle { hat {f}}, { hat {g}} rangle.}$

Bu bize verir Parseval'ın kimliği:^[3]

${ displaystyle toplamı _ {i = 1} ^ {N} | f (i) | ^ {2} = | f | _ {2} ^ {2} = langle f, f rangle = langle { hat {f}}, { hat {f}} rangle = | { hat {f}} | _ {2} ^ {2} = toplam _ {l = 0} ^ {N- 1} left | { hat {f}} left ( lambda _ {l} sağ) sağ | ^ {2}.}$

Genelleştirilmiş Evrişim Operatörü

Tanımı kıvrım iki işlev arasında ${ displaystyle f}$ ve ${ displaystyle g}$ doğrudan grafik sinyallerine uygulanamaz çünkü sinyal çevirisi grafikler bağlamında tanımlanmamıştır.^[4] Ancak, kompleksi değiştirerek üstel kayma Grafik Laplacian özvektörleri ile klasik Fourier Dönüşümünde, iki grafik sinyalinin evrişimi şu şekilde tanımlanabilir:^[3]

${ displaystyle (f * g) = { mathcal {I}} { mathcal {G}} { mathcal {F}} [{ mathcal {G}} { mathcal {F}} [(f * g )]],}$

${ displaystyle (f * g) (i) = toplamı _ {l = 0} ^ {N-1} { şapka {f}} sol ( lambda _ {l} sağ) { şapka {g }} left ( lambda _ {l} sağ) u_ {l} (i).}$

Evrişim operatörünün özellikleri

Genelleştirilmiş evrişim operatörü aşağıdaki özellikleri karşılar:^[3]

• Köşe etki alanındaki genelleştirilmiş evrişim, grafik spektral etki alanındaki çarpmadır: ${ displaystyle { widehat {f * g}} = { şapka {f}} { şapka {g}}.}$
• Değişebilirlik: ${ displaystyle f * g = g * f}$
• DAĞILMA: ${ displaystyle f * (g + h) = f * g + f * h}$
• İlişkisellik: ${ displaystyle (f * g) * h = f * (g * h)}$
• Skaler çarpımla ilişkilendirilebilirlik: ${ displaystyle alpha (f * g) = ( alpha f) * g = f * ( alpha g)}$, herhangi ${ displaystyle alpha in mathbb {R}}$.
• Çarpımsal kimlik: ${ displaystyle f * g_ {0} = f}$, nerede ${ displaystyle g_ {0} (i) = toplam _ {l = 0} ^ {N-1} mu _ {l} (i)}$ genelleştirilmiş evrişim operatörü için bir kimliktir.
• İki sinyalin genelleştirilmiş konvolüsyonunun toplamı, iki sinyalin toplamının çarpımı olan sabit bir çarpıdır:

${ displaystyle toplamı _ {i = 1} ^ {N} (f * g) (i) = { sqrt {N}} { hat {f}} (0) { hat {g}} (0 ) = { frac {1} { sqrt {N}}} left [ sum _ {i = 1} ^ {N} f (i) right] left [ sum _ {i = 1} ^ {N} g (i) sağ].}$

Genelleştirilmiş Çeviri Operatörü

Daha önce belirtildiği gibi, klasik çeviri operatörü ${ displaystyle T_ {v}}$ grafik ayarına genelleştirilemez. Genelleştirilmiş bir çeviri operatörünü tanımlamanın bir yolu, tepe noktasında merkezlenmiş bir delta işlevi ile genelleştirilmiş evrişimdir. ${ displaystyle n}$:^[2]${ displaystyle sol (T_ {n} f sağ) (i) = { sqrt {N}} sol (f * delta _ {n} sağ) (i) {=} { sqrt {N }} toplam _ {l = 0} ^ {N-1} { hat {f}} left ( lambda _ {l} right) u_ {l} ^ {*} (n) u_ {l} (ben),}$

nerede ${ displaystyle delta _ {i} (n) = sol {{ başla {dizi} {ll} 1, & { text {if}} i = n 0, & { text {aksi halde} } end {dizi}} sağ ..}$

Normalleştirme sabiti ${ displaystyle { sqrt {N}}}$ çeviri operatörünün sinyal ortalamasını korumasını sağlar,^[4] yani

${ displaystyle toplamı _ {i = 1} ^ {N} sol (T_ {n} f sağ) (i) = toplamı _ {i = 1} ^ {N} f (i).}$

Çeviri operatörünün özellikleri

Genelleştirilmiş evrişim operatörü aşağıdaki özellikleri karşılar:^[3]

Herhangi ${ displaystyle f, g in mathbb {R} ^ {N}}$, ve ${ displaystyle j, k in {1,2, noktalar, N }}$,

• ${ displaystyle T_ {j} (f * g) = sol (T_ {j} f sağ) * g = f * sol (T_ {j} g sağ)}$
• ${ displaystyle T_ {j} T_ {k} f = T_ {k} T_ {j} f}$
• ${ displaystyle toplamı _ {i = 1} ^ {N} sol (T_ {j} f sağ) (i) = { sqrt {N}} { şapka {f}} (0) = toplamı _ {i = 1} ^ {N} f (i)}$
• ${ displaystyle sol | T_ {j} f sağ | neq | f |}$

Başvurular

Görüntü sıkıştırma

Sinyalleri temsil etmek frekans alanı veri sıkıştırmaya yönelik yaygın bir yaklaşımdır. Grafik sinyalleri, grafik spektral alanında seyrek olabildiğinden, grafik Fourier dönüşümü ayrıca aşağıdakiler için de kullanılabilir: görüntü sıkıştırma.^[6][7]

Grafik gürültü azaltma

Klasik benzer gürültü azaltma Fourier dönüşümüne dayalı sinyallerin grafik filtreleri Graph Fourier dönüşümü temel alınarak grafik sinyal denoising için tasarlanabilir.^[8]

Veri sınıflandırması

Graph Fourier dönüşümü grafiklerde evrişimin tanımlanmasını sağladığından, geleneksel olanı uyarlamayı mümkün kılar. evrişimli sinir ağları (CNN) grafikler üzerinde çalışmak için. Grafik yapılandırılmış yarı denetimli öğrenme grafik gibi algoritmalar evrişimli ağ (GCN), bir grafik sinyalinin etiketlerini küçük bir etiketli düğüm alt kümesiyle grafik boyunca yayabilir.^[9]

Araç Kutusu

GSPBOX^[10][11] için bir alet kutusu sinyal işleme Grafik Fourier dönüşümü dahil olmak üzere grafiklerde. İkisini de destekler Python ve MATLAB Diller.

Ayrıca bakınız

• Fourier dönüşümü
• Laplacian matrisi
• Spektral grafik teorisi

Referanslar

Dış bağlantılar

• DeepGraphLibrary Grafik sinir ağlarının kolay uygulanması için oluşturulmuş ücretsiz bir Python paketi.