# Closest Vector Search, Integer programming, Viterbi algorithm

Consider some vector $v$, matrix $H$. The problem of finding integer vector $I$, such that it minimizes |v - H I|^2 - is NP problem. It is obviously equivalent to searching closest lattice point

http://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_.28CVP.29

(The lattice - spanned by columns of $H$).

I guess it is also called "interger programming problem" (not sure).

Question 1 Consider $H$ is special matrix

a) circulant matrix b) Toeplitz (may be I need to restrict few-diagonals case) matrix $H$.

what are effective algorithms to use in this case ?

Question 2 My vague feelings that we should use something called "Viterbi equalizer" algorithm - is there something like this true ? http://www.scholarpedia.org/article/Viterbi_algorithm

http://en.wikipedia.org/wiki/Viterbi_algorithm

## Communication background

Consider transmission of sequence of signals (bits) i1, i2, i3,... which are integers. Assume that during the transmission signals are distorted: $k$-th received signals is obtained as $r(k)=h_0 i_k+ h_1i_{k-1}+...h_{l}i_{k-l} + random_{k}$.

The part $h_0 i_k+ h_1i_{k-1}+...h_{l}i_{k-l}$ is called ISI (inter-symbol interference). (Here $i_m$ - "sent symbols").

$+ random_{k}$ - noise distorting symbol e.g. thermal noise. So we can right in matrix-vector form: $R=HI+noise$, where $H$ will be $l$-diagonal Toeplitz matrix.

The task of the "receiver" having $R$ and $H$ -- to find $I$ (e.g. from received signal, find sent signal). Under assumption of Gassian distrubution for noise one can easily come that maximum likelihood answer for $I$ will be such an integer vector that $I=argmin|R-HI|^2$.

Origin of ISI (inter-symbol interference) can be "multi-path" propagation, which appears due to multiple reflections of the radio wave. "Reflected waves" come later - so we get mixture of signals.

Rather clearly ISI resembles a convolutional code http://en.wikipedia.org/wiki/Convolutional_code The well-known method to decode such codes is Viterbi algorithm (as far as I heard).. http://en.wikipedia.org/wiki/Viterbi_algorithm

There is modification of it for the case of codes to the case of ISI. This is called "Viterbi equalizer" (as far as I heard).