Question

稀疏矩阵及其压缩格式

Answer 1

一般情况下，稀疏矩阵指的是元素大部分是0的矩阵(有些资料定义非零元素不超过5%的矩阵，为稀疏矩阵), 矩阵的稀疏性可以用一个分数来量化，即矩阵中零元素的个数除以矩阵中元素的总数。存储稀疏矩阵时只描述其非零元素的值及所在位置, tensorflow的sparse_tensor类型还会存储稀疏矩阵的形状.

存储稀疏矩阵时常用的有如下三种压缩格式:

这种存储格式比较简单易懂，每一个元素需要用一个三元组来表示，分别是（行号，列号，数值），对应上图右边的一列。这种方式简单，但是记录单信息多（行列），每个三元组自己可以定位，因此空间不是最优。

这是经常用的一种，我们会经常在一些标准的线性代数库或者数值运算库中看到此方式存储；CSR是比较标准的一种，也需要三类数据来表达：数值，列号，以及行偏移。CSR不是三元组，而是整体的编码方式。数值和列号与COO一致，表示一个元素以及其列号，行偏移表示某一行的第一个元素在values里面的起始偏移位置。如上图中，第一行的第一个元素1在values中是第0个, 所以是0偏移，第二行元素第一个元素2是2偏移，第三行第一个元素5是4偏移，第4行第一个元素6是7偏移。在行偏移的最后补上矩阵总的元素个数，本例中一共是9个非零元素。

CSC是和CSR相对应的一种方式，即按列压缩的意思。

以上图中矩阵为例：
Column Offsets：[0 2 5 7 9]
Row Indices：[0 2 0 1 3 1 2 2 3]
Values： [1 5 7 2 6 8 3 9 4]
Values中的元素要按列写, 跟COO和CSR不同, 指定了Values的元素顺序之后就可以写Row Indices了, 然后根据每一列第一个元素在Values中的位置确定偏移量Column Offsets. 如第一列第一个元素1是0偏移, 第二列第一个元素7是2偏移, 第三列第一个元素8是5偏移, 第四列第一个元素9是7偏移, 共9个元素.