L1-ノルム主成分分析 – 日本語百科事典辞書

L1-norm_principal_component_analysis
L1-ノルム主成分分析（L1-PCA）は、多変量データ分析の一般的な方法です。分析されたデータに外れ値（誤った値または破損）が含まれている可能性がある場合、L1-PCAは標準のL2-ノルム主成分分析（PCA）よりも好まれることがよく
L1-PCAとPCAの比較。名目データ（青い点）; 外れ値（赤い点）; PC（黒い線）; L1-PC（赤い線）; 名目上の最大分散線（点線）。
L1-PCAと標準PCAはどちらも、選択された基準に従ってデータ表現が最大化される部分空間を定義する直交方向（主成分）のコレクションを求めます。標準PCAは、データ表現を、部分空間へのデータポイント投影のL2ノルムの集計、または同等に、部分空間投影表現からの元のポイントのユークリッド距離の集計として定量化します。L1-PCAは、代わりに、部分空間へのデータポイント射影のL1-ノルムの集計を使用します。 PCAおよびL1-PCAでは、主成分（PC）の数が分析された行列のランク。これは、元のデータポイントによって定義された空間の次元と一致します。したがって、PCAまたはL1-PCAは、データのノイズ除去または圧縮を目的とした次元削減に一般的に使用されます。その高い人気に貢献した標準PCAの利点の中には、特異値分解（SVD）による低コストの計算実装と、データセットが真の多変量正規データソースによって生成される場合の統計的最適性が
ただし、最近のビッグデータセットでは、データに破損した障害のあるポイントが含まれていることが多く、一般に外れ値と呼ばれます。標準PCAは、処理されたデータのごく一部として表示される場合でも、外れ値に敏感であることが知られています。その理由は、L2-PCAのL2-ノルム定式化では、各データポイントの各座標の大きさを二乗して強調し、最終的には外れ値などの周辺ポイントを強調しすぎるためです。一方、L1-normの定式化に従って、L1-PCAは各データポイントの座標に線形の重点を置き、外れ値を効果的に抑制します。
コンテンツ
1 処方
2 解決
3 アルゴリズム
3.1 指数関数的な複雑さの正確なソリューション 3.2 多項式の複雑さの正確な解 3.3 おおよその効率的なソルバー
3.3.1 L1-BFアルゴリズム
4 複雑なデータ
5 テンソルデータ
6 コード
7 参考文献

処方
任意の行列を検討する
X= [X 1 X
2 … XN] ∈ R D
×× N { mathbf {X} = [ mathbf {x} _ {1}、 mathbf {x} _ {2}、 ldots、 mathbf {x} _ {N}] in mathbb {R} ^ {D times N}}
${$
からなる N { N}
D { D}

-次元データポイント。定義r = r a n k（（ X ）。 { r =rank（ mathbf {X}）}

。整数の場合 K { K}

そのような1 ≤ K < r
{ 1 leq K
、L1-PCAは次のように定式化されます：大 Q =
[ q 1 q 2 … q
K] ∈ R D ××K ‖X
⊤Q ‖ 1
対象 Q ⊤Q = I
K { { begin {aligned}＆{ underset { mathbf {Q} = [ mathbf {q} _ {1}、 mathbf {q} _ {2}、 ldots、 mathbf {q} _ {K}] in mathbb {R} ^ {D times K}} { max}} ~~ | mathbf {X} ^ { top} mathbf {Q} | _ {1} ＆{ text {subject to}} ~~ mathbf {Q} ^ { top} mathbf {Q} = mathbf {I}_{K}。end{aligned}}}
（1）為にK = 1
{ K = 1}

、（1）は、のL1-ノルム主成分（L1-PC）の検索を簡略化します。X
{ mathbf{X}}

に大 q ∈ R D ××1 ‖X
⊤q ‖ 1
対象 ‖ q‖ 2 =
1.1。
{ { begin {aligned}＆{ underset { mathbf {q} in mathbb {R} ^ {D times 1}} { max}} ~~ | mathbf {X} ^ { top} mathbf {q} | _ {1} \＆{ text {subject to}} ~~ | mathbf {q} | _ {2} = 1. end {aligned}}}
（2）（1）-（2）では、L1-ノルム‖ ⋅ ‖ 1
{ | cdot | _ {1}}

引数とL2-normの絶対エントリの合計を返します‖ ⋅ ‖ 2
{ | cdot | _ {2}}

引数のエントリの2乗の合計を返します。代用する場合‖ ⋅ ‖ 1
{ | cdot | _ {1}}

フロベニウス/L2-ノルムによる（2）‖ ⋅ ‖ F
{ | cdot | _ {F}}

、次に問題は標準PCAになり、行列によって解決されます Q { mathbf{Q}}

が含まれています K { K}

の支配的な特異ベクトルX
{ mathbf{X}}

（つまり、に対応する特異ベクトル K { K}

最高の特異値）。（ 2 ）の最大化メトリックは、次のように拡張できます。‖X ⊤ Q ‖
1= ∑
k= 1 K ∑
n= 1 N |X n ⊤
q k | { | mathbf {X} ^ { top} mathbf {Q} | _ {1} = sum _ {k = 1} ^ {K} sum _ {n = 1} ^ {N } | mathbf {x} _ {n} ^ { top} mathbf {q} _{k}|。}
（3）

解決
任意の行列の場合A ∈ R m
×× n { mathbf {A} in mathbb {R} ^ {m times n}}

とm ≥ n
{ m geq n}

、定義 Φ （（ A ）。 { Phi（ mathbf {A}）}

（L2ノルムの意味で）最も近い行列として A { mathbf{A}}

正規直交列がつまり、定義する Φ （（ A
）。= argmin Q ∈ R m ××n ‖
A − Q‖ F
対象 Q ⊤Q = I
n { { begin {aligned} Phi（ mathbf {A}）=＆{ underset { mathbf {Q} in mathbb {R} ^ {m times n}} { text {argmin} }} ~~ | mathbf {A}- mathbf {Q} | _ {F} \＆{ text {subject to}} ~~ mathbf {Q} ^ { top} mathbf {Q } = mathbf {I}_{n}。end{aligned}}}
（4）プロクラステスの定理は、 A { mathbf{A}}

SVDがありますU m
××
×× n ××
n ⊤ { mathbf {U} _ {m times n} { boldsymbol { Sigma}} _ {n times n} mathbf {V} _ {n times n} ^ { top}}

、それから Φ （（ A
）。= U V ⊤
{ Phi（ mathbf {A}）= mathbf {U} mathbf {V} ^ { top}}

。
Markopoulos、Karystinos、およびPados は、B BNM
{ mathbf {B} _ { text {BNM}}}

バイナリ核ノルム最大化（BNM）問題の正確な解決策です
最大B ∈
{{± 1 } N
××K ‖
XB ‖ ∗
2 { { begin {aligned} { underset { mathbf {B} in { pm 1 } ^ {N times K}} { text {max}}} ~~ | mathbf { X} mathbf {B} | _ {*} ^ {2}、 end {aligned}}}
（5）それからQ 1 = Φ（（ XB NM ）。 { { begin {aligned} mathbf {Q} _ { text {L1}} = Phi（ mathbf {X} mathbf {B} _ { text {BNM}}） end {aligned} }}
（6）（ 2 ）のL1-PCAの正確な解です。核ノルム‖ ⋅ ‖ ∗
{ | cdot | _ {*}}

in（2）は、その行列引数の特異値の合計を返し、標準のSVDを使用して計算できます。さらに、L1-PCAの解決策を考えると、Q L1
{ mathbf {Q} _ { text {L1}}}

、BNMの解は次のように取得できます。B NM = sgn（（ X
⊤Q 1 ）。 { { begin {aligned} mathbf {B} _ { text {BNM}} = { text {sgn}}（ mathbf {X} ^ { top} mathbf {Q} _ { text {L1}}） end {aligned}}}
（7）どこ sgn （（ ⋅ ）。 { { text {sgn}}（ cdot）}

を返します
{{± 1 }
{ { pm 1 }}

-その行列引数の符号行列（一般性を失うことなく、次のように考えることができます sgn （（ 0
）。= 1
{ { text {sgn}}（0）= 1}

）。また、次のようになります‖X ⊤ Q L1
‖1 ‖X B BNM ‖ ∗
{ | mathbf {X} ^ { top} mathbf {Q} _ { text {L1}} | _ {1} = | mathbf {X} mathbf {B} _ { text {BNM}} | _ {*}}

。（ 5）のBNMは、対蹠バイナリ変数に対する組み合わせの問題です。したがって、その正確な解決策は、すべての徹底的な評価を通じて見つけることができます2 N K
{ 2 ^ {NK}}

その実現可能性セットの要素、漸近的コスト O （（ 2 N K）。
{ { mathcal {O}}（2 ^ {NK}）}

。したがって、L1-PCAは、BNMを介してコストをかけて解決することもできます。 O （（ 2 N K）。
{ { mathcal {O}}（2 ^ {NK}）}

（データポイントの数と求められているコンポーネントの数の積の指数関数）。L1-PCAは、次の多項式の複雑さで最適に（正確に）解くことができることがわかります。 N { N}

固定データディメンションの場合 D { D}

、 O （（ Nr K − K + 1 ）。 { { mathcal {O}}（N ^ {rK-K + 1}）}

。
の特別な場合のためにK = 1
{ K = 1}

（シングルL1-PCのX
{ mathbf{X}}

）、BNMは二次二次最大化（BQM）形式を取ります
最大b ∈
{{± 1 } N
××1 b X X
b { { begin {aligned}＆{ underset { mathbf {b} in { pm 1 } ^ {N times 1}} { text {max}}} ~~ mathbf {b } ^ { top} mathbf {X} ^ { top} mathbf {X} mathbf{b}。end{aligned}}}
（8）（ 5）から（8）への遷移K = 1
{ K = 1}

の一意の特異値がX b { mathbf {X} mathbf{b}}

に等しい
‖X 2 X X b
{ | mathbf {X} mathbf {b} | _ {2} = { sqrt { mathbf {b} ^ { top} mathbf {X} ^ { top} mathbf {X } mathbf{b}}}}

、すべてのための b { mathbf{b}}

。次に、b BNM
{ mathbf {b} _ { text {BNM}}}

（ 7）のBQMの解であり、q 1 = Φ（（ Xb NM
）。=X b NM ‖
Xb NM ‖ 2
{ { begin {aligned} mathbf {q} _ { text {L1}} = Phi（ mathbf {X} mathbf {b} _ { text {BNM}}）= { frac { mathbf {X} mathbf {b} _ { text {BNM}}} { | mathbf {X} mathbf {b} _ { text {BNM}} | _ {2}}} end {整列}}}
（9）の正確なL1-PCですX
{ mathbf{X}}

、（ 1 ）で定義されているように。さらに、それはそれを保持しますb BNM= sgn （（ X⊤ q
L1）。
{ mathbf {b} _ { text {BNM}} = { text {sgn}}（ mathbf {X} ^ { top} mathbf {q} _ { text {L1}}）}

と‖X ⊤ q L1
‖1 ‖X b BNM ‖ 2
{ | mathbf {X} ^ { top} mathbf {q} _ { text {L1}} | _ {1} = | mathbf {X} mathbf {b} _ { text {BNM}} | _ {2}}

。

アルゴリズム

指数関数的な複雑さの正確なソリューション
上に示したように、L1-PCAの正確な解は、次の2段階のプロセスで取得できます。
1.（ 5）の問題を解いて、B BNM
{ mathbf {B} _ { text {BNM}}}

。2.SVDをに適用しますXB BNM
{ mathbf {X} mathbf {B} _ { text {BNM}}}

取得するQ L1
{ mathbf {Q} _ { text {L1}}}

。（ 5 ）のBNMは、の定義域を徹底的に検索することで解決できます。 B { mathbf{B}}

費用がかかる O （（ 2 N K）。
{ { mathcal {O}}（2 ^ {NK}）}

。

多項式の複雑さの正確な解
また、L1-PCAはコストで最適に解決できます O （（ Nr K −
K + 1）。
{ { mathcal {O}}（N ^ {rK-K + 1}）}

、いつr = r a n k（（ X ）。 { r =rank（ mathbf {X}）}

に関して一定です N { N}

（有限データディメンションの場合は常にtrue D { D}

）。

おおよその効率的なソルバー
2008年、Kwak は、L1-PCAの近似解の反復アルゴリズムを提案しました。K = 1
{ K = 1}

。この反復法は、後に一般化されました。 K >> 1 { K> 1}
1}””>
コンポーネント。半正定値計画法（SDP）を使用して、マッコイとトロップによって別の近似効率的なソルバーが提案されました。最近では、L1-PCA（および（5）のBNM）は、ビットフリッピング反復（L1-BFアルゴリズム）によって効率的に解決されました。

L1-BFアルゴリズム
1 関数L1BF（ X
{ mathbf{X}}

、 K { K}

）： 2初期化 B （（ 0
）。 ∈ {{± 1 } N
×× K { mathbf {B} ^ {（0）} in { pm 1 } ^ {N times K}}

と L {{
1 2 … NK }
{ { mathcal {L}} leftarrow {1，2、 ldots、NK }}

3セットt 0
{ t leftarrow 0}

とω ‖X B（（ 0
）。‖ ∗
{ omega leftarrow | mathbf {X} mathbf {B} ^ {（0）} | _ {*}}

4終了するまで（または T { T}

反復） 5
B B （（ t ）。 { mathbf {B} leftarrow mathbf {B} ^ {（t）}}

、t ′ t
{ t’ leftarrow t}

6の場合X∈ L
{ x in { mathcal {L}}}

7
k⌈X N ⌉ { k leftarrow lceil { frac {x} {N}} rceil}

、n X − N（（ k− 1 ）。 { n leftarrow xN（k-1）}

8n k − n k
{ _ {n、k} leftarrow- _ {n、k}}

//ビット 9 を反転します a （（ n k ）。 ‖X ∗ { a（n、k） leftarrow | mathbf {X} mathbf {B} | _ {*}}

// SVD以上で計算（を参照） 10 if a （（ n k ）。 >> ω { a（n、k）> omega}
omega }””> 11 B（（ t
）。 B { mathbf {B} ^ {（t）} leftarrow mathbf {B}}

、t ′ t + 1
{ t’ leftarrow t + 1}
12 ω a（（ n k ）。 { omega leftarrow a（n、k）}

13終了14の場合t ′ = t
{ t’= t}

//ビットが反転されなかった場合15 L = {{ 1 2 … NK }
{ { mathcal {L}} = {1，2、 ldots、NK }}

16終了17その他18 L {{
1 2 … NK }
{ { mathcal {L}} leftarrow {1，2、 ldots、NK }}

L1-BFの計算コストは O （（ ND m I n
{{N D } + N 2 K 2（（ K2 r ）。）。 { { mathcal {O}}（NDmin {N、D } + N ^ {2} K ^ {2}（K ^ {2} + r））}

。

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

テンソルデータ
L1-PCAは、テンソルデータの分析用に拡張されており、標準のタッカー分解に類似したL1-ノルムのロバストなL1-タッカーの形式になっています。 L1-Tuckerを解くための2つのアルゴリズムは、L1-HOSVDとL1-HOOIです。

コード
L1-PCAのMATLABコードは、MathWorks およびその他のリポジトリで入手できます。

参考文献
^ Markopoulos、Panos P .; Karystinos、George N .; パドス、ディミトリスA.。「L1部分空間信号処理のための最適なアルゴリズム」。信号処理に関するIEEEトランザクション。62（19）：5046〜5058。arXiv：1405.6785。Bibcode：2014ITSP…62.5046M。土井：10.1109/TSP.2014.2338077。S2CID1494171 。_ ^ Barrodale、I.（1968）。「L1近似とデータの分析」。応用統計。17（1）：51–57。土井：10.2307/2985267。JSTOR2985267。_ ^ Barnett、Vic; ルイス、トビー（1994）。統計データの外れ値（3. ed。）チチェスター：ワイリー。ISBN 978-0471930945。
^ カナデ、T .; Ke、Qifa。代替凸計画法による外れ値と欠測データの存在下でのロバストなL1ノルム因数分解。2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR’05）。巻 1.IEEE。p。739.CiteSeerX10.1.1.63.4605 。_ _ 土井：10.1109/CVPR.2005.309。ISBN 978-0-7695-2372-9。S2CID17144854 。_ ^ Jolliffe、IT（2004）。主成分分析（第2版）。ニューヨーク：スプリンガー。ISBN 978-0387954424。
^ ビショップ、クリストファーM.（2007）。パターン認識と機械学習（Corr。printing。ed。）ニューヨーク：スプリンガー。ISBN 978-0-387-31073-2。
^ ピアソン、カール（2010年6月8日）。「空間内の点のシステムに最も近い線と平面」。ロンドン、エジンバラ、ダブリンのフィロソフィカルマガジンとジャーナルオブサイエンス。2（11）：559–572。土井：10.1080/14786440109462720。
^ Markopoulos、Panos P .; クンドゥ、サンディパン; Chamadia、Shubham; パドス、ディミトリスA.（2017年8月15日）。「ビットフリッピングによる効率的なL1-ノルム主成分分析」。信号処理に関するIEEEトランザクション。65（16）：4252–4264。arXiv：1610.01959。Bibcode：2017ITSP…65.4252M。土井：10.1109/TSP.2017.2708023。S2CID7931130。_ ^ Golub、Gene H.（1973年4月）。「いくつかの修正された行列固有値の問題」。SIAMレビュー。15（2）：318–334。CiteSeerX10.1.1.454.9868。_ 土井：10.1137/1015032。 ^ Barnett、Vic; ルイス、トビー（1994）。統計データの外れ値（3. ed。）チチェスター：ワイリー。ISBN 978-0471930945。
^ Candès、Emmanuel J .; 李、小東; いいですか; ライト、ジョン（2011年5月1日）。「ロバストな主成分分析？」。ACMのジャーナル。58（3）：1–37。arXiv：0912.3599。土井：10.1145/1970392.1970395。S2CID7128002。_
^ Kwak、N.。「L1-ノルム最大化に基づく主成分分析」。パターン分析と機械知能に関するIEEEトランザクション。30（9）：1672–1680。CiteSeerX10.1.1.333.1176。_ 土井：10.1109/TPAMI.2008.114。PMID18617723。_ S2CID11882870。_ ^ エルデン、ラーズ; パク、ヘスン（1999年6月1日）。「スティーフェル多様体のプロクラステス問題」。NumerischeMathematik。82（4）：599–619。CiteSeerX10.1.1.54.3580。_ 土井：10.1007/s002110050432。S2CID206895591。_ ^ シェーネマン、ペーターH.（1966年3月）。「直交プロクラステス問題の一般化された解」。サイコメトリカ。31（1）：1–10。土井：10.1007/BF02289451。hdl：10338.dmlcz/103138。S2CID121676935。_ ^ Markopoulos、PP; クンドゥ、S; チャマディア、S; Tsagkarakis、N; パドス、DA（2018）。L1-Norm主成分分析による外れ値耐性データ処理。主成分分析の進歩。p。121. doi：10.1007/978-981-10-6704-4_6。ISBN 978-981-10-6703-7。
^ ニー、F; 黄、H; 丁、C; 羅、ディジュン; 王、H。「貪欲でないl1-ノルム最大化によるロバストな主成分分析」。人工知能に関する第22回国際合同会議：1433–1438。
^ マッコイ、マイケル; トロップ、ジョエルA.（2011）。「半正定値計画法を使用した堅牢なPCAの2つの提案」。統計の電子ジャーナル。5：1123〜1160。arXiv：1012.1086。土井：10.1214/11-EJS636。S2CID14102421。_
^ Markopoulos、PP。「ソフトウェアリポジトリ」。
^ Tsagkarakis、ニコラス; Markopoulos、Panos P .; Sklivanitis、ジョージ; パドス、ディミトリスA.（2018年6月15日）。「L1-複雑なデータのノルム主成分分析」。信号処理に関するIEEEトランザクション。66（12）：3256–3267。arXiv：1708.01249。Bibcode：2018ITSP…66.3256T。土井：10.1109/TSP.2018.2821641。S2CID21011653。_
^ Chachlakis、Dimitris G .; Prater-Bennette、Ashley; Markopoulos、Panos P.（2019年11月22日）。「L1-ノルムタッカーテンソル分解」。IEEEアクセス。7：178454–178465。arXiv：1904.06455。土井：10.1109/ACCESS.2019.2955134。
^ Markopoulos、Panos P .; Chachlakis、Dimitris G .; Prater-Bennette、Ashley（2019年2月21日）。「L1ノルム高次特異値分解」。IEEEProc。2018 IEEE Global Conference on Signal and Information Processing：1353–1357。土井：10.1109/GlobalSIP.2018.8646385。ISBN 978-1-7281-1295-4。S2CID67874182 。_ ^ Markopoulos、Panos P .; Chachlakis、Dimitris G .; Papalexakis、Evangelos。「ランク1L1-NormTUCKER2分解の正確なソリューション」。IEEE信号処理レター。25（4）：511–515。arXiv：1710.11306。Bibcode：2018ISPL…25..511M。土井：10.1109/LSP.2018.2790901。S2CID3693326。_ ^ 「L1-PCAツールボックス」。”