畳み込み

2つの正方形による畳み込み。解として得る波形は三角波となる。黄色の領域で示されている面積が2つの方形波の合成積である。

正方形がRC回路に入力された場合の出力信号波形を得るために、RC回路のインパルス応答と方形波の畳み込みを行っている。 黄色の領域で示されている面積が合成積である。

畳み込み（たたみこみ、テンプレート:Lang-en-short）とは、関数 テンプレート:Mvar を平行移動しながら関数 テンプレート:Mvar に重ね足し合わせる二項演算である。あるいはコンボリューションとも呼ばれる。

定義

一次元

連続

連続関数 テンプレート:Math の畳み込み テンプレート:Math は以下のように定義される：

$(f*g)(t)=\int f(\tau )g(t-\tau )d\tau$

積分を用いて2つの関数を合わせることから畳み込み積分、合成積、重畳積分とも呼ばれる。

積分範囲は関数の定義域に依存する。通常は区間 テンプレート:Math で定義される関数を扱うことが多いので、積分範囲は テンプレート:Math から テンプレート:Math で計算されることが多い。一方 テンプレート:Math が有限区間でしか定義されない場合には、テンプレート:Math が定義域内に入るように テンプレート:Math を周期関数と見なして計算される。この周期関数と見なして畳み込みをすることを循環畳み込み（じゅんかんたたみこみ、テンプレート:Lang-en-short）と呼ぶ。

離散

離散信号 テンプレート:Math の畳み込み テンプレート:Math は以下のように定義される：

$(f*g)(m)=\sum _{n}f(n)g(m-n)$

すなわち積分のかわりに総和を使って同様に定義される。そのため畳み込み和・重畳和とも呼ばれる。

総和の範囲も関数の定義域に依存し、関数が有限区間でしか定義されていない場合は周期関数とみなして畳み込み演算が行われる。また定義域外の値を 0 と定義し直した関数での畳み込みがよく行われる。これを線形畳み込み（せんけいたたみこみ、テンプレート:Lang-en-short）あるいは直線畳み込み（ちょくせんたたみこみ）と呼ぶ。

高次元

テンプレート:Math 上の複素数値函数 テンプレート:Mvarと テンプレート:Mvar の畳み込みは、それ自身が テンプレート:Math 上の複素数値函数として

$(f*g)(x)=\underset{{𝐑}^d}{\int }f(y)g(x-y)dy=\underset{{𝐑}^d}{\int }f(x-y)g(y)dy$

で定義されるものであるが、右辺の積分が存在してこれが定義可能となるには、テンプレート:Mvarと テンプレート:Mvar が無限遠において十分テンプレート:仮リンク必要がある。とはいえ、たとえば テンプレート:Mvar が無限遠において爆発するとしても、その影響は テンプレート:Mvar が十分に急減少であれば容易に打ち消すことができるから、この積分の存在条件は込み入ったものも考え得る。この問題をクリアする函数の条件としてよく用いられる場合を以下に挙げる。

コンパクト台付き函数

函数 テンプレート:Mvar と テンプレート:Mvar がともにコンパクト台連続函数ならば、それらの畳み込みは存在して、やはりコンパクト台連続函数となるテンプレート:Sfn。より一般に、一方がコンパクト台、他方が局所可積分函数ならば、畳み込み テンプレート:Math が定義されて連続である。

テンプレート:Math 上では両者が局所自乗可積分の場合、あるいは両者がともに半無限区間 テンプレート:Math (あるいはともに テンプレート:Math) に台を持つ場合でも畳み込みが定まる。

可積分函数

函数 テンプレート:Mvar と テンプレート:Mvar がともにL¹(R^d)に属するルベーグ可積分函数ならば、それらの畳み込み テンプレート:Math が存在してやはり可積分であるテンプレート:Sfn。これはトネリの定理の帰結である。このことは テンプレート:Math に属する数列の離散畳み込みや、より一般の群上の テンプレート:Math の畳み込みでも成立する。

同様にして、 テンプレート:Math と テンプレート:Math が テンプレート:Math のとき、 テンプレート:Math かつ

$\Vert f*g{\Vert }_p\le \Vert f{\Vert }_1\Vert g{\Vert }_p$

を満たす。特に テンプレート:Math のとき、これにより テンプレート:Math は畳み込みを積としてバナッハ代数を成す(また、等号成立は テンプレート:Mvar と テンプレート:Mvar がともに殆ど至る所非負のときである。)

より一般に、畳み込みに対するヤングの不等式により、畳み込み積は適当な テンプレート:Mvar-空間上の連続双線型演算となることが従う。具体的に書けば、 テンプレート:Math が

$\frac{1}{p}+\frac{1}{q}=\frac{1}{r}+1$

なる関係を満足するとして、

$\Vert f*g{\Vert }_r\le \Vert f{\Vert }_p\Vert g{\Vert }_q(f\in L^p({ℝ}^d),g\in L^q({ℝ}^d))$

となるから、畳み込み積は テンプレート:Math なる連続双線型写像を定めている。

畳み込みに対するヤングの不等式、循環畳み込みや離散畳み込みなどほかの文脈でも成立する。また、 テンプレート:Math 上では先に掲げた不等式はより厳しく評価できる: 先と同様の関係を持つ テンプレート:Math に対し、定数 テンプレート:Math が存在して

$\Vert f*g{\Vert }_r\le B_{p,q}\Vert f{\Vert }_p\Vert g{\Vert }_q(f\in L^p(ℝ),g\in L^q(ℝ)).$

テンプレート:Math の最適値は Beckner (1975) にある。より強い評価として テンプレート:Math に対し

$\Vert f*g{\Vert }_r\le C_{p,q}\Vert f{\Vert }_p\Vert g{\Vert }_{q,w}$

も得られる。ただし、 テンプレート:Math は弱 テンプレート:Mvar-ノルムである。 テンプレート:Math に対し弱い版のヤング不等式

$\Vert f*g{\Vert }_{r,w}\le C_{p,q}\Vert f{\Vert }_{p,w}\Vert g{\Vert }_{r,w}$

を考えれば、畳み込みは連続双線型写像 $L^{p,w}(ℝ)\times L^{q,w}(ℝ)\to L^{r,w}(ℝ)$ とも見られるテンプレート:Sfn。

急減少函数

コンパクト台付きや可積分な函数と同様に、函数が無限遠で十分テンプレート:仮リンクすれば畳み込みができて、それらの畳み込みもまた急速に減少することは重要な性質である。とくに テンプレート:Mvar と テンプレート:Mvar が急減少函数ならば、それらの畳み込み テンプレート:Math もまた急減少函数となる。このことを、畳み込みが微分と可換であるという事実と組み合わせれば、シュヴァルツ函数のクラスが畳み込みで閉じていることが導かれるテンプレート:Sfn。

分布

テンプレート:Main article 適当な条件の下で、函数と分布あるいは分布同士の畳み込みが定義できる。 テンプレート:Mvar がコンパクト台付き函数で テンプレート:Mvar が分布ならば テンプレート:Math は、函数の畳み込みの式を分布版にした

$\underset{{𝐑}^d}{\int }f(x-y)dG(y)$

で定義される滑らかな函数である (テンプレート:Mvar が密度函数 テンプレート:Mvar を持てば通常の函数の畳み込みに書き直せる)。より一般に、試験函数 テンプレート:Mvar に対して結合律

$f*(g*\phi )=(f*g)*\phi$

が成り立つような一意的な方法で畳み込みの定義を拡張することができて、それは テンプレート:Mvar が分布、 テンプレート:Mvar がコンパクト台付き分布のときには有効であるテンプレート:Sfn。

測度

二つの有界変動ボレル測度 テンプレート:Mvar と テンプレート:Mvar の畳み込みとは、

$\underset{{𝐑}^d}{\int }f(x)d\lambda (x)=\underset{{𝐑}^d}{\int }\underset{{𝐑}^d}{\int }f(x+y)d\mu (x)d\nu (y)$

で定義される測度 テンプレート:Mvar を言うテンプレート:Sfn。これは テンプレート:Mvar と テンプレート:Mvar を分布と見るとき、前節にいう分布の畳み込みに一致する。また テンプレート:Mvar と テンプレート:Mvar がルベーグ測度に関して絶対連続であるとき、それらの密度函数の テンプレート:Math-函数としての畳み込みとも一致する。

測度の畳み込みは、測度のテンプレート:仮リンクをノルムとして

$\Vert \mu *\nu \Vert \le \Vert \mu \Vert \Vert \nu \Vert$

を満たすという意味でのヤングの不等式が成立する。有界変動測度の空間はバナッハ空間であるから、測度の畳み込みは函数解析学の標準的な (分布の畳み込みに対しては適用できない) 方法で扱うことができる。

群上の畳み込み

適当な測度 テンプレート:Mvar を備えた群 テンプレート:Mvar とその上の実または複素数値ルベーグ可積分函数 テンプレート:Mvar と テンプレート:Mvar が与えられれば、それらの畳み込みを

$(f*g)(x)=\underset{G}{\int }f(y)g(y^{-1}x)d\lambda (y)$

で定義することができる。しかし一般には可換性が成り立たないことに注意すべきである。

局所コンパクト群上の不変積分の場合

典型的な場合として、 テンプレート:Mvar が局所コンパクトハウスドルフ位相群で テンプレート:Mvar が左ハール測度（左不変測度）の場合である。右不変測度 テンプレート:Mvar に対しても同様の積分

$\int f(x{y}^{-1})g(y)d\rho (y)$

を考えることができるが、 テンプレート:Mvar が単模でないならば両者は一致しない。前者の定義では、固定した函数 テンプレート:Mvar による畳み込みが群への左移動作用と可換:

$L_h(f*g)=(L_{h}f)*g$

となることからよく選ばれる。さらにこの定義では後で述べる測度の畳み込みの定義と矛盾しない。一方、左不変ではなく右不変測度を取り、後者の定義を用いれば右移動作用と可換になる。

よく知られた例の導出

局所コンパクトアーベル群上で、ある種のテンプレート:仮リンク (畳み込みのフーリエ変換はフーリエ変換の点ごとの積に一致する) が成立する。

円周群 テンプレート:Math にルベーグ測度を考えたものはよく知られた循環畳み込みの場合の例を与える: テンプレート:Math を固定して、ヒルベルト空間 テンプレート:Math に作用するよく知られた作用素:

$Tf(x)=\frac{1}{2\pi }\underset{𝐓}{\int }f(y)g(x-y)dy$

がとれる。作用素 テンプレート:Mvar はコンパクト作用素である。直接計算により、その随伴作用素 テンプレート:Math は テンプレート:Math による畳み込みであることが示せる。上で掲げた可換性により、 テンプレート:Mvar は正規作用素 (テンプレート:Math である。また テンプレート:Mvar は平行移動作用素とも可換である。そのような畳み込み作用素と平行移動作用素全体の成す作用素族を テンプレート:Mvar とすれば、 テンプレート:Mvar は正規作用素からなる可換族である。ヒルベルト空間上のスペクトル論に従えば、 テンプレート:Mvar を同時対角化する正規直交基底 テンプレート:Math が存在して、これが円周上の畳み込みを特徴付ける。具体的には

$h_k(x)=e^{ikx}(k\in \mathbb{Z})$

がちょうど テンプレート:Math の指標の全体の成す集合に一致する。この基底に属する各畳み込み作用素がコンパクト乗算作用素であることが、上で述べた循環畳み込みに対する畳み込み定理としてみることができる。

離散畳み込みの例は位数 テンプレート:Mvar の有限巡回群をとる。この場合の畳み込み作用素は巡回行列によって表現され、離散フーリエ変換によって対角化することができる。

同様の結果が (アーベルとは限らない) コンパクト群 テンプレート:Mvar に対しても知られている: 有限次元ユニタリ表現の行列要素の全体が テンプレート:Math の正規直交基底を成し (テンプレート:仮リンク)、適当な意味での畳み込み定理が (フーリエ変換に基づく調和解析の他の多くの側面とともに) 引き続き満足される。

群上の測度の畳み込み

位相群 テンプレート:Mvar 上の有限ボレル測度 テンプレート:Mvar と テンプレート:Mvar に対し、それらの畳み込み テンプレート:Math は テンプレート:Mvar の各可測部分集合 テンプレート:Mvar に対して

$(\mu *\nu )(E)=\iint 1_E(xy)d\mu (x)d\nu (y)$

で定義され、やはり有限測度となる。実際、全変動に関するヤングの不等式

$\Vert \mu *\nu \Vert \le \Vert \mu \Vert \Vert \nu \Vert$

が満足される。 テンプレート:Mvar が局所コンパクト群で左ハール測度 テンプレート:Mvar を持ち、 テンプレート:Mvar と テンプレート:Mvar が テンプレート:Mvar に関して絶対連続で各々密度函数を持つ場合には、畳み込み テンプレート:Math もまた絶対連続で、その密度函数は各測度の密度函数の (通常の函数としての) 畳み込みに一致する。

考える位相群が実数の加法群 テンプレート:Math のとき、その上の確率測度 テンプレート:Mvar と テンプレート:Mvar をとれば、測度の畳み込み テンプレート:Math は、分布 テンプレート:Mvar および テンプレート:Mvar に従う独立確率変数 テンプレート:Mvar および テンプレート:Mvar の和 テンプレート:Math の確率分布に対応する。

性質

積分演算に由来する性質として以下の性質がある。

• 交換律: $f*g=g*f$
• 結合律: $(f*g)*h=f*(g*h)$
• 分配律: $f*(g+h)=(f*g)+(f*h)$
• スカラー倍: $a(f*g)=(af)*g=f*(ag)$, a は任意の複素数。
• 微分: $\mathrm{D}(f*g)=\mathrm{D}f*g=f*\mathrm{D}g$, テンプレート:Math は微分演算子（離散系の場合は テンプレート:Math）
• テンプレート:仮リンク: $ℱ(f*g)=ℱ(f)\cdot ℱ(g)$, $ℱ(f)$ はフーリエ変換

畳み込み定理

テンプレート:仮リンクは次の式で示される。

$ℱ(f*g)=ℱ(f)\cdot ℱ(g)$

ここで $ℱ(f)$ はフーリエ変換である。この定理によりフーリエ変換を使って畳み込み演算を単純な掛け算に変換することが出来る。この定理はラプラス変換・Z変換やメリン変換といった変換に対しても適用できる。

計算

畳み込み演算を実際に計算する際には様々な技法が利用される。

離散時間信号

離散時間信号の畳み込み和は定義通りの畳み込み計算でなく、テンプレート:仮リンクを利用して計算される場合が多い。

離散時間信号では高速フーリエ変換 (FFT) を用いることで少ない計算量でフーリエ変換を実行できる。ゆえに関数 テンプレート:Math をFFTにより周波数表現へ変換し、その積を取って、最後にIFFTで時間表現へ戻すことで高速に畳み込み和を計算できる。

有限直線畳み込み

有限長信号の直線畳み込みは「範囲外が0埋めされた関数」と見なすことで通常の直線畳み込み演算を適用できる。しかし値が0と事前に確定している領域を実際に計算するのは無駄であり、実践的には有限区間に限って計算がおこなわれる。畳み込みは2つの関数を重ね合わせる演算であるため「0埋めした領域を畳み込んだ場合に出力扱いするか」にバリエーションが存在する。以下はその一例である。

• valid: 両関数が非ゼロの領域のみ出力 (L=N-M+1)
• full: 両関数が非ゼロでない限り出力 (L=N+M-1)
• same: 中央部分を入力と同じ長さだけ出力 (L=N)

fullは「両側 M-1 ゼロパディング+valid直線畳み込み」と同義であり、sameは「両側 (M-1)/2 ゼロパディング+valid直線畳み込み」と同義である。

応用

確率測度における畳み込み

集合関数の一種である確率測度の畳み込みは次のように表現される。確率測度 テンプレート:Math において任意のボレル集合 テンプレート:Mvar に対し、

$({\mu }_1*{\mu }_2)(B)=\int 1_B(x+y){\mu }_1(dx){\mu }_2(dy)$

と表現される。ここで1_BはBの定義関数である。これは テンプレート:Math を集合関数として捉えて、変数変換することで求まる。これにより、テンプレート:Math を分布に持つ確率変数 テンプレート:Math においてその和 テンプレート: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 となる。

線形システム

電気回路といった古典的な時不変（シフト不変）線形システムは、任意の入力 テンプレート:Math に対する出力 テンプレート:Math が テンプレート:Math とインパルス応答 テンプレート:Math の畳み込みで記述できる：

$y(t)=h(t)*x(t)$

ここで特に、入力 テンプレート:Math がデルタ関数 テンプレート:Math のとき出力は テンプレート:Math そのものになる。

ここで上式の両辺をフーリエ変換もしくはラプラス変換（離散系の場合はZ変換）すると畳み込み定理より下式のようになる。

$Y=HX$

ここで、

$H=\frac{Y}{X}$

を伝達関数といい、この式は古典制御論の基礎となっている。

音響学

エコーは元の音波と、音を反射するさまざまな物体に因る特性（インパルス応答）との畳み込みで記述される。カラオケやシンセサイザーに搭載されているエコー機能は、この畳み込みの効果を電気回路もしくはコンピュータでシミュレートすることで実現している。

光学および画像処理

撮像時のブレなどの多くのぶれ (blur) は畳み込みで記述できる。例えば、ピントがぼけた写真は、ピントがあった仮想的な画像と、絞りの特性を示す円との畳み込みである。また被写体等の動きによるブレも、静止した仮想的な画像と動きの特性との畳み込みであり、グラフィックソフトウェアのモーションブラーはこの畳み込み演算を計算によりシミュレートすることで実現している。

画像認識においても、異なるスケールの画像を認識するにあたり、畳み込みでぶれをつくってから、画像処理することがある。

統計学

テンプレート:Math がそれぞれ独立な連続型確率変数とすると、和の $S=X+Y$ の確率密度関数は畳み込みによって与えられる。テンプレート:Math の確率密度関数をそれぞれ $f_X,f_Y$ と表記すると、テンプレート:Math の密度関数は以下の式で与えられる。

$f_S(s)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}{f}_X(x)f_Y(s-x)dx$

歴史

畳み込み積分が用いられた最初期の例の一つは d'Alembert (1754) Recherches sur différents points importants du système du monde におけるテイラーの定理の導出にあるテンプレート:Sfn。また

$\int f(u)\cdot g(x-u)𝑑𝑢$

の形の式は テンプレート:仮リンク Treatise on differences and seriesテンプレート:Efn の505頁で用いられテンプレート:Sfn、そのすぐ後にLaplace、Fourier、Poissonらの研究に畳み込み演算が現れている。名称自体が広く用いられるようになるには1950年代あるいは1960年代を待たなければならない。それに先立ってはテンプレート:Lang-de（「畳み込み」）、composition product（「合成積」）、 superposition integral（「重ね合わせ積分」）などとも呼ばれ、あるいはカールソンの積分 (Carson's integral) とも言った。現代的な定義がより古い用例に馴染むわけでもないが、それでも早くは1903年ごろには出現している。

合成積の特別の場合としての演算

$\underset{0}{\overset{t}{\int }}\phi (s)\psi (t-s)𝑑𝑠(0\le t<\mathrm{\infty })$

は Volterra (1913) "Leçons sur les fonctions de lignes" にある

参考文献

• 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.
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation.

関連項目

• 逆畳み込み
• ブラインド・デコンボリューション
• インパルス応答 - 伝達関数
• フーリエ変換 - ラプラス変換
• 軟化子
• 基本解
• 自己回帰移動平均モデル
• 巡回行列
• アナログ信号処理
• コーシー積
• 積和演算

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:MathWorld
• テンプレート:PlanetMath
• テンプレート:SpringerEOM
• テンプレート:SpringerEOM
• 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.