
Click here for full text:
On the Optimality of Symbol by Symbol Filtering and Denoising
Ordentlich, Erik; Weissman, Tsachy
HPL2003254
Keyword(s): filtering; denoising; smoothing; state estimation; hidden Markov models; entropy rate; large deviations
Abstract: Please Note. This abstract contains mathematical formulae
which cannot be represented here. We consider the problem of optimally
recovering a finitealphabet discretetime stochastic process {X_{1}}
from its noisecorrupted observation process {Z_{t}}. In general,
the optimal estimate of X_{t} will depend on all the components
of {Z_{t}} on which it can be based. We characterize nontrivial
situations (i.e., beyond the case where (X_{t}, Z_{t})
are independent) for which optimum performance is attained using "symbol
by symbol'' operations (a.k.a. "singlet decoding''), meaning that the
optimum estimate of X_{t} depends solely on Z_{t}. For
the case where {X_{t}} is a stationary binary Markov process corrupted
by a memoryless channel, we characterize the necessary and sufficient
condition for optimality of symbol by symbol operations, both for the
filtering problem (where the estimate of X_{t} is allowed to depend
only on and
the denoising problem (where the estimate of X_{t} is allowed
dependence on the entire noisy process). It is then illustrated how our
approach, which consists of characterizing the support of the conditional
distribution of the noise free symbol given the observations, can be
used for characterizing the entropy rate of the binary Markov process
corrupted by the BSC in various asymptotic regimes. For general noisefree
processes (not necessarily Markov), general noise processes (not necessarily
memoryless) and general index sets (random fields) we obtain an easily
verifiable sufficient condition for the optimality of symbol by symbol
operations and illustrate its use in a few special cases. For example,
for binary processes corrupted by a BSC, we establish, under mild conditions,
the existence of a d > 0 such that the "saywhat yousee'' scheme
is optimal provided the channel crossover probability is less than d.
Finally, we show how for the case of a memoryless channel the large deviations
(LD) performance of a symbol by symbol filter is easy to obtain, thus
characterizing the LD behavior of the optimal schemes when these are singlet
decoders (and constituting the only known cases where such explicit characterization
is available). Notes:
36 Pages
Back to Index
