Algorithms and Fundamental Limits for Unlabeled Detection Using Types

We deal with the classical problem of testing two simple statistical hypotheses but, as a new element, it is assumed that the data vector is observed after an unknown permutation of its entries. What is the fundamental limit for the detection performance in this case? How much information for detect...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2019-04, Vol.67 (8), p.2022-2035
Main Authors: Marano, Stefano, Willett, Peter K.
Format: Article
Language:English
Subjects:
Algorithms
assignment problem
Complexity
Detectors
error exponents
fundamental limits of hypothesis testing
Greedy algorithms
Image processing
Labeling
Permutations
Signal processing
Signal processing algorithms
Testing
Timing
types
unknown permutation
Unlabeled detection
unordered data
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We deal with the classical problem of testing two simple statistical hypotheses but, as a new element, it is assumed that the data vector is observed after an unknown permutation of its entries. What is the fundamental limit for the detection performance in this case? How much information for detection is contained in the entry values and how much in their positions? In the first part of this paper, we answer these questions. In the second part, we focus on practical algorithms. A low-complexity detector solves the detection problem without attempting to estimate the permutation. A modified version of the auction algorithm is then considered, and two greedy algorithms with affordable worst case complexity are presented. The detection operational characteristics of these detectors are investigated by computer experiments. The problem we address is referred to as unlabeled detection and is motivated by large sensor network applications, but applications are also foreseen in different fields, including image processing, social sensing, genome research, and molecular communication.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2019.2899291