低ランク近似

1 定義と基礎理論

1.1 数学的定式化

低ランク近似とは、与えられた行列 \( A \in \mathbb{R}^{m \times n} \) に対して、より低いランク \( k \)（\( k < \text{rank}(A) \)）を持つ行列 \( \hat{A} \) を求め、\( A \) と \( \hat{A} \) の差を最小化する問題である。数学的には、以下の最適化問題として定式化される：

\[

\min_{\hat{A} \in \mathbb{R}^{m \times n}, \, \text{rank}(\hat{A}) \leq k} \| A - \hat{A} \|_F

\]

ここで \( \| \cdot \|_F \) はフロベニウスノルムを表す。この問題は、データ行列から情報を保持しつつ次元を削減する手法の基礎を提供する。

1.2 特異値分解と低ランク近似

1.2.1 行列の特異値分解

任意の行列 \( A \in \mathbb{R}^{m \times n} \) は、特異値分解（SVD）により次のように分解できる：

\[ A = U \Sigma V^\top \]

ここで \( U \in \mathbb{R}^{m \times m} \) と \( V \in \mathbb{R}^{n \times n} \) は直交行列、\( \Sigma \in \mathbb{R}^{m \times n} \) は対角行列であり、対角成分 \( \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{\min(m,n)} \geq 0 \) は特異値と呼ばれる。この分解は、行列の構造を特異値と特異ベクトルに分解する強力なツールである。

1.2.2 エッカート・ヤングの定理

エッカート・ヤングの定理は、低ランク近似の最適解が特異値分解から直接得られることを述べる。行列 \( A \) の特異値分解を \( A = U \Sigma V^\top \) とするとき、ランク \( k \) の最適近似 \( A_k \) は次のように与えられる：

\[ A_k = U_k \Sigma_k V_k^\top \]

ここで \( U_k \) は \( U \) の最初の \( k \) 列、\( V_k \) は \( V \) の最初の \( k \) 列、\( \Sigma_k \) は上位 \( k \) 個の特異値からなる対角行列である。この近似は、すべてのランク \( k \) 行列の中で、フロベニウスノルムの意味で \( A \) に最も近い。

1.2.3 フロベニウスノルム最適性

エッカート・ヤングの定理により、低ランク近似の誤差は切り捨てられた特異値の二乗和の平方根で与えられる：

\[

\| A - A_k \|_F = \sqrt{\sum_{i=k+1}^{\min(m,n)} \sigma_i^2}

\]

この性質は、特異値の減衰が速いほど、小さなランクでも高精度な近似が可能であることを示す。また、スペクトルノルムについても同様の最適性が成立し、誤差は \( \sigma_{k+1} \) となる。

1.3 低ランク近似の幾何学的解釈

低ランク近似は、高次元空間におけるデータ点の集合を、より低次元の部分空間に射影する操作と解釈できる。行列 \( A \) の各行（または各列）を \( \mathbb{R}^n \)（または \( \mathbb{R}^m \)）上の点とみなすと、ランク \( k \) 近似はこれらの点を、元の空間内の \( k \) 次元部分空間に射影し、射影後の点が元の点に最も近くなるような部分空間を選ぶことに相当する。この部分空間は、\( A \) の右（または左）特異ベクトルの最初の \( k \) 本で張られる。

2 主な計算手法

2.1 特異値分解を用いた直接法

最も基本的な低ランク近似の計算方法は、行列全体の完全な特異値分解を計算し、その後で上位 \( k \) 個の特異値と対応する特異ベクトルを取り出す方法である。この方法は精度が高いが、計算コストが \( O(mn \cdot \min(m,n)) \) と大きいため、大規模行列には不向きである。密行列に対しては、二重対角化を経由する効率的なアルゴリズム（例えば、Golub-Reinschアルゴリズム）が用いられる。

2.2 ランダム化特異値分解

2.2.1 ランダム化手法の基本原理

ランダム化特異値分解（randomized SVD）は、ランダム行列を用いて行列の部分空間を確率的にサンプリングし、近似を高速に得る手法である。基本的なアルゴリズムは以下の通り：

1. ランダム行列 \( \Omega \in \mathbb{R}^{n \times (k+p)} \) を生成する（各要素は標準正規分布など）。
2. \( Y = A \Omega \) を計算し、\( Y \) の列が張る部分空間を求める。
3. \( Y \) のQR分解 \( Y = QR \) から直交基底 \( Q \) を得る。
4. 小さな行列 \( B = Q^\top A \) を計算し、そのSVDを求める。
5. 最終的な近似行列を \( A_k \approx Q B_k \) として得る。

ここで \( p \) はオーバーサンプリングパラメータであり、近似精度を高めるために用いる。この手法の計算コストは \( O(mn \cdot (k+p)) \) 程度であり、大規模行列に対して大幅な高速化が可能である。

2.2.2 近似誤差の確率保証

ランダム化手法の誤差は確率的に評価される。適切なオーバーサンプリング（例えば \( p = 5 \) または \( p = 10 \)）を用いると、高い確率で近似誤差が最適値の一定倍以内に収まることが知られている。具体的には、以下の不等式が成立する：

\[

\| A - A_k^{(rand)} \|_F \leq (1 + \varepsilon) \| A - A_k \|_F

\]

ここで \( \varepsilon \) はオーバーサンプリングと分布に依存する小さな定数であり、理論的には \( O(\sqrt{k \log k}) \) 程度のオーバーサンプリングで十分であることが示されている。

2.3 反復的計算手法

2.3.1 ランチョス法

ランチョス法は、大規模な疎行列に対して少数の特異値と特異ベクトルを効率的に計算するための反復手法である。この手法は、クリロフ部分空間を用いて行列を三対角行列に縮約し、その後で三対角行列の固有値問題を解くことで特異値を得る。計算量は \( O(nnz \cdot k + n \cdot k^2) \) 程度であり、行列の非零要素数 \( nnz \) にほぼ線形となる。ただし、丸め誤差による直交性の喪失を防ぐために、再直交化が必要となる場合がある。

2.3.2 アーノルディ法

アーノルディ法は、ランチョス法を非対称行列に一般化した手法である。非対称行列の特異値分解は、\( A^\top A \) または \( AA^\top \) の固有値問題に帰着されるが、アーノルディ法を直接適用することも可能である。この手法は一般にランチョス法よりも計算コストが高く、安定性の面でも注意が必要であるが、より一般の行列に対して適用できる利点がある。

2.4 非負値行列因子分解

非負値行列因子分解（NMF）は、行列の要素がすべて非負であるという制約の下で低ランク近似を行う手法である。NMFでは、近似行列を \( A \approx WH \) と分解し、\( W \geq 0 \) および \( H \geq 0 \) を課す。これにより、分解結果の解釈性が向上し、部品表現としての意味が明確になる。最適化は乗法更新則や交互最小二乗法などの反復アルゴリズムにより行われ、局所最適解に収束する。ランク \( k \) の選択や初期値に依存するため、複数回の試行が推奨される。

3 応用分野

3.1 画像処理とデータ圧縮

3.1.1 画像の低ランク近似

デジタル画像は画素値の行列として表現できる。画像の特異値分解を行うと、多くの画像で特異値が急速に減衰する性質がある。この性質を利用し、少数の特異値と特異ベクトルのみを保持することで、画像を圧縮できる。例えば、ランク \( k \) の近似は、元の画像を \( k \) 個の「成分画像」の重ね合わせとして表現する。この手法は、特に平滑な領域の多い画像（例えば、天体写真や医療画像）で効果的である。

3.1.2 JPEG圧縮との関係

JPEG圧縮は、離散コサイン変換（DCT）を用いたブロック単位の圧縮手法であり、低ランク近似とは原理が異なる。しかし、JPEGの量子化ステップは高周波成分（小さな特異値に対応）を切り捨てる操作と類似しており、情報の損失を最小限に抑えつつデータ量を削減する点で共通する。低ランク近似はJPEGのような標準化された形式として実装されてはいないが、画像のノイズ除去や背景除去などの前処理として応用されることがある。

3.2 自然言語処理

3.2.1 潜在的意味解析

潜在的意味解析（LSA）は、文書-単語行列に低ランク近似を適用し、文書と単語の背後にある「潜在的な意味」を抽出する手法である。文書-単語行列 \( X \) の各要素は、単語の出現頻度やTF-IDF重みを表す。この行列に低ランク近似（通常は特異値分解）を施すことで、同義語や多義語の影響を軽減し、文書間の意味的な類似度を高精度に計算できる。近似後の行列の列ベクトルは、各文書の低次元表現として利用される。

3.2.2 文書-単語行列の次元削減

文書-単語行列は通常、語彙数（列数）が非常に大きい高次元行列となる。低ランク近似により数百程度の次元に削減することで、計算コストの削減と過学習の防止が同時に達成される。この次元削減された表現は、文書クラスタリング、文書分類、情報検索など、様々な下流タスクで利用される。次元削減後の行列は、元の空間に比べてノイズが除去された「滑らかな」意味空間を提供する。

3.3 推薦システム

3.3.1 行列因子分解法

推薦システムにおける行列因子分解法は、ユーザー-アイテム評価行列 \( R \) を低ランク行列 \( P Q^\top \) で近似する手法である。ユーザー数を \( m \)、アイテム数を \( n \)、ランクを \( k \) とすると、\( P \in \mathbb{R}^{m \times k} \) はユーザーの潜在因子ベクトル、\( Q \in \mathbb{R}^{n \times k} \) はアイテムの潜在因子ベクトルを表す。欠損値を含む不完全な行列に対しては、観測された要素のみを用いて \( P \) と \( Q \) を学習する。目的関数は以下の通り：

\[

\min_{P,Q} \sum_{(u,i) \in \mathcal{O}} (R_{ui} - P_u^\top Q_i)^2 + \lambda (\|P\|_F^2 + \|Q\|_F^2)

\]

ここで \( \mathcal{O} \) は観測された評価の集合、\( \lambda \) は正則化パラメータである。

3.3.2 Netflix Prizeと行列因子分解

Netflix Prize（2006年～2009年）は、Netflix社が主催した推薦システムの精度を競うコンペティションである。このコンペでは、行列因子分解法を用いたチームが優勝し、低ランク近似の有効性が広く認知される契機となった。優勝アルゴリズムは、特異値分解に類似した手法に加え、時間的なバイアスやユーザーの行動変化をモデル化する拡張を含んでいた。この成果は、後続の推薦システム研究に多大な影響を与えた。

3.4 計算科学と機械学習

3.4.1 主成分分析

主成分分析（PCA）は、低ランク近似の代表的な統計的手法である。データ行列の共分散行列の固有値分解を通じて、データの分散を最大限に説明する方向（主成分）を求める。PCAはデータの次元削減、可視化、ノイズ除去に広く用いられる。実際の計算では、データ行列の特異値分解が利用されることが多く、低ランク近似の枠組みに直接含まれる。PCAは顔認識（固有顔）、遺伝子発現解析、異常検知など、多様な分野で応用されている。

3.4.2 行列補完

行列補完は、観測された一部分の要素から行列全体の欠損値を推定する問題である。低ランク性を仮定することで、観測数が行列の自由度よりも少ない場合でも、理論的に安定な補完が可能となる。Netflix問題は行列補完の典型例であり、凸最適化や特異値閾値法などの手法が開発されている。厳密な条件（例えば、インコヒーレント条件）の下では、最小限の観測数で完全な行列を復元できることが示されている。

4 限界と拡張

4.1 近似精度の理論的限界

4.1.1 ランク選択の基準

低ランク近似で適切なランク \( k \) を選択することは、応用上重要な問題である。一般的な基準として以下がある：

• エネルギー保存率：全特異値の二乗和に対する上位 \( k \) 個の特異値の二乗和の比が閾値（例えば90%や95%）を超えるように選ぶ。
• スクリープロット：特異値を降順にプロットし、傾きが急激に変化する点（エルボー点）をランクとして選択する。
• 交差検証：データを訓練とテストに分割し、テスト誤差が最小となるランクを選択する。

理論的には、特異値の減衰パターンが近似誤差の下限を決定するが、ノイズの存在により実用的なランクはそれより小さくなる場合がある。

4.1.2 特異値の減衰と情報損失

低ランク近似の質は、行列の特異値の減衰速度に強く依存する。特異値が指数関数的に減衰する行列（例えば、平滑なカーネル行列）では、小さなランクで高精度な近似が可能である。一方、特異値がゆっくりと減衰する行列（例えば、ランダム行列や一部のグラフ行列）では、情報損失を抑えるために高いランクが必要となる。このような場合、低ランク近似の有用性は限定的であり、他の次元削減手法との組み合わせが検討される。

4.2 大規模行列への拡張

4.2.1 ストリーミングアルゴリズム

現代のデータ分析では、メモリに収まらない大規模行列や、逐次的に生成されるデータストリームを扱う必要がある。ストリーミング低ランク近似アルゴリズムは、データを一度だけ（または少数回）読み込みながら近似を更新する手法である。代表的な手法として、Frequency-Augmented SVD（FREQ-SVD）や列サンプリング法がある。これらの手法は、理論的な誤差保証を持ちながら、限られたメモリと計算資源で動作する。

4.2.2 分散計算環境での実装

大規模行列の低ランク近似は、分散計算フレームワーク（Apache Spark、Hadoopなど）を用いて実装されることが多い。特異値分解の分散実装では、行列をブロックに分割し、各ノードで部分的な計算を行った後、全体を統合する。ランダム化手法は、通信コストが低く、並列化に適しているため、分散環境で特に有効である。また、疎行列の場合は、非零要素のみを分散配置することで、メモリ効率と計算効率を両立できる。

4.3 テンソルへの一般化

4.3.1 テンソル低ランク近似の定義

テンソル低ランク近似は、行列の低ランク近似を多次元配列（テンソル）に拡張した概念である。テンソルには複数のランク概念が存在し、最も一般的なものは以下である：

• CPランク：ランク1テンソルの和として表現する場合の最小個数。
• Tuckerランク：各モード（次元）ごとの行列化のランクの組。

行列の場合と異なり、テンソルの低ランク近似は一般にNP困難であり、最適解を求めることは難しい。

4.3.2 CP分解とTucker分解

CP分解（CANDECOMP/PARAFAC）は、テンソルをランク1テンソルの和に分解する手法である。各ランク1テンソルは、各モードのベクトルの外積で表される。CP分解は解釈性が高いが、ランクの決定が困難であり、最適化アルゴリズムは初期値依存性が強い。

Tucker分解は、テンソルをコアテンソルと各モードの因子行列の積で表現する手法である。Tucker分解は、行列の特異値分解の自然な一般化とみなせ、低ランク近似としても用いられる。Tucker分解の計算には、高次特異値分解（HOSVD）が用いられ、これは各モードの行列化に特異値分解を適用する方法である。Tucker分解はCP分解よりも柔軟性が高いが、因子行列が直交する場合に最適性が保証される。