Structure metric: Difference between revisions
Wikispaces>genewardsmith **Imported revision 563665673 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 564238161 - 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:genewardsmith|genewardsmith]] and made on <tt>2015-10- | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2015-10-28 14:43:14 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>564238161</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 29: | Line 29: | ||
First, || **s**[i + j] mod **O** || ≤ ||**s**[i]|| + ||**s**[j]|| where **O** is the interval of equivalence. If an interval in the interval class of **s**[i] equals **s**[i] and an interval in the interval class of **s**[j] equals **s**[j], then their product, reduced modulo the interval of equivalence **O** equals **s**[**P**], will be **s**[i + j] mod **O**. Hence to get an interval in the class of **s**[i + j] mod **O** other than **s**[i + j] mod **O** as a product, either the interval in the class of **s**[i] must be other than **s**[i], or the interval in the class of **s**[j] must be other than **s**[j]. If always only one of the intervals is different than the defining interval for its class, then || **s**[i + j] mod **O** || equals ||**s**[i]|| + ||**s**[j]||. However, there may be overlap, so that the first interval is not in the class for **s**[i] and the second not in the class for **s**[j], so that the count is double on the right hand side. In any case, we get the inequality. Now d(**s**[i], **s**[j]) + d(**s**[j], **s**[k]) = || |**s**[i] - **s**[j]| || + || |**s**[j] - **s**[k]| || ≥ || |**s**[i] - **s**[k]| || = d(**s**[i], **s**[k]). | First, || **s**[i + j] mod **O** || ≤ ||**s**[i]|| + ||**s**[j]|| where **O** is the interval of equivalence. If an interval in the interval class of **s**[i] equals **s**[i] and an interval in the interval class of **s**[j] equals **s**[j], then their product, reduced modulo the interval of equivalence **O** equals **s**[**P**], will be **s**[i + j] mod **O**. Hence to get an interval in the class of **s**[i + j] mod **O** other than **s**[i + j] mod **O** as a product, either the interval in the class of **s**[i] must be other than **s**[i], or the interval in the class of **s**[j] must be other than **s**[j]. If always only one of the intervals is different than the defining interval for its class, then || **s**[i + j] mod **O** || equals ||**s**[i]|| + ||**s**[j]||. However, there may be overlap, so that the first interval is not in the class for **s**[i] and the second not in the class for **s**[j], so that the count is double on the right hand side. In any case, we get the inequality. Now d(**s**[i], **s**[j]) + d(**s**[j], **s**[k]) = || |**s**[i] - **s**[j]| || + || |**s**[j] - **s**[k]| || ≥ || |**s**[i] - **s**[k]| || = d(**s**[i], **s**[k]). | ||
These properties mean that the structure metric defines a //finite metric space//. This is a structure which has gained a certain amount of attention, particularly in terms of applications in fields requiring data analysis with an eye to similarities and differences.</pre></div> | These properties mean that the structure metric defines a //finite metric space//. This is a structure which has gained a certain amount of attention, particularly in terms of applications in fields requiring data analysis with an eye to similarities and differences. | ||
=Isometry= | |||
An [[https://en.wikipedia.org/wiki/Isometry|isometry]] between two metric spaces is a distance-preserving mapping; a mapping f from metric spaces X and Y such that the distance d(f(a), f(b)) in Y equals d(a, b) in X. If f is a bijection, then the isometry defines an isometric isomorphism between X and Y; in this case X and Y are said to be isometric. A metric space X is always isometric to itself by the identity map, but it may have nontrivial isometries. The isometries of X with itself define a group, the [[https://en.wikipedia.org/wiki/Isometry_group|isometry group]]. | |||
In the case of a finite metric space, the isometry group is defined by a permutation group on the set of points. Any finite metric space is completely characterized by the distance matrix (d(i, j)), where "i" denotes the ith point in some ordering. If S is a permutation matrix on these points, it is an element of the isometry group if and only if S.D.S^(-1) = D, where the dot is matrix multiplication. In this case, D is permutation-similar to itself by S.</pre></div> | |||
<h4>Original HTML content:</h4> | <h4>Original HTML content:</h4> | ||
<div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Structure metric</title></head><body><!-- ws:start:WikiTextTocRule: | <div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Structure metric</title></head><body><!-- ws:start:WikiTextTocRule:6:&lt;img id=&quot;wikitext@@toc@@normal&quot; class=&quot;WikiMedia WikiMediaToc&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/normal?w=225&amp;h=100&quot;/&gt; --><div id="toc"><h1 class="nopad">Table of Contents</h1><!-- ws:end:WikiTextTocRule:6 --><!-- ws:start:WikiTextTocRule:7: --><div style="margin-left: 1em;"><a href="#Definition">Definition</a></div> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:7 --><!-- ws:start:WikiTextTocRule:8: --><div style="margin-left: 1em;"><a href="#Properties">Properties</a></div> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:8 --><!-- ws:start:WikiTextTocRule:9: --><div style="margin-left: 1em;"><a href="#Isometry">Isometry</a></div> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:9 --><!-- ws:start:WikiTextTocRule:10: --></div> | ||
<!-- ws:end:WikiTextTocRule:10 --><br /> | |||
<!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Definition"></a><!-- ws:end:WikiTextHeadingRule:0 -->Definition</h1> | <!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Definition"></a><!-- ws:end:WikiTextHeadingRule:0 -->Definition</h1> | ||
The <em>structure metric</em> is a <a class="wiki_link_ext" href="https://en.wikipedia.org/wiki/Metric_(mathematics)" rel="nofollow">distance function</a> on the notes of a <a class="wiki_link" href="/constant%20structure">constant structure</a> <a class="wiki_link" href="/periodic%20scale">periodic scale</a> within the period, which give to it the property of being a <a class="wiki_link_ext" href="https://en.wikipedia.org/wiki/Metric_space" rel="nofollow">finite metric space</a>. If <strong>s</strong> is a periodic scale with quasiperiod <strong>P</strong>, and if <strong>s</strong>[i] with 0≤i&lt;<strong>P</strong> is a note of <strong>s</strong> within the period <strong>P</strong>, then we may define the base points set base(<strong>s</strong>[i]) to be the set of integers {j | <strong>s</strong>[j+i] - <strong>s</strong>[j] = <strong>s</strong>[i], 0≤j&lt;<strong>P</strong>}. These have the property that the interval between the base note <strong>s</strong>[j] and the note i steps away, <strong>s</strong>[j+i], is in class(i), the interval class to which <strong>s</strong>[i] belongs. If the cardinality of this set is n, there are n indicies which correspond to intervals of <strong>s</strong>[i], and <strong>P</strong>-n which correspond to indicies of intervals other than <strong>s</strong>[i]. In other words, there are <strong>P</strong>-n intervals, counting multiplicities, in the class of <strong>s</strong>[i] other than <strong>s</strong>[i]. Then the <em>structure complexity</em> ||<strong>s</strong>[i]|| of <strong>s</strong>[i] is defined to be <strong>P</strong>-n, and the structure metric is defined as d(<strong>s</strong>[i], <strong>s</strong>[j]) = || |<strong>s</strong>[i] - <strong>s</strong>[j]| ||.<br /> | The <em>structure metric</em> is a <a class="wiki_link_ext" href="https://en.wikipedia.org/wiki/Metric_(mathematics)" rel="nofollow">distance function</a> on the notes of a <a class="wiki_link" href="/constant%20structure">constant structure</a> <a class="wiki_link" href="/periodic%20scale">periodic scale</a> within the period, which give to it the property of being a <a class="wiki_link_ext" href="https://en.wikipedia.org/wiki/Metric_space" rel="nofollow">finite metric space</a>. If <strong>s</strong> is a periodic scale with quasiperiod <strong>P</strong>, and if <strong>s</strong>[i] with 0≤i&lt;<strong>P</strong> is a note of <strong>s</strong> within the period <strong>P</strong>, then we may define the base points set base(<strong>s</strong>[i]) to be the set of integers {j | <strong>s</strong>[j+i] - <strong>s</strong>[j] = <strong>s</strong>[i], 0≤j&lt;<strong>P</strong>}. These have the property that the interval between the base note <strong>s</strong>[j] and the note i steps away, <strong>s</strong>[j+i], is in class(i), the interval class to which <strong>s</strong>[i] belongs. If the cardinality of this set is n, there are n indicies which correspond to intervals of <strong>s</strong>[i], and <strong>P</strong>-n which correspond to indicies of intervals other than <strong>s</strong>[i]. In other words, there are <strong>P</strong>-n intervals, counting multiplicities, in the class of <strong>s</strong>[i] other than <strong>s</strong>[i]. Then the <em>structure complexity</em> ||<strong>s</strong>[i]|| of <strong>s</strong>[i] is defined to be <strong>P</strong>-n, and the structure metric is defined as d(<strong>s</strong>[i], <strong>s</strong>[j]) = || |<strong>s</strong>[i] - <strong>s</strong>[j]| ||.<br /> | ||
| Line 56: | Line 62: | ||
First, || <strong>s</strong>[i + j] mod <strong>O</strong> || ≤ ||<strong>s</strong>[i]|| + ||<strong>s</strong>[j]|| where <strong>O</strong> is the interval of equivalence. If an interval in the interval class of <strong>s</strong>[i] equals <strong>s</strong>[i] and an interval in the interval class of <strong>s</strong>[j] equals <strong>s</strong>[j], then their product, reduced modulo the interval of equivalence <strong>O</strong> equals <strong>s</strong>[<strong>P</strong>], will be <strong>s</strong>[i + j] mod <strong>O</strong>. Hence to get an interval in the class of <strong>s</strong>[i + j] mod <strong>O</strong> other than <strong>s</strong>[i + j] mod <strong>O</strong> as a product, either the interval in the class of <strong>s</strong>[i] must be other than <strong>s</strong>[i], or the interval in the class of <strong>s</strong>[j] must be other than <strong>s</strong>[j]. If always only one of the intervals is different than the defining interval for its class, then || <strong>s</strong>[i + j] mod <strong>O</strong> || equals ||<strong>s</strong>[i]|| + ||<strong>s</strong>[j]||. However, there may be overlap, so that the first interval is not in the class for <strong>s</strong>[i] and the second not in the class for <strong>s</strong>[j], so that the count is double on the right hand side. In any case, we get the inequality. Now d(<strong>s</strong>[i], <strong>s</strong>[j]) + d(<strong>s</strong>[j], <strong>s</strong>[k]) = || |<strong>s</strong>[i] - <strong>s</strong>[j]| || + || |<strong>s</strong>[j] - <strong>s</strong>[k]| || ≥ || |<strong>s</strong>[i] - <strong>s</strong>[k]| || = d(<strong>s</strong>[i], <strong>s</strong>[k]).<br /> | First, || <strong>s</strong>[i + j] mod <strong>O</strong> || ≤ ||<strong>s</strong>[i]|| + ||<strong>s</strong>[j]|| where <strong>O</strong> is the interval of equivalence. If an interval in the interval class of <strong>s</strong>[i] equals <strong>s</strong>[i] and an interval in the interval class of <strong>s</strong>[j] equals <strong>s</strong>[j], then their product, reduced modulo the interval of equivalence <strong>O</strong> equals <strong>s</strong>[<strong>P</strong>], will be <strong>s</strong>[i + j] mod <strong>O</strong>. Hence to get an interval in the class of <strong>s</strong>[i + j] mod <strong>O</strong> other than <strong>s</strong>[i + j] mod <strong>O</strong> as a product, either the interval in the class of <strong>s</strong>[i] must be other than <strong>s</strong>[i], or the interval in the class of <strong>s</strong>[j] must be other than <strong>s</strong>[j]. If always only one of the intervals is different than the defining interval for its class, then || <strong>s</strong>[i + j] mod <strong>O</strong> || equals ||<strong>s</strong>[i]|| + ||<strong>s</strong>[j]||. However, there may be overlap, so that the first interval is not in the class for <strong>s</strong>[i] and the second not in the class for <strong>s</strong>[j], so that the count is double on the right hand side. In any case, we get the inequality. Now d(<strong>s</strong>[i], <strong>s</strong>[j]) + d(<strong>s</strong>[j], <strong>s</strong>[k]) = || |<strong>s</strong>[i] - <strong>s</strong>[j]| || + || |<strong>s</strong>[j] - <strong>s</strong>[k]| || ≥ || |<strong>s</strong>[i] - <strong>s</strong>[k]| || = d(<strong>s</strong>[i], <strong>s</strong>[k]).<br /> | ||
<br /> | <br /> | ||
These properties mean that the structure metric defines a <em>finite metric space</em>. This is a structure which has gained a certain amount of attention, particularly in terms of applications in fields requiring data analysis with an eye to similarities and differences.</body></html></pre></div> | These properties mean that the structure metric defines a <em>finite metric space</em>. This is a structure which has gained a certain amount of attention, particularly in terms of applications in fields requiring data analysis with an eye to similarities and differences.<br /> | ||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:4:&lt;h1&gt; --><h1 id="toc2"><a name="Isometry"></a><!-- ws:end:WikiTextHeadingRule:4 -->Isometry</h1> | |||
An <a class="wiki_link_ext" href="https://en.wikipedia.org/wiki/Isometry" rel="nofollow">isometry</a> between two metric spaces is a distance-preserving mapping; a mapping f from metric spaces X and Y such that the distance d(f(a), f(b)) in Y equals d(a, b) in X. If f is a bijection, then the isometry defines an isometric isomorphism between X and Y; in this case X and Y are said to be isometric. A metric space X is always isometric to itself by the identity map, but it may have nontrivial isometries. The isometries of X with itself define a group, the <a class="wiki_link_ext" href="https://en.wikipedia.org/wiki/Isometry_group" rel="nofollow">isometry group</a>.<br /> | |||
<br /> | |||
In the case of a finite metric space, the isometry group is defined by a permutation group on the set of points. Any finite metric space is completely characterized by the distance matrix (d(i, j)), where &quot;i&quot; denotes the ith point in some ordering. If S is a permutation matrix on these points, it is an element of the isometry group if and only if S.D.S^(-1) = D, where the dot is matrix multiplication. In this case, D is permutation-similar to itself by S.</body></html></pre></div> | |||