Intelligence Architecture けんきうノート

◆ GitBookに移行します

ノルム最小化によるフィルタ(仮題)

[Math rendered by jsMath]

- ユークリッドノルムと平均値

N次元のベクトル \(x=(x_1, \ldots, x_N)\) のノルム \(||x||\) といえば、 普通は直線距離であるユークリッドノルム \(\sqrt{\sum_i{x_i}^2}\) のことを考えるでしょう。 ここで、スカラ \(m\) と、N個の成分が全て1であるベクトル \(\bf{1}\) を用いて、最適化問題 \[ \arg\min_m||x-m{\bf 1}|| = \arg\min_m\sum_i(x_i-m)^2 \] を解くと、 \( {d \over dm} \sum_i(x_i-m)^2 = 0 \) より \( m=\frac1N\sum_ix_i \) となります。 これはベクトル \(x\) の各成分を、N個の独立したスカラデータと見たときの算術平均になっています。 統計的観点では、2次モーメント \(\sum_i(x_i-m)^2\) を最小化する \(m\) はデータ分布の平均値であり、そのときの2次モーメントは分散であるという、周知の事実を言ってます。

- \(p\)-ノルム

ユークリッドノルムは2乗の和の2乗根なわけですが、これをp乗の和のp乗根に一般化します: \[ ||x||_p = \sqrt[p]{\sum_i{|x_i|}^p} \] これは \(p\)-ノルムと言われます。

- \(1\)-ノルムとメディアン

\(p=1\) のとき(\(1\)-ノルム) \[ ||x||_1 = \sum_i|x_i| \] であり、いわゆるマンハッタン距離になります。 ではユークリッドノルムと同様に \[ \arg\min_m||x-m{\bf 1}||_1 = \arg\min_m\sum_i|x_i-m| \] を考えてみましょう。 数直線上で考えるとわかりやすいです:

(図)

(特にNが奇数のとき)\(m\) はメディアンになっています。

- \(\infty\)-ノルムと最小最大の中間値

\(p\rightarrow\infty\)の極限をとると、 \[ ||x||_\infty = \max_i|x_i| \] となります。 これは \(M = \arg\max_i|x_i|\) として \[\eqalign{ \sqrt[p]{\sum_i{|x_i|}^p} &=\sqrt[p]{(|x_M|)^p\sum_i({|x_i|/|x_M|})^p} \\ &=|x_M|\sqrt[p]{\sum_{i\ne M}({|x_i|/|x_M|})^p+1} \\ &\rightarrow |x_M| }\] となるからです。 \(\infty\)-ノルムとかスープ(sup)ノルムとか言われます。 よって \[ \arg\min_m||x-m{\bf 1}||_\infty = \arg\min_m\left(\max_i|x_i-m|\right) \] であり、解 \(m=\frac12(\min_ix_i+\max_ix_i)\) となります:

(図)

もはや最小データや最大データ以外には不感になってしまいます。

- 問題

いったんまとめると、与えられた \(x\) に対し、 \( \arg\min_m||x-m{\bf 1}||_p \) の解は

  • \(p=1\) のときメディアン \(m={\rm median}_i \ x_i\)
  • \(p=2\) のとき平均値 \(m=\frac1N\sum_ix_i\)
  • \(p\rightarrow\infty\) のとき最小最大の中間値 \(m=\frac12(\min_ix_i+\max_ix_i)\)

と、たったひとつのパラメータ \(p\) に対して意外とバラエティに富んでいる気がします。

それでは一般の \(p\) ではどうなるのかが気になります。言い換えると \(m(p;x)\) はいったいどういう形なのでしょうか?

- To be continued...

  • \(p\) が偶数のときは解析的に求まるが、それ以外の場合は絶対値の不連続性が効いて難しそう。
    • それでも反復的な数値計算で求めることはできそう。
    • しかし数値計算ではあくまで数値として与えられた \(x\) についてしか求まらないので、結局 \(m(p;x)\) がどういう関数か直接的にはわからなさそう。
  • 特に \(p\) が1〜2の間は、メディアンと平均値の中間的な性質をもつはず。
    • どのように中間的なの?少なくともリニアではなさそう。
    • たとえば画像の空間フィルタとして用いるとどうなるの?