2
$\begingroup$

This question is based on my doubt on the application of Lloyd's algorithm in minimizing quantization error when performing scalar quantization to this problem. I have a quantization function to partition /quantize a real valued data. The way I understand the working of Lloyd's algorithm is that it can be used to optimize the error between quantized and unquantized data.

Problem statement : Let a binary valued data $\mathbf{s} = \{1,0,1,1\}$ containing 4 elements is encoded using an encoding function $g()$. So, $s(1) = 1, s(2) =0, s(3) = 1, s(4)=1$.

The output of encoding produces a scalar real valued number, say $x = g_1(\mathbf{s})$.

$g_1(.)$ is the inverse function of $g(.)$. Now, the function $g()$ is an iterative function $x(t) = g(x({t-1}))$. Let $t = 1,2,3,4$ so, there will be 4 values in array $\mathbf{x}$.

In my application, I have a quantizer function $\mathcal{Q}(.)$ defined as

$s(t) = \mathcal{Q}(x(t))$. Now, it is desired that this output be close to the original array vector $\mathbf{s} = \{1,0,1,1\}$.

Objective : The encoding and quantization steps results in some error, and in many papers I have seen that Lloyd's algorithm is applied in Vector Quantization esp. in kmeans clustering.

Where can I apply Lloyd's algorithm in my case?

Please do suggest any other appropriate way that makes more sense. Shall really appreciate insights and corrections in any step of my approach of applying Lloyd's algorithm.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

Lloyds algorithm assumes continuous input data.

You encode multivariate continuous data (e.g. RGB colors of pixels) with a finite dictionary (e.g. color palette entries).

So you will encode different shades of red as 0, different shades of blue as 1, ... Every of these codes will have a color assigned to it, but only one shade of red.

The error is then how much the real shade of red diverts from the shade of red assigned to the codeword 0; and how much the actual shade of blue diverts from the blue assigned to the codeword 1.

The more codewords you allow, the better your approximation can be.

But if your input data is already binary, e.g. 1, 0, 1, 1, the only reasonable encoding is isomorphic to the original data, and encode 0s as a codeword corresponding to 0 and 1s as the codeword corresponding to 1.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thank you but your answer is quite unclear to me and does not address all of my problems. Can you please kindly provide some insights? A scalar valued number can be obtained from some binary valued data using the iterative application of an inverse function, $g_1(.)$. Let, this scalar value be called as $x_1$. Now, using a partition (pre-determined and known), I can obtain the binary symbols using the partition $p$ as the threshold point and from the real valued iterates $x(2) = g(x(1)), x(3) = g(x(2)), x(4) = g(x(3))$. $\endgroup$
    – Ria George
    Commented Mar 30, 2017 at 15:15
  • $\begingroup$ it is assumed that there is a one-to-one mapping between the functions $g(.)$ and its inverse $g_1(.)$. Then, the symbols can be obtained using a quantization function $\mathcal{Q}(x(1)) = s(1) =1$, if $x(1) >=p$, otherwise $\mathcal{Q}(x(1)) = s(1) =0$. In this whole process, I think there should be some error but I don't know where, at which step. $\endgroup$
    – Ria George
    Commented Mar 30, 2017 at 15:15
  • $\begingroup$ Stop using binary valued data! You don't need to quantize binary data, it already is quantized. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Mar 31, 2017 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.