Draft:Frequency offsets least mean squares

• Comment: Source #2 does not seem to explicitly discuss this algorithm, and sources #1 and #3 are by Pärlin et. al
  who presumably wrote the algorithm. Are there articles where other scholars discuss or reference the algorithm? The article is very well written! Just need to show notability. Cerebellum (talk) 12:13, 23 December 2023 (UTC)

---

Applying FO-LMS for estimating and tracking the channel, carrier frequency offset, and sampling frequency offset between a transmitter and receiver.

The frequency offsets least mean squares (FO-LMS) algorithm is an adaptive filter that allows estimating and tracking the channel between a transmitter and a receiver under carrier and sampling frequency offsets. Frequency offsets degrade the performance of classical adaptive filters, making them unsuitable in certain cases. Therefore, FO-LMS was developed to explicitly estimate the channel as well as the carrier and sampling frequency offsets. Like the classical least mean squares (LMS) adaptive filter, FO-LMS is a stochastic gradient descent method, which means that the algorithm's decisions made at each and every iteration are based on the instantaneous estimate of the actual gradient. This makes the FO-LMS a robust algorithm with low computational burder, albeit with slow convergence rate. The ability to estimate and track carrier and sampling frequency offsets in addition to the channel makes FO-LMS suitable for applications where the transmitted signal or parts of it are known but where frequency offsets are detrimental to performance, such as bistatic radars, orthogonal frequency-division multiplexing communication systems, or interference cancellation.

Algorithm description

The FO-LMS algorithm is applicable when a transmitted signal $x(t)$, which in its discrete-time baseband complex form ${\textstyle x(n)}$ is known to the receiver, is received due to the channel and frequency offsets as

$d(n)=\mathbf {h} ^{H}\mathbf {y} _{n}e^{j\sum _{i=1}^{n}{\epsilon (i)}}+v(n)$,

where ${\textstyle v(n)}$ is the measurement noise, ${\textstyle \mathbf {h} }$ denotes the finite complex-valued impulse response of the channel with length $M$, the multiplicative term ${\textstyle e^{j\sum _{i=1}^{n}{\epsilon (i)}}}$ accounts for the carrier frequency offset, and ${\textstyle \mathbf {y} _{n}}$ accounts for sampling ${\textstyle x(t)}$ with sampling frequency offset ${\textstyle \eta (n)}$ so that

$\mathbf {y} _{n}={\Bigg [}x\left(\sum _{i=1}^{n-M+1}{\left(1+\eta (i)\right)}\right),\dots ,x\left(\sum _{i=1}^{n}{\left(1+\eta (i)\right)}\right){\Bigg ]}$.

The idea behind FO-LMS is to use the gradient descent method to find a channel estimate ${\textstyle {\hat {\mathbf {h} }}}$, carrier frequency offset estimate ${\textstyle {\hat {\epsilon }}}$, and sampling frequency offset estimate ${\textstyle {\hat {\eta }}}$ that minimize the cost function ${\textstyle C(n)=E\left\{|e(n)|^{2}\right\}}$, where $E\{\cdot \}$ denotes the expected value and the estimation error at the current sample $n$ is the difference between the received signal and the estimate of the received signal

$e(n)=d(n)-{\hat {\mathbf {h} }}_{n-1}^{H}{\hat {\mathbf {y} }}_{n}e^{j\sum _{i=1}^{n}{{\hat {\epsilon }}(i-1)}}$,

where ${\hat {\mathbf {y} }}_{n}$ is the result of resampling ${\textstyle x(n)}$ with sampling frequency offset ${\textstyle {\hat {\eta }}(n)}$. In practice, use of the expected value is not feasible and the algorithm relies instead on a single realization of the estimation error as is characteristic to the stochastic gradient descent method. At each and every iteration, FO-LMS updates the parameter estimates by minimizing the error so that

${\hat {\mathbf {h} }}_{n}={\hat {\mathbf {h} }}_{n-1}+\mu _{\mathrm {h} }{\hat {\mathbf {y} }}_{n}e^{j\phi (n)}e^{*}(n)$,

${\hat {\epsilon }}(n)={\hat {\mathrm {\epsilon } }}(n-1)+\mu _{\epsilon }\Im {\left\{{\hat {\mathbf {h} }}_{n-1}^{H}{\hat {\mathbf {y} }}_{n}e^{j\phi (n)}e^{*}(n)\right\}}$,

${\hat {\eta }}(n)={\hat {\eta }}(n-1)+\mu _{\eta }\Re {\left\{{\hat {\mathbf {h} }}_{n-1}^{H}{\hat {\mathbf {y} }}'_{n}e^{j\phi (n)}e^{*}(n)\right\}}$,

where ${\hat {\mathbf {y} }}'_{n}$ is the derivative of ${\hat {\mathbf {y} }}_{n}$ and can typically be calculated using first-order divided difference, ${\textstyle \phi (n)=\sum _{i=1}^{n}{\hat {\epsilon }}(i-1)}$ is the instantaneous phase shift caused by the estimated carrier frequency offset ${\textstyle {\hat {\epsilon }}(n)}$, $\Im {\{\cdot \}}$ denotes the imaginary part of a complex number, $\Re {\{\cdot \}}$ the real part, and $\mu _{\mathrm {h} }$, $\mu _{\mathrm {\epsilon } }$, and $\mu _{\mathrm {\eta } }$ are the algorithm step sizes for controlling how rapidly the parameter estimates are advanced. Larger step sizes result in quicker convergence but also in larger excess mean squared error while in steady state.

Convergence and stability

The step sizes $\mu _{\mathrm {h} }$, $\mu _{\mathrm {\epsilon } }$, and $\mu _{\mathrm {\eta } }$ control how quickly the algorithm converges to around-optimal parameter estimates. The algorithm never converges to the optimal parameters exactly but with suitable step sizes the parameter estimates approach and change around the optimal values. This is because the algorithm relies on a single realization of the estimation error at each iteration, rather than on the expectation. As such, the step sizes also control how close to the optimal parameters the estimates will be on average once they have approached the optimal values. Larger step sizes will cause the algorithm to magnify the estimation inaccuracies that results from using a single realization of the estimation error and the parameter estimates will vary further away from the optimal values, potentially even overshooting irrevocably and causing divergence. Useful step sizes bounds to prevent divergence are

$0<\mu _{w}\leq {\frac {2-\mu _{\epsilon }|{\mathbf {y} }_{n}{\mathbf {w} }_{n-1}|^{2}-\mu _{\eta }|\mathbf {y} '_{n}\mathbf {w} _{n-1}|^{2}}{\lVert {\mathbf {y} }_{n}\rVert ^{2}}}$,

$0<\mu _{\epsilon }\leq {\frac {2-\mu _{w}\lVert {\mathbf {y} }_{n}\rVert ^{2}-\mu _{\eta }|\mathbf {y} '_{n}\mathbf {w} _{n-1}|^{2}}{|{\mathbf {y} }_{n}{\mathbf {w} }_{n-1}|^{2}}}$,

$0<\mu _{\eta }\leq {\frac {2-\mu _{w}\lVert {\mathbf {y} }_{n}\rVert ^{2}-\mu _{\epsilon }|{\mathbf {y} }_{n}{\mathbf {w} }_{n-1}|^{2}}{|\mathbf {y} '_{n}\mathbf {w} _{n-1}|^{2}}}$.

Inescapably the upper bound for any of the step sizes depends on the other two step sizes and, therefore, the step sizes need to be selected collectively.

See also

• Adaptive filter
• Least mean squares filter

External links

• An open-source implementation of the FO-LMS algorithm is available for GNU Radio in gr-adapt (main source file).

This page will be placed in the following categories if it is moved to the article namespace.

Categories:

• Digital signal processing
• Filter theory