## 2 Sequential Importance Resampling  
In this section, we briefly describe Sequential Importance Resampling (SIR), one of the most common variants of PFs [1]. PFs employ the Importance Sampling (IS) principle to estimate the true state \(\mathbf{X}_{t}\in\mathbb{R}^{M}\) of a system. IS uses an arbitrary proposal distribution \(q(\mathbf{X}_{t}|\mathbf{X}_{t-1})\) to randomly generate \(\mathbf{x}_{t}\in\mathbb{R}^{N\times M}\), a population of \(N\) statistically independent hypotheses for the state, called particles. Each particle \(\mathbf{x}_{t}^{i}\) is then weighted by an unnormalized importance weight \(\mathbf{w}_{t}^{i}\in\mathbb{R}\)\(\forall i=0,1,...,N-1\), which is computed based on the resemblance between \(\mathbf{x}_{t}^{i}\) and \(\mathbf{X}_{t}\). In this way, \(\mathbf{x}_{t}\) approximates the posterior of the true state. To weight each particle correctly, at every time step \(t\), we collect \(\mathbf{Y}_{t}\in\mathbb{R}^{M_{y}}\), a set of measurable quantities that are related to \(\mathbf{X}_{t}\) by some pdf. At the initial time \(t=0\), no measurement has been collected, so the particles are initially drawn from the initial distribution \(q_{0}(\mathbf{X}_{0})=p_{0}(\mathbf{X}_{0})\) and weighted equally as \(1/N\). Then, for any time step \(t=1,2,...,T_{PF}\), measurements are collected, and each particle is drawn from the proposal distribution as follows:  
\[\mathbf{x}_{t}^{i}\sim q(\mathbf{x}_{t}^{i}|\mathbf{x}_{t-1}^{i},\mathbf{Y}_{ t}) \tag{1}\]  
and weighted by  
\[\mathbf{w}_{t}^{i}=\mathbf{w}_{t-1}^{i}\frac{p(\mathbf{x}_{t}^{i}|\mathbf{x}_ {t-1}^{i})p(\mathbf{Y}_{t}|\mathbf{x}_{t}^{i})}{q(\mathbf{x}_{t}^{i}|\mathbf{ x}_{t-1}^{i},\mathbf{Y}_{t})} \tag{2}\]  
where \(p(\mathbf{x}_{t}^{i}|\mathbf{x}_{t-1}^{i})\) and \(p(\mathbf{Y}_{t}|\mathbf{x}_{t}^{i})\) are known from the model. The IS step performs (1) and (2) in sequence. Then, to effectively represent the pdf of the state, the weights are normalized as follows:  
\[\mathbf{\tilde{w}}_{t}^{i}=\mathbf{w}_{t}^{i}/\sum_{z=0}^{N-1} \mathbf{w}_{t}^{z} \tag{3}\]  
However, the side effect of using IS is degeneracy, a phenomenon that (within a few iterations) makes all weights but one decrease towards 0. The variance of the weights is indeed proven to increase at every \(t\)[1]. The most popular strategy for tackling degeneracy is to perform resampling, a task that regenerates the particle population by deleting the particles with low weights and duplicating those with high weights. In SIR, resampling is performed if the Effective Sample Size (ESS)  
\[N_{eff}=1/\sum_{i=0}^{N-1}(\mathbf{\tilde{w}}_{t}^{i})^{2} \tag{4}\]  
decreases below an arbitrary threshold, which is commonly set to Several resampling schemes exist [31] and can be described as comprising three steps. The first step is to process the normalized weights \(\tilde{\mathbf{w}}\) to generate \(\mathbf{ncopies}\in\mathbb{Z}^{N}\) whose \(i\)-th element, \(\mathbf{ncopies}^{i}\), defines how many times the \(i\)-th particle must be copied, such that  
\[\sum_{i=0}^{N-1}\mathbf{ncopies}^{i}=N \tag{5}\]  
The second step is redistribution, which involves duplicating each particle \(\mathbf{x}^{i}\) as many times as \(\mathbf{ncopies}^{i}\). A textbook redistribution is described by Algorithm 1, which we refer to as Sequential Redistribution (S-R). This algorithm achieves an \(O(N)\) time complexity on a single core as (5) holds. A practical example for \(N=8\) particles is shown in Figure 1. In the final step of resampling, all weights are reset to \(\frac{1}{N}\). ```
0:\(\mathbf{x}\), \(\mathbf{ncopies}\), \(N\)
0:\(\mathbf{x}_{\texttt{HEUP}}\)
1:\(z\gets 0\)
2:for\(j\gets 0\); \(j<N\); \(j\gets j+1\)do
3:for\(k\gets 0\); \(k<\mathbf{ncopies}^{j}\); \(k\gets k+1\)do
4:\(\mathbf{x}_{new}^{i}\leftarrow\mathbf{x}^{j}\),\(z\gets z+1\)
5:endfor
6:endfor
```  
**Algorithm 1** Sequential Redistribution (S-R)  
We note that all resampling schemes require redistribution, independently of the chosen strategy to perform the first step.