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

DOI10.1109/TIT.2007.903117zbMATH Open1318.94030arXivcs/0609049OpenAlexW2950761701MaRDI QIDQ3548924FDOQ3548924

Authors: Asaf Cohen, Neri Merhav, Tsachy Weissman 

Publication date: 21 December 2008

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/cs/0609049

Recommendations

• Scanning and Sequential Decision Making for Multidimensional Data—Part II: The Noisy Case
• Scanning and prediction in multidimensional data arrays
• Universal schemes for sequential decision from individual data sequences
• Sequential decision fusion: Theory and applications.
• Multidimensional multiscale scanning in exponential families: limit theory and statistical consequences
• scientific article; zbMATH DE number 3932240
• Publication:4731996
• The statistics of optimal decision making: exploring the relationship between signal detection theory and sequential analysis
• Sequential selection procedures. A decision theoretic approach

Mathematics Subject Classification ID

Random fields; image analysis (62M40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Coding theorems (Shannon theory) (94A24) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Source coding (94A29)

Cited In (6)

• Scanning and Sequential Decision Making for Multidimensional Data—Part II: The Noisy Case
• Peano modes at theD  =  2 delocalisation transition
• Sensor networks: from dependence analysis via matroid bases to online synthesis
• Title not available (Why is that?)
• Convergence of the best linear predictor of a weakly stationary random field
• Scanning and prediction in multidimensional data arrays

This page was built for publication: Scanning and Sequential Decision Making for Multidimensional Data–Part I: The Noiseless Case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548924)