Truncated SVD (2023)

PCA

主成分分析 (PCA) は、以前の投稿で扱ったため、ここでは要約のみとします。

PCAによるデータ削減は、データを線形変換して新しい座標系に写すことで達成されます。この新しい座標系では、元のデータよりも少ない次元で（ほとんどの）データの変動を説明できます。

詳細には立ち入りませんが、これには共分散行列の固有値分解が含まれます。

［画像: Principal Component Analysis］

特異値分解 (SVD) は、実数行列 M を M=U*Σ*V^T となる3つの行列 U, Σ, V に分解する行列分解技術です。

M が mxn の場合、U は mxm、Σ は mxn、V は nxn となります。U と V はどちらも正規直交行列であり、Σ は非負の係数を持つ長方形対角行列です。

これはPCAと非常によく似ていますが、SVDの分解はデータ行列に対して行われるのに対し、PCAの分解は共分散行列に対して行われます。

Σ の対角係数は M の特異値として知られており、特異値が減少順に並べられるようにSVDを並べ替えるのが一般的です。非ゼロの特異値の数は M のランクに等しくなります。

SVDはPCAと密接に関連しています。

• V の列は主方向/軸（固有ベクトル）です。
• U*Σ の列は主成分（スコア）です。
• 特異値は共分散行列の固有値に関連しています。

Wikipediaより:

［画像: SVD matrices］

Truncated SVD

月の1024x1024のグレースケール画像で試してみましょう。

［画像: Truncated SVD (moon)］

このような画像は、それぞれ1024個の成分を持つ1024個のベクトルとして解釈できます。つまり、1024次元空間内の1024個のベクトルの集合です。

この集合に対してPCA/SVDを実行すると、3つの行列 U, Σ, V は1024x1024になります。特に、Σ は正方対角行列になります。つまり、対角上の係数のみがゼロでない可能性があります。対角インデックスが（左上から）大きいものから小さいものへとソートされるように3つの行列を並べ替えるのが一般的です。

Truncated SVD は、単純に、上位 n 個の係数以外はすべて Σ の係数をゼロにする行為です。

係数の切り捨ては、U と V の 1024-n 列も破棄することを意味します（それらはゼロと掛け合わされるため）。

切り捨てられた行列 U'、Σ'、V'^T を使用して元の行列 M'=U'*Σ'*V'^T を再構築すると、M' が得られ、これは M に似たものになります。ドロップする係数が少ないほど、M' は M をより正確に近似します。しかし、PCA/SVDの情報保持特性により、上位の係数をいくつか保持するだけで、元の情報のすべて（またはほぼすべて）を復元するのに十分な場合があります。

月の再構築

上記のすべてを月の画像に適用してみましょう。単一の値 n で切り捨てるのはあまり示唆的ではないため、代わりに n をその全範囲にわたってスイープし、近似がどのように振る舞うかを見ていきます。

以下の画像とビデオはすべて同じレイアウトを共有しています。

• 左半分は再構築された行列 M' です。
• 右半分は再構築誤差 abs(M-M') です。
• 減少する黄色いグラフは、ゼロアウトされる特異値が少なくなるにつれてのMSEです。

［画像: Truncated SVD (moon)］

このスクリーンショットは、わずか32個（1024個中）のコンポーネントで再構築された M' です。右クリックして新しいタブで開くと、1:1の品質で見ることができます。

それらの32個のコンポーネントが実際にどれだけのコストだったのか、立ち止まって考える価値があります。切り捨てられた因子は U' (1024x32)、生き残った32個の特異値、そして V' (1024x32) です。これは65536個の数値であり、M の1048576個の数値と比較すると、16倍の削減率です。それにもかかわらず、画像はまだ月として認識できます。

以下は、再構築に使用されるコンポーネントが増えるにつれて同じ画像ペアを示すビデオです。ほとんどの「アクション」は最初の数フレームで発生します。

［画像: Truncated SVD sequence (moon)］

ここで注目すべきは（PCA/SVDの魔法）、誤差グラフがどれほど速く減少するかということです。これは、最初のコンポーネントが M に存在する情報の大部分を捉えているのに対し、後続のコンポーネントは高周波/低振幅の細かいディテールしか運ばないことを証明しています。

これは、フーリエ変換、コサイン/サイン変換などと同様のことを思い出させます。これらの変換は空間と周波数の二重性を扱いますが、PCA/SVDは純粋に分散駆動の基底変換です。しかし、同様の方法で、これらのすべての手法は情報を二重形式に変換し、「情報の量」が構造化された、管理しやすい方法で現れます。

FT/CTなどは、人間の知覚システムが輝度（色度に対して）や低周波（高周波に対して）に敏感であることを利用する.jpeg、.mp3などの圧縮システムの基盤となっています。

SVD/PCAの場合、Σ の上位係数は下位の係数よりも多くのデータ分散を捉えます。

これらのシーケンスは、2、4、8、16、32、64、128個の係数での再構築です。

［画像: Truncated SVD sequence (boi)］

簡単なケースと難しいケース

前述のように、行列分解は、データに行が互いに線形従属である特別な空間への基底変換として解釈できます。そのような場合、より低いランクの U/V 行列で元の行列を正確に再構築するのに十分です。実際、Σ は、データの損失なしに破棄できる行/列の数だけ、対角線上にゼロ値の係数を持ちます。

極端なケースは以下（中心化された正方形のボックス形状）で示されています。この場合、1個の係数/行/列で十分です。この場合、形状の内側と外側では、すべての行/列が同一です。ちなみに、ボックスは分離可能な畳み込みフィルタです（将来的に低ランク畳み込みに関する投稿を予定しています）。

［画像: Truncated SVD (rect)］

形状を回転させると、PCA/SVDはそのような基底変換を「自動検出」する能力がありますが、悲惨な結果になります。しかし、ここでは離散数学を扱っており、回転した形状は「ピクセル化」され、分解が数値的に純粋でなくなります。

最初の数フレームのビデオで、再構築が「未回転の正方形であろうと固執している」ように見えるのは面白いです。

［画像: Truncated SVD (tilted rect)］

［動画］

以下は五角形の形状です。

［画像: Truncated SVD (pentagon)］

［動画］

実用的な用途

データ分析における次元削減以外にも、SVDの切り捨てには興味深い実用的な用途があります。

データ圧縮

Bart Wronski は、この技術を使用したPBRテクスチャセットの圧縮に関する非常に興味深い記事を書いています。

BCnテクスチャ圧縮も次元削減に基づいています。このトピックに関するNathan Reed による良い記事があります。

低ランク近似

低ランク近似。

Bart Wronski によるもう一つの興味深い記事です。いつか低ランク畳み込みに関する独自の投稿をしたいと思っています。

実装の詳細

Maverick (https://maverickrender.com/) のAPIには、この投稿の画像/ビデオに使用した古いPCA/SVD C++コードがありました。しかし、Atrix256 によるこの記事を読んだ後、古いxsvd_cクラスの実装部分をEigenに置き換えるという決断をするかもしれません。