Ref

  1. Minkowski Engine Document
  2. official code of “OpenShape: Scaling Up 3D Shape Representation Towards Open-World Understanding”

定义与专业术语 Definitions and Terminology

下面介绍Minkowski Engine中的关于稀疏卷积的定义与专业术语。（基本都是汉化搬运Ref.1，力图加上我的一点个人理解）

稀疏张量 Sparse Tensor

首先引入稀疏矩阵：是一个零元素占整个矩阵元素的绝大多数的矩阵。而稀疏张量是稀疏矩阵的维度扩展，其中非零元素用索引 Indices（记为C\mathcal{C}）和与其对应的值 Values/Features（记为F\mathcal{F}）。

Indices作为稀疏张量非零元素的位置表示，Values则是这个元素本身的值。

在实际应用中，我们用**坐标列表 COOrdinate list (COO)**的格式对稀疏张量进行存储。这种存储策略本质上是将稀疏张量中的非零元素坐标拼接（concatenate）存入一个坐标矩阵（记为C\bf C），将非零元素值存入另一个向量（记为F\bf F）。那么，一个稀疏张量T\mathscr{T}，其坐标的维度假设为D\bf D，如果每一个元素是向量，则其秩为rank=D+1\text{rank}=D+1; 如果每一个元素是标量，则其秩为rank=D\text{rank}=D

回顾一下Rank(秩): 秩是向量空间的一个子空间的维数，它可以用来衡量一组向量的线性独立性。对于矩阵来说，秩就是矩阵中线性独立行向量或列向量的最大数量。这里的“秩”实际上是指稀疏张量的阶数（order），也就是张量中每个元素的维度。

在传统的稀疏张量中，索引或坐标必须是非负整数，而在 Minkowski Engine框架中，负坐标也是有效坐标。

写成数学表示如下：

C=[x11x12⋯x1D⋮⋮⋱⋮xN1xN2⋯xND],F=[f1T⋮fNT]\mathbf{C}= \begin{bmatrix} x_1^1 & x_1^2 & \cdots & x_1^D \\ \varvdots & \varvdots & \ddots & \varvdots \\ x_N^1 & x_N^2 & \cdots & x_N^D \end{bmatrix},\mathbf{F}= \begin{bmatrix} \mathbf{f}_1^T \\ \varvdots \\ \mathbf{f}_N^T \end{bmatrix}

T[xi1,xi2,⋯ ,xiD]={fiif (xi1,xi2,⋯ ,xiD)∈C0otherwise\left.\left.\left.\mathscr{T}[x_i^1,x_i^2,\cdots,x_i^D]=\left\{ \begin{array} {ll}\mathbf{f}_i & \quad\mathrm{if~}(x_i^1,x_i^2,\cdots,x_i^D)\in\mathcal{C} \\ 0 & \quad\mathrm{otherwise} \end{array}\right.\right.\right.\right.

稀疏张量的坐标管理 Coordinate Manager

类似传统深度学习，稀疏张量也想实现卷积（带特定步长）、池化等算子，这些操作都需要寻找非零元素的临近元素，输出的结果也和输入的坐标不一样，因此需要构建一个良好的管理稀疏张量非零元素的坐标管理机制。实际应用中，坐标管理通过缓存的思想来实现（叫做Coordinates Manager）。这一个模块会缓存所有的坐标和卷积核映射，因为他们会频繁地重用。

在Minkowski Engine框架中，当使用MinkowskiEngine.SparseTensor初始化一个稀疏张量，我们就无形之中创建了一个Coordinate Manager。我们也可以选择性的规定很多个SparseTensor共享一个COO.Manager。调用MinkowskiEngine.SparseTensor.coords_man则可以访问这个COO.Manager。

非零元素的坐标键值 Coordinate Key

在一个Coordinate Manager中，所有的对象存储在一个Unordered Map。坐标键值就是缓存稀疏张量坐标的Hash Key。

如果两个稀疏张量具有相同的坐标管理器和相同的坐标键，则稀疏张量的坐标相同，并且它们共享相同的内存空间。

稀疏张量的操作映射 Kernel Map

要找出如何使用空间局部操作（如卷积或池化）将稀疏张量映射到另一个稀疏张量，其核心问题就是坐标的映射。我们需要找到输入稀疏张量中的哪个坐标映射到输出稀疏张量中的哪个坐标。Minkowski Engine将这种映射称作kernel map。

我们以一个k3的卷积为例，用一对整数列表来表示一个映射：输入映射列表II和输出映射列表OO. i∈Ii \in I表示输入稀疏张量的坐标矩阵或者特征矩阵的行索引，同样地，o∈Oo \in O表示输出稀疏张量的坐标矩阵行索引。列表里的整数排列是有序的，具体而言要求II中的第kk个元素ik∈Ii_k \in I与OO中的第kk个元素ok∈Oo_k \in O相对应。

一个k3的卷积核一共有3×3=93 \times 3 = 9个元素，所以对于一个k3核我们需要9对这样的列表。