Harmonic entropy: Difference between revisions
Wikispaces>mbattaglia1 **Imported revision 624269955 - Original comment: ** |
Wikispaces>mbattaglia1 **Imported revision 624270037 - Original comment: ** |
||
| Line 1: | Line 1: | ||
<h2>IMPORTED REVISION FROM WIKISPACES</h2> | <h2>IMPORTED REVISION FROM WIKISPACES</h2> | ||
This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | ||
: This revision was by author [[User:mbattaglia1|mbattaglia1]] and made on <tt>2017-12-27 19: | : This revision was by author [[User:mbattaglia1|mbattaglia1]] and made on <tt>2017-12-27 19:46:10 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>624270037</tt>.<br> | ||
: The revision comment was: <tt></tt><br> | : The revision comment was: <tt></tt><br> | ||
The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | ||
| Line 176: | Line 176: | ||
//Harmonic Rényi Entropy with a=7, with the high value of a being chosen to approximate min-entropy (a=//∞//). The basis set is still all rationals with Tenney height ≤ 10000, the spreading function a Gaussian distribution with s=1% (~17 cents), and the complexity function sqrt(n·d).// | //Harmonic Rényi Entropy with a=7, with the high value of a being chosen to approximate min-entropy (a=//∞//). The basis set is still all rationals with Tenney height ≤ 10000, the spreading function a Gaussian distribution with s=1% (~17 cents), and the complexity function sqrt(n·d).// | ||
= = | = = | ||
=Convolution-Based | =Convolution-Based Expression For Quickly Computing Renyi Entropy= | ||
Below is given an derivation that expresses Harmonic Renyi Entropy in terms of two simpler functions, each of which is a convolution product and hence can be computed quickly using the Fast Fourier Transform. The below derivation depends on the use of complexity-normalization probabilities, although it may be possible to extend to domain-integral probabilities instead. | Below is given an derivation that expresses Harmonic Renyi Entropy in terms of two simpler functions, each of which is a convolution product and hence can be computed quickly using the Fast Fourier Transform. The below derivation depends on the use of complexity-normalization probabilities, although it may be possible to extend to domain-integral probabilities instead. | ||
| Line 290: | Line 290: | ||
so that | so that | ||
[[math]] | [[math]] | ||
\rho_a(d) = \left[S^a \ast K^a](-d) | \rho_a(d) = \left[S^a \ast K^a\right](-d) | ||
[[math]] | [[math]] | ||
We have now succeeded in representing ρ<span style="vertical-align: sub;">a</span>(d) as a convolution. | We have now succeeded in representing ρ<span style="vertical-align: sub;">a</span>(d) as a convolution. | ||
Note that the function K<span style="vertical-align: super;">a</span>(d) involves a slight abuse of notation, as it is not literally K(d) taken to the a'th power (as the square of the delta distribution is undefined). Rather, we are simply taking the weights of each delta distribution in the summation to the a'th power. | |||
===Round-up=== | ===Round-up=== | ||
| Line 327: | Line 327: | ||
<!-- ws:end:WikiTextTocRule:77 --><!-- ws:start:WikiTextTocRule:78: --><div style="margin-left: 3em;"><a href="#Examples--a=∞: Harmonic Min-Entropy">a=∞: Harmonic Min-Entropy</a></div> | <!-- ws:end:WikiTextTocRule:77 --><!-- ws:start:WikiTextTocRule:78: --><div style="margin-left: 3em;"><a href="#Examples--a=∞: Harmonic Min-Entropy">a=∞: Harmonic Min-Entropy</a></div> | ||
<!-- ws:end:WikiTextTocRule:78 --><!-- ws:start:WikiTextTocRule:79: --><div style="margin-left: 1em;"><a href="#toc10"> </a></div> | <!-- ws:end:WikiTextTocRule:78 --><!-- ws:start:WikiTextTocRule:79: --><div style="margin-left: 1em;"><a href="#toc10"> </a></div> | ||
<!-- ws:end:WikiTextTocRule:79 --><!-- ws:start:WikiTextTocRule:80: --><div style="margin-left: 1em;"><a href="#Convolution-Based | <!-- ws:end:WikiTextTocRule:79 --><!-- ws:start:WikiTextTocRule:80: --><div style="margin-left: 1em;"><a href="#Convolution-Based Expression For Quickly Computing Renyi Entropy">Convolution-Based Expression For Quickly Computing Renyi Entropy</a></div> | ||
<!-- ws:end:WikiTextTocRule:80 --><!-- ws:start:WikiTextTocRule:81: --><div style="margin-left: 3em;"><a href="#Convolution-Based | <!-- ws:end:WikiTextTocRule:80 --><!-- ws:start:WikiTextTocRule:81: --><div style="margin-left: 3em;"><a href="#Convolution-Based Expression For Quickly Computing Renyi Entropy--Preliminaries">Preliminaries</a></div> | ||
<!-- ws:end:WikiTextTocRule:81 --><!-- ws:start:WikiTextTocRule:82: --><div style="margin-left: 3em;"><a href="#Convolution-Based | <!-- ws:end:WikiTextTocRule:81 --><!-- ws:start:WikiTextTocRule:82: --><div style="margin-left: 3em;"><a href="#Convolution-Based Expression For Quickly Computing Renyi Entropy--Convolution product for ψ(d)">Convolution product for ψ(d)</a></div> | ||
<!-- ws:end:WikiTextTocRule:82 --><!-- ws:start:WikiTextTocRule:83: --><div style="margin-left: 3em;"><a href="#Convolution-Based | <!-- ws:end:WikiTextTocRule:82 --><!-- ws:start:WikiTextTocRule:83: --><div style="margin-left: 3em;"><a href="#Convolution-Based Expression For Quickly Computing Renyi Entropy--Convolution product for ρa(d)">Convolution product for ρa(d)</a></div> | ||
<!-- ws:end:WikiTextTocRule:83 --><!-- ws:start:WikiTextTocRule:84: --><div style="margin-left: 3em;"><a href="#Convolution-Based | <!-- ws:end:WikiTextTocRule:83 --><!-- ws:start:WikiTextTocRule:84: --><div style="margin-left: 3em;"><a href="#Convolution-Based Expression For Quickly Computing Renyi Entropy--Round-up">Round-up</a></div> | ||
<!-- ws:end:WikiTextTocRule:84 --><!-- ws:start:WikiTextTocRule:85: --><div style="margin-left: 1em;"><a href="#References">References</a></div> | <!-- ws:end:WikiTextTocRule:84 --><!-- ws:start:WikiTextTocRule:85: --><div style="margin-left: 1em;"><a href="#References">References</a></div> | ||
<!-- ws:end:WikiTextTocRule:85 --><!-- ws:start:WikiTextTocRule:86: --></div> | <!-- ws:end:WikiTextTocRule:85 --><!-- ws:start:WikiTextTocRule:86: --></div> | ||
| Line 503: | Line 503: | ||
<em>Harmonic Rényi Entropy with a=7, with the high value of a being chosen to approximate min-entropy (a=</em>∞<em>). The basis set is still all rationals with Tenney height ≤ 10000, the spreading function a Gaussian distribution with s=1% (~17 cents), and the complexity function sqrt(n·d).</em><br /> | <em>Harmonic Rényi Entropy with a=7, with the high value of a being chosen to approximate min-entropy (a=</em>∞<em>). The basis set is still all rationals with Tenney height ≤ 10000, the spreading function a Gaussian distribution with s=1% (~17 cents), and the complexity function sqrt(n·d).</em><br /> | ||
<!-- ws:start:WikiTextHeadingRule:54:&lt;h1&gt; --><h1 id="toc10"><!-- ws:end:WikiTextHeadingRule:54 --> </h1> | <!-- ws:start:WikiTextHeadingRule:54:&lt;h1&gt; --><h1 id="toc10"><!-- ws:end:WikiTextHeadingRule:54 --> </h1> | ||
<!-- ws:start:WikiTextHeadingRule:56:&lt;h1&gt; --><h1 id="toc11"><a name="Convolution-Based | <!-- ws:start:WikiTextHeadingRule:56:&lt;h1&gt; --><h1 id="toc11"><a name="Convolution-Based Expression For Quickly Computing Renyi Entropy"></a><!-- ws:end:WikiTextHeadingRule:56 -->Convolution-Based Expression For Quickly Computing Renyi Entropy</h1> | ||
Below is given an derivation that expresses Harmonic Renyi Entropy in terms of two simpler functions, each of which is a convolution product and hence can be computed quickly using the Fast Fourier Transform. The below derivation depends on the use of complexity-normalization probabilities, although it may be possible to extend to domain-integral probabilities instead.<br /> | Below is given an derivation that expresses Harmonic Renyi Entropy in terms of two simpler functions, each of which is a convolution product and hence can be computed quickly using the Fast Fourier Transform. The below derivation depends on the use of complexity-normalization probabilities, although it may be possible to extend to domain-integral probabilities instead.<br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:58:&lt;h3&gt; --><h3 id="toc12"><a name="Convolution-Based | <!-- ws:start:WikiTextHeadingRule:58:&lt;h3&gt; --><h3 id="toc12"><a name="Convolution-Based Expression For Quickly Computing Renyi Entropy--Preliminaries"></a><!-- ws:end:WikiTextHeadingRule:58 -->Preliminaries</h3> | ||
The Harmonic Renyi Entropy is defined as<br /> | The Harmonic Renyi Entropy is defined as<br /> | ||
<br /> | <br /> | ||
| Line 559: | Line 559: | ||
We thus reduce the term inside the logarithm to the quotient of the functions ρ<span style="vertical-align: sub;">a</span>(d) and ψ(d)<span style="vertical-align: super;">a</span>. Our aim is now to express each of these two functions in terms of a convolution product.<br /> | We thus reduce the term inside the logarithm to the quotient of the functions ρ<span style="vertical-align: sub;">a</span>(d) and ψ(d)<span style="vertical-align: super;">a</span>. Our aim is now to express each of these two functions in terms of a convolution product.<br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:60:&lt;h3&gt; --><h3 id="toc13"><a name="Convolution-Based | <!-- ws:start:WikiTextHeadingRule:60:&lt;h3&gt; --><h3 id="toc13"><a name="Convolution-Based Expression For Quickly Computing Renyi Entropy--Convolution product for ψ(d)"></a><!-- ws:end:WikiTextHeadingRule:60 -->Convolution product for ψ(d)</h3> | ||
ψ(d), the normalization function, is written as follows:<br /> | ψ(d), the normalization function, is written as follows:<br /> | ||
<br /> | <br /> | ||
| Line 603: | Line 603: | ||
--><script type="math/tex">\psi(d) = \left[S \ast K\right](-d)</script><!-- ws:end:WikiTextMathRule:26 --><br /> | --><script type="math/tex">\psi(d) = \left[S \ast K\right](-d)</script><!-- ws:end:WikiTextMathRule:26 --><br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:62:&lt;h3&gt; --><h3 id="toc14"><a name="Convolution-Based | <!-- ws:start:WikiTextHeadingRule:62:&lt;h3&gt; --><h3 id="toc14"><a name="Convolution-Based Expression For Quickly Computing Renyi Entropy--Convolution product for ρa(d)"></a><!-- ws:end:WikiTextHeadingRule:62 -->Convolution product for ρ<span style="vertical-align: sub;">a</span>(d)</h3> | ||
The derivation for ρ<span style="vertical-align: sub;">a</span>(d) proceeds similarly. Recall the function is written as follows:<br /> | The derivation for ρ<span style="vertical-align: sub;">a</span>(d) proceeds similarly. Recall the function is written as follows:<br /> | ||
<!-- ws:start:WikiTextMathRule:27: | <!-- ws:start:WikiTextMathRule:27: | ||
| Line 637: | Line 637: | ||
<!-- ws:start:WikiTextMathRule:32: | <!-- ws:start:WikiTextMathRule:32: | ||
[[math]]&lt;br/&gt; | [[math]]&lt;br/&gt; | ||
\rho_a(d) = \left[S^a \ast K^a](-d)&lt;br/&gt;[[math]] | \rho_a(d) = \left[S^a \ast K^a\right](-d)&lt;br/&gt;[[math]] | ||
--><script type="math/tex">\rho_a(d) = \left[S^a \ast K^a](-d)</script><!-- ws:end:WikiTextMathRule:32 --><br /> | --><script type="math/tex">\rho_a(d) = \left[S^a \ast K^a\right](-d)</script><!-- ws:end:WikiTextMathRule:32 --><br /> | ||
<br /> | <br /> | ||
We have now succeeded in representing ρ<span style="vertical-align: sub;">a</span>(d) as a convolution.<br /> | We have now succeeded in representing ρ<span style="vertical-align: sub;">a</span>(d) as a convolution.<br /> | ||
Note that the function K<span style="vertical-align: super;">a</span>(d) involves a slight abuse of notation, as it is not literally K(d) taken to the a'th power (as the square of the delta distribution is undefined). Rather, we are simply taking the weights of each delta distribution in the summation to the a'th power.<br /> | |||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:64:&lt;h3&gt; --><h3 id="toc15"><a name="Convolution-Based | <!-- ws:start:WikiTextHeadingRule:64:&lt;h3&gt; --><h3 id="toc15"><a name="Convolution-Based Expression For Quickly Computing Renyi Entropy--Round-up"></a><!-- ws:end:WikiTextHeadingRule:64 -->Round-up</h3> | ||
Taking all of this, we can rewrite the original expression for Harmonic Renyi Entropy as follows:<br /> | Taking all of this, we can rewrite the original expression for Harmonic Renyi Entropy as follows:<br /> | ||
<!-- ws:start:WikiTextMathRule:33: | <!-- ws:start:WikiTextMathRule:33: | ||