STA Chapter2 part2

Sublinear Time Algorithms

Estimating the Number of Connected Components

Connected Components(連結成分,以下c.cと書く)
  • c.c内の任意の二点間を結ぶパスが存在する。
  • 異なるc.c間にはいかなるパスも存在しない。

問題設定

入力
  • 無向グラフG(V,E)
  • 制限 \led
目標

c.cの数をcとしたとき、εd-additiveとは見積もった数yが、
c - \epsilon n \le y \le c + \epsilon n
をみたすこと。

文字の定義および、整理

n_{u}をuに含まれるc.cのノードの数とする。
このとき、任意のc.c　A ⊆ Vに関して
\sum_{u \in A} \frac{1}{n_{u}} = \sum_{u \in A} \frac{1}{|A|} = 1
また、
c = \sum_{u \in V} \frac{1}{n_{u}}
\hat{n}_{u} = \mathrm{min} \left{ n_{u} \: , \: \frac{2}{\epsilon} \right} \; , \; \hat{c} = \sum_{u \in V} \frac{1}{\hat{n}_{u}
とすると、
| \frac{1}{n_{u}} - \frac{1}{\hat{n}_{u}} | \le \frac{2}{\epsilon}
となる。
\hat{n}_{u} = n_{u}のときは0、\hat{n}_{u} = \frac{2}{\epsilon}のとき、\frac{2}{\epsilon} < n_{u} \leftrightarrow \frac{\epsilon}{2} - \frac{1}{n_{u}} > 0
これより、シグマをとって
| c - \hat{c} | \le \frac{\epsilon n}{2}

アルゴリズム

estimate_cc(u)

　uからBFS(幅優先探索)を走らせる。
　　c.c全体を見つける
　　2/ε個の異なるノードを見つける
　いずれかを満たしたらノードの数を出力する。
estimate_cc(u)の計算時間
O \left( \frac{d}{\epsilon} \right)
各ノードから出るエッジの数はせいぜいdであるため。

approx_num_cc(G,ε)

　 U = \left{ u_{1}, u_{2}, \ldots , u_{r} \right} , r = \Theta \left( \frac{1}{\epsilon~{3}} \right) で集合Ｕを選ぶ
　各u∈Uに関して、estimate_cc(u)を用い、\hat{n}_{u}を求める。
　\tilde{c} = \frac{n}{r}\sum_{n \in U}\frac{1}{\hat{n}_{u}}を出力
approx_num_cc(G,ε)の計算時間
O \left( \frac{1}{\epsilon^{3}}\frac{d}{\epsilon} \right) = O \left( \frac{d}{\epsilon^{4} \right)

Pr \left( | \tilde{c} - \hat{c} | \le \frac{\epsilon n}{2} \right) \ge \frac{3}{4}の証明

Chernoff boundにおいて
p = E \left[ \frac{1}{\hat{n}_{ui} \right] ,\; S = \sum_{i=1}^{r}\frac{1}{\hat{n}_{ui}} , \; m=r, \; \delta = \frac{\epsilon}{2}とおく、
\tilde{c} = \frac{n}{r}\sum_{n \in U}\frac{1}{\hat{n}_{u}} ,\; E \left[ \frac{1}{\hat{n}_{ui}} \right] = \frac{1}{n}\sum_{i=1}^{n} \frac{1}{\hat{n}_{ui}} = \frac{\hat{c}}{n} ,\; r = \Theta \left( \frac{1}{\epsilon^{3}} \right)
であることに注意すると、
Pr \left( | \frac{1}{r} \sum_{i=1}^{r} \frac{1}{\hat{n}_{ui}} - E \left[ \frac{1}{\hat{n}_{ui} \right] | \ge \frac{\epsilon}{2} E \left[ \frac{1}{\hat{n}_{ui}} \right] \right) \le \exp{ \left( -\Omega \left( rE \left[ \frac{1}{\hat{n}_{ui}} \right] \left( \frac{\epsilon}{2}p \right) \right) \right) }
Pr \left( | \frac{\tilde{c}}{n} - \frac{\hat{c}}{n} | \ge \frac{\epsilon}{2} \frac{\hat{c}}{n} \right) = Pr \left( | \frac{\tilde{c}}{n} - \frac{\hat{c}}{n} | \ge \frac{\epsilon\hat{c}}{2} \right) \le \exp{ \left( - \Omega \left( r \frac{\hat{c}}{n} \left( \frac{\epsilon}{2} \right)^{2} \right) \right) } =\exp{ \left( - \Omega \left( \frac{1}{\epsilon}\frac{\hat{c}}{n} \right) \right) }
定義より、
\frac{\epsilon}{2} \le \frac{1}{\hat{n}_{u}} \le 1 , \; \frac{\epsilon n}{2} \le \hat{c} \le n
よって、
Pr \left( | \tilde{c} - \hat{c} | \ge \frac{\epsilon n}{2} \right) \ge exp{ \left( - \Omega \left( 1 \right) \right) } < \frac{1}{4}
ここで、
| c - \hat{c} | \le \frac{\epsilon n}{2} , | c - \hat{c} | \le |c-\hat{c}| + |\tilde{c} - \hat{c}|より
Pr \left( | c - \tilde{c} | \le \epsilon n \right) = Pr \left( | \tilde{c} - \hat{c} | \le \frac{\epsilon n}{2} \right) \ge \frac{3}{4}

STA Chapter2 part1

Sublinear Time Algorithms
Sublinear Time Algorithms Lecture2

やる内容

  • Chernoff bound
  • Estimating the number of connected components
  • Estimating the weight of the minimum spanning tree

Chernoff bound

Let X_{1},X_{2},\ldots,X_{m} be m independent identically distributed random variables such that X_{i} \in \left[ 0,1 \right] .
\mathrm{Let} \;\; S = \sum_{i=1}^{m} X_{i}\;\; \mathrm{and} \;\; p = E\left[ X_{i} \right] = \frac{E \left[ S \right]}{m}.
Then,
Pr \left( |{\frac{s}{m} - p| \geq \delta p \right) \leq e^{-\Omega\big( m p \delta^2\big)} .

ってわかるか！と、
もとの資料がさくっとしか書いていなかったので、調べた事を。

Chernoff bound

確率論における確率の上限を与える不等式
前述の式はm個のサンプリングの点をとったとき、それが本当の平均とδ以上割合ずれる確率が指数関数で抑えられるという話。
確率の上限を与える不等式として、

  • Marcovの不等式
  • Chevyshefの不等式
  • Chernoff bound

の三つの話をする。

Marcovの不等式

Xを非負の確率変数とする。任意のa>0に対し、
Pr \left( X \ge a \right) \le \frac{E \left[ X \right]}{a}
が成り立つ。

証明

a>0に対し、
I = \left{ 1 \;\; X \ge a \\ 0 \;\; else
X \ge a, a> 0より
I \le \frac{X}{a}
E \left[ I \right] = Pr \left( I = 1 \right) = Pr \left( X \ge a \right)
平均をとると
Pr \left( X \ge a \right) = E\left[ I \right] \le E \left[ \frac{X}{a} \right] = \frac{ E\left[ X \right]}{a}

Chebyshevの不等式

任意のa>0に対し
Pr \left( | X - E\left[ X \right] | \right) \le \frac{Var \left[ X \right]}{a^{2}}
が成り立つ。

証明

Pr \left( | X - E\left[ X \right] | \ge a \right) = Pr \left( | X - E\left[ X \right] |^{2} \ge a^{2} \right)
Marcovの不等式より
Pr \left( | X - E\left[ X \right] |^{2} \ge a^{2} \right) \le \frac{E\left[ \left( X - E\left[ X \right] \right)^{2} \right]}{a^{2}} = \frac{Var \left[ X \right]}{a^{2}}

ちなみにこの不等式から大数の法則が導ける.(大雑把に言うと、サンプルの数を増やせば増やす程サンプルの平均は理論上の平均に近くなるという話)

Chernoff bound

確率変数Xの積率母関数
M_{X}(t) = E \left[ exp{tX} \right]
を定義する。

Xの生じる確率をpとすると
\begin{align} M_{X}(t) & = & E \left[ exp{tX} \right] \\ & = & p exp{t} + \left( 1 - p \right) \\ & = & 1 + p \left( exp{t} - 1 \right)\\ & \le & e^{p \left( e^{t} - 1 \right) } \end{align}
任意のt > 0 に対して、
Pr \left( X \ge a \right) = Pr \left( exp{tX} \ge exp{ta} \right) \le \frac{E \left[ exp{tX} \right]}{exp{a}}
任意のt<0に対して、
Pr \left( X \le a \right) = Pr \left( exp{tX} \ge exp{ta} \right) \le \frac{E \left[ exp{tX} \right]}{exp{a}}
ここで、
X_{1},X_{2},\ldots,X_{m} を互いに独立で同一の分布に従うランダムに選んだm個のサンプルとする。X_{i} \in \left[ 0,1 \right] .
Pr \left( X_{i} = 1 \right) = p_{i}とし、 S = \sum_{i=1}^{m} X_{i}\;\; \mathrm{and} \;\; p = E\left[ X_{i} \right] = \frac{E \left[ S \right]}{m}. とする。
任意のδ>0に対して、
\begin{align} Pr \left( \frac{S}{m} \ge \left( 1 + \delta \right) p \right) & = & Pr \left( S \ge \left( 1 + \delta \right) mp \right) \\ & = & Pr \left( exp{tS} \ge exp{ \left( 1 + \delta \right) mtp} \right) \\ & \le & \frac{E \left[ exp{tS} \right] }{exp{\left( 1 + \delta \right) mtp}} \\ & \le & \frac{exp{\left( e^{t} - 1 \right) mp}}{exp{\left( 1 + \delta \right) mtp}} \end{align}
t= \log{\left( 1 + \delta \right) } > 0 と設定し、式を整理すると
Pr \left( \frac{S}{m} \ge \left( 1 + \delta \right) p \right) \le \left( \frac{exp{\delta}}{\left( 1 + \delta \right)^{\left( 1 + \delta \right)}} \right)^{mp}
特に 0 < \delta \le 1について、
\frac{exp{\delta}}{\left( 1 + \delta \right)^{\left( 1 + \delta \right)}} \le exp{-\frac{\delta^{2}}{3}}
が成立する。(対数とって右辺引く左辺をして微分をしたら確かめられる)
ここから、
Pr \left( \frac{S}{m} \ge \left( 1 + \delta \right) p \right) \le exp{ - \frac{m\delta^{2}p}{3}
が成立する。
Pr \left( \frac{S}{m} \le \left( 1 - \delta \right) p \right) についても同様に考えると、
Pr \left( \frac{S}{m} \le \left( 1 - \delta \right) p \right) \le \left( \frac{exp{\delta}}{\left( 1 - \delta \right)^{\left( 1 - \delta \right)}} \right)^{mp} \le exp{ - \frac{m\delta^{2}p}{2} }
以上より、
Pr \left( | \frac{S}{m} - p | \ge \delta p \right) \le exp{ - \Omega \left( m\delta^{2}p \right) }
となる。

STA Chapter1 part3

Sublinear Time Algorithms

Graph connectivity

入力：　G = (V,E), n = |V| , m = |E| , bounded degree d*1 グラフはn×dの隣接行列で与えられる
目的：　グラフが連結グラフか？

目的を以下のように変更する

Gが連結性にε-closeとは、Gを連結するのに高々εdn本の枝を足せばよいことを言う。

作りたいアルゴリズム*2
  • if Gが連結 then accept 1
  • if Gがε-far-from 連結 then reject 3/4

アルゴリズム

  1. O(1/εd)のノード(頂点)をランダムに選ぶ。
  2. 各ノードsに関して幅優先探索を行う
    1. \ge \frac{2}{\epsilon d}をみたすノードが見つかる
    2. sがサイズ \le \frac{2}{\epsilon d}の連結グラフ
  3. もし2.2が起きたらGをrejectして停止
  4. そうでなければaccept

O \left( \frac{1}{\epsilon d} \times \frac{2}{\epsilon d} \times d \right) = O \left( \frac{1}{\epsilon^{2} d} \right)

もし、Gがε-farならばGはεdnの連結成分*3を持つ.
もし、Gがεdn未満のc.cをもつならばGはε-close
ということになる。
すなわち、εdn-1本足すとGは連結にできる。

このことから、
Gは少なくとも \frac{\epsilon dn}{2}個でサイズは最大でも \frac{2}{\epsilon d}であるc.cをもつことになる。

もし、これが成り立たないと仮定すると
Gは少なくとも \frac{\epsilon dn}{2}個で \frac{2}{\epsilon d}以上のサイズであるc.cをもつ
これは、
頂点数　> \frac{\epsilon dn}{2} \times \frac{2}{\epsilon d} = nとなり矛盾。

Gが連結ならば、rejeectが起きないので100% accept
Gがε-far-fromならば、
\mathrm{Prob [ fail ]} \ge 1 - \mathrm{Prob [ pass ]} \ge 1 - {\left( 1 - \frac{\epsilon d}{2} \right) }^{O(1 / \epsilon d)} \ge 1 - e^{-c'} \ge \frac{3}{4}
となる。

*1:nもmもdより少ない

*2:このようなアルゴリズムをone-sided error algorithmという

*3:c.cと表記する

STA Chapter1 part2

Sublinear Time Algorithms

Point-set diameter

distance matrix -> 距離行列について
配列iと配列jの距離を記述（iとjの距離がDij）

  • >対称行列である（iとjの距離＝jとiの距離）

以下を満たす

  1. d_{ii} = 0
  2. d_{ij} \ge 0
  3. d_{ij} \le d_{ik} + d_{kj}

入力：　m×m距離行列d
目的：　直径 \hat{d} \overset{\underset{\mathrm{def}}{\;}}{=} max_{u,v} d(u,v)を求める。

アルゴリズム

  1. x \in Vを適当に取る
  2. d(x,y) が最大となるyを選ぶ
  3. z=d(x,y)として出力する。

行列全部を調べるとm×m回かかるが、これはm回調べるだけでよい。
すなわち O \left( \sqrt{\mathrm{input \: size}} \right) ですむ。
この際zの取りうる値は
\frac{\hat{d}}{2} \le z \le \hat{d}
である。
右の不等式は定義より明らか。左の不等式の証明は
\hat{d} = d(a,b) \le d(a,x) + d(x,b) \le d(x,a) + d(x,b) \le d(x,y) + d(x,y) = 2z.
となる。

Sequence monotonicity

入力：　x_{1},\cdots ,x_{n} 要素の集合（半順序つき）
目的：　単調？　すなわち、x_{1}\le x_{2}\le \cdots \le x_{n}

この問題から以下のように設定を変更する。

入力：　x_{1},\cdots ,x_{n} 要素の集合（半順序つき）
目的：　単調に近い（ε-close)　すなわち、大きさ(1-ε)nの単調増加部分列がある。
例　n = 5 ε = 2/5　で　1 4 2 5 3という列、ここで1 　 2 　 3　は大きさ3の単調部分列

BPPのtester
  • if x_{1},\cdots ,x_{n}が単調 then 3/4の確率で正解を出す。
  • if x_{1},\cdots ,x_{n}が大きさ(1-ε)nの単調増加部分列がない。 then 3/4の確率で失敗を出す。

ここでいう3/4は本質的にあまり意味がなく、1/2より大きく1より小さければよい。
というのもテストを定数回繰り返し正解と失敗のうち、多いほうが問題に対する入力の答えとなるため。

単純なアイディア１

ランダムにi＜jを満たすi,jをとりx_{i} < x_{j}をみたすか調べる。
\Omega(\sqrt{(n})})かかる。*1

理由：

\underbrace{c, c-1, \dots, 1},\underbrace{2c, 2c-1, \dots, c+1},\dots, \dots, \dots,\underbrace{n, n-1, \dots, n-c+1}.
という風に並んでいるときを考えると、これは失敗としたい。
しかし、\underbrace{\cdots}でくくった部分の二点をとらない限り正解を出す。
c = \sqrt{n}とすると、長さ\sqrt{n}のブロックが\sqrt{n}個存在する。
すなわち、同じブロック内の二点を選ぶ確率は\frac{1}{\sqrt{n}}
ゆえに\sqrt{n}以上必要。
※弱点は全体的な変化を見る確率が高いために局所的な変化に気付きにくい。

単純なアイディア2

ランダムにiを選んでx_{i} < x_{i+1}をみたすか調べる。
これもあまりうまくいかない。

理由：

\underbrace{1, 2, \dots, n/c},\underbrace{1, 2, \dots, n/c},\dots, \underbrace{1, 2, \dots, n/c}.
という風に並んでいるときを考えると、これは失敗としたい。
しかし、\underbrace{\cdots}でくくった部分の境目をとらない限り正解を出す。
この部分をとる確率はc/n.このため、線形時間かかるためよろしくない。
※弱点は局所的な変化を見る確率が高いために全体的な変化がわからない。

これら二つをうまく組み合わせられないだろうか？というのが次のアイディア
と、その前に今後使う記号の説明。
'[n]'は1からnまでの整数の集合
'x \in_{R} S 'は集合Sの中からランダムに選んだものがx

解決策*2

Repeat-O(1/ε)times
x_{1}, \cdots , x_{n}の二分木*3の葉集合Lを考える。
i \in_{R} L でとる。
x_{i}からルートへのぼる。
途中で通ったx_{j}の集合X_{j}
x_{i}から操作中に\mathcal{a < b \; and \;} x_{a} < x_{b}となったら失敗。
badな葉の個数がε|L|個以上の場合、正解とする確率は1/4以下
\left( 1 - \frac{\epsilon |L|}{|L|} \right)^{\frac{c}{\epsilon}} = \left( 1 - \epsilon \right)^{\frac{c}{\epsilon}} \le exp{-c} \le \frac{1}{4}
※
1 + x \le exp{x}は恒等的に成立する。（右辺引く左辺の関数を考えるとわかる）
ここでx = -\epsilonを代入し、辺々\frac{c}{\epsilon}乗すればよい。


P_{i}をx_{i}からルートまでに現れる要素の集合とする。
葉、x_{i},x_{j}がgoodならばP_{i} \cup P_{j}は単調増加
例
以下の二分木を考える。

x_{8}
x_{4} x_{12}
x_{2} x_{6} x_{10} x_{14}
x_{1} x_{3} x_{5} x_{7} x_{9} x_{11} x_{13} x_{15}

x_{1}が正しいのならば[tex:x_{1}

*1:\Omega(n)は最低でもnの定数回は同じ操作を繰り返さなければならないという意味

*2:元の資料とは異なる

*3:二分木、二分探索についてはWikipedia→http://bit.ly/fCiOyZ

STA Chapter1 part1

Sublinear Time Algorithms

これまでの常識：
問題を解くのに入力すべてを見なければ話にならないとされていた。

しかし、一部を見るだけで判断できないか？（モチベーションとしては、生体情報やネットワークグラフのようにそれ自体が巨大な量を持つ問題を解きたい）
そんなことが出来るのか？ということだが、幾つか条件を簡単にすると実際に出来ることが知られている。
近似の細かさのεだとか次数の上限dなどがパラメータとしては入っている。


時間計算量に関するエントリ（http://d.hatena.ne.jp/nsasaki/20110426/1303807572）の中で、線形時間よりも早いものを扱うのが今回の話。\sqrt{x}とかも含む。

使う資料はTel Aviv University（イスラエル）の準線形アルゴリズム時間に関する授業ノート
Ronitt Rubinfeld, Sublinear time algorithms, Fall 2009
http://www.cs.tau.ac.il/~ronitt/COURSES/F09course/index.html

時間計算量に関して

基礎知識

おおざっぱに言うと、n の増大に対して計算量がどの割合で膨張するのかを示すもの。
計算式の中では一番強いものに引っ張られる。

↓は代表的なもの

名前 早さ 概要 数式 例
factorial time slower nのn乗に比例した時間を費やす n! 巡回セールスマン問題の総当たりによる解法
指数関数時間 slow 定数のn乗に比例した時間を費やす k^{n} ルービックキューブの総当たりによる解法
多項式時間 fast nの定数乗に比例した時間を費す n^{k} 比較ソート (バブル、挿入、選択ソート)
linearithmic time faster 多項式時間と線形時間の中間の時間を費す n * \log{n} 線形対数ソート*1 (クイックソート、ヒープソート、マージソート)
線形時間 even faster Nに直接比例した時間を費やす k * n 配列走査
対数時間 much faster Nの対数に比例した時間を費やす k * \log{n} 2分探索
定数時間 fastest 入力がどんなに大きくても固定の時間を費やす k インデックスによる配列要素へのアクセス

参考:Time Complexity [C++ Reference] -- http://www.cppreference.com/wiki/complexity

たとえば、
n! + 100^{n} + n^{200} + n\log{n} + 2n + 40\log{n} + 50
という式があったとする。
n=1では500が圧倒的に大きい。
しかし、n = 1000　を代入すると、
1000! \approx 1000^{1000} \times exp{-1000} \approx 10^{2700}*2
*3
100^{1000} = 10^{2000}
1000^{200} = 10^{600}
1000\log{(1000)} \approx 6*10^{3}
2*1000 = 2*10^{3}
40\log{(1000)} \approx 2.4*10^{2}
と天文学的な数字の上のほうと比べて下のほうは誤差といってもいい程度に見える。
下三つはまだ、そんなに差が出ていない。が、
これらも
n=100000000000000000000000000000000000000000000000000000000000000000
くらいを代入すれば差が開く。

*1:直訳なので正しいかは怪しい。

*2: n! \approx \sqrt{2\pi n}\frac{n^{n}}{exp{n}}というスターリングの近似公式をつかった。

*3:exp{2} \approx 10 \;\; \log{10} \approx 2と近似した

通信の基礎 part3

通信 授業
スペクトルと信号処理

フーリエ変換の性質

  • f(t) \longleftrightarrow F(\omega)
  • g(t) \longleftrightarrow G(\omega)
  1. 線形性
    • af(t)+bg(t) \longleftrightarrow aF(\omega)+bG(\omega)
  2. 対称性
    • f(t) \longleftrightarrow F(\omega) \Rightarrow F(t) \longleftrightarrow 2\pi f(-\omega)
  3. 相似性
    • f(at) \longleftrightarrow \frac{1}{|a|}F(\frac{\omega}{a})
  4. 周波数推移
    • \fbox{f(t)exp{j\omega_{0}t} \longleftrightarrow F(\omega - \omega_{0})
    • 周波数変換
    • ベースバンド信号→無限周波数へ
  5. 時間推移
    • f(t - t_{0} ) \longleftrightarrow F(\omega) exp{-j\omega t_{0}}

共役対称性
\fbox{F(-\omega) = \int_{-\infty}^{\infty} f(t) exp{-j\omega t} dt = F^{*}(\omega)
F(\omega) = \int_{-\infty}^{\infty} f(t) exp{-j\omega t} dt
\begin{align}F^{*}(\omega) & = & \left[\int_{-\infty}^{\infty} f(t) exp{-j\omega t} dt \right]^{*} \\ & = & \int_{-\infty}^{\infty} f(t) exp{j\omega t} dt = F(-\omega) \end{align}

パーセバルの定理

\fbox{\int_{-\infty}^{\infty} f^{2}(t) exp{-j\omega t} dt = \frac{1}{2\pi}\int_{-\infty}^{\infty} |F(\omega)|^{2} d\omega

\mathcal{F} [ f(t)g(t) ] = \frac{1}{2\pi}F(\omega)*G(\omega)
G(-\omega) = G*(\omega)
\begin{align} \int_{-\infty}^{\infty} f(t)g(t)exp{-j\omega t} dt & = & \frac{1}{2\pi}F(\omega)*G(\omega) \\ & = & \frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega^{'})G(\omega - \omega^{'})d\omega^{'} \\ & = & \frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega^{'})G^{*}(\omega^{'} - \omega)d\omega^{'}\end{align}
ここで、f(t) = g(t) , \omega = 0　を代入すると
\begin{align} \int_{-\infty}^{\infty} f^{2}(t) dt & = & \frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega^{'})F^{*}(\omega^{'})d\omega^{'} \\ & = & \frac{1}{2\pi}\int_{-\infty}^{\infty} | F(\omega^{'}) |^{2} d\omega^{'}\end{align}

たたみ込み積分

g(t) = \int_{-\infty}^{\infty} f(\tau)h(t-\tau)d\tau
f(t)*h(t) \Leftrightarrow \frac{1}{2\pi}F(\omega)H(\omega)



―――――――＞\fbox{?}―――――――＞
インパルス　　　　　　　　　　　　　h(t)

伝達関数とインパルス応答

\delta(t)　　　　　　　　　　　　　h(t)
―――――――＞\fbox{\mathcal{L}}―――――――＞
f(t)　　　　　　　　　　　　　g(t)


g(t) = f(t) * h(t)
\mathcal{L} \left[ f(t) \right] = g(t) \; \; , \;\; \mathcal{L} \left[ \delta(t) \right] = h(t)
線形

  • \mathcal{L} \left[ af_{1}(t) + bf_{2}(t) \right] = ag_{1}(t) + bg_{2}(t)

時間不変

  • \mathcal{L} \left[ f(t-t_{0}) \right] = g(t - t_{0})

G(\omega) = F(\omega)H(\omega) \begin{cases}g(t) \longrightarrow G(\omega) \\ f(t) \longrightarrow F(\omega) \\ h(t) \longrightarrow H(\omega) \end{cases}

フィルタ

  • 低域通過フィルタ
  • 高域通過フィルタ
  • 帯域通過フィルタ
無歪伝送（歪み、ひずみ）

振幅が周波数に対して平坦であり、かつ位相が周波数に関して直線的に変化する。
g(t) = kf(t-t_{d})
\begin{align} G(\omega) & = & kF(\omega) exp{-j\omega t_{d}} \\ & = & F(\omega) (k exp{-j\omega t_{d} } ) \end{align}
k exp{-j\omega t_{d} } = H(\omega) とする
|H(\omega) | = k , \; \; \angle H(\omega) = \omega t_{d}

理想低域フィルタ

ある周波数範囲の信号のみをそのまま通過させ、それ以外の周波数成分を完全に減衰させるもの。
t<0で0でないインパルス応答を持つシステムであるため実現不可能である。
H(\omega) = \begin{cases} \; 1 \; (|\omega | \le \omega_{L} ) \\ \; 0 \; (|\omega | > \omega_{L}) \end{cases}

\begin{align} h(t) & = & \frac{1}{2\pi} \int_{-\infty}^{\infty} H(\omega) exp{j\omega t} d\omega \\ & = & \frac{1}{2\pi} \int_{-\omega_{L}}^{\omega_{L}} exp{j\omega t} d\omega \\ & = & \frac{1}{2\pi} \left[ \frac{exp{j\omega t} }{jt} \right]_{-\omega_{L}}^{\omega_{L}} = \frac{1}{2\pi} \times \frac{exp{j\omega t} - exp{-j\omega t} }{jt} \\ & = & \frac{1}{2\pi} \times \frac{2j \sin{(\omega_{L} t)} }{ jt } = \frac{\omega_{L}}{\pi} \times \frac{\sin{(\omega_{L}t)} }{\omega_{L}t \end{align}

※sinc関数が出ている

窓関数

有限の時間範囲Tの中だけ0でない値をとる関数
\cos{\omega t} = \frac{1}{2}(exp{j\omega t} + exp{-j\omega t})
\pi( \frac{t}{T} ) = \begin{cases} \;\; 1 \; (|t| \le \frac{T}{2} )\\ \;\; 0 \; (|t| > \frac{T}{2} ) \end{cases}
f(t) = exp{j\omega_{0}t}
F(\omega) = 2\pi\delta(\omega - \omega_{0})
\begin{align} W(\omega_{0}) & = & \int_{-\infty}^{\infty} w(t) exp{-j\omega_{0} t}dt \\ & = & \int_{-\frac{T}{2}}^{\frac{T}{2}} exp{-j\omega_{0}t}dt = T \times \frac{\sin{(\omega T/2)}}{\omega T/2} \end{align}