ON THE LP WHICH FINDS A MMAE STACK FILTER

Two methods are proposed to modify the linear program (LP) developed in [1] to find a stack filter which minimizes the mean absolute error (MAE). In the first approach, the number of constraints is substantially reduced at the expense of requiring a zero-one LP to solve for an optimal filter. This scheme reduces the number of constraints from O(n2n) to O(2n), which is exactly the cardinality of the set of possible binary vectors which can appear in the window of the filter. In the second approach, the LP is transformed into a maxflow problem. This guarantees that the problem can be solved in time which is a polynomial function of the number of variables in the LP, as opposed to the worst case exponential time that may occur with the simplex method. It also allows the many fast algorithms for the max-flow problem to be used to find an optimal stack filter. Recursive algorithms for the construction of the window width n constraint matrix for both the original LP and the max-flow modification are also provided.