# Finding the best mismatched detector for channel coding and hypothesis testing

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

*See also*

- Extremal Distributions in Information Theory and Hypothesis Testing (ITW 2004)
- Entropy, Inference, and Channel Coding (IMA 2005)
- UCSD 2007 presentation
- Statistical SVMs for robust detection, supervised learning, and universal classification (ITW 2009)
- Anomaly Detection Using Projective Markov Models in a Distributed Sensor Network
- Minimax Robust Quickest Change Detection

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}}