Optimal nonlinear filtering under the mean absolute error criterion

A class of sliding window operators called generalized stack filters is developed. This class of filters, which includes all rank order filters, stack filters and digital morphological filters, is the set of all filters possessing the threshold decomposition architecture and a consistency property called the stacking property. Conditions under which these filters possess the weak superposition property known as the threshold decomposition are determined. An algorithm is provided which determines a generalized stack filter which minimizes the Mean Absolute Error (MAE) between the output of the filter and a desired input signal, given noisy observations of that signal. The algorithm is a linear program whose complexity depends upon the window width of the filter and the number of threshold levels observed by each of the filters in the superposition architecture. The results show that choosing the generalized stack filter which minimizes the MAE is equivalent to massively parallel threshold-crossing decision making when these decisions are consistent with each other. An adaptive filtering algorithm is developed for the class of generalized stack filters. The adaptation algorithm can be interpreted as a learning algorithm for a group of decision-making units, the decisions of which are subject to a set of constraints called the stacking constraints. Under a rather weak statistical assumption on the training inputs, the decision strategy adopted by the group, which evolves according to the proposed learning algorithm, can be shown to converge asymptotically to an optimal strategy in the sense that it corresponds to an optimal generalized stack filter under the mean absolute error criterion. This adaptive algorithm requires only increment, decrement and comparison operations and only local interconnections between the learning units. Implementation of the algorithm in hardware is therefore very feasible