| |
Click here for full text:
On the Optimality of Symbol by Symbol Filtering and Denoising
Ordentlich, Erik; Weissman, Tsachy
HPL-2003-254
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 finite-alphabet discrete-time stochastic process {X1}
from its noise-corrupted observation process {Zt}. In general,
the optimal estimate of Xt will depend on all the components
of {Zt} on which it can be based. We characterize non-trivial
situations (i.e., beyond the case where (Xt, Zt)
are independent) for which optimum performance is attained using "symbol
by symbol'' operations (a.k.a. "singlet decoding''), meaning that the
optimum estimate of Xt depends solely on Zt. For
the case where {Xt} 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 Xt is allowed to depend
only on  and
the denoising problem (where the estimate of Xt 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 noise-free
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 "say-what- you-see'' 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
|
printable version
