Speed-up of Encoder Optimization Step in Multiple Description Scalar Quantizer Design

The design of optimal multiple description scalar quantizers was pioneered by Vaishampayan with a generalization of Lloyd's algorithm, which alternatively optimizes the decoder, respectively the encoder, while the other component is fixed. We propose an algorithm which speeds up the encoder optimization step from $O{(N^2)}$ to $O{(N \log N)}$ time complexity, where $N$ is the number of cells in the central partition.