畳み込み

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

## 定義

### 一次元

#### 連続
連続関数  の畳み込み  は以下のように定義される：
:(f * g)(t) = \int f(\tau) g(t - \tau)\, d\tau
積分を用いて2つの関数を合わせることから**畳み込み積分**、**合成積**、**重畳積分**とも呼ばれる。

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

#### 離散
離散信号  の畳み込み  は以下のように定義される：
:(f * g)(m) = \sum_n {f(n) \, g(m - n)}

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

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

### 高次元
 上の複素数値函数 と  の畳み込みは、それ自身が  上の複素数値函数として
:(f * g )(x) = \int_{\mathbf{R}^d} f(y)g(x-y)\,dy = \int_{\mathbf{R}^d} f(x-y)g(y)\,dy
で定義されるものであるが、右辺の積分が存在してこれが定義可能となるには、と  が無限遠において十分必要がある。とはいえ、たとえば  が無限遠において爆発するとしても、その影響は  が十分に急減少であれば容易に打ち消すことができるから、この積分の存在条件は込み入ったものも考え得る。この問題をクリアする函数の条件としてよく用いられる場合を以下に挙げる。

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

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

#### 可積分函数
函数  と  がともに''L''<sup>1</sup>('''R'''<sup>''d''</sup>)に属するルベーグ可積分函数ならば、それらの畳み込み  が存在してやはり可積分である。これはトネリの定理の帰結である。このことは  に属する数列の離散畳み込みや、より一般の群上の  の畳み込みでも成立する。

同様にして、  と  が  のとき、  かつ
: \|{f}*g\|_p\le \|f\|_1\|g\|_p
を満たす。特に  のとき、これにより  は畳み込みを積としてバナッハ代数を成す(また、等号成立は  と  がともに殆ど至る所非負のときである)。
 
より一般に、畳み込みに対するヤングの不等式により、畳み込み積は適当な -空間上の連続双線型演算となることが従う。具体的に書けば、  が
: \frac{1}{p}+\frac{1}{q}=\frac{1}{r}+1
なる関係を満足するとして、
: \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))
となるから、畳み込み積は  なる連続双線型写像を定めている。

畳み込みに対するヤングの不等式、循環畳み込みや離散畳み込みなどほかの文脈でも成立する。また、  上では先に掲げた不等式はより厳しく評価できる: 先と同様の関係を持つ  に対し、定数  が存在して
: \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})).
 の最適値は Beckner (1975) にある。より強い評価として  に対し
: \lVert f*g\rVert_r \le C_{p,q}\lVert f\rVert_p\,\lVert g\rVert_{q,w}
も得られる。ただし、  は弱 -ノルムである。  に対し弱い版のヤング不等式
: \|f*g\|_{r,w}\le C_{p,q}\|f\|_{p,w}\|g\|_{r,w}
を考えれば、畳み込みは連続双線型写像 L^{p,w}(\mathbb{R})\times L^{q,w}(\mathbb{R})\to L^{r,w}(\mathbb{R}) とも見られる。

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

#### 分布

適当な条件の下で、函数と分布あるいは分布同士の畳み込みが定義できる。  がコンパクト台付き函数で  が分布ならば  は、函数の畳み込みの式を分布版にした
: \int_{\mathbf{R}^d} f(x-y)dG(y)
で定義される滑らかな函数である ( が密度函数  を持てば通常の函数の畳み込みに書き直せる)。より一般に、試験函数  に対して結合律
: f*(g*\varphi) = (f*g)*\varphi
が成り立つような一意的な方法で畳み込みの定義を拡張することができて、それは  が分布、  がコンパクト台付き分布のときには有効である。

#### 測度
二つの有界変動ボレル測度  と  の畳み込みとは、
: \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)
で定義される測度  を言う。これは  と  を分布と見るとき、前節にいう分布の畳み込みに一致する。また  と  がルベーグ測度に関して絶対連続であるとき、それらの密度函数の -函数としての畳み込みとも一致する。

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

### 群上の畳み込み
適当な測度  を備えた群  とその上の実または複素数値ルベーグ可積分函数  と  が与えられれば、それらの畳み込みを
: (f * g)(x) = \int_G f(y) g(y^{-1}x)\,d\lambda(y)
で定義することができる。しかし一般には可換性が成り立たないことに注意すべきである。

#### 局所コンパクト群上の不変積分の場合
典型的な場合として、  が局所コンパクトハウスドルフ位相群で  が左ハール測度（左不変測度）の場合である。右不変測度  に対しても同様の積分
: \int f(xy^{-1})g(y) \, d\rho(y)
を考えることができるが、  が単模でないならば両者は一致しない。前者の定義では、固定した函数  による畳み込みが群への左移動作用と可換:
: L_h(f*g) = (L_hf)*g
となることからよく選ばれる。さらにこの定義では後で述べる測度の畳み込みの定義と矛盾しない。一方、左不変ではなく右不変測度を取り、後者の定義を用いれば右移動作用と可換になる。

#### よく知られた例の導出
局所コンパクトアーベル群上で、ある種の (畳み込みのフーリエ変換はフーリエ変換の点ごとの積に一致する) が成立する。

円周群  にルベーグ測度を考えたものはよく知られた循環畳み込みの場合の例を与える:  を固定して、ヒルベルト空間  に作用するよく知られた作用素:
: T {f}(x) =  \frac{1}{2 \pi} \int_{\mathbf{T}} {f}(y) g( x - y) \, dy
がとれる。作用素  はコンパクト作用素である。直接計算により、その随伴作用素  は  による畳み込みであることが示せる。上で掲げた可換性により、  は正規作用素 ( である。また  は平行移動作用素とも可換である。そのような畳み込み作用素と平行移動作用素全体の成す作用素族を  とすれば、  は正規作用素からなる可換族である。ヒルベルト空間上のスペクトル論に従えば、  を同時対角化する正規直交基底  が存在して、これが円周上の畳み込みを特徴付ける。具体的には
: h_k (x) = e^{ikx} \quad (k \in \mathbb{Z})
がちょうど  の指標の全体の成す集合に一致する。この基底に属する各畳み込み作用素がコンパクト乗算作用素であることが、上で述べた循環畳み込みに対する畳み込み定理としてみることができる。

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

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

#### 群上の測度の畳み込み
位相群  上の有限ボレル測度  と  に対し、それらの畳み込み  は  の各可測部分集合  に対して
: (\mu * \nu)(E) = \iint 1_E(xy) \,d\mu(x) \,d\nu(y)
で定義され、やはり有限測度となる。実際、全変動に関するヤングの不等式
:\lVert\mu * \nu\rVert \le \lVert\mu\rVert\,\lVert\nu\rVert
が満足される。  が局所コンパクト群で左ハール測度  を持ち、  と  が  に関して絶対連続で各々密度函数を持つ場合には、畳み込み  もまた絶対連続で、その密度函数は各測度の密度函数の (通常の函数としての) 畳み込みに一致する。

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

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

* 交換律: f*g = g*f
* 結合律: (f*g)*h = f*(g*h)
* 分配律: f*(g+h) = (f*g) + (f*h) 
* スカラー倍: a(f*g) = (a f)*g = f*(a g), *a* は任意の複素数。
* 微分: {\rm D}(f*g) = {\rm D}f*g = f*{\rm D}g,  は微分演算子（離散系の場合は ）
* : \mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g), \mathcal{F}(f) はフーリエ変換

### 畳み込み定理
は次の式で示される。  

:\mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g)

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

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

### 離散時間信号
離散時間信号の畳み込み和は定義通りの畳み込み計算でなく、を利用して計算される場合が多い。

離散時間信号では高速フーリエ変換 (FFT) を用いることで少ない計算量でフーリエ変換を実行できる。ゆえに関数  を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直線畳み込み」と同義である。

## 応用

### 確率測度における畳み込み
集合関数の一種である確率測度の畳み込みは次のように表現される。確率測度  において任意のボレル集合  に対し、
:(\mu_1 *\mu_2 )(B) = \int 1_B (x +y)\ \mu_1(dx)\mu_2(dy)
と表現される。ここで1*B*は*B*の定義関数である。これは  を集合関数として捉えて、変数変換することで求まる。これにより、 を分布に持つ確率変数  においてその和  の分布が畳み込みにあたることが分かる。

### 多項式の掛け算
多項式の掛け算の結果の係数列は、元の多項式の係数列の線形畳み込みになる。実際
:
 \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

であり、掛け算の結果の係数が  となる。

### 線形システム
電気回路といった古典的な時不変（シフト不変）線形システムは、任意の入力  に対する出力  が  とインパルス応答  の畳み込みで記述できる：
:y(t) = h(t) * x(t)
ここで特に、入力  がデルタ関数  のとき出力は  そのものになる。

ここで上式の両辺をフーリエ変換もしくはラプラス変換（離散系の場合はZ変換）すると畳み込み定理より下式のようになる。
:Y = H X
ここで、
:H = \frac{Y}{X} 
を伝達関数といい、この式は古典制御論の基礎となっている。

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

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

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

### 統計学
 がそれぞれ独立な連続型確率変数とすると、和の S=X+Y の確率密度関数は畳み込みによって与えられる。 の確率密度関数をそれぞれ f_X, f_Y と表記すると、 の密度関数は以下の式で与えられる。

f_S (s) = \int^{\infty}_{-\infty} f_X(x) f_Y(s - x)\, dx

## 歴史
畳み込み積分が用いられた最初期の例の一つは d'Alembert (1754) *Recherches sur différents points importants du système du monde* におけるテイラーの定理の導出にある。また
: \int f(u)\cdot g(x-u)\mathit{du}
の形の式は  *Treatise on differences and series* の505頁で用いられ、そのすぐ後にLaplace、Fourier、Poissonらの研究に畳み込み演算が現れている。名称自体が広く用いられるようになるには1950年代あるいは1960年代を待たなければならない。それに先立っては（「畳み込み」）、*composition product*（「合成積」）、 *superposition integral*（「重ね合わせ積分」）などとも呼ばれ、あるいはカールソンの積分 (*Carson's integral*)
とも言った。現代的な定義がより古い用例に馴染むわけでもないが、それでも早くは1903年ごろには出現している。

合成積の特別の場合としての演算
: \int_0^t\varphi(s)\psi(t-s)\mathit{ds} \quad (0\le t
は 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.
* 
* 
*
* .

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

## 外部リンク
* 
* 
* 
* 
* 
* 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.