📂行列代数

スパース行列

定義

自然言語において、スパース^sparse（希薄な、まばらな）とは、値が$0$である場合、ほぼ存在しないものとみなされることからきた言葉だ。スパーシティ^sparsityは、どれだけ多くの$0$から構成されているかの度合いを指す。

スパース行列

大部分の成分が$0$である行列をスパース行列という。

$S$-スパース ¹

$\mathbf{v} \in \mathbb{R}^{d}$が多くても、$S \ll d$個の$0$でない成分がある場合、$\mathbf{x}$は**$S$-スパース**であると言われる。ここで、整数$S \in \mathbb{Z}$はベクトル$\mathbf{v}$のサポート$\operatorname{supp} \mathbf{v} = \left\{ k : \mathbf{v}_{k} \ne 0 \right\}$に対して次の不等式を満たす。 $$ \operatorname{card} \left( \operatorname{supp} \mathbf{v} \right) \le S $$ ここで、$\operatorname{card}$はカーディナリティを意味する。

説明

語彙的には希薄行列や疎行列があるが、通常、どちらも使わず、英語の発音そのままに[スパース・マトリックス]と読むことが多い。スパース行列は、その名の通り、行列に「意味ある」情報がスパース（希薄）である行列として定義されるが、「大部分が」という言葉から推測できるように、数学的に厳密な定義ではない。具体的な$S$が与えられ、それが「十分にスパース」であると表現されると、その定義ははっきりする。

最適化理論

最適化理論では、スパース回帰は回帰問題において解のスパーシティを最大化すること、つまり$S$を最小限にする最適化問題を指す。

グラフ理論

グラフ理論では通常、データとして与えられるランダムネットワークの隣接行列はスパース行列とみなされる。

データ構造

実用的な計算の領域では、スパース行列はデータ構造に近い。例えば、最後の成分だけが$\sqrt{2}$で、他はすべて$0$の$X,Y \in \mathbb{R}^{10^{6} \times 10^{6}}$を考えてみる。この行列を保存するためには、浮動小数点で埋められた$2 \cdot 10^{12}$スロットの配列が必要だが、その情報がスパース行列であることが確実であれば、使われない$0$をすべて保存する必要はなく、最後のスロットだけがあれば十分である。これは、単に保存が便利なだけでなく、演算でも効率良く行える。これら2つの行列は非常に大きいが、その積は簡単に $$ X Y = \begin{bmatrix} 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 2 \end{bmatrix} $$ のように計算できる。この乗算をシュトラッセンのアルゴリズムで計算したとしても、それが賢明とは言えないだろう。「コンピュータでスパース行列を計算する」とは、これらの行列を少ない容量で読み書きでき、$0$がある部分を省略して非常に速く計算できることを意味する²。