On the Optimality of Symbol by Symbol Filtering and Denoising

Ordentlich, Erik ; Weissman, Tsachy

HP Development Company

关键词: filtering;    denoising;    smoothing;    state estimation;    hidden Markov models;    entropy rate;    large deviations;   

RP-ID  :  HPL-2003-254

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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 onand 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