WEJC.COM

Exponentially Weighted Polynomial Least Squares (EWPLS) Smoother/Predictor/Tracking Algorithm

The EWPLS algorithm is effectively described by its name:  Exponentially Weighted Polynomial Least Squares.  It is a multidimensional polynomial least-squares estimator.  Exponential weighting is applied on the time axis so that older observations are weighted less strongly than newer ones.  Using exponential weighting allows the algorithm to be implemented as a sequential algorithm so that older samples needn't be stored.  These observations are approximated by a polynomial of a user-specified order.  Additionally the dimension of the observation space can be specified by the user though 3 dimensions makes sense in this context.  This algorithm is computationally efficient and its memory footprint is small. 

This software is written in the C++ language though can be used in C-Language software when compiled in C++ mode which tends to be standard practice anyway.

Projectile tracking is a common use for this algorithm.  For this case a 3-dimensional estimator with, say, a 4th order polynomial model, is employed for tracking and ballistic or drag coefficient estimation.  At any point the 3-dimensional position, velocity, acceleration, etc. vectors are available with little computational load.  The ballistic or drag coefficient can be calculated from the estimated acceleration and velocity vectors.  A special member function, GetDragDeceleration, has been added to simplify simple drag and ballistic coefficient estimation for real-time calculation.  The Drag Deceleration is an antecedent to both the Drag and Ballistic coefficients.

I cannot claim originality for this algorithm as it's a fairly simple and obvious approach.  However there are modifications employed that increase computational speed, decrease size, and increase flexibility of use.  This algorithm is an effective smoother, estimator, and predictor for real-world applications.  This algorithm was originally designed for use with stochastic market tracking algorithms.

There is currently one downside to the EWPLS algorithm for radar/sonar tracking problems.  The Doppler range-rate measurements are not employed directly in the observations.  I'm currently working on this though the math gets a bit messy and I've yet to get a tractable solution.  A Kalman Filter can incorporate these range-rate measurements directly if so implemented.  Doppler-derived range techniques can be employed to the raw data to refine the position observation before adding the observation to the EWPLS algorithm in the interim however.

This software is released under a BSD 3-clause license which is fairly lenient as to OEM use.  Please read the license statement at the top each module for the appropriate legal jargon.

The timing for a 3-dimensional, 4th order, EWPLS tracker/smoother/predictor appears in the tables below.  These timing runs were made on a mid-range HP laptop as specified below.  There are two basic operations here.  The first action is adding a new observation which takes about 1.33 μs.  The second operation is only necessary when the estimated polynomial coefficient set is needed.  In this case an additional delay of 0.31 μs is needed for the linear system solution.  So, to add a new observation and update the estimated polynomial coefficients at each step will take about 1.64 μs per observation when Time Shifting Mode is employed.  Without Time Shifting Mode the total time is about 1.49 μs.

The static memory footprint for a 64-bit EWPLS build is 432 bytes.  Additional memory is allocated for the working arrays though this should come in under 1 Kbyte.

*********************************************************************************************************************************************************************************
* EWPLS_Timing_NO --- Timing run WITHOUT Time Shifting Enabled
* For a 4th order polynomial in 3 dimensions
* Single-Thread on an i7-2630QM CPU @ 2 to 2.9 GHz [64-bit compilation]
* GNU C++ compiler in C++11 mode with -O3 optimizations
*****************************************************************************

- EWPLS static memory footprint [64-bit compilation]: 432 bytes

- Adding an observation           = 1.18 us [ 848351 per second]
- Solving for coefficients           = 0.31 us [ 3205118 per second]
- Both Adding and Solving        = 1.49 us [ 670800 per second]

*****************************************************************************
* EWPLS_Timing_TS --- Timing run WITH Time Shifting Enabled
* For a 4th order polynomial in 3 dimensions
* Single-Thread on an i7-2630QM CPU @ 2 to 2.9 GHz [64-bit compilation]
* GNU C++ compiler in C++11 mode with -O3 optimizations
*****************************************************************************

- EWPLS static memory footprint [64-bit compilation]: 432 bytes

- Adding an observation         = 1.33 us [ 751440 per second]
- Solving for coefficients         = 0.31 us [ 3205128 per second]
- Both Adding and Solving      = 1.64 us [ 608725 per second]