Computer Science – Information Theory
Scientific paper
2006-09-11
Computer Science
Information Theory
46 pages, 2 figures. Revised version: title changed, section 1 revised, section 3.1 added, a few minor/technical corrections m
Scientific paper
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 was 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 non-optimal 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 multi-dimensional 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.
Cohen Asaf
Merhav Neri
Weissman Tsachy
No associations
LandOfFree
Scanning and Sequential Decision Making for Multi-Dimensional Data - Part I: the Noiseless Case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Scanning and Sequential Decision Making for Multi-Dimensional Data - Part I: the Noiseless Case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scanning and Sequential Decision Making for Multi-Dimensional Data - Part I: the Noiseless Case will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-25458