# Non-Autoregressive Sparse Transformer Networks for Pedestrian Trajectory Prediction
## 3 Methods
### Sparse Temporal Transformer  
Similar to sparse spatial attention, we can also obtain sparse temporal attention. Similarly, the \(n-\)th pedestrian across \(T_{obs}\) time steps can be formulated as a direct temporal graph \(G_{tp}=(V^{n},E^{n}),\,\,n=1,\ldots,N\), each node \(v_{t}^{n}\in V^{n},\,\,\,t=1,\ldots,T_{obs}\) corresponding the \(n-\)th pedestrian at time \(t\). The weighted edges \((v_{t}^{n},v_{t-\tau}^{n})\in E^{n},\,\,\,\tau=0,\ldots,(t-1)\) represent the influence from time \(t-\tau\) to \(t\) for pedestrian \(n\). We represent the temporal relation of nodes as a lower triangular matrix since the current location of the agent is often related to the past. The edge feature of for pedestrian \(n\) is initialized as Equation (8). The superscript n is omitted for simplification. \[e_{ij}^{\prime}= \begin{cases}\varphi((\,x_{i}-x_{j}),(y_{i}-y_{j}))&i>j\\ 1&i=j\quad i,j=1,\ldots,T_{obs}\\ 0&i<j\end{cases}  \tag{8}\]  
where \(e_{ij}^{\prime}\) represents the temporal influence from time \(j\) to \(i\). \(\varphi(\cdot)\) is a linear embedding function. The process of message passing is illustrated in Figure 3, where \(h_{t}\) is the feature of node \(v_{t}^{n}\) for pedestrian \(n\) at time \(t\), the superscript n is omitted for simplification. The temporal interaction between time \(i\) and \(j\) is learned from their embedding features and the edge feature \(e_{ij}^{\prime}\). Given the node feature \(h_{t}(t=1,\ldots,T_{obs})\) for pedestrian \(n\), we can represent the corresponding query vector as \(Q_{t}=f_{Q}(h_{t})\), the key vector as \(K_{t}=f_{K}(h_{t})\), and the value vector as \(V_{t}=f_{V}(h_{t})\). We define the message from time node \(v_{j}^{n}\) to \(v_{t}^{n}\)\((t,j=0,\ldots,T_{obs})\) in the directed temporal graph as  
\[\hat{\beta}_{tj}=\frac{Q_{t}K_{j}^{T}}{\sqrt{d_{k}}}+e_{tj} \tag{9}\]  
where \(d_{k}\) is the dimension of the query vector \(Q_{i}\) and the key vector \(K_{i}\). Then, we obtain the attention \(\beta_{tj}\) by the Softmax function by the temporal transformer shown in Equation (3). Thus, we can obtain the temporal interaction matrix \(A_{TI}^{n}\) for pedestrian n, where its \((t,j)-\)th element \(\beta_{tj}\) represents the influence at time \(j\) to \(t\). The \(t-th\) column in \(A_{TI}^{n}\) represents the initiative relation from the current time to other time steps. While the \(t-th\) row in \(A_{TI}^{n}\) represents the passive relations from the other time steps to the current time. \(A_{TI}^{n}\) is computed by the location of pedestrian n at each time step, and then we stack all the temporal interaction matrices of N pedestrians and, finally, obtain the dense temporal interaction matrix \(A_{TI}\in R^{N\times T_{obs}\times T_{obs}}\). Similarly, we generate a sparse temporal interaction mask \(M_{TP}\) to filter the irrelevant time steps. \[m_{ij}^{\prime}=\left\{ \begin{array}{ll}1&\beta_{ij}\geq\delta\text{ and }i\geq j\\ 0&\beta_{ij}<\delta\text{ or }i<j\end{array} \right. \tag{10}\]  
where \(m_{ij}^{\prime}\) and \(\beta_{ij}\) are the \((i,\,j)-th\) element in \(M_{TP}\) and \(A_{TI}^{n}\), respectively. \(\delta\in[0,1]\) is the element-wise threshold. After the sparse temporal mask \(M_{TP}\) is obtained, the sparse temporal interaction \(A_{TI}^{sparse}\) of all the pedestrians can be computed as  
\[A_{TI}^{sparse}=M_{TP}\odot A_{TI} \tag{11}\]  
Thus, a sparse temporal attention matrix representing the sparse temporal directed interactions is eventually obtained. We also adopt the multi-head attention mechanism to calculate the temporal feature at \(t\) time step for pedestrian \(n\):  
\[h_{t}^{\prime}=f\Big{(}h_{t}+\sum_{j=1}^{t}\beta_{tj}^{\prime}V_{j}\Big{)}+ \Big{(}h_{t}+\sum_{j=1}^{t}\beta_{tj}^{\prime}V_{j}\Big{)}\;\;t=1,\ldots,T_{ obs} \tag{12}\]  
where \(\beta_{tj}^{\prime}\) is the element in \(A_{TI}^{sparse}\). The sparse temporal transformer outputs the updated feature at each time step for pedestrian n, and the computation could be paralleled for all pedestrians. It captures the temporal dependencies for trajectory prediction.