奇異值分解

💡

質問やフィードバックがありましたら、フォームからお願いします

特異値分解（Singular Value Decomposition）とは

特異値分解は、私にとって行列の本質を探求するプロセスであり、非常に重要な行列分解の一つです。

高校や大学の線形代数の授業を思い出すと、最も一般的な行列分解はLU分解でした。

当時、線形方程式 $Ax=b$ を解くためには、まずAの逆行列を求めればよいのではないかとずっと考えていました。なぜわざわざ行列を分解する必要があるのか、授業では行列分解の目的についてあまり触れられず、手計算が強調されたため、非常に悪い思い出が残っています。この部分については、後の章で触れますので、どうぞお楽しみに～

本題に戻ると、特異値分解は行列を3つの行列に分解することができます：

A=U\Sigma V^{T}

ここで、Uは $AA^T$ の固有ベクトルから構成された行列で、Uは必ず直交行列になります。

$\Sigma$ は対角行列であり、 $AA^T$ または $A^TA$ の固有値の平方根です。 $AA^T$ の特性により、固有値は常に非負数です。通常、固有値は大きい順に並べられます。

$V^T$ は $A^TA$ の固有ベクトルから構成された行列で、こちらも直交行列です。

エンジニアの視点から大まかに理解すると、各行列はこの3つの操作に分解できると考えられます：

U: 回転

S: 拡大または縮小

V: 回転

しかし、画像の観点から考えると、各画像は無数のより単純な固有ベクトルが回転と拡大縮小の組み合わせによって構成されていると想像できます。

応用

SVDは様々な分野で非常に一般的に使用されており、いくつかの一般的な応用を紹介します。最後に画像圧縮を例として締めくくります。

主成分分析

時には、データを分析する際に特徴数が多すぎてデータ間の関係を直感的に把握できないことがあります。データ分析において一般的な方法の一つが主成分分析です。核心的な概念は、データの共分散行列を固有ベクトル（主成分）に投影して次元削減を達成することです。

https://link.medium.com/hqd7YIs1SCb

レコメンデーションシステム

Netflixは自社のレコメンデーションシステムの精度を向上させるためにコンペティションを開催し、最終的にBellKor’s Pragmatic Chaosチームが10%の改善を達成して優勝しました。当時の突破口の一つは、あるチームがSVDを使ってアルゴリズムを改善したことで、他のチームも次々とSVDを使用し始めたことです。

レコメンデーションシステムでは、ユーザーの好みは少数の要因によってのみ影響を受けるべきであり、レコメンデーションシステムでは欠損値の問題がしばしば発生します。そのため、Netflixのコンペ中にFunk SVDが発明され、レコメンデーションシステムで一般的に直面する疎行列の問題を解決し、2つの行列に分解されました。

詳細な解説はこのサイトを参照してください。

画像圧縮

画像をピクセルで満たされた行列と考えることができ、画像の行列に特異値分解を行うことは、その画像にとって最も重要な固有ベクトルの固有値を見つけることに相当します。前のいくつかの特異値を選び出し、重要でないものを取り除くことで、行列のサイズを減少させることができ、同時に良好な効果を得ることができます。

import numpy as np
from PIL import Image
import matplotlib.pyplot as plt

image = Image.open('./pizza.jpg')
image_array = np.array(image.convert('L')) # グレースケールに変換して処理しやすくする

U, S, VT = np.linalg.svd(image_array) # 特異値分解
k = 50 # 上位50の特異値を取得

# 元の画像行列を U * S（上位50の特異値） * Vt に変換
image_compressed = U[:, :k] @ np.diag(S[:k]) @ VT[:k, :]
image_compressed = np.clip(image_compressed, 0, 255)
image_compressed = image_compressed.astype('uint8')
plt.imshow(image_compressed, cmap='gray')
plt.show()