Non-linear filter
Encyclopedia
A nonlinear filter is a signal-processing device whose output is not a linear function
of its input. Terminology concerning the filtering problem may refer to the time domain (state space
) showing of the signal or to the frequency domain
representation of the signal. When referring to filters with adjectives such as "bandpass, highpass, and lowpass" one has in mind the frequency domain. When resorting to terms like "additive noise", one has in mind the time domain, since the noise that is to be added to the signal is added in the state space
representation of the signal. The state space representation is more general and is used for the advanced formulation of the filtering problem as a mathematical problem in probability and statistics of stochastic processes.
When the noise is additive, i.e. it is added to the signal (rather than multiplied for example) and the statistics of the noise process are known to follow the gaussian statistical law, then a linear filter is known to be optimal under a number of possible criteria (for example the mean square error criterion, aiming at minimizing the variance of the error). This optimality is one of the main reasons why linear filters are so important in the history of signal processing.
However, in several cases one cannot find an acceptable linear filter, either because the noise is non-additive or non-gaussian. For example, linear filters can remove additive high frequency noise if the signal and the noise do not overlap in the frequency domain
. Still, in two-dimensional signal processing the signal may have important and structured high frequency components, like edges and small details in image processing. In this case a linear lowpass filter would blur sharp edges and yield bad results. Nonlinear filters should be used instead.
Nonlinear filters locate and remove data that is recognised as noise. The algorithm is 'nonlinear' because it looks at each data point and decides if that data is noise or valid signal. If the point is noise, it is simply removed and replaced by an estimate based on surrounding data points, and parts of the data that are not considered noise are not modified at all. Linear filters, such as those used in bandpass, highpass, and lowpass, lack such a decision capability and therefore modify all data.
Nonlinear filters are sometimes used also for removing very short wavelength, but high amplitude features from data. Such a filter can be thought of as a noise spike-rejection filter, but it can also be effective for removing short wavelength geological features, such as signals from surficial features.
Examples of nonlinear filters include:
When moving to the time domain description of a system, in state space
form, there is the possibility of describing more effectively the dynamics of a system, considering also the case where the time-evolution of the system is described by non-linear differential (or difference in discrete time) equations, or the case where the observations are a known nonlinear function of the signal then perturbed by additive noise. These are possible further sources of non-linearity, besides non-additive or non-gaussian noise, for which in most cases we have to move into the state space
description of a system and abandon the frequency domain
formulation.
representation of a system, one can have the most general formulation of the nonlinear filtering problem, see also "filtering problem (stochastic processes)
". In this context, and more generally in estimation theory
, control theory
, and engineering, a nonlinear filter is an algorithm that estimates the state
of a (stochastic) dynamical system
from noisy measurements, where either the system dynamics model or measurement model is a nonlinear function of the state. When the system is linear the optimal solution is the Kalman filter
. The problem of optimal nonlinear filtering was solved by Ruslan L. Stratonovich
(1959, 1960), see also Harold J. Kushner
's work and Moshe Zakai
's, who introduced a simplified dynamics for the unnormalized conditional law of the filter known as Zakai equation
. Its linear case is known as the Kalman filter
(or Kalman-Bucy filter). The Kushner-Stratonovich solution to the nonlinear filtering problem in continuous time takes the form of a mathematical object called Stochastic Partial Differential Equation. It has been proved by Mireille Chaleyat-Maurel and Dominique Michel that the solution is infinite dimensional in general, and as such requires finite dimensional approximations. These may be heuristics-based such as the Extended Kalman Filter
or the Assumed Density Filters described in Peter S. Maybeck's book or more methodologically driven such as the projection filters introduced by Damiano Brigo
, Bernard Hanzon
and François Le Gland, some sub-families of which are shown to coincide with the Assumed Density Filters.
Linear function
In mathematics, the term linear function can refer to either of two different but related concepts:* a first-degree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....
of its input. Terminology concerning the filtering problem may refer to the time domain (state space
State space (controls)
In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...
) showing of the signal or to the frequency domain
Frequency domain
In electronics, control systems engineering, and statistics, frequency domain is a term used to describe the domain for analysis of mathematical functions or signals with respect to frequency, rather than time....
representation of the signal. When referring to filters with adjectives such as "bandpass, highpass, and lowpass" one has in mind the frequency domain. When resorting to terms like "additive noise", one has in mind the time domain, since the noise that is to be added to the signal is added in the state space
State space (controls)
In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...
representation of the signal. The state space representation is more general and is used for the advanced formulation of the filtering problem as a mathematical problem in probability and statistics of stochastic processes.
Frequency domain
In signal processing one often deals with obtaining an input signal and processing it into an output signal. At times the signal may be transmitted through a channel which corrupts it, resulting in a noisy output. As a consequence, the user at the output end has to attempt to reconstruct the original signal given the noisy one.When the noise is additive, i.e. it is added to the signal (rather than multiplied for example) and the statistics of the noise process are known to follow the gaussian statistical law, then a linear filter is known to be optimal under a number of possible criteria (for example the mean square error criterion, aiming at minimizing the variance of the error). This optimality is one of the main reasons why linear filters are so important in the history of signal processing.
However, in several cases one cannot find an acceptable linear filter, either because the noise is non-additive or non-gaussian. For example, linear filters can remove additive high frequency noise if the signal and the noise do not overlap in the frequency domain
Frequency domain
In electronics, control systems engineering, and statistics, frequency domain is a term used to describe the domain for analysis of mathematical functions or signals with respect to frequency, rather than time....
. Still, in two-dimensional signal processing the signal may have important and structured high frequency components, like edges and small details in image processing. In this case a linear lowpass filter would blur sharp edges and yield bad results. Nonlinear filters should be used instead.
Nonlinear filters locate and remove data that is recognised as noise. The algorithm is 'nonlinear' because it looks at each data point and decides if that data is noise or valid signal. If the point is noise, it is simply removed and replaced by an estimate based on surrounding data points, and parts of the data that are not considered noise are not modified at all. Linear filters, such as those used in bandpass, highpass, and lowpass, lack such a decision capability and therefore modify all data.
Nonlinear filters are sometimes used also for removing very short wavelength, but high amplitude features from data. Such a filter can be thought of as a noise spike-rejection filter, but it can also be effective for removing short wavelength geological features, such as signals from surficial features.
Examples of nonlinear filters include:
- phase-locked loopPhase-locked loopA phase-locked loop or phase lock loop is a control system that generates an output signal whose phase is related to the phase of an input "reference" signal. It is an electronic circuit consisting of a variable frequency oscillator and a phase detector...
s - detectorDetector (radio)A detector is a device that recovers information of interest contained in a modulated wave. The term dates from the early days of radio when all transmissions were in Morse code, and it was only necessary to detect the presence of a radio wave using a device such as a coherer without necessarily...
s - mixerFrequency mixerIn electronics a mixer or frequency mixer is a nonlinear electrical circuit that creates new frequencies from two signals applied to it. In its most common application, two signals at frequencies f1 and f2 are applied to a mixer, and it produces new signals at the sum f1 + f2 and difference f1 -...
s - median filterMedian filterIn signal processing, it is often desirable to be able to perform some kind of noise reduction on an image or signal. The median filter is a nonlinear digital filtering technique, often used to remove noise. Such noise reduction is a typical pre-processing step to improve the results of later...
s - rankletRankletIn statistics, a ranklet is an orientation-selective non-parametric feature which is based on the computation of Mann–Whitney–Wilcoxon rank-sum test statistics...
s
When moving to the time domain description of a system, in state space
State space (controls)
In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...
form, there is the possibility of describing more effectively the dynamics of a system, considering also the case where the time-evolution of the system is described by non-linear differential (or difference in discrete time) equations, or the case where the observations are a known nonlinear function of the signal then perturbed by additive noise. These are possible further sources of non-linearity, besides non-additive or non-gaussian noise, for which in most cases we have to move into the state space
State space (controls)
In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...
description of a system and abandon the frequency domain
Frequency domain
In electronics, control systems engineering, and statistics, frequency domain is a term used to describe the domain for analysis of mathematical functions or signals with respect to frequency, rather than time....
formulation.
Time domain: nonlinear filter (estimation theory)
When moving in the time domain and mostly under the state spaceState space (controls)
In control engineering, a state space representation is a mathematical model of a physical system as a set of input, output and state variables related by first-order differential equations...
representation of a system, one can have the most general formulation of the nonlinear filtering problem, see also "filtering problem (stochastic processes)
Filtering problem (stochastic processes)
In the theory of stochastic processes, the filtering problem is a mathematical model for a number of filtering problems in signal processing and the like. The general idea is to form some kind of "best estimate" for the true value of some system, given only some observations of that system...
". In this context, and more generally in estimation theory
Estimation theory
Estimation theory is a branch of statistics and signal processing that deals with estimating the values of parameters based on measured/empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value affects the distribution of the...
, control theory
Control theory
Control theory is an interdisciplinary branch of engineering and mathematics that deals with the behavior of dynamical systems. The desired output of a system is called the reference...
, and engineering, a nonlinear filter is an algorithm that estimates the state
Thermodynamic state
A thermodynamic state is a set of values of properties of a thermodynamic system that must be specified to reproduce the system. The individual parameters are known as state variables, state parameters or thermodynamic variables. Once a sufficient set of thermodynamic variables have been...
of a (stochastic) dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
from noisy measurements, where either the system dynamics model or measurement model is a nonlinear function of the state. When the system is linear the optimal solution is the Kalman filter
Kalman filter
In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
. The problem of optimal nonlinear filtering was solved by Ruslan L. Stratonovich
Ruslan L. Stratonovich
Ruslan Leont'evich Stratonovich was an outstanding physicist, engineer, and probabilist. Professor Stratonovich was born on May 31, 1930 in Moscow, Russia...
(1959, 1960), see also Harold J. Kushner
Harold J. Kushner
Harold J. Kushner is an American applied mathematician and a Professor Emeritus of Applied Mathematics at Brown University. He is known for his work on the theory of stochastic stability , the theory of non-linear filtering , and for the development of numerical methods for stochastic control...
's work and Moshe Zakai
Moshe Zakai
Moshe Zakai is Distinguished Professor at the Technion, Israel in Electrical Engineering, member of the Israel Academy of Sciences and Humanities and Rothschild Prize winner.- Biography :...
's, who introduced a simplified dynamics for the unnormalized conditional law of the filter known as Zakai equation
Zakai equation
In filtering theory the Zakai equation is a linear recursive filtering equation for the un-normalized density of a hidden state. In contrast, the Kushner equation gives a non-linear recursive equation for the normalized density of the hidden state...
. Its linear case is known as the Kalman filter
Kalman filter
In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
(or Kalman-Bucy filter). The Kushner-Stratonovich solution to the nonlinear filtering problem in continuous time takes the form of a mathematical object called Stochastic Partial Differential Equation. It has been proved by Mireille Chaleyat-Maurel and Dominique Michel that the solution is infinite dimensional in general, and as such requires finite dimensional approximations. These may be heuristics-based such as the Extended Kalman Filter
Kalman filter
In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...
or the Assumed Density Filters described in Peter S. Maybeck's book or more methodologically driven such as the projection filters introduced by Damiano Brigo
Damiano Brigo
Damiano Brigo is an applied mathematician, and current Gilbart Chair of Financial Mathematics at King's College, London, known for a number of results in systems theory, probability and mathematical finance.-Main results:...
, Bernard Hanzon
Bernard Hanzon
Bernand Hanzon is an academic, mathematician, and researcher. He has worked on systems theory, probability and statistics, and mathematical finance...
and François Le Gland, some sub-families of which are shown to coincide with the Assumed Density Filters.
- Extended Kalman FilterExtended Kalman filterIn estimation theory, the extended Kalman filter is the nonlinear version of the Kalman filter which linearizes about the current mean and covariance...
and Unscented Kalman filter - Particle filterParticle filterIn statistics, particle filters, also known as Sequential Monte Carlo methods , are sophisticated model estimation techniques based on simulation...