RoPE 小迷思
题意
RoPE 的核心思想在于：存在一族线性映射 $M_i:\mathbb R^d\to\mathbb R^d (i\in\mathbb Z)$，使得对于任意的 $\mathbf q,\mathbf k\in\mathbb R^d$，
只与 $t-s$ 有关，于是可以在 Transformer 中用它记录相对位置信息。标准的 RoPE 中，上述线性映射由 $d/2$ 个旋转矩阵 $\begin{bmatrix}\cos(\theta) & -\sin(\theta)\ \sin(\theta) & \cos(\theta)\end{bmatrix}$ 组成。
现在我们稍微放宽条件，不再要求 $\mathbf q,\mathbf k$ 的任意性。
- 给定整数 $d\ge 2$。求所有函数 $f:\mathbb Z\to\mathbb R$，使得存在 $\mathbf q,\mathbf k\in\mathbb R^d$，以及一族线性映射 $M_i:\mathbb R^d\to\mathbb R^d (i\in\mathbb Z)$，满足
题解
$f$ 符合要求当且仅当：$f$ 是一个 $d$ 阶线性递推序列，即存在 $a_1,\ldots,a_d\in\mathbb R$ 使得 $f(t)=\sum_{i=1}^d a_if(t-i) (\forall t\in\mathbb Z)$。
（简要）证明
必要性
若 $f$ 符合要求，令 $\mathbf v_s=M_s\mathbf q, \mathbf w_t=M_t\mathbf k$，则 $f(t-s)=\langle\mathbf v_s,\mathbf w_t\rangle$。
令 $d’$ 是最小的自然数使得 $\{\mathbf v_0,\ldots,\mathbf v_{d’}\}$ 线性相关。则 $d’\leq d$。设
则对于任意 $t\in\mathbb Z$，由于内积关于 $\mathbf v$ 的线性性，有 $f(t-d’)=\sum_{i=0}^{d’-1}b_if(t-i)$，即 $f$ 是 $d’$ 阶线性递推，从而 $f$ 是 $d$ 阶线性递推。
充分性
若 $f(t)=\sum_{i=1}^d a_if(t-i) (\forall t\in\mathbb Z)$。令 $\mathbf q=\begin{bmatrix}1 & 0 & 0 & \cdots & 0\end{bmatrix}^{\mathrm T}$，$\mathbf k=\begin{bmatrix}0 & 1 & 0 & \cdots & 0\end{bmatrix}^{\mathrm T}$，则 $\mathbf v_s$ 和 $\mathbf w_t$ 分别是 $M_s,M_t$ 对应矩阵的第一列和第二列，我们可以独立地指定它们。具体构造如下：
对于 $1\leq i\leq d$，令 $\mathbf v_i=e_i$，即只有第 $i$ 位为 $1$ 的 One-Hot 向量；
令所有 $\mathbf v_i (i\in\mathbb Z)$ 满足 $\mathbf v_i=\sum_{j=1}^da_j\mathbf v_{i+j}$，这可以唯一确定所有 $\mathbf v_i$（除非 $a_j$ 全为 $0$，这是平凡情况）；
对于任意 $i\in\mathbb Z$，令 $\mathbf w_i=\sum_{j=1}^df(i-j)e_j$。
容易验证，当 $1\leq s\leq d$ 时 $\langle\mathbf v_s,\mathbf w_t\rangle=f(t-s)$。对 $s$ 向数轴两端用数学归纳法（结合内积关于 $\mathbf v$ 的线性性）即可证明该等式对于任意 $s\in\mathbb Z$ 成立。