Entropy from Laplacian Density

[Niels Fröhling]

Hy;

Is there a direct formula known to calculate order-0 entropy from laplacian
density function-parameters (known variance and mean)?

Maybe there are some approximations, like integration and piecewise splitting
into f(x)=x*z because I suppose there are direct calculations known for
calculating entropy of linear functions, right?

My problem is that I can't iterate over the entire defined space (I have 20000
laplacian parameters for a -65536 to 65535 range).

Thanks
Niels

[Thomas Richter]

Niels Fr�hling schrieb:

> Hy;
>
> Is there a direct formula known to calculate order-0 entropy from
> laplacian density function-parameters (known variance and mean)?

Sure there are. Depends a bit on what you're looking at, i.e. is this a
one-sided or a two-sided Laplacian distribution?

For a continuous Laplacian distribution, one can integrate the
differential entropy directly. For its discretization (i.e.
quantization), you also find closed formula in the literature, for
example here:

G.J. Sullivan, "Efficient Scalar Quantization", Proc. of ICASSP 2004,
Vol. 4, pp. 605-608, 2004.

Gary uses a nice trick to more or less write down the answer directly,
but one can also compute the result explicitly by geometric summation.

Here Gary considers a two-sided Laplacian source with variance \sigma, i.e.

p(x) ~ exp(-|x|*\sqrt{2}/\sigma)

and considers a quantizer of the form

q = sign(x) * \max(0,\floor{\frac{|x|}{2}-\frac{z}{2}+1}), i.e.
a bucket size of s and a dead-zone of z.

Then the 0-order entropy of the discrete source given by q can be
computed to be

H_L(q) = B(\exp{-T}) + \exp{-T}\floor{1+\frac{B(\exp{-s})}{1-\exp{-s})}

where T = zs / 2 and B(p) = -p log_2(p) - (1-p)\log_2(1-p).

Results for other quantizers are also in the quoted paper.

> Maybe there are some approximations, like integration and piecewise
> splitting into f(x)=x*z because I suppose there are direct calculations
> known for calculating entropy of linear functions, right?

No need to approximate. The Laplace distribution is one of the very few
sources where you have explicit results for the rate/distortion curve.
The above article provides details.

> My problem is that I can't iterate over the entire defined space (I
> have 20000 laplacian parameters for a -65536 to 65535 range).

Well, maybe I don't quite understand where your problem is. Why do you
need to iterate? Iterate over what?

So long,
Thomas

[Niels Fröhling]

Hy Thomas;

Yes, it's TSGS.
I'll look into it in the afternoon, just want to send you my thanks. :)

>> Maybe there are some approximations, like integration and piecewise
>> splitting into f(x)=x*z because I suppose there are direct
>> calculations known for calculating entropy of linear functions, right?
>
> No need to approximate. The Laplace distribution is one of the very few
> sources where you have explicit results for the rate/distortion curve.
> The above article provides details.

Great! How about Gaussian?

>> My problem is that I can't iterate over the entire defined space (I
>> have 20000 laplacian parameters for a -65536 to 65535 range).
>
> Well, maybe I don't quite understand where your problem is. Why do you
> need to iterate? Iterate over what?

Well, without the formula I was iterating over the value-range

for (i = -65536; i < 65535; i++)

and summing up the entropy the naive way, as if it's a statistical
distribution. I normalized the LDF through calculating the area covered of the
range 0 to 15 and matching it with the area covered from the real statistics
from 0 to 15. It's surprisingly exact.

So you see 20000*131072 is a lot considering it's not the most easiest code in
the loop-body.

> So long,
> Thomas

Ciao and thanks
Niels

[Thomas Richter]

Hi Niels,

> Yes, it's TSGS.
> I'll look into it in the afternoon, just want to send you my thanks. :)

You're welcome.

>>> Maybe there are some approximations, like integration and piecewise
>>> splitting into f(x)=x*z because I suppose there are direct
>>> calculations known for calculating entropy of linear functions, right?
>>
>> No need to approximate. The Laplace distribution is one of the very few
>> sources where you have explicit results for the rate/distortion curve.
>> The above article provides details.
>
> Great! How about Gaussian?

The rate-distortion curve is known exactly, I'm not sure about the
entropy, I can't remember right now. Unfortunately, you just ask me one
day too late, I'm now on vacation and don't have the right book handy,
but in case you want to try your luck, you find the r-d curve of the
gaussian, the laplacian and the uniform source in the Marcellin/Taubman
book on JPEG 2000 (and the sources quoted there). I think that's about
what one can compute exactly, unless you call incomplete gamma functions
exact solutions. I did that once for a rate-allocation algorithm, and
the result doesn't look nice. I can dig that out if you like.

For gaussians, you do have of course the old result that it is the
worst-possible source in the rate distortion sense (i.e. the R-D curve
of any other source has higher rate for the same distortion), which is a
rather direct application of variation theory. The proof is short, but I
cannot reproduce it off my head. It's also in the mentioned source.

> Well, without the formula I was iterating over the value-range
>
> for (i = -65536; i < 65535; i++)
>
> and summing up the entropy the naive way, as if it's a statistical
> distribution. I normalized the LDF through calculating the area covered
> of the range 0 to 15 and matching it with the area covered from the real
> statistics from 0 to 15. It's surprisingly exact.

Hmm. Sounds like a numerical nightmare for me. Summing large quatities
creates surprising sources for numerical errors.

> So you see 20000*131072 is a lot considering it's not the most easiest
> code in the loop-body.

Agreed. (-:

So long,
Thomas

[Niels Fröhling]

Thomas Richter wrote:

> G.J. Sullivan, "Efficient Scalar Quantization", Proc. of ICASSP 2004,
> Vol. 4, pp. 605-608, 2004.
>
> Gary uses a nice trick to more or less write down the answer directly,
> but one can also compute the result explicitly by geometric summation.
>
> Here Gary considers a two-sided Laplacian source with variance \sigma, i.e.
>
> p(x) ~ exp(-|x|*\sqrt{2}/\sigma)
>
> and considers a quantizer of the form
>
> q = sign(x) * \max(0,\floor{\frac{|x|}{2}-\frac{z}{2}+1}), i.e.
> a bucket size of s and a dead-zone of z.
>
> Then the 0-order entropy of the discrete source given by q can be
> computed to be
>
> H_L(q) = B(\exp{-T}) + \exp{-T}\floor{1+\frac{B(\exp{-s})}{1-\exp{-s})}
>
> where T = zs / 2 and B(p) = -p log_2(p) - (1-p)\log_2(1-p).
>
> Results for other quantizers are also in the quoted paper.

Damn this is a nice source of those equations mentioned above:

http://cnx.org/content/m11090/latest/

For those without access to the paper. The page also shows approximations.

Ciao
Niels

[Thomas Richter]

Niels Fr�hling wrote:

> Damn this is a nice source of those equations mentioned above:
>
> http://cnx.org/content/m11090/latest/
>
> For those without access to the paper. The page also shows approximations.

Thanks. The computation there looks correct (and follows the same lines
how I computed it), but it is unnecessarily complicated. (-; It is a
one-liner if you know the trick; one has to use here the self-similarity
of the exponential.

Thanks,
Thomas