最近はノルムに関することをよくやっているのでそろそろ話をしましょうか。
ノルムとは
数学的にはベクトル空間や行列のすべてのベクトルの大きさや長さを合計したものです。 簡単のために、ノルムが高いほど、（中の）行列やベクトルは大きいと言うことができます。
ほとんどの場合、ノルムは次のような式で表されます：
ここで 
はベクトルまたは行列です。
例えば、ベクトル 
のユークリッドノルムは 
で、これはベクトル 
上の例はユークリッドノルム、正式には 
ノルムの計算の仕方を示しています。 実数にはそれに対応するノルムがあります（実数という言葉が強調されているのは、整数だけに限らないということです）
正式には 
の 
ノルムは次のように定義されます：
where 
以上です。
面白いのは、すべての ノルムが互いに非常に似ているように見えても、その数学的性質は非常に異なっており、したがってその応用も劇的に異なっていることです。
l0-norm
最初に取り上げるのは 
-norm です。 定義によれば、の-ノルムは
厳密には-ノルムは実際にはノルムではありません。 多くの人がノルムと呼んでいるが、-normの形で定義された基数関数である。 この関数にはゼロ乗とゼロ根が存在するので、扱いが少し難しい。 もちろん、どんな
もそうなるのですが、ゼロ乗の定義の問題、特にゼロ根の問題が、このあたりを混乱させているのです。
ベクトル中の非ゼロ要素の総数-norm>は、非ゼロ要素の数なので、非常に多くのアプリケーションで使用されています。 最近では、劣決定連立方程式の最短解を求めるCompressive Sensingの台頭により、さらに注目されています。 最短解とは、非ゼロ項目が最も少ない解、すなわち-normが最も小さい解を意味する。 この問題は通常-normの最適化問題または-optimisationと呼ばれる。
l0-optimisation
圧縮センシングを含む多くのアプリケーションは、ある制約に対応するベクトルの-normを最小化しようとするので「-minimisation」と呼ばれる。 標準的な最小化問題は次のように定式化される：
subject to 
しかし、これを行うのは簡単なことではない。 -norm の数学的表現がないため、計算機科学者は -minimisation を NP-hard problem と見なし、単に複雑すぎて解くのがほとんど不可能であると言っているのである。
多くの場合、最小化問題は
最小化や最小化などの高次ノルム問題に緩和される。
l1-norm
ノルムの定義に従って、のノルムは
このノルムはノルム族の中では非常にありふれたもので、最小化問題は最小化問題よりも高次の問題である。 マンハッタン・ノルムはその愛称であり、様々な分野で多くの名称と形式を持っている。 もしノルムが2つのベクトルや行列の差に対して計算されるなら、つまり
これはコンピュータビジョン研究者の間では絶対差分和（SAD）と呼ばれています。
より一般的な信号の差の測定の場合、単位ベクトルへのスケーリングは次のようになります：
ここで
はのサイズです。
これは平均絶対誤差（MAE）として知られています。
l2-norm
すべてのノルムで最も有名なのが – ノームです。 これは工学や科学全体のほとんどすべての分野で使われている。 基本的な定義に従うと、-normは
-normはユークリッド・ノルムとしてよく知られていて、ベクトルの差を測る標準量として使われます。 -norm と同様に、ベクトルの差分に対してユークリッドノルムを計算すると、ユークリッド距離:
またはその2乗形式で、コンピュータビジョン研究者の間ではSSD (Sum of Squared Difference) として知られる。
信号処理分野で最もよく知られているアプリケーションは、2 つの信号間の類似性、品質、または相関を計算するために使用される平均二乗誤差 (MSE) の測定法です。 MSEは、
最適化の項で述べたように、計算的な観点からも数学的な観点からも多くの問題があるため、多くの最適化問題は、代わりに-や-最適化となって緩和されているのである。 そこで、の最適化について説明する。
l2-最適化
最適化の場合と同様に、ノルムの最小化問題は
subject to
制約行列
がフルランクとすると、この問題は無限解の劣決定系であると言える。 この場合の目標は、これらの無限の解の中から最良の解、すなわち最も低いノルムを持つ解を引き出すことである。 これを直接計算するとなると、非常に面倒な作業となる。
ラグランジュ乗数のトリックを使うと、ラグランジアン
ここで、
は導入したラグランジュ乗数である。 この式を0に微分して最適解を求めると
この解を制約条件に差し込むと
そして最後に
この式を使って-最適化問題に対して瞬時に最適解を計算できるようになったのです。 この式は Moore-Penrose Pseudoinverse としてよく知られており、この問題自体は通常 Least Square problem, Least Square regression, Least Square optimisation として知られています。
しかしながら、Least Square 法の解は簡単に計算できても、それが必ずしも最善の解である必要はありません。 -norm 自体が滑らかな性質を持っているため、この問題に対する単一の最適解を見つけるのは難しいのです。
l1-optimisation
通常、最小化問題は
subject to
ノームはノームの場合のように滑らかではないので、この問題の解は-最適化よりもはるかに良く一意的である。
しかし、-最小化の問題は-最小化とほとんど同じ形をしているにもかかわらず、解くのはずっと難しい。 この問題は滑らかな関数を持たないので、問題を解くのに使ったトリックはもう通用しないのです。 その解を見つけるために残された唯一の方法は、直接探索することである。 解を求めるということは、可能な解を一つ一つ計算して、「無限にある」可能な解の中から最良のものを見つけるということです。
この問題の解を数学的に見つける簡単な方法はないので、-最適化の有用性は何十年も非常に限られています。 最近になって、計算能力の高いコンピュータの進歩により、すべての解を「掃引」することができるようになりました。 多くの有用なアルゴリズム、すなわち線形計画法、あるいは非線形計画法などの凸最適化アルゴリズムを用いることで、この問題に対する最適解を見つけることが可能になったのである。 圧縮センシングなど、-最適化に依存する多くのアプリケーションが可能になりました。
現在、-最適化のためのツールボックスが数多く提供されています。 これらのツールボックスは通常、同じ問題を解決するために異なるアプローチやアルゴリズムを使っています。 例えば、l1-magic, SparseLab, ISAL1,
ここまで、-norm, -norm, -normから始まる多くのノルムファミリーのメンバーについて説明してきました。 そろそろ次のものに移りましょう。 ノルムの基本的な定義が同じであれば、l-whatever個のノルムが存在しうることは冒頭で述べた通りですが、それら全てについて話すにはかなりの時間がかかりそうです。 幸い、-, – , -ノルムを除けば、他のものは普通普通ではないので、それほど面白いものはありません。 そこで、ノルムの極限である
-ノルム（l-無限ノルム）を見てみましょう。
l-infinity norm
ノルムの定義はいつものように
ここでこの定義はまた厄介に見えますが、実は非常に単純なんですよ。 ベクトル
を考えてみましょう。
がベクトルの最も大きい項目だとすると、無限大の性質そのものです。 ということは、
then
then
Now we can simply say the -norm is
that is maximum entries’ magnitudes of that the vector.(そのベクターの最大エントリーの大きさを示す)と言えるのである。 これで-norm
の意味が理解できたと思いますが、からまでのノルムについて説明しました。
参考文献：
Mathematical Norm – wikipedia
Mathematical Norm – MathWorld
Michael Elad – “Sparse and Redundant Representations .SparseとRedundantの表現”: From Theory to Applications in Signal and Image Processing” , Springer, 2010.
Linear Programming – MathWorld
Compressive Sensing – Rice University
Edit (15/02/15) : 内容が不正確なものを修正
線形計画法 – MathWorld
Compressive Sensing – Rice University