低ランク近似

数学において、低ランク近似とは、与えられた行列をより低いランクの行列で近似するプロセスを指します。より正確には、これは最小化問題であり、コスト関数は、近似行列のランクが低減されているという制約の下で、与えられた行列 (データ) と近似行列 (最適化変数) との適合度を測定します。この問題は、数学的モデリングとデータ圧縮に使用されます。ランク制約は、データに適合するモデルの複雑さに関する制約に関連しています。アプリケーションでは、ランク制約とは別に、非負性やハンケル構造など、近似行列に対する他の制約が課されることがよくあります。

低ランク近似は、主成分分析、因子分析、全最小二乗法、潜在意味解析、直交回帰、動的モード分解など、他の多くの手法と密接に関連しています。

与えられた

• 構造仕様、${\displaystyle {\mathcal {S}}:\mathbb {R} ^{n_{p}}\to \mathbb {R} ^{m\times n}}$
• 構造パラメータのベクトル、${\displaystyle p\in \mathbb {R} ^{n_{p}}}$
• 規範 、そして${\displaystyle \|\cdot \|}$
• 希望ランク、${\displaystyle r}$

${\displaystyle {\text{最小化}}\quad {\text{以上}}{\widehat {p}}\quad \|p-{\widehat {p}}\|\quad {\text{条件付き}}\quad \operatorname {ランク} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r.}$

• 線形システム識別。この場合、近似行列はハンケル構造になります。
• 機械学習では、近似行列は非線形に構造化されます。
• 推奨システム。この場合、データ マトリックスには欠損値があり、近似はカテゴリになります。
• 距離行列の完成。この場合には、正定値制約があります。
• 自然言語処理。この場合、近似値は非負になります。
• コンピュータ代数。この場合、近似はシルベスター構造になります。

フロベニウスノルムで測定された適合度を持つ非構造化問題、すなわち、

${\displaystyle {\text{最小化}}\quad {\text{以上}}{\widehat {D}}\quad \|D-{\widehat {D}}\|_{\text{F}}\quad {\text{以下}}\quad \operatorname {ランク} {\big (}{\widehat {D}}{\big )}\leq r}$

は、データ行列の特異値分解によって解析的に解くことができる。この結果は、行列近似補題またはエッカート・ヤング・ミルスキー定理と呼ばれる。この問題は、もともとエアハルト・シュミット^[1]によって無限次元の積分作用素の文脈で解決された（ただし、彼の方法はヒルベルト空間上の任意のコンパクト作用素に簡単に一般化できる） 。その後、C.エッカートとG.ヤング^{[2]によって再発見された。L} .ミルスキーは、 この結果を任意のユニタリ不変ノルムに一般化した。^[3]

${\displaystyle D=U\Sigma V^{\top }\in \mathbb {R} ^{m\times n},\quad m\geq n}$

を の特異値分解とします。ここで は特異値 を持つ直交対角行列です。 が与えられた場合、 、、 を次のように 分割します。${\displaystyle D}$${\displaystyle \Sigma =:\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{m})}$${\displaystyle m\times m}$${\displaystyle \sigma _{1}\geq \ldots \geq \sigma _{m}}$${\displaystyle r\in \{1,\dots ,m-1\}}$${\displaystyle U}$${\displaystyle \Sigma }$${\displaystyle V}$

${\displaystyle U=:{\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}},\quad \Sigma =:{\begin{bmatrix}\Sigma _{1}&0\\0&\Sigma _{2}\end{bmatrix}},\quad {\text{and}}\quad V=:{\begin{bmatrix}V_{1}&V_{2}\end{bmatrix}},}$

ここで、は、は、はである。すると、切り捨て特異値分解から得られる階数行列は、 ${\displaystyle U_{1}}$${\displaystyle m\times r}$${\displaystyle \Sigma _{1}}$${\displaystyle r\times r}$${\displaystyle V_{1}}$${\displaystyle n\times r}$${\displaystyle r}$

${\displaystyle {\widehat {D}}^{*}=U_{1}\Sigma _{1}V_{1}^{\top },}$

というのは

${\displaystyle \|D-{\widehat {D}}^{*}\|_{\text{F}}=\min _{\operatorname {rank} ({\widehat {D}})\leq r}\|D-{\widehat {D}}\|_{\text{F}}={\sqrt {\sigma _{r+1}^{2}+\cdots +\sigma _{m}^{2}}}.}$

最小化関数は、 の場合にのみ一意です。 ${\displaystyle {\widehat {D}}^{*}}$${\displaystyle \sigma _{r+1}\neq \sigma _{r}}$

をの実数（おそらく長方形）行列とする。 ${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle m\leq n}$

${\displaystyle A=U\Sigma V^{\top }}$

は の特異値分解です。と は直交行列であり、 は となる要素を持つ対角行列であることを思い出してください。 ${\displaystyle A}$${\displaystyle U}$${\displaystyle V}$${\displaystyle \Sigma }$${\displaystyle m\times n}$ ${\displaystyle (\sigma _{1},\sigma _{2},\cdots ,\sigma _{m})}$${\displaystyle \sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{m}\geq 0}$

スペクトルノルムにおけるの最良のランク近似は で表され、次のように与えられると 主張する。${\displaystyle k}$${\displaystyle A}$${\displaystyle \|\cdot \|_{2}}$

${\displaystyle A_{k}:=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}$

ここで、およびはそれぞれ、およびの 番目の列を表します。 ${\displaystyle u_{i}}$${\displaystyle v_{i}}$${\displaystyle i}$${\displaystyle U}$${\displaystyle V}$

まず、

${\displaystyle \|A-A_{k}\|_{2}=\left\|\sum _{i=1}^{\color {red}{n}}\sigma _{i}u_{i}v_{i}^{\top }-\sum _{i=1}^{\color {red}{k}}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{2}=\left\|\sum _{i=\color {red}{k+1}}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{2}=\sigma _{k+1}}$

したがって、 と に列がある場合、 であることを示す必要があります。 ${\displaystyle B_{k}=XY^{\top }}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle k}$${\displaystyle \|A-A_{k}\|_{2}=\sigma _{k+1}\leq \|A-B_{k}\|_{2}}$

には列があるため、 の最初の列の非自明な線形結合が存在する必要があります。つまり、 ${\displaystyle Y}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle V}$

${\displaystyle w=\gamma _{1}v_{1}+\cdots +\gamma _{k+1}v_{k+1},}$

となる。一般性を失うことなく、となるようにスケール化できる。または（同値として）となる。したがって、 ${\displaystyle Y^{\top }w=0}$${\displaystyle w}$${\displaystyle \|w\|_{2}=1}$${\displaystyle \gamma _{1}^{2}+\cdots +\gamma _{k+1}^{2}=1}$

${\displaystyle \|A-B_{k}\|_{2}^{2}\geq \|(A-B_{k})w\|_{2}^{2}=\|Aw\|_{2}^{2}=\gamma _{1}^{2}\sigma _{1}^{2}+\cdots +\gamma _{k+1}^{2}\sigma _{k+1}^{2}\geq \sigma _{k+1}^{2}.}$

上記の不等式の両辺の平方根を取ると、結果が導き出されます。

をの実数（おそらく長方形）行列とする。 ${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle m\leq n}$

${\displaystyle A=U\Sigma V^{\top }}$

は の特異値分解です。 ${\displaystyle A}$

フロベニウスノルムにおけるへの最良ランク近似は で表され、次のように与えられる と主張する。${\displaystyle k}$${\displaystyle A}$${\displaystyle \|\cdot \|_{F}}$

${\displaystyle A_{k}=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}$

ここで、およびはそれぞれ、およびの 番目の列を表します。 ${\displaystyle u_{i}}$${\displaystyle v_{i}}$${\displaystyle i}$${\displaystyle U}$${\displaystyle V}$

まず、

${\displaystyle \|A-A_{k}\|_{F}^{2}=\left\|\sum _{i=k+1}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}}$

したがって、とに列が ある場合、${\displaystyle B_{k}=XY^{\top }}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle k}$

${\displaystyle \|A-A_{k}\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}\leq \|A-B_{k}\|_{F}^{2}.}$

スペクトルノルムを持つ三角不等式により、 ならば となる。およびがそれぞれ、およびの上記のSVD法による階数近似を表すものとする。すると、任意の${\displaystyle A=A'+A''}$${\displaystyle \sigma _{1}(A)\leq \sigma _{1}(A')+\sigma _{1}(A'')}$${\displaystyle A'_{k}}$${\displaystyle A''_{k}}$${\displaystyle k}$${\displaystyle A'}$${\displaystyle A''}$${\displaystyle i,j\geq 1}$

${\displaystyle {\begin{aligned}\sigma _{i}(A')+\sigma _{j}(A'')&=\sigma _{1}(A'-A'_{i-1})+\sigma _{1}(A''-A''_{j-1})\\&\geq \sigma _{1}(A-A'_{i-1}-A''_{j-1})\\&\geq \sigma _{1}(A-A_{i+j-2})\qquad ({\text{since }}{\rm {rank}}(A'_{i-1}+A''_{j-1})\leq i+j-2))\\&=\sigma _{i+j-1}(A).\end{aligned}}}$

、およびのとき、について次のように結論づけられる。${\displaystyle \sigma _{k+1}(B_{k})=0}$${\displaystyle A'=A-B_{k}}$${\displaystyle A''=B_{k}}$${\displaystyle i\geq 1,j=k+1}$

${\displaystyle \sigma _{i}(A-B_{k})\geq \sigma _{k+i}(A).}$

したがって、

${\displaystyle \|A-B_{k}\|_{F}^{2}=\sum _{i=1}^{n}\sigma _{i}(A-B_{k})^{2}\geq \sum _{i=k+1}^{n}\sigma _{i}(A)^{2}=\|A-A_{k}\|_{F}^{2},}$

必要に応じて。

フロベニウスノルムは近似誤差のすべての要素を均一に重み付けします 。誤差の分布に関する事前知識は、重み付き低ランク近似問題を考慮することで考慮できます。 ${\displaystyle D-{\widehat {D}}}$

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {D}}\quad \operatorname {vec} (D-{\widehat {D}})^{\top }W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad \operatorname {rank} ({\widehat {D}})\leq r,}$

ここで、行列を 列ごとにベクトル化し、与えられた正（半）定値重み行列です。 ${\displaystyle {\text{vec}}(A)}$ ${\displaystyle A}$${\displaystyle W}$

一般的な重み付き低ランク近似問題は、特異値分解による解析解を許容せず、局所最適化法によって解決されますが、局所最適化法では、全体的に最適な解が見つかるという保証はありません。

相関のない重みの場合、重み付き低ランク近似問題は次のように定式化することもできます。^{[4] [5]}非負行列と行列に対して、最大でランク の行列 、 、を最小化します。 ${\displaystyle W}$${\displaystyle A}$${\displaystyle \sum _{i,j}(W_{i,j}(A_{i,j}-B_{i,j}))^{2}}$${\displaystyle B}$${\displaystyle r}$

とする。 の場合、最も速いアルゴリズムは で実行される。^{[6] [7]}使用されている重要なアイデアの1つは、Oblivious Subspace Embedding（OSE）と呼ばれ、Sarlosによって最初に提案されました。^[8]${\displaystyle \|A\|_{p}=\left(\sum _{i,j}|A_{i,j}^{p}|\right)^{1/p}}$${\displaystyle p=2}$${\displaystyle nnz(A)+n\cdot poly(k/\epsilon )}$

については、このエントリワイズL1ノルムは外れ値が存在する場合にフロベニウスノルムよりもロバストであることが知られており、ノイズに関するガウス仮定が適用されない可能性があるモデルで示されます。 を最小化しようとするのは自然なことです。^[9]およびについては、証明可能な保証を備えたアルゴリズムがいくつかあります。^{[10] [11]}${\displaystyle p=1}$${\displaystyle \|B-A\|_{1}}$${\displaystyle p=0}$${\displaystyle p\geq 1}$

とを任意の距離空間の2つの点集合とします。 が行列を表すとします。ここで。このような距離行列はソフトウェアパッケージで一般的に計算され、画像多様体の学習、手書き認識、多次元展開などに応用されています。記述サイズを縮小する試みとして、 ^{[12] [13]}ではこのような行列の低ランク近似を研究することができます。 ${\displaystyle P=\{p_{1},\ldots ,p_{m}\}}$${\displaystyle Q=\{q_{1},\ldots ,q_{n}\}}$${\displaystyle A}$${\displaystyle m\times n}$${\displaystyle A_{i,j}=dist(p_{i},q_{i})}$

分散およびストリーミング設定における低ランク近似問題は^{[14]で検討されている。}

同値の使用

${\displaystyle \operatorname {rank} ({\widehat {D}})\leq r\quad \iff \quad {\text{there are }}P\in \mathbb {R} ^{m\times r}{\text{ and }}L\in \mathbb {R} ^{r\times n}{\text{ such that }}{\widehat {D}}=PL}$

そして

${\displaystyle \operatorname {rank} ({\widehat {D}})\leq r\quad \iff \quad {\text{there is full row rank }}R\in \mathbb {R} ^{m-r\times m}{\text{ such that }}R{\widehat {D}}=0}$

重み付き低ランク近似問題はパラメータ最適化問題と同等になる

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {D}},P{\text{ and }}L\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad {\widehat {D}}=PL}$

そして

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {D}}{\text{ and }}R\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad R{\widehat {D}}=0\quad {\text{and}}\quad RR^{\top }=I_{r},}$

ここで はサイズ の単位行列です。 ${\displaystyle I_{r}}$${\displaystyle r}$

ランク制約のイメージ表現は、もう 1 つの変数を固定し、もう 1つの変数 (または) に対してコスト関数を交互に最小化するパラメータ最適化手法を示唆しています。 と の両方に対する同時最小化は困難な双凸最適化問題ですが、変数の 1 つだけに対する最小化は線形最小二乗問題であり、全体的に効率的に解くことができます。 ${\displaystyle P}$${\displaystyle L}$${\displaystyle P}$${\displaystyle L}$

結果として得られる最適化アルゴリズム (交互投影と呼ばれる) は、線形収束率で、重み付き低ランク近似問題の局所的最適解にグローバルに収束します。(または) パラメータの開始値を指定する必要があります。ユーザー定義の収束条件が満たされると、反復は停止します。 ${\displaystyle P}$${\displaystyle L}$

重み付き低ランク近似のための交互投影アルゴリズムの Matlab実装:

function [dh, f] = wlra_ap ( d, w, p, tol, maxiter ) [ m , n ] = size ( d ); r = size ( p , 2 ); f = inf ; for i = 2 : maxiter % L 上の最小化bp = kron ( eye ( n ), p ); vl = ( bp ' * w * bp ) \ bp ' * w * d (:); l = reshape ( vl , r , n ); % P 上の最小化bl = kron ( l ' , eye ( m )); vp = ( bl ' * w * bl ) \ bl ' * w * d (:); p = reshape ( vp , m , r ); % 終了条件をチェックdh = p * l ; dd = d - dh ; f ( i ) = dd (:) ' * w * dd (:); abs ( f ( i - 1 ) - f ( i )) < tolの場合、break 、 end 、endfor 
          
   
    
       
                
         
    
       
                
         
    
             
          
             

交互投影アルゴリズムは、画像形式でパラメータ化された低ランク近似問題が変数またはに関して双線型であるという事実を利用しています。問題の双線型の性質は、変数投影と呼ばれる代替アプローチで効果的に使用されます。^[15]${\displaystyle P}$${\displaystyle L}$

再び、画像形式でパラメータ化された重み付き低ランク近似問題を考えてみましょう。変数に関する最小化（線形最小二乗問題）は、近似誤差の関数としての閉じた形式の表現につながります。${\displaystyle L}$${\displaystyle P}$

${\displaystyle f(P)={\sqrt {\operatorname {vec} ^{\top }(D){\Big (}W-W(I_{n}\otimes P){\big (}(I_{n}\otimes P)^{\top }W(I_{n}\otimes P){\big )}^{-1}(I_{n}\otimes P)^{\top }W{\Big )}\operatorname {vec} (D)}}.}$

したがって、元の問題は、に関して を最小化する非線形最小二乗問題と同等です。 この目的のために、Levenberg-Marquardt アルゴリズムなどの標準的な最適化手法を使用できます。 ${\displaystyle f(P)}$${\displaystyle P}$

重み付き低ランク近似のための変数投影アルゴリズムの Matlab実装:

関数[ dh, f] = wlra_varpro ( d, w, p, tol, maxiter ) prob = optimset (); prob.solver = ' lsqnonlin ' ; prob.options = optimset ( ' MaxIter ' , maxiter , ' TolFun ' , tol ) ; prob.x0 = p ; prob.objective = @( p ) cost_fun ( p , d , w ); [ p , f ] = lsqnonlin ( prob ) ; [ f , vl ] = cost_fun ( p , d , w ) ; dh = p * reshape ( vl , size ( p , 2 ) , size ( d , 2 ) ) ; 
     
      
        
     
      
        

関数[f, vl] = cost_fun ( p, d, w ) bp = kron ( eye ( size ( d , 2 )), p ); vl = ( bp ' * w * bp ) \ bp ' * w * d (:); f = d (:) ' * w * ( d (:) - bp * vl ); 
    
            
          

変数投影アプローチは、カーネル形式でパラメータ化された低ランク近似問題にも適用できます。この方法は、非線形最小二乗最小化の段階で削除された変数の数が残された最適化変数の数よりはるかに多い場合に効果的です。このような問題は、カーネル形式でパラメータ化されたシステム識別で発生します。この場合、削除された変数は近似軌道であり、残りの変数はモデルパラメータです。線形時間不変システムのコンテキストでは、削除手順はカルマン平滑化と同等です。

通常、新しいソリューションは低ランクであるだけでなく、アプリケーションの要件により他の凸制約も満たすことが望まれます。私たちが関心のある問題は次のとおりです。

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {p}}\quad \|p-{\widehat {p}}\|\quad {\text{subject to}}\quad \operatorname {rank} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r{\text{ and }}g({\widehat {p}})\leq 0}$

この問題は、不正確な（半正定値計画法）緩和から良い解を回復することを含め、現実世界で多くの応用があります。すべての要素が非負であることを要求するなど、追加の制約が線形である場合、この問題は構造化低ランク近似と呼ばれます。^[16]より一般的な形式は、凸制限低ランク近似と呼ばれます。 ${\displaystyle g({\widehat {p}})\leq 0}$

この問題は、多くの問題を解決するのに役立ちます。しかし、凸制約と非凸（低ランク）制約の組み合わせのため、困難です。のさまざまな実現に基づいて、さまざまな手法が開発されました。ただし、交互方向乗数法（ADMM）は、凸目的関数、ランク制約、およびその他の凸制約を持つ非凸問題を解決するために適用できるため、^[17]上記の問題を解決するのに適しています。さらに、一般的な非凸問題とは異なり、ADMMは、その双対変数が反復で収束する限り、実行可能なソリューションが収束することを保証します。 ${\displaystyle g({\widehat {p}})\leq 0}$

• CUR行列近似は元の行列の行と列から作成される。

• MT Chu、RE Funderlic、RJ Plemmons、「構造化低ランク近似」、線形代数とその応用、第366巻、2003年6月1日、157～172ページdoi :10.1016/S0024-3795(02)00505-0

• 構造化低ランク近似用の C++ パッケージ