マトリックス補完
Filling in missing entries of a matrix
ランク1の部分的に明らかになった5行5列の行列の行列補完。左：観測された不完全な行列、右：行列補完の結果。

行列補完とは、部分的に観測された行列の欠落しているエントリを埋めるタスクであり、統計におけるデータ補完を実行することと同等です。さまざまなデータ セットが自然に行列形式で構成されています。1 つの例は、Netflix の問題に登場する映画の評価行列です。各エントリが顧客による映画の評価を表す評価行列があるとします。顧客が映画を視聴済みで、それ以外の場合は欠落している場合、残りのエントリを予測して、次に何を見るべきかについて顧客に適切な推奨を行う必要があります。もう 1 つの例は、ドキュメント用語行列です。ドキュメントのコレクションで使用される単語の頻度は行列として表すことができます。各エントリは、指定されたドキュメント内での関連用語の出現回数に対応します。 ( i , j ) {\displaystyle (i,j)} j {\displaystyle j} i {\displaystyle i} i {\displaystyle i} j {\displaystyle j}

完成行列の自由度の数に制限がない場合、この問題は、隠れた要素に任意の値を割り当てることができるため、劣決定問題となる。したがって、行列が最大行列式を持つ、正定値行列である、低ランク行列であるなど、行列に関する何らかの仮定を仮定することで、良設定問題を作成することができる。[1] [2]

たとえば、行列が低ランク構造であると仮定し、最低ランクの行列を探すか、または完成した行列のランクがわかっている場合は、既知のエントリと一致するランク の行列を探すことができます。図は、部分的に明らかにされたランク 1 の行列 (左側) は、欠損エントリのある行がすべて 3 行目と同じになるはずなので、ゼロ エラー (右側) で完成できることを示しています。Netflix 問題の場合、ユーザーの嗜好は映画のジャンルや公開時間など、いくつかの要素で説明できることが多いため、評価行列は低ランクであると予想されます。その他の応用としては、画像内の欠損ピクセルを再構築する必要があるコンピューター ビジョン、部分的な距離情報からネットワーク内のセンサーのグローバル ポジショニングを検出すること、および多クラス学習などがあります。行列完成問題は一般にNP 困難ですが、追加の仮定の下では、高い確率で正確な再構築を達成する効率的なアルゴリズムが存在します。 r {\displaystyle r}

統計学習の観点から見ると、行列補完問題はベクトル正則化の一般化である行列正則化の応用である。例えば、低ランク行列補完問題では、核ノルムの形をとる正則化ペナルティを適用することができる。 R ( X ) = λ ‖ X ‖ ∗ {\displaystyle R(X)=\lambda \|X\|_{*}}

低ランク行列補完

行列補完問題の変種の一つは、観測された要素集合内のすべての要素について、復元したい行列 と一致する最低ランクの行列を求める問題である。この問題の数学的定式化は以下の通りである。 X {\displaystyle X} M {\displaystyle M} E {\displaystyle E}

min X rank ( X ) subject to X i j = M i j ∀ i , j ∈ E {\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}

カンデスとレヒト[3]は、観測されたエントリのサンプリングと十分な数のサンプリングされたエントリに関する仮定のもとで、この問題は高い確率で唯一の解を持つことを証明した。

復元する行列が階数であると分かっている場合、同等の定式化は、 を解くことである。ここで M {\displaystyle M} r {\displaystyle r} X {\displaystyle X} X i j = M i j ∀ i , j ∈ E {\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}

仮定

分析を簡素化し、問題が不確定にならないようにするために、観測されるエントリのサンプリングとサンプリングされたエントリの数に関して多くの仮定が頻繁に行われます。

観測されたエントリの均一なサンプリング

分析を扱いやすくするために、観測されるエントリと固定濃度の集合は、濃度 のエントリのすべてのサブセットのコレクションからランダムに均一にサンプリングされると仮定されることが多い。分析をさらに簡略化するために、代わりに がベルヌーイサンプリングによって構築される、つまり各エントリが の確率 で観測されると仮定される。 が に設定され、 が の望ましい期待濃度、 が行列の次元である場合（一般性を失うことなく とする）、 が の範囲内にある確率が高いため、ベルヌーイサンプリングは均一サンプリングの良い近似となる。[3] もう1つの簡略化は、エントリが独立に、かつ復元抽出されると仮定することである。[4] E {\displaystyle E} | E | {\displaystyle |E|} E {\displaystyle E} p {\displaystyle p} p {\displaystyle p} N m n {\displaystyle {\frac {N}{mn}}} N {\displaystyle N} E {\displaystyle E} m , n {\displaystyle m,\;n} m < n {\displaystyle m<n} | E | {\displaystyle |E|} O ( n log ⁡ n ) {\displaystyle O(n\log n)} N {\displaystyle N}

観測されたエントリ数の下限

復元しようとしている行列（ ）のランクが であると仮定する。 を一意に再構成するために必要な要素数には、情報理論的な下限が存在する。ランクが かそれ以下の行列 の集合は 、次元 の 代数多様体である。この結果を用いると、 のときに行列完備化が一意に解を持つため には、少なくとも 個の要素が観測されなければならない ことがわかる 。[5] m {\displaystyle m} n {\displaystyle n} M {\displaystyle M} m < n {\displaystyle m<n} r {\displaystyle r} M {\displaystyle M} m {\displaystyle m} n {\displaystyle n} r {\displaystyle r} C m × n {\displaystyle {\mathbb {C} }^{m\times n}} ( n + m ) r − r 2 {\displaystyle (n+m)r-r^{2}} 4 n r − 4 r 2 {\displaystyle 4nr-4r^{2}} C n × n {\displaystyle {\mathbb {C} }^{n\times n}} r ≤ n / 2 {\displaystyle r\leq n/2}

第二に、 の行と列ごとに少なくとも1つの観測エントリが存在する必要があります。の特異値分解は で与えられます。列が観測されない場合、の右特異ベクトル、を任意の値に変更しても、観測エントリの集合に一致する行列が得られることは容易にわかります。同様に、行が観測されない場合、の左特異ベクトル、は任意の値になることがあります。観測エントリの集合をベルヌーイサンプリングすると仮定すると、クーポンコレクター効果により、各行と各列から高い確率で観測されるためには、のオーダーのエントリが観測される必要があることが示唆されます。[6] M {\displaystyle M} M {\displaystyle M} U Σ V † {\displaystyle U\Sigma V^{\dagger }} i {\displaystyle i} i th {\displaystyle i^{\text{th}}} M {\displaystyle M} v i {\displaystyle v_{i}} M {\displaystyle M} j {\displaystyle j} j th {\displaystyle j^{\text{th}}} M {\displaystyle M} u i {\displaystyle u_{i}} O ( n log ⁡ n ) {\displaystyle O(n\log n)}

必要条件を組み合わせ、（多くの実際のアプリケーションで有効な仮定）と仮定すると、行列完成の問題が不十分な決定にならないようにするために必要な観測エントリの数の下限は約 になります。 r ≪ m , n {\displaystyle r\ll m,n} n r log ⁡ n {\displaystyle nr\log n}

矛盾

インコヒーレンスの概念は、圧縮センシングにおいて生まれました。これは、行列補完の文脈において、各特異ベクトルが「スパース」になりすぎないようにするために導入されました。つまり、特異ベクトルの全ての座標が同程度の大きさであり、一部の座標だけが著しく大きな大きさを持つという状況は避けるべきです。[7] [8] すると、標準基底ベクトルは特異ベクトルとしては望ましくなく、ベクトルは望ましいものになります。特異ベクトルが十分に「スパース」である場合に何が起こり得るかを示す例として、特異値分解を用いた行列を考えてみましょう。行列 を再構成する前に、 のほぼすべての要素をサンプリングする必要があります。 M {\displaystyle M} 1 n [ 1 1 ⋮ 1 ] {\displaystyle {\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}} R n {\displaystyle \mathbb {R} ^{n}} m {\displaystyle m} n {\displaystyle n} [ 1 0 ⋯ 0 ⋮ ⋮ 0 0 0 0 ] {\displaystyle {\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}} I m [ 1 0 ⋯ 0 ⋮ ⋮ 0 0 0 0 ] I n {\displaystyle I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}} M {\displaystyle M}

CandèsとRecht [3]は、列空間が の次元部分空間である行列の一貫性を と定義する。ここで はへの直交射影である。一貫性のなさは、 を 行列で特異値分解すると、 U {\displaystyle U} r − {\displaystyle r-} R n {\displaystyle \mathbb {R} ^{n}} μ ( U ) = n r max i < n ‖ P U e i ‖ 2 {\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}} P U {\displaystyle P_{U}} U {\displaystyle U} U Σ V † {\displaystyle U\Sigma V^{\dagger }} m {\displaystyle m} n {\displaystyle n} M {\displaystyle M}

  1. μ ( U ) , μ ( V ) ≤ μ 0 {\displaystyle \mu (U),\;\mu (V)\leq \mu _{0}}
  2. のエントリの上限は ∑ k u k v k † {\displaystyle \sum _{k}u_{k}v_{k}^{\dagger }} μ 1 r m n {\displaystyle \mu _{1}{\sqrt {\frac {r}{mn}}}}

一部の人にとっては。 μ 0 , μ 1 {\displaystyle \mu _{0},\;\mu _{1}}

ノイズを含む低ランク行列補完

現実世界の応用では、少量のノイズによって損なわれた要素がごく少数しか観測されないことがしばしばある。例えば、Netflixの問題では、評価は不確実である。CandèsとPlan [9]は、核ノルム最小化によって、ノイズを含む少数のサンプルから、大きな低ランク行列の多くの欠損要素を埋めることが可能であることを示した。ノイズモデルは、以下のことを仮定している。

Y i j = M i j + Z i j , ( i , j ) ∈ Ω , {\displaystyle Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,}

ここではノイズ項である。ノイズは確率的または決定論的である可能性がある。あるいは、モデルは次のように表すこともできる。 Z i j : ( i , j ) ∈ Ω {\displaystyle {Z_{ij}:(i,j)\in \Omega }}

P Ω ( Y ) = P Ω ( M ) + P Ω ( Z ) , {\displaystyle P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),}

ここで、は、何らかの に対して であると仮定する要素を持つ行列です。不完全行列を復元するために、次の最適化問題を解こうとします。 Z {\displaystyle Z} n × n {\displaystyle n\times n} Z i j {\displaystyle Z_{ij}} ( i , j ) ∈ Ω {\displaystyle (i,j)\in \Omega } ‖ P Ω ( Z ) ‖ F ≤ δ {\displaystyle \|P_{\Omega }(Z)\|_{F}\leq \delta } δ > 0 {\displaystyle \delta >0}

min X ‖ X ‖ ∗ subject to ‖ P Ω ( X − Y ) ‖ F ≤ δ {\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}}

データと整合するすべての行列の中で、核ノルムが最小となるものを見つけよ。カンデスとプラン[9]は、この再構成が正確であることを示した。彼らは、ノイズのない完全な回復が起こった場合、行列補完は摂動に対して安定であることを証明した。誤差はノイズレベルに比例する。したがって、ノイズレベルが小さい場合、誤差は小さい。ここで、行列補完問題は制限等長性（RIP）に従わない。行列の場合、RIPはサンプリング演算子が δ {\displaystyle \delta }

( 1 − δ ) ‖ X ‖ F 2 ≤ 1 p ‖ P Ω ( X ) ‖ F 2 ≤ ( 1 + δ ) ‖ X ‖ F 2 {\displaystyle (1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}}

十分に小さいランクと十分に小さい値を持つすべての行列に対して適用できます。これらの手法は、RIPが成立しないスパース信号回復問題にも適用できます。 X {\displaystyle X} δ < 1 {\displaystyle \delta <1}

高ランク行列補完

高ランク行列の補完は一般にNP困難である[要出典]。しかし、特定の仮定のもとでは、不完全な高ランク行列、あるいはフルランク行列でさえも補完可能である。

Eriksson、Balzano、Nowak [10]は、行列の列が複数の低ランク部分空間の和集合に属するという仮定の下で、行列を完成する問題を考察した。列は部分空間の和集合に属するため、この問題は部分空間クラスタリング問題の欠損データ版とみなすことができる。 が、その（完全な）列が最大で 個の部分空間の和集合にあり、各 が であり、 と仮定する行列とすると、 Eriksson、Balzano、Nowak [10]は、緩やかな仮定の下で、 の各列は、少なくとも のエントリが一様ランダムに観測される限り、不完全なバージョンから高い確率で完全に復元できることを示した。この場合、定数は、通常の非整合条件、部分空間の幾何学的配置、部分空間上の列の分布によって決まる。 X {\displaystyle X} n × N {\displaystyle n\times N} k {\displaystyle k} rank ≤ r < n {\displaystyle \operatorname {rank} \leq r<n} N ≫ k n {\displaystyle N\gg kn} X {\displaystyle X} C r N log 2 ⁡ ( n ) {\displaystyle CrN\log ^{2}(n)} X {\displaystyle X} C > 1 {\displaystyle C>1}

このアルゴリズムは、(1) 局所近傍、(2) 局所部分空間、(3) 部分空間の改良、(4) 行列の完全補完といった複数のステップから構成されます。この手法は、インターネット距離行列の補完やトポロジーの識別に適用できます。

低ランク行列補完アルゴリズム

様々な行列補完アルゴリズムが提案されている。[8]これらには、凸緩和ベースのアルゴリズム、[3]勾配ベースのアルゴリズム、[11]交代最小化ベースのアルゴリズム、[12]ガウス・ニュートンアルゴリズム、[13]離散考慮ベースのアルゴリズムなどがある。[14]

凸緩和

ランク最小化問題はNP困難である。カンデスとレヒトによって提案された一つのアプローチは、問題の凸緩和を形成し、（の非ゼロ特異値の個数を数える）の代わりに（の特異値の和を与える）核ノルムを 最小化することである。[3]これは、ベクトルのL0ノルムではなくL1ノルムを最小化するのと類似している。凸緩和は、最適化問題が次式と等価であることに着目することで、 半正定値計画法（SDP）を用いて解くことができる。 ‖ M ‖ ∗ {\displaystyle \|M\|_{*}} M {\displaystyle M} rank ( M ) {\displaystyle {\text{rank}}(M)} M {\displaystyle M}

min W 1 , W 2 trace ⁡ ( W 1 ) + trace ⁡ ( W 2 ) subject to X i j = M i j ∀ i , j ∈ E [ W 1 X X T W 2 ] ⪰ 0 {\displaystyle {\begin{aligned}&\min \limits _{W_{1},W_{2}}&&\operatorname {trace} (W_{1})+\operatorname {trace} (W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}}

SDPを用いて凸緩和を解く複雑さはである。SDPT3のような最先端のソルバーは、100×100までの行列しか扱えない。[15] 凸緩和を近似的に解く別の一次手法として、Cai、Candès、Shenによって導入された特異値閾値アルゴリズムがある。[15] O ( max ( m , n ) 4 ) {\displaystyle O({\text{max}}(m,n)^{4})}

Candès と Recht は、バナッハ空間上のランダム変数の研究を用いて、観測されるエントリの数が のオーダーである場合（一般性を失うことなく と仮定）、ランク最小化問題には一意の解があり、その解は、ある定数 に対して確率でその凸緩和の解でもあることを示しています。 のランクが小さい場合（）、観測集合のサイズは のオーダーまで減少します。これらの結果は最適に近いものです。なぜなら、行列完成問題が不足決定にならないために観測されなければならないエントリの最小数は のオーダーだからです。 max { μ 1 2 , μ 0 μ 1 , μ 0 n 0.25 } n r log ⁡ n {\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n} m < n {\displaystyle m<n} 1 − c n 3 {\displaystyle 1-{\frac {c}{n^{3}}}} c {\displaystyle c} M {\displaystyle M} r ≤ n 0.2 μ 0 {\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}} μ 0 n 1.2 r log ⁡ n {\displaystyle \mu _{0}n^{1.2}r\log n} n r log ⁡ n {\displaystyle nr\log n}

この結果はカンデスとタオによって改良された。[6] 彼らは仮定を強化することで、最適境界値との差が多重対数係数のみである境界値を達成した。彼らは非整合性の代わりに、パラメータ を持つ強い非整合性を仮定した。この性質は以下を示す： μ 3 {\displaystyle \mu _{3}}

  1. | ⟨ e a , P U e a ′ ⟩ − r m 1 a = a ′ | ≤ μ 3 r m {\displaystyle |\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}} のためにそしてのために a , a ′ ≤ m {\displaystyle a,a'\leq m} | ⟨ e b , P U e b ′ ⟩ − r n 1 b = b ′ | ≤ μ 3 r n {\displaystyle |\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}} b , b ′ ≤ n {\displaystyle b,b'\leq n}
  2. のエントリは、大きさが次の式で制限されます。 ∑ i u i v i † {\displaystyle \sum _{i}u_{i}v_{i}^{\dagger }} μ 3 r m n {\displaystyle \mu _{3}{\sqrt {\frac {r}{mn}}}}

直感的には、行列の強い非整合性は、標準基底ベクトルの直交射影が、特異ベクトルがランダムに分布している場合に高い尤度を持つ大きさを持つことを主張している。[7] U {\displaystyle U} U {\displaystyle U}

カンデスとタオは、がで観測されるエントリ数が のオーダーであるとき、ランク最小化問題は唯一の解を持ち、それはある定数 に対する確率でその凸緩和の解でもあることを発見した。任意の に対して、この主張が成り立つのに十分な観測エントリ数は のオーダーである。 r {\displaystyle r} O ( 1 ) {\displaystyle O(1)} μ 3 4 n ( log ⁡ n ) 2 {\displaystyle \mu _{3}^{4}n(\log n)^{2}} 1 − c n 3 {\displaystyle 1-{\frac {c}{n^{3}}}} c {\displaystyle c} r {\displaystyle r} μ 3 2 n r ( log ⁡ n ) 6 {\displaystyle \mu _{3}^{2}nr(\log n)^{6}}

もう一つの凸緩和法[16]は、階数制約の下でフロベニウスの2乗ノルムを最小化することである。これは、

min X ‖ X ‖ F 2 subject to X i j = M i j ∀ i , j ∈ E Rank ⁡ ( X ) ≤ k . {\displaystyle {\begin{aligned}&\min \limits _{X}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {Rank} (X)\leq k.\end{aligned}}}

のランクをモデル化するために直交射影行列（つまり）を導入し、この問題の凸緩和をとることで、次の半正定値計画が得られる。 Y {\displaystyle Y} Y 2 = Y , Y = Y ′ {\displaystyle Y^{2}=Y,Y=Y'} X {\displaystyle X} X = Y X , trace ( Y ) ≤ k {\displaystyle X=YX,{\text{trace}}(Y)\leq k}

min X , Y , θ trace ( θ ) subject to X i j = M i j ∀ i , j ∈ E trace ⁡ ( Y ) ≤ k , 0 ⪯ Y ⪯ I ( Y X X ⊤ θ ) ⪰ 0. {\displaystyle {\begin{aligned}&\min \limits _{X,Y,\theta }&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {trace} (Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}}

この緩和法において、 Yが射影行列（すなわち、2値固有値を持つ）である場合、この緩和法はタイトである。そうでない場合、全体の目的関数の有効な下限値を与える。さらに、 Yの固有値を貪欲に丸めることにより、（わずかに）大きな目的関数を持つ実行可能な解に変換することができる。[16]注目すべきことに、この凸緩和法は、 SDPを解くことなく、 XとYの交互最小化によって解くことができ、SDPT3やMosekといった最先端のSDPソルバーの典型的な数値的限界を超えてスケ​​ールする。

このアプローチは、より一般的な再定式化手法の特殊なケースであり、トレース行列凸目的を持つ任意の低ランク問題に対して有効な下限値を得るために適用することができます。[17]

勾配降下法

Keshavan、Montanari、Oh [11]は、復元される行列 による の階数が であることがわかっている行列補完の変形を検討しています。彼らは、要素のベルヌーイサンプリング、一定のアスペクト比、要素の大きさの上限（上限を とする）、および条件数定数（ただし、 とはそれぞれの最大と最小の特異値）を仮定しています。さらに、彼らは 2 つの非整合条件が および で満たされると仮定しています。ただし、とは定数です。 を、観測された要素の集合で一致し、それ以外の場所で 0 となる行列とします。次に、彼らは次のアルゴリズムを提案しています。 m {\displaystyle m} n {\displaystyle n} M {\displaystyle M} r {\displaystyle r} m n {\displaystyle {\frac {m}{n}}} M {\displaystyle M} M max {\displaystyle M_{\text{max}}} σ 1 σ r {\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}} σ 1 {\displaystyle \sigma _{1}} σ r {\displaystyle \sigma _{r}} M {\displaystyle M} μ 0 {\displaystyle \mu _{0}} μ 1 σ 1 σ r {\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}} μ 0 {\displaystyle \mu _{0}} μ 1 {\displaystyle \mu _{1}} M E {\displaystyle M^{E}} M {\displaystyle M} E {\displaystyle E}

  1. 列のエントリを 0 に設定して、列から次数 より大きいすべての観測値を削除してトリムします。同様に、行から次数 より大きいすべての観測値を削除します。 M E {\displaystyle M^{E}} 2 | E | n {\displaystyle {\frac {2|E|}{n}}} 2 | E | n {\displaystyle {\frac {2|E|}{n}}}
  2. 第一主成分に投影する。得られた行列を と呼ぶ。 M E {\displaystyle M^{E}} r {\displaystyle r} Tr ( M E ) {\displaystyle {\text{Tr}}(M^{E})}
  3. 直線探索法による勾配降下法で、正規化関数を解きます。をで初期化します。とが矛盾する場合、勾配降下法全体にわたって矛盾が維持されるように強制する関数 を設定します。 min X , Y min S ∈ R r × r 1 2 ∑ i , j ∈ E ( M i j − ( X S Y † ) i j ) 2 + ρ G ( X , Y ) {\displaystyle \min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)} G ( X , Y ) {\displaystyle G(X,Y)} X , Y {\displaystyle X,\;Y} X 0 , Y 0 {\displaystyle X_{0},\;Y_{0}} Tr ( M E ) = X 0 S 0 Y 0 † {\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }} G ( X , Y ) {\displaystyle G(X,Y)} X , Y {\displaystyle X,\;Y} X 0 {\displaystyle X_{0}} Y 0 {\displaystyle Y_{0}}
  4. 行列を返します。 X S Y † {\displaystyle XSY^{\dagger }}

アルゴリズムのステップ1と2では、真の行列（二乗平均平方根誤差（RMSE）で測定）に非常に近い行列が、高い確率で生成されます。特に、確率 で、何らかの定数 に対して、 となります。 はフロベニウスノルムを表します。この結果が成り立つためには、すべての仮定を満足する必要はないことに注意してください。例えば、非整合条件は正確な再構成においてのみ作用します。最後に、トリミングは情報を捨てることを伴うため直感に反するように思えるかもしれませんが、第一主成分への投影によって、観測された要素よりも基礎となる行列に関するより多くの情報が得られることを保証します。 Tr ( M E ) {\displaystyle {\text{Tr}}(M^{E})} M {\displaystyle M} 1 − 1 n 3 {\displaystyle 1-{\frac {1}{n^{3}}}} 1 m n M max 2 ‖ M − Tr ( M E ) ‖ F 2 ≤ C r m | E | m n {\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}} C {\displaystyle C} ‖ ⋅ ‖ F {\displaystyle \|\cdot \|_{F}} M E {\displaystyle M^{E}} r {\displaystyle r} M {\displaystyle M}

ステップ3では、内部最小化問題がに対して と同じ解を持つことに注目することで、候補行列の空間を縮小できます。ここで、 とは行列に直交します。次に、 2つのグラスマン多様体の外積に対して勾配降下法を実行できます。 であり、観測される要素集合が の位数である場合、ステップ3で返される行列は とまったく同じです。このとき、アルゴリズムは の位数最適です。これは、行列完成問題が過小決定にならないためには、要素数が の位数でなければならないことが分かっているためです。 X , Y {\displaystyle X,\;Y} ( X , Y ) {\displaystyle (X,Y)} ( X Q , Y R ) {\displaystyle (XQ,YR)} Q {\displaystyle Q} R {\displaystyle R} r {\displaystyle r} r {\displaystyle r} r ≪ m , n {\displaystyle r\ll m,\;n} n r log ⁡ n {\displaystyle nr\log n} M {\displaystyle M} n r log ⁡ n {\displaystyle nr\log n}

交互最小二乗法による最小化

交代最小化は、与えられたデータに最も適合する低ランク行列を見つけるための、広く適用可能で経験的に成功しているアプローチです。例えば、低ランク行列補完問題において、この手法は最も正確かつ効率的な方法の一つと考えられており、Netflix問題における優勝候補の主要な構成要素となりました。交代最小化アプローチでは、低ランク目標行列は双線形形式で表されます。

X = U V T {\displaystyle X=UV^{T}} ;

アルゴリズムは、最良のものと最良のものを交互に探します。全体的な問題は非凸ですが、各部分問題は典型的には凸であり、効率的に解くことができます。Jain、Netrapalli、およびSanghavi [12]は、行列補完と行列センシングの両方において、交互最小化の性能を保証する最初の方法の一つを示しました。 U {\displaystyle U} V {\displaystyle V}

交代最小化アルゴリズムは、次の非凸問題を解く近似的な方法と考えることができます。

min U , V ∈ R n × k ‖ P Ω ( U V T ) − P Ω ( M ) ‖ F 2 {\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}

Jain、Netrapalli、Sanghaviによって提案されたAltMinCompleteアルゴリズムはここに記載されています：[12]

  1. 入力: 観測セット、値 Ω {\displaystyle \Omega } P Ω ( M ) {\displaystyle P_{\Omega }(M)}
  2. それぞれの要素が等確率でいずれかに属するようにサブセットに分割する（置換抽出法） Ω {\displaystyle \Omega } 2 T + 1 {\displaystyle 2T+1} Ω 0 , ⋯ , Ω 2 T {\displaystyle \Omega _{0},\cdots ,\Omega _{2T}} Ω {\displaystyle \Omega } Ω t {\displaystyle \Omega _{t}}
  3. U ^ 0 = S V D ( 1 p P Ω 0 ( M ) , k ) {\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)} すなわち、左上の特異ベクトル k {\displaystyle k} 1 p P Ω 0 ( M ) {\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}
  4. クリッピング:より大きい値を持つすべての要素をゼロに設定し、列を直交化します。 U ^ 0 {\displaystyle {\hat {U}}^{0}} 2 μ k n {\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}} U ^ 0 {\displaystyle {\hat {U}}^{0}}
  5. 行うために t = 0 , ⋯ , T − 1 {\displaystyle t=0,\cdots ,T-1}
  6. V ^ t + 1 ← argmin V ∈ R n × k ‖ P Ω t + 1 ( U ^ V T − M ) ‖ F 2 {\displaystyle \quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}}
  7. U ^ t + 1 ← argmin U ∈ R m × k ‖ P Ω T + t + 1 ( U ( V ^ t + 1 ) T − M ) ‖ F 2 {\displaystyle \quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}}
  8. 終わりのために
  9. 戻る X = U ^ T ( V ^ T ) T {\displaystyle X={\hat {U}}^{T}({\hat {V}}^{T})^{T}}

彼らは、非整合行列のランダムな要素を観測することで、AltMinCompleteアルゴリズムが段階的に回復できることを示した。サンプル複雑度（）の観点から見ると、理論的には、交代最小化は凸緩和よりも大きな緩和を必要とする可能性がある。しかし、経験的にはそうではないようで、サンプル複雑度の境界をさらに厳しくできることを示唆している。時間複雑度の観点から見ると、AltMinCompleteには | Ω | = O ( ( σ 1 ∗ σ k ∗ ) 6 k 7 log ⁡ n log ⁡ ( k ‖ M ‖ F / ϵ ) ) {\displaystyle |\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))} M {\displaystyle M} M {\displaystyle M} O ( log ⁡ ( 1 / ϵ ) ) {\displaystyle O(\log(1/\epsilon ))} | Ω | {\displaystyle |\Omega |} Ω {\displaystyle \Omega }

O ( | Ω | k 2 log ⁡ ( 1 / ϵ ) ) {\displaystyle O(|\Omega |k^{2}\log(1/\epsilon ))} 。

凸緩和に基づく方法は厳密な分析が可能ですが、交互最小化に基づくアルゴリズムの方が実用上はより成功していることは注目に値します。[要出典]

ガウス・ニュートン

因数分解に基づくアルゴリズムに簡単に追加できるのが、ガウス・ニュートン行列回復（GNMR）です。[13]交代最小化と同様に、GNMRは因数分解された低ランク行列の完成目標を扱います。

min U , V ∈ R n × k ‖ P Ω ( U V T ) − P Ω ( M ) ‖ F 2 {\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}

GNMRは古典的なガウス・ニュートン法に着想を得て、目的関数を線形化します。その結果、以下の線形最小二乗法の部分問題が得られます。

min Δ U , Δ V ∈ R n × k ‖ P Ω ( U 0 V 0 T + U 0 Δ V T + Δ U V 0 T ) − P Ω ( M ) ‖ F 2 {\displaystyle {\begin{aligned}&{\underset {\Delta U,\Delta V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(U_{0}V_{0}^{T}+U_{0}\Delta V^{T}+\Delta UV_{0}^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}

GNMRは、初期化から開始し、線形最小二乗法のサブ問題を反復的に解き、収束するまで更新します。最小二乗法のサブ問題はランク落ちであるため、GNMRは最小ノルム解を選択し、明示的な正則化を行わなくてもとの間のバランスを維持します。このアルゴリズムは、強力な理論的保証を持つことが示されています。さらに、その単純さにもかかわらず、実験結果から、GNMRは、特に観測値がスパースな場合や行列が悪条件である場合に、いくつかの一般的なアルゴリズムよりも優れた性能を示すことが示されています。 ( U 0 , V 0 ) {\displaystyle (U_{0},V_{0})} U t + 1 ← U t + Δ U , {\displaystyle U_{t+1}\leftarrow U_{t}+\Delta U,} V t + 1 ← V t + Δ V {\displaystyle V_{t+1}\leftarrow V_{t}+\Delta V} U {\displaystyle U} V {\displaystyle V}

離散を考慮した行列補完

レコメンデーションシステムなどのアプリケーションでは、行列のエントリが離散的（例えば、1から5までの整数評価）であるため、この離散性を行列補完問題に組み込むことでパフォーマンスを向上させることができます。離散を考慮した行列補完アプローチでは、補完された行列のエントリが有限の離散アルファベットに一致するように促す正則化子を導入します。

この分野における初期の手法では、離散性を強制するために、 -ノルムを-ノルムの凸緩和として利用し、近似勾配法を用いた効率的な最適化を可能にしました。これを基に、Führlingら (2023) [14]は、-ノルムを-ノルムの連続かつ微分可能な近似に置き換えることで、問題をより扱いやすくし、性能を向上させました。 ℓ 1 {\displaystyle \ell _{1}} ℓ 0 {\displaystyle \ell _{0}} ℓ 1 {\displaystyle \ell _{1}} ℓ 0 {\displaystyle \ell _{0}}

離散を考慮した行列完成問題は次のように定式化できます。

arg ⁡ min X ∈ R m × n f ( X ) + λ g ( X ) + ζ r ( X ∣ 0 ) , {\displaystyle {\underset {{\boldsymbol {X}}\in \mathbb {R} ^{m\times n}}{\arg \min }}\,f({\boldsymbol {X}})+\lambda g({\boldsymbol {X}})+\zeta r({\boldsymbol {X}}\mid 0),}

どこ：

  • ( X ) = 1 2 ‖ P Ω ( X − O ) ‖ F 2 {\displaystyle ({\boldsymbol {X}})={\frac {1}{2}}\left\|P_{\Omega }({\boldsymbol {X}}-{\boldsymbol {O}})\right\|_{F}^{2}} は観測されたエントリへの忠実性を保証します。 は観測されたセットへの射影として、 は観測された行列として使用されます。 P Ω {\displaystyle P_{\Omega }} Ω {\displaystyle \Omega } O {\displaystyle {\boldsymbol {O}}}
  • g ( X ) = ‖ X ‖ ∗ {\displaystyle g({\boldsymbol {X}})=\|{\boldsymbol {X}}\|_{*}} 低位構造を強制する核規範です。
  • r ( X ∣ 0 ) = ∑ k = 1 | A | ‖ vec Ω ¯ ⁡ ( X ) − a k 1 ‖ 0 {\displaystyle r({\boldsymbol {X}}\mid 0)=\sum _{k=1}^{|{\mathcal {A}}|}\left\|\operatorname {vec} _{\overline {\Omega }}({\boldsymbol {X}})-a_{k}\mathbf {1} \right\|_{0}} は離散空間正則化子であり、 は離散アルファベット（例：{1, 2, 3, 4, 5}）であり、は観測されないエントリの集合です。 A {\displaystyle {\mathcal {A}}} Ω ¯ {\displaystyle {\overline {\Omega }}}

この非凸問題を解くために、 -ノルムを連続関数で近似します。この近似は分数計画法を用いて凸化され、問題は一連の凸部分問題に変換されます。 ℓ 0 {\displaystyle \ell _{0}}

このアルゴリズムは、離散空間正則化に近似演算を適用し、特異値閾値処理によって低ランク制約を強制することで、行列推定値を反復的に更新する。-ノルムベースの手法による解でプロセスを初期化することで、収束を加速することができる。MovieLens-100kなどのデータセットでテストされたシミュレーション結果は、この手法が-ノルムベースの先行手法および他の最先端技術の両方よりも優れていることを示しており、特に観測エントリの比率が低い場合（例えば20%から60%）に顕著である。[14] ℓ 1 {\displaystyle \ell _{1}} ℓ 1 {\displaystyle \ell _{1}}

アプリケーション

行列補完のいくつかの応用は、カンデスとプラン[9]によって次のように要約されている。

協調フィルタリング

協調フィルタリングとは、多数のユーザーから嗜好情報を収集することで、ユーザーの興味について自動的に予測を行うタスクです。Apple、Amazon、Barnes & Noble、Netflixなどの企業は、部分的な知識からユーザーの嗜好を予測しようと試みています。このような行列補完問題では、個人の嗜好や嗜好に影響を与える要素は通常ごくわずかであるため、未知の完全な行列は低ランクとみなされることが多いです。

システム識別

制御においては、離散時間線形時間不変状態空間モデルを適合させたい。

x ( t + 1 ) = A x ( t ) + B u ( t ) y ( t ) = C x ( t ) + D u ( t ) {\displaystyle {\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}}

入力と出力のシーケンス へのベクトル は、時刻 におけるシステムの状態であり、システムモデルの順序です。入力/出力のペアから、行列と初期状態を復元することが求められます。この問題は、低ランク行列補完問題として捉えることもできます。 u ( t ) ∈ R m {\displaystyle u(t)\in \mathbb {R} ^{m}} y ( t ) ∈ R p , t = 0 , … , N {\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N} x ( t ) ∈ R n {\displaystyle x(t)\in \mathbb {R} ^{n}} t {\displaystyle t} n {\displaystyle n} A , B , C , D {\displaystyle A,B,C,D} x ( 0 ) {\displaystyle x(0)}

モノのインターネット（IoT）のローカリゼーション

IoTセンサーネットワークでは、位置推定（または全地球測位）問題が自然に発生します。この問題は、局所的または部分的なペアワイズ距離の集合から、ユークリッド空間におけるセンサーマップを復元することです。したがって、センサーが2次元平面に配置されている場合はランク2、3次元空間に配置されている場合はランク3の行列完成問題となります。[18]

ソーシャルネットワークの回復

現実世界のソーシャルネットワークのほとんどは、低ランクの距離行列を持っています。プライベートノード、限られたストレージや計算リソースなどの理由により、ネットワーク全体を測定できない場合、距離エントリの一部しか把握できません。犯罪ネットワークはそのようなネットワークの良い例です。低ランク行列補完は、これらの観測されていない距離を復元するために使用できます。[19]

参照

参考文献

  1. ^ ジョンソン、チャールズ・R. (1990). 「行列完成問題：概観」.行列理論とその応用. 応用数学シンポジウム論文集. 第40巻. pp.  171– 198. doi :10.1090/psapm/040/1059486. ISBN  9780821801543。
  2. ^ Laurent, Monique (2008). 「行列完成問題」.最適化百科事典. 第3巻. pp.  221– 229. doi :10.1007/978-0-387-74759-0_355. ISBN  978-0-387-74758-3。
  3. ^ abcde Candès, EJ; Recht, B. (2009). 「凸最適化による正確な行列完成」.計算数学の基礎. 9 (6): 717– 772. arXiv : 0805.4471 . doi : 10.1007/s10208-009-9045-5 .
  4. ^ Recht, B. (2009). 「行列補完へのよりシンプルなアプローチ」(PDF) . Journal of Machine Learning Research . 12 : 3413–3430 . arXiv : 0910.0651 . Bibcode :2009arXiv0910.0651R.
  5. ^ Xu, Zhiqiang (2018). 「低ランク行列回復のための最小測定数」.応用および計算調和解析. 44 (2): 497– 508. arXiv : 1505.07204 . doi :10.1016/j.acha.2017.01.005. S2CID  11990443.
  6. ^ ab Candès, EJ; Tao, T. (2010). 「凸緩和の威力：近似最適行列補完」. IEEE Transactions on Information Theory . 56 (5): 2053– 2080. arXiv : 0903.1476 . Bibcode :2010ITIT...56.2053C. doi :10.1109/TIT.2010.2044061. S2CID  1255437.
  7. ^ ab Tao, T. (2009年3月10日). 「凸緩和の威力：近似最適行列補完」.新着情報.
  8. ^ ab Nguyen, LT; Kim, J.; Shim, B. (2019年7月10日). 「低ランク行列補完：現代的​​概観」. IEEE Access . 7 (1): 94215–94237 . arXiv : 1907.11705 . Bibcode :2019arXiv190711705N. doi :10.1109/ACCESS.2019.2928130. S2CID  198930899.
  9. ^ abc Candès, EJ; Plan, Y. (2010). 「ノイズ付き行列補完」. Proceedings of the IEEE . 98 (6): 925– 936. arXiv : 0903.3131 . doi :10.1109/JPROC.2009.2035722. S2CID  109721.
  10. ^ ab Eriksson, B.; Balzano, L.; Nowak, R. (2011). 「欠損データを含む高ランク行列補完と部分空間クラスタリング」arXiv : 1112.5629 [cs.IT].
  11. ^ ab Keshavan, RH; Montanari, A.; Oh, S. (2010). 「少数のエントリからの行列完成」. IEEE Transactions on Information Theory . 56 (6): 2980– 2998. arXiv : 0901.3150 . Bibcode :2010ITIT...56.2980K. doi :10.1109/TIT.2010.2046205. S2CID  53504.
  12. ^ abc Jain, P.; Netrapalli, P.; Sanghavi, S. (2013). 「交互最小化を用いた低ランク行列補完」.第45回ACMシンポジウム論文集. ACM. pp.  665– 674. arXiv : 1212.0467 . doi :10.1145/2488608.2488693. ISBN  978-1-4503-2029-0. S2CID  447011。
  13. ^ ab Zilber, Pini; Nadler, Boaz (2022). 「GNMR: 低ランク行列復元のための証明可能な1行アルゴリズム」. SIAM Journal on Mathematics of Data Science . 4 (2): 909– 934. doi :10.1137/21M1433812. PMC 11784930. PMID 39896132  . 
  14. ^ abc Führling, Niclas; Ando, Kengo; Abreu, Giuseppe Thadeu Freitas de; González G., David; Gonsa, Osvaldo (2023). 「凸型\ell_0ノルム近似による離散的認識行列補完」. IEEE Transactions on Signal Processing . XX (X): XXX– XXX. doi :10.1109/TSP.2023.XXXXXXX (2025年7月1日非アクティブ).{{cite journal}}: CS1 maint: DOI inactive as of July 2025 (link)
  15. ^ ab Cai, J.-F.; Candès, EJ; Shen, Z. (2010). 「行列補完のための特異値閾値アルゴリズム」. SIAM Journal on Optimization . 20 (4): 1956– 1982. arXiv : 0810.3286 . doi :10.1137/080738970. S2CID  1254778.
  16. ^ ab Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021). 「混合射影円錐最適化：ランク制約のモデリングにおける新たなパラダイム」.オペレーションズ・リサーチ. 70 (6): 3321– 3344. arXiv : 2009.10395 . doi :10.1287/opre.2021.2182. S2CID  221836263.
  17. ^ Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2023). 「低ランク最適化に関する新たな視点」. Optimization Online . 202 ( 1–2 ): 47–92 . arXiv : 2105.05947 . doi :10.1007/s10107-023-01933-9.
  18. ^ Nguyen, LT; Kim, J.; Kim, S.; Shim, B. (2019). 「低ランク行列補完によるIoTネットワークのローカリゼーション」. IEEE Transactions on Communications . 67 (8): 5833– 5847. Bibcode :2019ITCom..67.5833N. doi :10.1109/TCOMM.2019.2915226. S2CID  164605437.
  19. ^ Mahindre, G.; Jayasumana, AP; Gajamannage, K.; Paffenroth, R. (2019). 「有向ソーシャルネットワークのトポロジーのサンプリングと復元について – 低ランク行列補完に基づくアプローチ」2019 IEEE 第44回ローカルコンピュータネットワーク会議 (LCN) . IEEE. pp.  324– 331. doi :10.1109/LCN44214.2019.8990707. ISBN  978-1-7281-1028-8. S2CID  211206354。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Matrix_completion&oldid=1322920821"