L1ノルム主成分分析

L1ノルム主成分分析（L1-PCA）は、多変量データ分析の一般的な手法です。^[1] L1-PCAは、分析されたデータに外れ値（誤った値や破損）が含まれる可能性がある場合に、堅牢であると考えられているため、 標準的なL2ノルム主成分分析（PCA）よりも好まれることがよくあります。^{[2] [3] [4]}

L1-PCA と標準 PCA はどちらも、選択された基準に従ってデータ表現が最大化されるサブスペースを定義する直交方向 (主成分)のコレクションを探します。 ^{[5] [6] [7]}標準 PCA は、データ表現を、サブスペースへのデータ ポイント投影のL2 ノルム の総計、または同等に、サブスペース投影された表現からの元のポイントの総ユークリッド距離として定量化します。L1-PCA は、代わりに、サブスペースへのデータ ポイント投影の L1 ノルムの総計を使用します。^[8] PCA と L1-PCA では、主成分 (PC) の数は、分析された行列のランクよりも低く、元のデータ ポイントによって定義される空間の次元と一致します。したがって、PCA または L1-PCA は、データのノイズ除去または圧縮を目的とした次元削減によく使用されます。標準PCAが広く普及した理由としては、特異値分解（SVD）^[9]による低コストの計算実装と、データセットが真の多変量正規データソースによって生成された場合の統計的最適性などが挙げられます。

しかし、現代のビッグデータセットでは、データに破損した欠陥のあるポイント、一般に外れ値と呼ばれるポイントが含まれることがよくあります。^[10] 標準PCAは、外れ値が処理データのごく一部にしか現れない場合でも、外れ値に敏感であることが知られています。^[11] その理由は、L2-PCAのL2ノルム定式化では、各データポイントの各座標の大きさに2乗の重点を置くため、外れ値などの周辺ポイントが過度に強調されてしまうためです。一方、L1-ノルム定式化に従うと、L1-PCAは各データポイントの座標に線形の重点を置くため、外れ値が効果的に抑制されます。^[12]

次元データポイントからなる任意の行列 を考えます。 を定義します。となる整数に対して、L1-PCAは次のように定式化されます: ^[1]${\displaystyle \mathbf {X} =[\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{N}]\in \mathbb {R} ^{D\times N}}$${\displaystyle N}$ ${\displaystyle D}$${\displaystyle r=rank(\mathbf {X} )}$${\displaystyle K}$${\displaystyle 1\leq K<r}$

について、（１ ）は、の L1ノルム主成分（L1-PC）を求めることに簡略化される。${\displaystyle K=1}$${\displaystyle \mathbf {X} }$

( 1 )-( 2 )において、L1ノルムは 引数の絶対値の合計を返し、L2ノルムは引数の二乗値の合計を返します。( 2 )にフロベニウス/L2ノルムを代入すると、問題は標準的なPCAとなり、支配的な特異ベクトル（すなわち、最も高い特異値に対応する特異ベクトル）を含む行列によって解かれます 。 ${\displaystyle \|\cdot \|_{1}}$${\displaystyle \|\cdot \|_{2}}$${\displaystyle \|\cdot \|_{1}}$${\displaystyle \|\cdot \|_{F}}$${\displaystyle \mathbf {Q} }$${\displaystyle K}$${\displaystyle \mathbf {X} }$${\displaystyle K}$

（ ２ ）の最大化メトリックは次のように展開できる。

となる任意の行列に対して、 を（L2ノルムの意味で） に最も近い正規直交列を持つ行列として定義します。つまり、 と定義します。 ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n}}$${\displaystyle m\geq n}$${\displaystyle \Phi (\mathbf {A} )}$${\displaystyle \mathbf {A} }$

プロクルステスの定理^{[13] [14]}によれば、 がSVD を持つ場合、 と なります。 ${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }}$${\displaystyle \Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }}$

マルコプロス、カリスティノス、パドス^[1]は、が二元核ノルム最大化（BNM）問題に対する正確な解である ことを示した。${\displaystyle \mathbf {B} _{\text{BNM}}}$

それから

は、（ ２ ）のL1-PCAの正確な解である。（２ ）の核ノルム は、その行列引数の特異値の総和を返し、標準的なSVDによって計算することができる。さらに、L1-PCAの解が与えられれば、BNMの解は次のように得られる。 ${\displaystyle \|\cdot \|_{*}}$${\displaystyle \mathbf {Q} _{\text{L1}}}$

ここで、 は行列引数の - 符号行列を返します(一般性を失うことなく、 と見なすことができます)。さらに、 となります。 ( 5 )の BNM は、対蹠バイナリ変数に関する組み合わせ問題です。したがって、その正確な解は、その実現可能性セットのすべての要素を徹底的に評価することで、漸近コストで見つけることができます。したがって、L1-PCA も、BNM を介して、コスト (データ ポイントの数と求められるコンポーネントの数の積の指数) で解くことができます。L1-PCA は、固定データ次元 、 に対して、多項式複雑度で最適に (正確に) 解くことができることがわかります。^[1]${\displaystyle {\text{sgn}}(\cdot )}$${\displaystyle \{\pm 1\}}$${\displaystyle {\text{sgn}}(0)=1}$${\displaystyle \|\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {B} _{\text{BNM}}\|_{*}}$${\displaystyle 2^{NK}}$ ${\displaystyle {\mathcal {O}}(2^{NK})}$${\displaystyle {\mathcal {O}}(2^{NK})}$${\displaystyle N}$${\displaystyle D}$${\displaystyle {\mathcal {O}}(N^{rK-K+1})}$

（の単一L1-PC ）の特別な場合、BNMは2進2次最大化（BQM）形式を取る。 ${\displaystyle K=1}$${\displaystyle \mathbf {X} }$

（ 5）から（8）への遷移は、 の唯一の特異値が任意の に対して に等しいため、真である。そして、 が （ 7） のBQMの解である場合、${\displaystyle K=1}$${\displaystyle \mathbf {X} \mathbf {b} }$${\displaystyle \|\mathbf {X} \mathbf {b} \|_{2}={\sqrt {\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} }}}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {b} _{\text{BNM}}}$

は、( 1 )で定義されているように、の正確なL1-PCである。さらに、 および が成り立つ。 ${\displaystyle \mathbf {X} }$${\displaystyle \mathbf {b} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}})}$${\displaystyle \|\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}$

上記のように、L1-PCA の正確な解は、次の 2 段階のプロセスによって得られます。

1. ( 5 )の問題を解いてを得る。${\displaystyle \mathbf {B} _{\text{BNM}}}$
2. SVD を に適用してを取得します。
${\displaystyle \mathbf {X} \mathbf {B} _{\text{BNM}}}$${\displaystyle \mathbf {Q} _{\text{L1}}}$

( 5 )のBNMは、コスト での領域を網羅的に探索することによって解くことができる。 ${\displaystyle \mathbf {B} }$${\displaystyle {\mathcal {O}}(2^{NK})}$

また、L1-PCAは、 が に関して定数であるとき、コスト で最適に解くことができます（有限データ次元 に対しては常に当てはまります）。^{[1] [15]}${\displaystyle {\mathcal {O}}(N^{rK-K+1})}$${\displaystyle r=rank(\mathbf {X} )}$${\displaystyle N}$${\displaystyle D}$

2008年にKwak ^[12]は、のL1-PCAの近似解を求める反復アルゴリズムを提案した。この反復法は後に成分に対して一般化された。^[16]別の近似効率の良いソルバーは、半正定値計画法（SDP）を用いたMcCoyとTropp ^[17]によって提案された。最近では、L1-PCA（および（5）のBNM）は、ビットフリッピング反復（L1-BFアルゴリズム）によって効率的に解かれた。^[8]${\displaystyle K=1}$${\displaystyle K>1}$

1  関数L1BF( , ):${\displaystyle \mathbf {X} }$${\displaystyle K}$
 2 初期化し、
 3 設定し、
 4 終了まで（または繰り返し）${\displaystyle \mathbf {B} ^{(0)}\in \{\pm 1\}^{N\times K}}$${\displaystyle {\mathcal {L}}\leftarrow \{1,2,\ldots ,NK\}}$${\displaystyle t\leftarrow 0}$${\displaystyle \omega \leftarrow \|\mathbf {X} \mathbf {B} ^{(0)}\|_{*}}$${\displaystyle T}$
 5           , 
 6 
 7               , 
 8              の場合// ビット反転
 9               // SVD またはより高速に計算 ( [8]を参照) 
10 
11                   , 
12                  の場合${\displaystyle \mathbf {B} \leftarrow \mathbf {B} ^{(t)}}$${\displaystyle t'\leftarrow t}$${\displaystyle x\in {\mathcal {L}}}$${\displaystyle k\leftarrow \lceil {\frac {x}{N}}\rceil }$${\displaystyle n\leftarrow x-N(k-1)}$${\displaystyle [\mathbf {B} ]_{n,k}\leftarrow -[\mathbf {B} ]_{n,k}}$                ${\displaystyle a(n,k)\leftarrow \|\mathbf {X} \mathbf {B} \|_{*}}$               ${\displaystyle a(n,k)>\omega }$${\displaystyle \mathbf {B} ^{(t)}\leftarrow \mathbf {B} }$${\displaystyle t'\leftarrow t+1}$${\displaystyle \omega \leftarrow a(n,k)}$
13 終わり
14 if // ビットは反転されなかった
15 if${\displaystyle t'=t}$                    ${\displaystyle {\mathcal {L}}=\{1,2,\ldots ,NK\}}$
16 終了する
17 その他
18                      ${\displaystyle {\mathcal {L}}\leftarrow \{1,2,\ldots ,NK\}}$

L1-BFの計算コストは​​である。^[8]${\displaystyle {\mathcal {O}}(NDmin\{N,D\}+N^{2}K^{2}(K^{2}+r))}$

L1-PCAは複雑なデータの処理にも一般化されています。複雑なL1-PCAについては、2018年に2つの効率的なアルゴリズムが提案されました。^[18]

L1-PCAは、標準的なタッカー分解のL1ノルムロバスト類似物であるL1-タッカーの形で、テンソルデータの解析にも拡張されています。^[19] L1-タッカーを解くための2つのアルゴリズムは、L1-HOSVDとL1-HOOIです。^{[19] [20] [21]}

L1-PCAのMATLABコードはMathWorksから入手可能です。^[22]