畳み込み
畳み込み（たたみこみ、英: convolution）とは関数 g を平行移動しながら関数 f に重ね足し合わせる二項演算である。畳み込み積分、合成積、重畳積分、あるいは英語に倣いコンボリューションとも呼ばれる。
Contents
歴史
畳み込み積分が用いられた最初期の例の一つは d'Alembert (1754) Recherches sur différents points importants du système du monde におけるテイラーの定理の導出にある[1]。また
- [math]\int f(u)\cdot g(x-u)\mathit{du}[/math]
の形の式は Lacroix Treatise on differences and series[注釈 1] の505頁で用いられ[2]、そのすぐ後にLaplace, Fourier, Poissonらの研究に畳み込み演算が現れている。名称自体が広く用いられるようになるには1950年代あるいは1960年代を待たなければならない。それに先立ってはドイツ語: faltung（「畳み込み」）、composition product（「合成積」）、 superposition integral（「重ね合わせ積分」）などとも呼ばれ、あるいはカールソンの積分 (Carson's integral)[3] とも言った。現代的な定義がより古い用例に馴染むわけでもないが、それでも早くは1903年ごろには出現している[4][5]。
合成積の特別の場合としての演算
- [math]\int_0^t\varphi(s)\psi(t-s)\mathit{ds} \quad (0\le t\lt \infty)[/math]
は Volterra (1913) "Leçons sur les fonctions de linges" にある[6]
一次元
定義
関数 f, g の畳み込みは f ∗ g と書き、以下のように定義される：
- [math](f * g)(t) = \int f(\tau) g(t - \tau)\, d\tau[/math]
積分範囲は関数の定義域に依存する。通常は区間 (−∞, +∞) で定義される関数を扱うことが多いので、積分範囲は −∞ から +∞ で計算されることが多い。一方 f, g が有限区間でしか定義されない場合には、g(t − τ) が定義域内に入るように f, g を周期関数と見なして計算される。この周期関数と見なして畳み込みをすることを循環畳み込み（じゅんかんたたみこみ、英: cyclic convolution）と呼ぶ。
離散値で定義された関数に対する畳み込みは、積分のかわりに総和を使って同様に定義される：
- [math](f * g)(m) = \sum_n {f(n) \, g(m - n)}[/math]
総和の範囲も関数の定義域に依存し、関数が有限区間でしか定義されていない場合は周期関数とみなして畳み込み演算が行われる。また、離散系の場合、定義域外の値を 0 と定義し直した関数での畳み込みをよく行われる。これを線形畳み込み（せんけいたたみこみ、英: linear convolution）と呼ぶ。線形畳み込みは直線畳み込み（ちょくせんたたみこみ）とも呼ばれる。なお離散系の場合は積分を使わずに総和を使うので、畳み込み積分・重畳積分とは呼ばず、畳み込み和・重畳和と呼ぶ。
性質
積分演算に由来する性質として以下の性質がある。
- 交換律
- [math]f*g = g*f[/math]
- 結合律
- [math](f*g)*h = f*(g*h)[/math]
- 分配律
- [math]f*(g+h) = (f*g) + (f*h) [/math]
- スカラー倍
- [math]a(f*g) = (a f)*g = f*(a g)[/math]
- ただし、a は任意の実数または複素数。
- 微分
- [math]{\rm D}(f*g) = {\rm D}f*g = f*{\rm D}g[/math]
- ただし、D は微分演算子（離散系の場合は Df(n) = f(n + 1) − f(n)）。
- 畳み込み定理
- [math]\mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g)[/math]
ただし [math]\mathcal{F}(f)[/math] は関数 f のフーリエ変換である。この定理はラプラス変換・Z変換やメリン変換といった変換に対しても適用できる。
フーリエ変換を使って畳み込み演算を単純な掛け算に変換することが出来る。離散系での関数の場合、定義通りの畳み込み計算をしないで、関数 f, g の高速フーリエ変換 (FFT) を掛け算した結果を逆高速フーリエ変換 (IFFT) をすることで、高速に畳み込みの計算処理をするのが一般的である。
応用
確率測度における畳み込み
集合関数の一種である確率測度の畳み込みは次のように表現される。確率測度 μ1, μ2 において任意のボレル集合 B に対し、
- [math](\mu_1 *\mu_2 )(B) = \int 1_B (x +y)\ \mu_1(dx)\mu_2(dy)[/math]
と表現される．ここで1BはBの定義関数である．これは μ1, μ2 を集合関数として捉えて、変数変換することで求まる。これにより、μ1, μ2 を分布に持つ確率変数 X, Y においてその和 X + Y の分布が畳み込みにあたることが分かる。
多項式の掛け算
多項式の掛け算の結果の係数列は、元の多項式の係数列の線形畳み込みになる。実際
- [math] \left(\sum_{i=0}^m a_i x^i \right)\left(\sum_{j=0}^l b_j x^j\right) = \sum_{k=0}^{m+l}\left(\sum_{i+j=k} a_i b_j \right)x^k = \sum_{k=0}^{m+l}\left(\sum_{i=0}^k a_i b_{k-i} \right)x^k [/math]
であり、掛け算の結果の係数が a*b となる。
線形システム
電気回路といった古典的な時不変（シフト不変）線形システムは、任意の入力 x(t) に対する出力 y(t) が x(t) とインパルス応答 h(t) の畳み込みで記述できる：
- [math]y(t) = h(t) * x(t)[/math]
ここで特に、入力 x(t) がデルタ関数 δ(t) のとき出力は h(t) そのものになる。
ここで上式の両辺をフーリエ変換もしくはラプラス変換（離散系の場合はZ変換）すると、#畳み込み定理より下式のようになる。
- [math]Y = H X[/math]
ここで、
- [math]H = \frac{Y}{X}[/math]
音響学
エコーは元の音波と、音を反射するさまざまな物体に因る特性（インパルス応答）との畳み込みで記述される。カラオケやシンセサイザーに搭載されているエコー機能は、この畳み込みの効果を電気回路もしくはコンピュータでシミュレートすることで実現している。
光学および画像処理
撮像時のブレなどの多くのぶれ (blur) は畳み込みで記述できる。例えば、ピントがぼけた写真は、ピントがあった仮想的な画像と、絞りの特性を示す円との畳み込みである。また被写体等の動きによるブレも、静止した仮想的な画像と動きの特性との畳み込みであり、グラフィックソフトウェアのモーションブラーはこの畳み込み演算を計算によりシミュレートすることで実現している。
画像認識においても、異なるスケールの画像を認識するにあたり、畳み込みでぶれをつくってから、画像処理することがある。
統計学
X, Y がそれぞれ独立な連続型確率変数とすると、和の [math]S=X+Y[/math] の確率密度関数は畳み込みによって与えられる。X, Y の確率密度関数をそれぞれ [math]f_X, f_Y[/math] と表記すると、S の密度関数は以下の式で与えられる.
[math]f_S (s) = \int^{\infty}_{-\infty} f_X(x) f_Y(s - x)\, dx[/math]
高次元
Rd 上の複素数値函数 f, g の畳み込みは、それ自身が Rd 上の複素数値函数として
- [math](f * g )(x) = \int_{\mathbf{R}^d} f(y)g(x-y)\,dy = \int_{\mathbf{R}^d} f(x-y)g(y)\,dy[/math]
で定義されるものであるが、右辺の積分が存在してこれが定義可能となるには、f, g が無限遠において十分急速に減少する必要がある。とはいえ、例えば g が無限遠において爆発するとしても、その影響は f が十分に急減少ならば容易に打ち消すことができるから、この積分の存在条件は込み入ったものも考え得る。この問題をクリアする函数の条件としてよく用いられる場合を以下に挙げる。
コンパクト台付き函数
f と g がともにコンパクト台連続函数ならば, それらの畳み込みは存在して, やはりコンパクト台連続函数となる[7]. より一般に, 一方がコンパクト台, 他方が局所可積分函数ならば, 畳み込み f ∗ g が定義されて連続である.
R 上では両者が局所自乗可積分の場合, あるいは両者がともに半無限区間 テンプレート:Closed-open (あるいはともに テンプレート:Open-closed) に台を持つ場合でも畳み込みが定まる.
可積分函数
f と g がともにL1(Rd)に属するルベーグ可積分函数ならば, それらの畳み込み f ∗ g が存在してやはり可積分である[8]. これはトネリの定理の帰結である. このことは ℓ1 に属する数列の離散畳み込みや、より一般の群上の L1 の畳み込みでも成立する.
同様にして, f ∈ L1(Rd) と g ∈ Lp(Rd) が 1 ≤ p ≤ ∞ のとき, f ∗ g ∈ Lp(Rd) かつ
- [math]\|{f}*g\|_p\le \|f\|_1\|g\|_p[/math]
を満たす. 特に p = 1 のとき, これにより L1 は畳み込みを積としてバナッハ代数を成す. (また, 等号成立は f と g がともに殆ど至る所非負のときである.)
より一般に, 畳み込みに対するヤングの不等式により, 畳み込み積は適当な Lp-空間上の連続双線型演算となることが従う. 具体的に書けば, 1 ≤ p,q,r ≤ ∞ が
- [math]\frac{1}{p}+\frac{1}{q}=\frac{1}{r}+1[/math]
なる関係を満足するとして,
- [math]\lVert f*g\rVert_{r} \le \lVert f \rVert_{p}\,\lVert g\rVert_{q} \quad (f\in L^p(\mathbb{R}^d),\,g\in L^q(\mathbb{R}^d))[/math]
となるから, 畳み込み積は Lp × Lq → Lr なる連続双線型写像を定めている.
畳み込みに対するヤングの不等式は, 循環畳み込みや離散畳み込みなどほかの文脈でも成立する. また, R 上では先に掲げた不等式はより厳しく評価できる: 先と同様の関係を持つ 1 < p, q, r < ∞ に対し, 定数 Bp,q < 1 が存在して
- [math]\lVert f*g\rVert _{r}\le B_{p,q}\lVert f\rVert _{p}\,\lVert g\rVert _{q}\quad (f\in L^p(\mathbb{R}),\,g\in L^q(\mathbb{R})).[/math]
Bp,q の最適値は Beckner (1975) にある[9]. より強い評価として 1 < p, q, r < ∞ に対し
- [math]\lVert f*g\rVert_r \le C_{p,q}\lVert f\rVert_p\,\lVert g\rVert_{q,w}[/math]
も得られる. ただし, テンプレート:Normq,w は弱 Lp-ノルムである. 1 < p, q, r < ∞ に対し弱い版のヤング不等式
- [math]\|f*g\|_{r,w}\le C_{p,q}\|f\|_{p,w}\|g\|_{r,w}[/math]
を考えれば, 畳み込みは連続双線型写像 [math]L^{p,w}(\mathbb{R})\times L^{q,w}(\mathbb{R})\to L^{r,w}(\mathbb{R})[/math] とも見られる[10].
急減少函数
コンパクト台付きや可積分な函数と同様に、函数が無限遠で十分急速に減少すれば畳み込みができて, それらの畳み込みもまた急速に減少することは重要な性質である. とくに f と g が急減少函数ならば, それらの畳み込み f ∗ g もまた急減少函数となる. このことを, 畳み込みが微分と可換であるという事実と組み合わせれば, シュヴァルツ函数のクラスが畳み込みで閉じていることが導かれる[11].
分布
適当な条件の下で, 函数と分布あるいは分布同士の畳み込みが定義できる. f がコンパクト台付き函数で G が分布ならば f ∗ G は, 函数の畳み込みの式を分布版にした
- [math]\int_{\mathbf{R}^d} f(x-y)dG(y)[/math]
で定義される滑らかな函数である (G が密度函数 g を持てば通常の函数の畳み込みに書き直せる). より一般に, 試験函数 φ に対して結合律
- [math]f*(g*\varphi) = (f*g)*\varphi[/math]
が成り立つような一意的な方法で畳み込みの定義を拡張することができて, それは f が分布, g がコンパクト台付き分布のときには有効である[12].
測度
- [math]\int_{\mathbf{R}^d} f(x)d\lambda(x) = \int_{\mathbf{R}^d}\int_{\mathbf{R}^d}f(x+y)\,d\mu(x)\,d\nu(y)[/math]
で定義される測度 λ を言う[13]. これは μ と ν を分布と見るとき, 前節にいう分布の畳み込みに一致する. また μ と ν がルベーグ測度に関して絶対連続であるとき, それらの密度函数の L1-函数としての畳み込みとも一致する.
測度の畳み込みは, 測度の全変動をノルムとして
- [math]\lVert\mu*\nu\rVert \le \lVert\mu\rVert\,\lVert\nu\rVert[/math]
を満たすという意味でのヤングの不等式が成立する. 有界変動測度の空間はバナッハ空間であるから, 測度の畳み込みは函数解析学の標準的な (分布の畳み込みに対しては適用できない) 方法で扱うことができる.
群上の畳み込み
適当な測度 λ を備えた群 G とその上の実または複素数値ルベーグ可積分函数 f と g が与えられれば, それらの畳み込みを
- [math](f * g)(x) = \int_G f(y) g(y^{-1}x)\,d\lambda(y)[/math]
で定義することができる. しかし一般には可換性が成り立たないことに注意すべきである.
局所コンパクト群上の不変積分の場合
典型的な場合として, G が局所コンパクトハウスドルフ位相群で λ が左ハール測度（左不変測度）の場合である. 右不変測度 ρ に対しても同様の積分
- [math]\int f(xy^{-1})g(y) \, d\rho(y)[/math]
を考えることができるが, G が単模でないならば両者は一致しない. 前者の定義では, 固定した函数 g による畳み込みが群への左移動作用と可換:
- [math]L_h(f*g) = (L_hf)*g[/math]
となることからよく選ばれる. さらにこの定義では後で述べる測度の畳み込みの定義と矛盾しない. 一方, 左不変ではなく右不変測度を取り, 後者の定義を用いれば右移動作用と可換になる.
よく知られた例の導出
局所コンパクトアーベル群上で, ある種の畳み込み定理 (畳み込みのフーリエ変換はフーリエ変換の点ごとの積に一致する) が成立する.
円周群 T にルベーグ測度を考えたものはよく知られた循環畳み込みの場合の例を与える: g ∈ L1(T) を固定して, ヒルベルト空間 L2(T) に作用するよく知られた作用素:
- [math]T {f}(x) = \frac{1}{2 \pi} \int_{\mathbf{T}} {f}(y) g( x - y) \, dy[/math]
がとれる. 作用素 T はコンパクト作用素である. 直接計算により, その随伴作用素 T* は g(−y) による畳み込みであることが示せる. 上で掲げた可換性により, T は正規作用素 (T*T = TT* である. また T は平行移動作用素とも可換である. そのような畳み込み作用素と平行移動作用素全体の成す作用素族を S とすれば, S は正規作用素からなる可換族である. ヒルベルト空間上のスペクトル論に従えば, S を同時対角化する正規直交基底 {hk} が存在して, これが円周上の畳み込みを特徴付ける. 具体的には
- [math]h_k (x) = e^{ikx} \quad (k \in \mathbb{Z})[/math]
がちょうど T の指標の全体の成す集合に一致する. この基底に属する各畳み込み作用素がコンパクト乗算作用素であることが, 上で述べた循環畳み込みに対する畳み込み定理としてみることができる.
離散畳み込みの例は位数 n の有限巡回群をとる. この場合の畳み込み作用素は巡回行列によって表現され, 離散フーリエ変換によって対角化することができる.
同様の結果が (アーベルとは限らない) コンパクト群 G に対しても知られている: 有限次元ユニタリ表現の行列要素の全体が L2(G) の正規直交基底を成し (ピーター–ワイルの定理), 適当な意味での畳み込み定理が (フーリエ変換に基づく調和解析の他の多くの側面とともに) 引き続き満足される.
群上の測度の畳み込み
位相群 G 上の有限ボレル測度 μ と ν に対し, それらの畳み込み μ ∗ ν は G の各可測部分集合 E に対して
- [math](\mu * \nu)(E) = \iint 1_E(xy) \,d\mu(x) \,d\nu(y)[/math]
で定義され, やはり有限測度となる. 実際, 全変動に関するヤングの不等式
- [math]\lVert\mu * \nu\rVert \le \lVert\mu\rVert\,\lVert\nu\rVert[/math]
が満足される. G が局所コンパクト群で左ハール測度 λ を持ち, μ と ν が λ に関して絶対連続で各々密度函数を持つ場合には、畳み込み μ ∗ ν もまた絶対連続で, その密度函数は各測度の密度函数の (通常の函数としての) 畳み込みに一致する.
考える位相群が実数の加法群 (R, +) のとき, その上の確率測度 μ と ν をとれば, 測度の畳み込み μ ∗ ν は, 分布 μ および ν に従う独立確率変数 X および Y の和 X + Y の確率分布に対応する.
注釈
- ↑ 百科辞典シリーズ Traité du calcul différentiel et du calcul intégral, Chez Courcier, Paris, 1797-1800. の最後の三巻
出典
- ↑ Dominguez-Torres 2010, p. 2.
- ↑ Dominguez-Torres 2010, p. 4.
- ↑ R. N. Bracewell (2005), “Early work on imaging theory in radio astronomy”, in W. T. Sullivan, The Early Years of Radio Astronomy: Reflections Fifty Years After Jansky's Discovery, Cambridge University Press, p. 172, ISBN 978-0-521-61602-7
- ↑ John Hilton Grace and Alfred Young (1903), The algebra of invariants, Cambridge University Press, p. 40
- ↑ Leonard Eugene Dickson (1914), Algebraic invariants, J. Wiley, p. 85
- ↑ Lothar von Wolfersdorf (2000), "Einige Klassen quadratischer Integralgleichungen", Sitzungsberichte der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-naturwissenschaftliche Klasse, volume 128, number 2, 6–7
- ↑ Hörmander 1983, Chapter 1.
- ↑ Stein & Weiss 1971, Theorem 1.3.
- ↑ Beckner, William (1975), "Inequalities in Fourier analysis", Ann. of Math. (2) 102: 159–182. Independently, Brascamp, Herm J. and Lieb, Elliott H. (1976), "Best constants in Young's inequality, its converse, and its generalization to more than three functions", Advances in Math. 20: 151–173. See Brascamp–Lieb inequality
- ↑ Reed & Simon 1975, IX.4.
- ↑ Stein & Weiss 1971, Theorem 3.3.
- ↑ Hörmander 1983, §4.2.
- ↑ Rudin 1962.
参考文献
- Dominguez-Torres, Alejandro (Nov 2, 2010). "Origin and history of convolution". 41 pgs. http://www.slideshare.net/Alexdfar/origin-adn-history-of-convolution. Cranfield, Bedford MK43 OAL, UK. Retrieved Mar 13, 2013.
- Hörmander, L. (1983), The analysis of linear partial differential operators I, Grundl. Math. Wissenschaft., 256, Springer, ISBN 3-540-12104-8, MR 0717035
- Stein, Elias; Weiss, Guido (1971), Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press, ISBN 0-691-08078-X
- Reed, Michael; Simon, Barry (1975), Methods of modern mathematical physics. II. Fourier analysis, self-adjointness, New York-London: Academic Press Harcourt Brace Jovanovich, Publishers, pp. xv+361, ISBN 0-12-585002-6, MR 0493420
- Rudin, Walter (1962), Fourier analysis on groups, Interscience Tracts in Pure and Applied Mathematics, No. 12, Interscience Publishers (a division of John Wiley and Sons), New York–London, ISBN 0-471-52364-X, MR 0152834.
関連項目
外部リンク
- Weisstein, Eric W. “Convolution”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。
- convolution - PlanetMath.（英語）
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- {{#invoke:citation/CS1|citation
|CitationClass=citation }}
- The Joy of Convolution Java Applet を使った視覚的な畳み込みの説明
- Examples of sampled impulse responses to be used in convolution reverbs (Fokke Van Saane)
- Examples of impulse responses synthesized from oscillator spectra, to be used in convolution reverbs (Emmanuel Deruty)
- BruteFIR; A software for applying long FIR filters to multi-channel digital audio, either offline or in realtime.
- Freeverb3 Reverb Impulse Response Processor: DSP library with convolution engines.