A Caltech Library Service

Scanning and Sequential Decision Making for Multidimensional Data –- Part I: The Noiseless Case

Cohen, Asaf and Merhav, Neri and Weissman, Tsachy (2007) Scanning and Sequential Decision Making for Multidimensional Data –- Part I: The Noiseless Case. IEEE Transactions on Information Theory, 53 (9). pp. 3001-3019. ISSN 0018-9448. doi:10.1109/TIT.2007.903117.

See Usage Policy.


Use this Persistent URL to link to this item:


We investigate the problem of scanning and prediction (“scandiction,” for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: First, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field’s distribution, yet asymptotically achieves the same performance as if this distribution were known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function.We then discuss the scenario where a nonoptimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multidimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2007 IEEE. Reprinted with permission. Manuscript received September 11, 2006; revised May 7, 2007. [Posted online: 2007-08-27] The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Seattle, WA, July 2006, and the Electricity 2006 convention, Eilat, Israel, November 2006. The authors would like to thank Jacob Ziv and Erez Sabbag for several interesting and fruitful discussions. The valuable comments of the anonymous referees are also gratefully acknowledged.
Subject Keywords:Individual image, multidimensional data, random field, scandiction, sequential decision making, universal scanning
Issue or Number:9
Record Number:CaltechAUTHORS:COHieeetit07
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8921
Deposited By: Archive Administrator
Deposited On:01 Oct 2007
Last Modified:08 Nov 2021 20:54

Repository Staff Only: item control page