Minimum Complexity Sequential Multihypothesis Detection

Previous work in sequential multihypothesis testing has considered the goal of minimizing the expected number of observations required to choose a hypothesis with a desired level of accuracy. Motivated by reduced-complexity decoding applications, we consider sequential multihypothesis testing techniques that remove individual hypotheses from consideration as they become unlikely in order to minimize the expected aggregate number of hypotheses tested. In the limit of small decision error probabilities, the optimal sequential test that {\em rejects} a single hypothesis is characterized. A full minimum complexity sequential multihypothesis testing scheme which assumes the same error probability at each drop of a hypothesis then follows in a straightforward manner. Numerical results have demonstrated significant complexity savings via this approach.