Finding the best mismatched detector for channel coding and hypothesis testing

Emmanuel Abbe, Muriel Médard, Sean Meyn, and Lizhong Zheng

See also

Evolution of the transient phase of the stochastic Newton-Raphson method for hypothesis testing

Abstract: The mismatched-channel formulation is generalized to obtain simplified algorithms for computation of capacity bounds and improved signal constellation designs. The following issues are addressed:

For a given finite dimensional family of linear detectors, how can we compute the best in this class to maximize the reliably received rate? That is, what is the best mismatched detector in a given class?

For computation of the best detector, a new algorithm is proposed based on a stochastic approximation implementation of the Newton-Raphson method.

The geometric setting provides a unified treatment of channel coding and robust/adaptive hypothesis testing.

References

@unpublished{abbmedmeyzhe07a,
Author = {E. Abbe and M. M\'edard and S. Meyn and L. Zheng},
Note = {{Presented at the 2nd Annual Information Theory and Applications Workshop, UCSD (invited)}},
Title = {Finding the best mismatched detector for channel coding and hypothesis testing},
Year = {2007}}

@inproceedings{huaunnmeyveesur09,
Title = {Statistical {SVMs} for robust detection, supervised learning, and universal classification},
Author = {Huang, D. and Unnikrishnan, J. and Meyn, S. and Veeravalli, V. and Surana, A.},
Booktitle = {Proceedings of the {Information Theory Workshop on Networking and Information Theory}, Volos, Greece.},
Keywords = {Hypothesis testing; Information theory; Support Vector Machine},
Url = {http://itw09.org/},
Year = {2009},

Abstract = {The support vector machine (SVM) has emerged as one of the most popular
approaches to classification and supervised learning. It is a flexible
approach for solving the problems posed in these areas, but the approach is
not easily adapted to noisy data in which absolute discrimination is not
possible. We address this issue in this paper by returning to the
statistical setting. The main contribution is the introduction of a
statistical support vector machine (SSVM) that captures all of the
desirable features of the SVM, along with desirable statistical features of
the classical likelihood ratio test. In particular, we establish the
following:
(i) The SSVM can be designed so that it forms a continuous function of
the data, yet also approximates the potentially discontinuous log
likelihood ratio test.
(ii) Extension to universal detection is developed, in which only one
hypothesis is labeled (a semi-supervised learning problem).
(iii) The SSVM generalizes the robust hypothesis testing problem based on
a moment class.

Motivation for the approach and analysis are each based on ideas from
information theory. A detailed performance analysis is provided in the
special case of i.i.d. observations.}}

@misc{unnveemey09b,
Author = {J. Unnikrishnan and Venugopal V. Veeravalli and Sean Meyn},
Howpublished = {Submitted for publication, {IEEE Trans. IT}.},
Title = {Minimax Robust Quickest Change Detection},
Url = {http://www.citebase.org/abstract?id=oai:arXiv.org:0911.2551},
Year = {2009}}

@article{panmey06a,
Author = {Pandit, C. and Meyn, S. P.},
Date-Added = {2006-05-03 10:52:30 -0500},
Date-Modified = {2007-07-11 11:01:34 -0400},
Journal = SPA,
Keywords = {Information Theory},
Month = {May},
Number = {5},
Pages = {724-756},
Title = {Worst-Case Large-Deviations with Application to Queueing and Information Theory},
Volume = {116},
Year = {2006}}

@inproceedings{panmeyven04b,
Author = {Huang, J. and Pandit, C. and Meyn, S. and Veeravalli, V. V.},
Booktitle = {In Proc. IEEE Information Theory Workshop, San Antonio, TX},
Month = {October 24-29},
Pages = {76-81},
Title = {Extremal Distributions in Information Theory and Hypothesis Testing (Invited.)},
Year = {2004}}

@inproceedings{meysurlinnar09,
Author = {Meyn, S. and Surana, A. and Lin, Y. and Narayanan, S.},
Booktitle = {Proc. {48th IEEE Conference on Decision and Control}},
Month = {December 16-18},
Title = {Anomaly Detection Using Projective {Markov} Models in a Distributed Sensor Network},
Year = {2009}}