A Caltech Library Service

Scanning and Sequential Decision Making for Multidimensional Data -- Part II: The Noisy Case

Cohen, Asaf and Weissman, Tsachy and Merhav, Neri (2008) Scanning and Sequential Decision Making for Multidimensional Data -- Part II: The Noisy Case. IEEE Transactions on Information Theory, 54 (12). pp. 5609-5631. ISSN 0018-9448.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of sequential decision making for random fields corrupted by noise. In this scenario, the decision maker observes a noisy version of the data, yet judged with respect to the clean data. In particular, we first consider the problem of scanning and sequentially filtering noisy random fields. In this case, the sequential filter is given the freedom to choose the path over which it traverses the random field (e.g., noisy image or video sequence), thus it is natural to ask what is the best achievable performance and how sensitive this performance is to the choice of the scan. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance, and quantify the excess loss occurring when nonoptimal scanners are used, compared to optimal scanning and filtering. We then discuss the problem of scanning and prediction for noisy random fields. This setting is a natural model for applications such as restoration and coding of noisy images. We formally define the problem of scanning and prediction of a noisy multidimensional array and relate the optimal performance to the clean scandictability defined by Merhav and Weissman. Moreover, bounds on the excess loss due to suboptimal scans are derived, and a universal prediction algorithm is suggested. This paper is the second part of a two-part paper. The first paper dealt with scanning and sequential decision making on noiseless data arrays.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2008 IEEE. Reprinted with permission. Manuscript received May 20, 2007; revised July 17, 2008. Current version published November 21, 2008. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Seattle, WA, July 2006, and the IEEE International Symposium on Information Theory, Nice, France, June 2007. Communicated by W. Szpankowski, Associate Editor for Source Coding. The authors would like to thank the anonymous referee and the Associate Editor for Source Coding, Prof. Wojciech Szpankowski, for their valuable and constructive comments, which improved the presentation. Color versions Figures 1–4 and 6 in this paper are available online at
Subject Keywords:Filtering; hidden Markov model; multidimensional data; prediction; random field; scandiction; scanning; sequential decision making
Issue or Number:12
Record Number:CaltechAUTHORS:COHieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12928
Deposited By: Archive Administrator
Deposited On:09 Jan 2009 22:53
Last Modified:03 Oct 2019 00:33

Repository Staff Only: item control page