Generator embedding optimization: Difference between revisions

When optimizing tunings of [[regular temperament]]s, it is fairly quick and easy to find ''approximate'' solutions, using (for example) [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#General method|the general method which is discussed in D&D's guide to RTT]] and available in D&D's [[RTT library in Wolfram Language]]. This RTT library also includes four other methods which quickly and easily find ''exact'' solutions. These four methods are further different from the general method insofar as they are ''not'' general; each one works only for certain optimization problems. It is these four specialized exact-solution methods which are the subject of this article.

The other two of these four specialized methods—the zero-damage method, and the coinciding-damage method—are significantly more challenging to understand than the general method. Most students of RTT would not gain enough musical insight by familiarizing themselves with them to have justified the investment. This is why these two methods were not discussed in D&D's guide. However, if you feel compelled to understand the nuts and bolts of these methods anyway, then those sections of the article may well appeal to you.  

= Intro =

== A summary of the methods ==

The three biggest sections of this article are dedicated to three specialized tuning methods, one for each of the three special [[optimization power]]s: the [[pseudoinverse]] method is used for <math>p = 2</math> ([[miniRMS]] tuning schemes), the zero-damage method is used for <math>p = 1</math> ([[miniaverage]] tuning schemes), and the coinciding-damage method is used for <math>p = ∞</math> ([[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#Common_interpretations|minimax]] tuning schemes).  

== Exact vs. approximate solutions ==

Because <math>𝒈 = 𝒋G</math>, if <math>𝒈</math> is the primary target, not <math>G</math>, and a formula for <math>G</math> is known, then it is possible to substitute that into <math>𝒈 = 𝒋G</math> and thereby bypass explicitly solving for <math>G</math>. For example, this was essentially what was done in the [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Only held-intervals method|Only-held intervals method]] and [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Pseudoinverse_method_for_.5Bmath.5D.F0.9D.91.9D.3D2.5B.2Fmath.5D|Pseudoinverse method]] sections of [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation|D&D's guide: Tuning computation]]).  

| <math>2</math>

| Pseudoinverse

| Exact

| <math>G</math>

| <math>1</math>

| Zero-damage

| Exact

| <math>G</math>

| <math>∞</math>

| Coinciding-damage

| Exact

| <math>G</math>

| rowspan="2" | General

| Power

| rowspan="2" | Approximate

| rowspan="2" | <math>𝒈</math>

| power limit

| N/A

| Only held-intervals

| Exact

| <math>G</math>

== The generator embedding ==

== Algebraic setup ==

But wait&mdash;there are actually two more matrices we haven't recognized yet, on the just side of things. These are <math>G_{\text{j}}</math> and <math>M_{\text{j}}</math>. Unsurprisingly, these two are closely related to <math>G</math> and <math>M</math>, respectively. The subscript <math>\text{j}</math> stands for "just intonation", so this is intended to indicate that these are the generators and mapping for JI.  

We could replace either or both of these matrices with <math>I</math>, an ''[[Dave Keenan & Douglas Blumeyer's guide to RTT/Exploring temperaments#Nullspace|identity matrix]]''. On account of both <math>G_{\text{j}}</math> and <math>M_{\text{j}}</math> being identity matrices, we can eliminate them from our expression

We can even understand this in terms of a units analysis, where if <math>M_{\text{j}}</math> is taken to have units of '''g'''/'''p''', and  <math>G_{\text{j}}</math> is taken to have units of '''p'''/'''g''', then together we find their units to be ... nothing. And an identity matrix that isn't even understood to have units is definitely useless and to be eliminated. Though it's actually not as simple as the <math>\small \sf p</math>'s and <math>\small \sf g</math>'s canceling out; for more details, see [[Dave Keenan & Douglas Blumeyer's guide to RTT/Units analysis#The JI mapping times the JI generators embedding|here]].

== Deduplication ==

=== Between target-interval set and held-interval basis ===

=== Constant damage target-intervals ===

=== Within target-interval set ===

= Only held-intervals method =

== Unchanged-interval basis ==

In the D&D's guide article, this method was discussed in terms of ''held-intervals'', which are a trait of a tuning scheme, or in other words, a ''request'' that a person makes of a tuning optimization procedure which that procedure will then satisfy. But there's something interesting that happens once we request enough many intervals to be held unchanged&mdash;that is, when our held-interval count <math>h</math> reaches the size of our generator count, also known as [[rank]] <math>r</math>&mdash;then we have no room left for optimization. At this point, the tuning is entirely determined by the held-intervals. And thus we get another, perhaps better, way to look at the interval basis: no longer in terms of a request on a tuning scheme, but as a characteristic of a specific tuning itself. Under this conceptualization, what we have is not a helf-interval basis <math>\mathrm{H}</math>, but an [[unchanged-interval basis|''unchanged-interval'' basis]] <math>\mathrm{U}</math>.  

== Generator embedding ==

So, substituting <math>\mathrm{U}</math> in for <math>\mathrm{H}</math> in the formula we learned [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Only held-intervals method|from the D&D's guide article]]:

= Pseudoinverse method =

Similarly, we can take the pseudoinverse formula as presented in [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Pseudoinverse method]], substitute <math>𝒋G</math> for <math>𝒈</math>, and cancel out:

== Connection with the only held-intervals method ==

or in other words, the two held-intervals are {{vector|1 1 0}} and {{vector|0 1 4}}, which as ratios are <math>\frac61</math> and <math>\frac{1875}{1}</math>, respectively. Those may seem like some pretty strange intervals to be unchanged, for sure, but there is a way to think about it that makes it seem less strange. This tells us that whatever the error is on <math>\frac21</math>, it is the negation of the error on <math>\frac31</math>, because when those intervals are combined, we get a pure <math>\frac61</math>. This also tells us that whatever the error is on <math>\frac31</math>, that it in turn is the negation of the error on <math>\frac{625}{1} = \frac{5^4}{1}</math>.<ref group="note">Gene Ward Smith discovering this relationship: https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_16172#16172</ref> Also, remember that these intervals form a ''basis'' for the held-intervals; any interval that is a linear combination of them is also unchanged.

== Example ==

Let's refer back to the example given in [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Plugging back in]], picking up from this point:

The matrices with shapes <math>(3, 8)(8, 2)(2, 2)</math> led us to a <math>(3, \cancel{8})(\cancel{8}, \cancel{2})(\cancel{2}, 2) = (3, 2)</math>-shaped matrix, and that's just what we want in a <math>G</math> here. Specifically, we want a <math>(d, r)</math>-shaped matrix, one that will convert <math>(r, 1)</math>-shaped generator-count vectors&mdash;those that are results of mapping <math>(d, 1)</math>-shaped [[prime-count vector]]s by the temperament mapping matrix&mdash;back into <math>(d, 1)</math>-shaped prime-count vectors, but now representing the intervals as they sound under this tuning of this temperament.

== Pseudoinverse: The "how" ==

=== Like an inverse ===

As you might suppose&mdash;given a name like ''pseudo''inverse&mdash;this thing is ''like'' a normal matrix inverse, but not ''exactly''. True inverses are only defined for ''square'' matrices, so the pseudoinverse is essentially a way to make something similar available for non-square i.e. ''rectangular'' matrices. This is useful for RTT because the <math>M\mathrm{T}W</math> matrices we use it on are usually rectangular; they are always <math>(r, k)</math>-shaped matrices.

To finally get to understanding why, let's look to an expression discussed here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Basic_algebraic_setup|Basic algebraic setup]]:

=== Definition of inverse ===

=== Sometimes an inverse ===

# The third big difference&mdash;and this is probably the most important one, but we had to build up to it by looking at the other two big differences first&mdash;is that only one of those two possible results of multiplying a rectangular matrix by its pseudoinverse will actually even give an identity matrix! It will be the one of the two that gives the ''smaller'' square matrix.

Now, one fact we can take from this is that the first column of <math>M^{+}</math>&mdash;the non-JI vector {{vector|<math>\frac{17}{33}</math> <math>\frac{16}{33}</math> <math>\frac{-4}{33}</math>}}&mdash;shares at least one thing in common with other JI intervals such as <math>\frac21</math> {{vector|1 0 0}}, <math>\frac{81}{40}</math> {{vector|-3 4 -1}}, and <math>\frac{160}{81}</math> {{vector|5 -4 1}}: they all get mapped to {{rket|1 0}} by this meantone mapping matrix <math>M</math>. Note that this is no ''guarantee'' that {{vector|<math>\frac{17}{33}</math> <math>\frac{16}{33}</math> <math>\frac{-4}{33}</math>}} is close to these intervals (in theory, we can add or subtract an indefinite number of temperament commas from an interval without altering what it maps to!), but it at least ''suggests'' that it's reasonably close to them, i.e. that it's about an octave in size.  

=== Example of when the pseudoinverse does not behave like a true inverse ===

While this matrix <math>M^{+}M</math> clearly isn't an identity matrix, since it's not all zeros except for ones running along its main diagonal, and it doesn't really look anything like an identity matrix from a superficial perspective&mdash;just judging by the numbers we can read off its entries&mdash;it turns out that ''behavior-wise'' this matrix does actually work out to be as "close" to an identity matrix as we can get, at least in a certain sense. And since our goal with tuning this temperament was to approximate JI as closely as possible, from this certain mathematical perspective, this is the matrix that accomplishes that. But again, we'll get to why exactly this matrix is the one that accomplishes that in a little bit.

=== Demystifying the formula ===

== Pseudoinverse: The "why" ==

=== Derivative, for slope ===

=== A unique minimum ===

As discussed in the tuning fundamentals article (in the section [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#Power continuum|Non-unique tunings &ndash; power continuum]]), the graphs of mean damage and max damage&mdash;which are equivalent to the power means with powers <math>p = 1</math> and <math>p = ∞</math>, respectively&mdash;consist of straight line segments connected by sharp corners, while all other optimization powers between <math>1</math> and <math>∞</math> form smooth curves. This is important because it is only for graphs with smooth curves that we can use its derivative to find the minimum point; the sharp corners of the other type of graph create discontinuities at those points, which in this context means points which have no definitive slope. The simple mathematical methods we use to find slope for smooth graphs get all confused and crash or give wrong results if we try to use them on these types of graphs.  

=== A toy example using the derivative ===

Kicking off with the setup discussed [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Basic_algebraic_setup|here]], we have:

Ta-da! There's our generator size: 100.234 ¢.<ref group="note">The actual answer is more like 100.236. The result here is due to compounding rounding errors that I was too lazy to account for when preparing these materials. Sorry about that. ~Douglas</ref>

But if we really want to see the connection between the pseudoinverse and the finding the zero of the derivative&mdash;how they both find the point where the slope of the RMS graph is zero and therefore it is at its minimum&mdash;we're going to have to upgrade from an equal temperament (rank-1 temperament) to a rank-2 temperament. In other words, we need to address tunings with ''more than one generator'', ones can't be represented by a simple scalar anymore, but instead need to be represented with a vector.

Alright! We're finally ready to surface <math>𝒈</math>. It's been hiding in <math>𝒕</math> all along; the tuning map is equal to the generator tuning map times the mapping, i.e. <math>𝒕 = 𝒈M</math>. So we can just substitute that in everywhere. Exactly what we'll do is <math>𝖙 = 𝒕\mathrm{T}W = (𝒈M)\mathrm{T}W = 𝒈(M\mathrm{T}W) = 𝒈𝔐</math>, that last step introducing a new Fraktur-style symbol.<ref group="note">Ideally we'd've consistently applied the Fraktur-styling effect to each of these letters, changing no other properties, i.e. ended up with an uppercase italic M and lowercase bold italic j and t, but unfortunately a consistent effect was not available using Unicode and the wiki's <math>\LaTeX</math> abilities, a consistent effect, anyway, that also satisfactorily captured the compound aspect of what these things represent.</ref>

# The middle term, <math>-2𝖏𝔐^\mathsf{T}𝒈^\mathsf{T}</math>, has a single factor of <math>𝒈</math>, so it will remain but with that factor gone. (Technically it's a factor of <math>𝒈^\mathsf{T}</math>, but for reasons that would probably require a deeper understanding of the subtleties of matrix calculus than the present author commands, it works out this way anyway. Perhaps we should have differentiated instead with respect to <math>𝒈^\mathsf{T}</math>, rather than <math>𝒈</math>?)<ref group="note">Perhaps re-running this process in the recognition of the fact that these matrices are shorthand for an underlying system of equations, and the derivative of <math>𝒈</math> is, in fact, its gradient, or in other words, the vector of partial derivatives with respect to each of its entries (as discussed in more detail in the later section, [[#Multiple derivatives]]), we could nail this down.</ref>

== With held-intervals ==

The pseudoinverse method can be adapted to handle tuning schemes which have held-intervals. The basic idea here is that we can no longer simply grab the tuning found as the point at the bottom of the tuning damage graph bowl hovering above the floor, because that tuning probably doesn't also happen to be one that leaves the requested interval unchanged. We can imagine an additional feature in our tuning damage space: the line across this bowl which connects every point where the generator tunings work out such that our interval is indeed unchanged. Again, this line probably doesn't straight through the bottommost point of our RMS-damage graph. But that's okay. That just means we ''could'' still decrease the overall damage further if we didn't hold the interval unchanged. But assuming we're serious about holding this interval unchanged, we've simply modified the problem a bit. Now we're looking for the point along this new held-interval line which is closest to the floor. Simple enough to understand, in concept! The rest of this section is dedicated to explaining how, mathematically speaking, we're able to identify that point. It still involves matrix calculus&mdash;derivatives of vectors, and such&mdash;but now we also pull in some additional ideas. We hope you dig it.<ref group="note">If you don't dig it, please consider alternative attempts to explain these ideas here: [[User:Sintel/Generator_optimization#Constraints]], here: [[Constrained_tuning/Analytical_solution_to_constrained_Euclidean_tunings]], and here: [[Target tuning#Least squares tunings]]</ref>

=== Topographic view ===

=== Matching slopes ===

You may recall that in the simpler case&mdash;with no held-intervals&mdash;we identified the point at the bottom of the bowl using derivatives; this point is where the derivative (slope) is equal to zero. Well, what can we notice about the point we're seeking to identify? It's where the slopes of the RMS damage graph for the target-intervals and the error of the held-interval match!

But there's another special way of asking for the same thing, that isn't as obvious-looking, but consolidates it all down to a single equation, which&mdash;due to some mathemagic&mdash;eventually works out to give us a really nice solution. Here's what that looks like:

What we've done here is added a new variable <math>λ</math><ref group="note">This is a different lambda to the one conventionally used for eigenvalues, or as we call them, scaling factors. This lambda refers to Lagrange, the mathematician who developed this technique.</ref>, a multiplier which scales the error in the interval we want to be unchanged. We can visualize its effect as saying: we don't care about the relative lengths of these two vectors; we only care about wherever they point in exactly the same direction. This trick works as long as we take the derivative with respect to <math>λ</math> as well, which you'll note we're doing now too.<ref group="note">To help develop your intuition for these sorts of problems, we recommend Grant Sanderson's series of videos for Khan Academy's YouTube channel, about Lagrange multipliers for constrained optimizations: https://www.youtube.com/playlist?list=PLCg2-CTYVrQvNGLbd-FN70UxWZSeKP4wV</ref> We don't expect this to be clear straight away; the reason this works will probably only become clear in later steps of working through the problem.

As a final change, we're going to recognize the fact that for higher-dimensional temperaments, we might sometimes have multiple held-intervals. Which is to say that our new variable might actually itself be a vector! So we'll use a bold <math>\textbf{λ}</math> here to capture that idea.<ref group="note">See https://en.m.wikipedia.org/wiki/Lagrange_multiplier#Multiple_constraints for more information.</ref> (The example we will demonstrate with periodically will still only have one held-interval, though, but that's fine if this is a one-entry vector, whose only entry is <math>λ_1</math>.) Note that we need to locate <math>\textbf{λ}</math> on the right side of each term now, so that its <math>h</math> height matches up with the <math>h</math> width of <math>\mathrm{H}</math>.

=== Multiple derivatives ===

=== Break down matrices ===

=== Build matrices back up ===

The replacements for <math>\mathrm{B}</math> and <math>\mathrm{D}</math> may seem obvious enough, but you may initially balk at the replacement of <math>\mathrm{A}</math> here, but there's a reason that works. It's due to the fact that the thing <math>\mathrm{A}</math> represents is the product of a thing and its own transpose, which means entries mirrored across the main diagonal are equal to each other. So if <math>\mathrm{a}_{12} = \mathrm{a}_{21}</math>, then <math>\frac12(\mathrm{a}_{12} + \mathrm{a}_{21}) = \mathrm{a}_{12} = \mathrm{a}_{21}</math>. Feel free to check this yourself, or compare with our work-through in the footnote here.<ref group="note">

=== Hardcoded example ===

As for <math>\mathrm{T}W</math>, that's easy, because <math>W</math>&mdash;being a unity-weight matrix&mdash;is an identity matrix, so it's equal simply to <math>\mathrm{T}</math>. But regarding <math>M\mathrm{T}W = M\mathrm{T}</math>, that would be helpful to compute in advance:

And that's all there is to it.<ref group="note">Writes the present author, Douglas Blumeyer, who is relieved to have completely demystified this process for himself, after being daunted by it for over a year, then struggling for a solid week to assemble it from the hints left by the better-educated tuning theorists who came before me.</ref>

== For all-interval tuning schemes ==

So far we've looked at how to use the linear algebra operation called the pseudoinverse to compute miniRMS tunings. We can use a variation of that approach to solve [[Euclideanized]] [[all-interval tuning scheme]]s. So where miniRMS tuning schemes are those with the optimization power <math>p</math> is equal to <math>2</math>, all-interval minimax-ES tuning schemes are those with the dual norm power <math>\text{dual}(q)</math> equal to <math>2</math>.

=== Example ===

== With alternative complexities ==

The following examples all pick up from a shared setup here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Alternative complexities#Computing all-interval tuning schemes with alternative complexities]].

=== Minimax-E-S ===

This example specifically picks up from the setup laid out here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Alternative complexities#Log-product2]]. Plugging <math>L^{-1}</math> into our pseudoinverse method for <math>S_{\text{p}}</math> we find:

<pre>

Out: {1199.562 163.891] </pre>

This example specifically picks up from the setup laid out here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Alternative complexities#Sum-of-prime-factors-with-repetition2]]. Plugging <math>\text{diag}(𝒑)^{-1}</math> into our pseudoinverse method for <math>S_{\text{p}}</math> we find:

<pre>

Out: {1199.567 164.102] </pre>

This example specifically picks up from the setup laid out here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Alternative complexities#Count-of-prime-factors-with-repetition2]]. Plugging <math>I</math> into our pseudoinverse method for <math>S_{\text{p}}</math> we find:

<pre>

Out: {1198.595 162.737] </pre>

This example specifically picks up from the setup laid out here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Alternative complexities#Log-integer-limit-squared2]].  

<pre>

Out: {1199.544 163.888] </pre>

This example specifically picks up from the setup laid out here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Alternative complexities#Log-odd-limit-squared2]]. We use the pseudoinverse method, with our same <math>MS_{\text{p}}</math> and <math>S_{\text{p}}</math> equivalents as from the minimax-E-lils-S examples:

<pre>

Out: {1200 164.062] </pre>

Note that miniaverage tunings have not been advocated by tuning theorists thus far. We've included this section largely in order to complete the set of methods with exact solutions, one for each of the key optimization powers <math>1</math>, <math>2</math>, and <math>∞</math>.<ref group="note">Another reason we wrote the method for this optimization power up is because it was low-hanging fruit, on account of the fact that it was already described on the wiki in the [[Target tunings]] page, where it is presented as a method for finding "minimax" tunings, not ''miniaverage'' tunings. This is somewhat misleading, because while this method works for any miniaverage tuning scheme, it only works for some minimax tuning schemes under very specific conditions (which that page does meet, and so it's not outright ''wrong''). The conditions are: unity-weight damage (check), and all members of the target-interval set expressible as products of other members (check, due to their choice of target-interval set, closely related to a tonality diamond, plus octaves are constrained to be unchanged). The reason why these are the two necessary conditions for this miniaverage method working for a minimax tuning scheme is because when you are solving for the minimax, you actually want the tunings where the target-intervals' damages ''equal each other'', not where they are ''zero'', and these zero-damage tunings will only match the tunings where other intervals' damages equal each other in the case where two intervals' damages being equal implies that another target's damage is zero, because that other target is the product of those first two; and the unity-weight damage requirement is to ensure that the slopes of each target's [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#3D tuning damage graphs|hyper-V]] are all the same, because otherwise the points where two damages are equal like this will no longer line up directly over the point where the third target's damage is zero. For more information on this problem, please see the discussion page for the problematic wiki page, where we are currently requesting the page be updated accordingly.</ref> So, you may prefer to skip ahead to the next section if you're feeling more practically minded. However, the method for <math>p = ∞</math> is related but more complicated, and its explanation builds upon this method's explanation, so it may still be worth it to work through this one first.

== The zero-damage point set ==

== Gather and process zero-damage points ==

=== Unchanged-interval bases ===

=== Canonicalize and filter deficient matrices ===

=== De-dupe ===

=== Convert to generators ===

Now we just need to convert each of these unchanged-interval bases <math>\mathrm{U}_{(i,j)}</math> to a corresponding generator embedding <math>G</math>. To do this, we use the formula <math>G = \mathrm{U}(M\mathrm{U})^{-1}</math>, where <math>M</math> is the temperament mapping (the derivation of this formula, and examples of working through this calculation, are both described later in this article here: [[#Only unchanged-intervals method]]).<ref group="note">Note that this technique for converting zero-damage points to generator tunings is much simpler than the technique described on the [[Target tunings]] page. The Target tunings page uses eigendecomposition, which unnecessarily requires you to find the commas for the temperament, compute a full [[projection matrix]] <math>P</math>, and then when you need to spit a generator tuning map <math>𝒈</math> out at the end, requires the computation of a [[generator detempering]] to do so (moreover, it doesn't explain or even mention eigendecomposition; it assumes the reader knows how and when to do them, cutting off at the point of listing the eigenvectors&mdash;a big thanks to Sintel for unpacking the thought process in that article for us). The technique described here skips the commas, computing the generator embedding <math>G</math> directly rather than via <math>P = GM</math>, and then when you need to spit a generator tuning map out at the end, it's just <math>𝒈 = 𝒋G</math>, which is much simpler than the generator detempering computation.

So in the Target tunings approach, <math>P</math> is the projection matrix, <math>\mathrm{V}</math> is a matrix consisting of a list of unrotated vectors&mdash;both ones with scaling factor 1 (unchanged-intervals) and those with scaling factor 0 (commas)&mdash;and <math>\textit{Λ}</math> is a diagonal scaling factors matrix, where you can see along the main diagonal we have 1's paired with the unrotated vectors for unchanged-intervals and 0's paired with the unrotated vectors for commas.  

Note that every one of those unusual looking values above&mdash;whether it be <math>\frac21</math>, <math>\frac{81}{40}</math>, <math>\frac{8\sqrt[2]{5}}{9}</math>, or otherwise in the first column&mdash;or <math>\frac32</math>, <math>\frac{40}{27}</math>, <math>\sqrt[3]{\frac{10}{3}}</math>, or otherwise in the second column&mdash;is an approximation of <math>\frac21</math> or <math>\frac32</math>, respectively.

== Find damages at points ==

As discussed in [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#Absolute errors]], these vertical bars mean to take the absolute value of each entry of this vector, not to take its magnitude.

So here's that. Since we've gone with [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#Weight_slope|simplicity-weight damage]] here, we'll be using <math>S</math> to represent our simplicity-weight matrix rather than the generic <math>W</math> for weight matrix:

== Choose the winner ==

Often people will prefer to have the tuning in terms of the cents sizes of the generators, which is our generator tuning map <math>𝒈</math><ref group="note">Technically this gives us the ''tunings'' of the generators, in ¢/g.</ref>, but again we can find that as easily as <math>𝒋G</math>:

== Tie-breaking ==

In this case, we fall back to our general method, which is equipped to find the true optimum somewhere in between these two extreme ends of goodness, albeit as an approximate solution.<ref group="note">The article for the minimax tuning scheme, [[Target tunings]], suggests that you fall back to the miniRMS method to tie-break between these, but that sort of misses the point of the problem. The two tied points are on extreme opposite ends of the slice of good solutions, and the optimum solution lies somewhere in between them. We don't want the tie-break to choose one or the other extreme; we want to find a better solution somewhere in between them.</ref> This method is discussed here: [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Tie_breaking:_power_limit_method|power limit method]]. Or, if you'd like a refresher on how to think about non-unique tunings, please see [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#Non-unique tunings]].

We note that there may be a way to find an exact solution to a nested miniaverage, in a similar fashion to the nested minimax discussed in the coinciding-damage method section below, but it raises some conceptual issues about what a nested miniaverage even means.<ref group="note">There does not seem to be any consensus about how to identify a true optimum in the case of multiple solutions when <math>p=1</math>. See https://en.wikipedia.org/wiki/Least_absolute_deviations#Properties, https://www.researchgate.net/publication/223752233_Dealing_with_the_multiplicity_of_solutions_of_the_l1_and_l_regression_models, and https://stats.stackexchange.com/questions/275931/is-it-possible-to-force-least-absolute-deviations-lad-regression-to-return-the.</ref> We have done some pondering of this problem but it remains open; we didn't prioritize solving it, on account of the fact that nobody uses miniaverage tunings anyway.

The zero-damage method is easily modified to handle held-intervals along with target-intervals.<ref group="note">In fact, the Target tunings page of the wiki uses this more complicated approach in order to realize pure octaves, and so the authors of this page had to reverse engineer from it how to make it work ''without'' any held-intervals.</ref> In short, rather than assembling our set of unchanged-interval bases <math>\mathrm{U}_1</math> through <math>\mathrm{U}_n</math> (where <math>n = {{k}\choose{r}}</math>) corresponding to the zero-damage points by finding every combination of <math>r</math> different ones of our <math>k</math> target-intervals (one for each generator to be responsible for tuning exactly), instead we must first reserve <math>h</math> (''held''-unchanged-interval count) columns of each <math>\mathrm{U}_n</math> for the held-intervals, leaving only the remaining <math>r - h</math> columns to be assembled from the target-intervals as normal. So, we'll only have <math>{{k}\choose{r - h}}</math> candidate tunings / zero-damage points / unchanged-interval bases in this case.

(Note that <math>\mathrm{U}_{(1)}</math> here pairs <math>\frac21</math> with <math>\frac21</math>. That's because the octave happens to appear both in our held-interval basis <math>\mathrm{H}</math> ''and'' our target-interval list <math>\mathrm{T}</math>. We could have chosen to remove <math>\frac21</math> from <math>\mathrm{T}</math> upon adding it to <math>\mathrm{H}</math>, because once you're insisting a particular interval takes no damage there's no sense also including it in a list of intervals to minimize damage to. But we chose to leave <math>\mathrm{T}</math> alone to make our points above more clearly, i.e. with <math>k</math> remaining equal to <math>8</math>.)<ref group="note">Held-intervals should generally be removed if they also appear in the target-interval list <math>\mathrm{T}</math>. If these intervals are not removed, the correct tuning can still be computed; however, during optimization, effort will have been wasted on minimizing damage to these intervals, because their damage would have been held to 0 by other means anyway. In general, it should be more computationally efficient to remove these intervals from <math>\mathrm{T}</math> in advance, rather than submit them to the optimization procedures as-is. Duplication of intervals between these two sets will most likely occur when using a target-interval set scheme (such as a TILT or OLD) that automatically chooses the target-interval set.</ref>

For a rank-3 temperament, with 2 held-intervals, we'd again have 8 choose 1 = 8 tunings to check. With 1 held-interval, we'd have 8 choose 2 = 28 tunings to check.

=== Maxization ===

And to be clear, the <math>\textbf{i}</math>-norm is maxized here&mdash;has norm power <math>∞</math>&mdash;because the norm power on the retuning magnitude is <math>1</math>, and these norm powers must be duals.

=== Example ===

== With alternative complexities ==

= Coinciding-damage method =

== History ==

This method was originally developed by [[Keenan Pepper]] in 2012,<ref group="note">See https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_20405.html and https://yahootuninggroupsultimatebackup.github.io/tuning-math/topicId_21022.html</ref>, in a 142-line long [https://www.python.org/ Python] file called [https://github.com/keenanpepper/tiptop/blob/main/tiptop.py tiptop.py].  

Specifically, Keenan's method was developed for its tie-breaking abilities, at a time where the [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Tie_breaking:_power_limit_method|power-limit method]]'s ability to tie-break was unknown or not popular.  

Keenan's method was modified in 2021-2023 by [[Douglas Blumeyer]] in order to accommodate ordinary tunings&mdash;those with target-interval sets where the optimization power is <math>∞</math> and the norm power may be anything or possibly absent&mdash;and this is what will be discussed immediately below. Douglas's modifications also included support for held-intervals, and for alternative complexities, both of which are discussed in sections below, and also an improvement that both simplifies it conceptually and allows it to identify optimum tunings more quickly. [[Dave Keenan]] further modified Keenan's method during this time so that it can find exact solutions in the form of generator embeddings, which is also reflected in all the explanations below.  

== Coinciding-damage points ==

=== Points for finding damage minimaxes ===

Damage ''minimaxes'' are always found at points in tuning damage space where individual target-interval [[Dave Keenan & Douglas Blumeyer's guide to RTT/tuning_fundamentals#3D_tuning_damage_graphs|hyper-V]] damage graphs intersect, or cross, to form a point.  

And you might wonder: but why don't we just scan along the max graph and pick the <math>-+</math> point? Well, the problem is: we don't have a function for the max damage graph, other than defining it in terms of all the other target-interval damage graphs. So it turns out that checking all of these crossing points is a more efficient way for a computer to find this point, than doing it the way that might seem more obvious to a human observer.<pre>*</pre> Once we start learning about tie-breaking, we'll see that this is not always exactly the case. But it's fine for now.

=== Zero-damage coincidings ===

We may observe that the latter kind of point, the coinciding-''zero''-damage points&mdash;those where damage graphs intersect on the zero-damage floor&mdash;may seem to be less likely candidates for minimax tunings, considering that by the nature of being on the zero-damage floor, where no target-interval's damage could possibly be any lower, there's almost certainly some target-interval with higher damage (whose damage is still increasing in one direction or another). And this can clearly be seen on the diagram we included a bit earlier. However, as we'll find in the later section about tie-breaking, and hinted at in an asterisked comment earlier, these points are often important for tie-breaking between tunings which are otherwise tied with each other when it comes to those higher-up damages (i.e. at least one direction, a higher-up damage is neither going up nor going down, such as along an intersection of two damage graphs whose creases are parallel).

In general, the number of target-intervals whose graphs will intersect at a point&mdash;i.e., their damages will coincide&mdash;is equal to the dimension of the tuning damage space. So in 3D tuning damage, we need three hyper-V's to intersect. Think of it this way: a 3D point has a coordinate in the format <math>(x,y,z)</math>, and we need one plane, one target-interval, for each element of that coordinate. But for intersections among creases along the floor, we only need one ''less'' than the dimensionality of the tuning damage space to specify a point; that's because we already know that one of the coordinates is 0.

=== Points vs. lines; tuning space vs. tuning damage space ===

In tuning damage space, a tuning corresponds with a vertical line, perpendicular to the zero damage floor. Any point on this line identifies this same tuning. If we took an aerial view on tuning damage space, looking straight down on it&mdash;as we do in the [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#Topographic_tuning_damage_graphs|topographic, contour style graphs]] these lines ''would'' look like points. Basically in this view, the only dimensions are for the generators, and the extra dimension for damage is collapsed. In other words, we go from tuning damage space back to simply tuning space.  

== How to gather coinciding-damage points ==

=== For a general coinciding-damage point ===

=== For a zero-damage point ===

== How to build constraint matrices ==

=== For a general coinciding-damage point ===

=== For a zero-damage point ===

== A simple example ==

=== A system of approximations ===

Another way to view a matrix expression like this<ref group="note">were everything transposed, anyway; a superficial issue</ref> is as a system of multiple expressions&mdash;in this case, a system of approximations:

=== Apply constraint to system ===

=== The meaning of the ReDPOTIC product ===

But our original intention here was to find the tuning where <math>\frac21</math> and <math>\frac31</math> have coinciding damage. Well, it turns out this is an equivalent situation. If&mdash;according to this temperament's mapping {{map|12 19 28}}&mdash;it takes 12 steps to reach <math>\frac21</math> and also it takes 19 steps to reach <math>\frac31</math>, and that it therefore takes 31 steps to reach a <math>\frac61</math>, and it is also the case that <math>\frac61</math> is pure, then that implies that whatever error there is on <math>\frac21</math> must be the exact opposite of whatever damage there is on <math>\frac31</math>, since their errors apparently cancel out. So if their errors are exact opposites&mdash;negations&mdash;then their damages are the same. So we achieve coinciding target-interval damages via an unchanged-interval that they all relate to. Cue the success fanfare.

=== Comparing the zero-damage method's unchanged-interval bases with the coinciding-damage method's constraint matrices ===

=== Get damage lists ===

=== Identify minimax ===

== A bigger example ==

=== Prepare constraint matrix ===

Another thing to note is that we set up the constraint matrix so that there's one target-interval that has a non-zero entry in each row, and that this is also the ''first'' target-interval column with a non-zero entry, i.e. the one that's been anchored to the positive direction. As we can see, in our case, that target-interval is <math>\frac75</math>. Setting up our constraint matrix in this way is how we establish&mdash;using the transitive property of equality&mdash;that all four of these target-intervals with non-zero entries somewhere their column will have coinciding (equal) damages. Because if A's damage equals B's, and B's damage equals C's, then we also know that A's damage equals C's. And same for D. So we end up with A's damage = B's damage = C's damage = D's damage. All four have coinciding damage.

=== Prepare tempered and just sides of to-be equality ===

=== Apply constraint ===

=== Solve for generator embedding ===

=== Convert generator embedding to generator map ===

And so that's the tuning (in cents) we find for this constraint matrix! (But remember, this is only one of many candidates for the minimax tuning here&mdash;it is not necessarily the actual minimax tuning. We picked this particular ReDPOTIC / constraint matrix / coinciding-damage point / candidate tuning example basically at random.)

=== Sanity-check ===

=== Relation to only-held intervals method and zero-damage method ===

== With held-intervals ==

=== Counts of target-intervals with held-intervals ===

=== Modified constraint matrices ===

We do this by changing our constraint matrices <math>K</math>; rather than building them to represent permutations of relative direction for combinations of <math>r + 1</math> target-intervals, instead we only combine <math>r + 1 - h</math> target-intervals for each of these constraint matrices, where <math>h</math> is the count of held-intervals. As a result of this, each <math>K</math> has <math>h</math> fewer columns than before&mdash;or at least it would, if we didn't replace these columns with <math>h</math> new columns, one for each of our <math>h</math> held-intervals. Remember, each of these constraint matrices gets multiplied together with other matrices that represent information about our temperament and tuning scheme&mdash;our targeted intervals, and their weights (if any)&mdash;in order to take a system of approximations (represented by matrices) and crunch it down to a smaller system of equalities (still represented by matrices) that can be automatically solved (using a matrix inverse). So, instead of these constraint matrices doing only a single job&mdash;enforcing that <math>r + 1</math> target-intervals receive coinciding damage, each constraint matrix now handles two jobs at once&mdash;enforcing that only <math>r + 1 - h</math> target-intervals receive coinciding damage, and that <math>h</math> held-intervals receive zero damage.  

# We accordingly extend the weight matrix <math>W</math> diagonally so that matrix shapes work out for multiplication purposes, or said another way, so that each held-interval appended to <math>\mathrm{T}</math> gets matched up with a dummy weight.<ref group="note">This weight is irrelevant, since these aren't really target-intervals, they're held-intervals, and so the damage to them must be 0; we can choose any value for this weight other than 0 and the effect will be the same, so we may as well choose 1).</ref>

Oh, right&mdash;we didn't ''have'' a row for this held-interval yet. All the rows we had before were for our ''target''-intervals. No big deal, though. We just added an extra row for this, our ''held''-interval, and we can fill out the new entries it creates in the other columns with zeros.

=== Prepare tempered and just sides of to-be equality ===

= \\[50pt] \small

Again, same as before, but with one more column on the right now.

=== Solve for generator embedding ===

=== Convert generator embedding to generator tuning map ===

=== System of equations style ===

The third equation&mdash;which in the earlier "bigger example" was used to enforce that a fourth target-interval received coinciding damage to the other three target-intervals tapped by the constraint matrix&mdash;here has been replaced with an equation that enforces that {{rket|0 1 2}}, the generator-count vector that <math>\frac53</math> maps to in this temperament, is equal to the just tuning of that same interval. And so, when we solve this system of equations, we now get a completely different set of generator tunings.

=== Sanity-check ===

== Tie-breaking ==

We've noted that the zero-damage method for miniaverage tuning schemes cannot directly handle non-unique methods itself. When it finds a non-unique miniaverage (more than one set of generator tunings cause the same minimum sum damage), the next step is to start over with a different method, specifically, the [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Tie_breaking:_power_limit_method|power-limit method]], which can only provide an approximate solution.

[[File:Basic advanced tiebreaking.png|none|thumbnail|600x600px]]

Let's just dive into an example.

The example given in the diagrams back in article 3 [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning fundamentals#How_to_choose_the_true_optimum|here]] and article 6 [[Dave Keenan & Douglas Blumeyer's guide to RTT/Tuning computation#Tie_breaking:_power_limit_method|here]] were a bit silly. The easiest way to break the tie in this case would be to remove the offending target-interval from the set, since with constant damage, it will not aid in preferring one tuning to another. More natural examples of tied tunings&mdash;that cannot be resolved so easily&mdash;require 3D tuning damage space. So that's what we'll be looking at here.

=== Basic tie-breaking example: Comparing tunings for minimax ===

! Constraint matrix

! colspan="2" | Candidate generator tuning map

! Target-interval damage list

! <math>K</math>

! <math>𝒈_i</math>

! {{rbra|<math>g_1</math> <math>g_2</math>}}

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ +1 & 0 \\ 0 & -1 \\ 0 & 0 \\ \end{array} \right]</math>

| <math>𝒈_2</math>

| {{rbra|238.612 2779.374}}

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ -1 & 0 \\ 0 & +1  \\ 0 & 0 \\ \end{array} \right]</math>

| <math>𝒈_3</math>

| {{rbra|233.985 2816.390}}

| [30.075 30.075 30.075 30.075]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ -1 & 0 \\ 0 & -1 \\ 0 & 0 \\ \end{array} \right]</math>

| <math>𝒈_4</math>

| {{rbra|233.985 2756.240}}

| [30.075 30.075 30.075 30.075]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ +1 & 0 \\ 0 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_2</math>

| {{rbra|238.612 2779.374}}

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ +1 & 0 \\ 0 & 0 \\ 0 & -1 \\ \end{array} \right]</math>

| <math>𝒈_1</math>

| {{rbra|238.612 2793.254}}

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ -1 & 0 \\ 0 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_5</math>

| {{rbra|233.985 2696.090}}

| [30.075 30.075 90.225 30.075]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ -1 & 0 \\ 0 & 0 \\ 0 & -1 \\ \end{array} \right]</math>

| <math>𝒈_4</math>

| {{rbra|233.985 2756.240}}

| [30.075 30.075 30.075 30.075]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ 0 & 0 \\ +1 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_6</math>

| {{rbra|239.215 2790.240}}

| [3.923 11.769 3.923 3.923]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ 0 & 0 \\ +1 & 0 \\ 0 & -1 \\ \end{array} \right]</math>

| <math>𝒈_1</math>

| {{rbra|238.612 2793.254}}

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ 0 & 0 \\ -1 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_2</math>

| {{rbra|238.612 2779.374}}

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} +1 & +1 \\ 0 & 0 \\ -1 & 0 \\ 0 & -1 \\ \end{array} \right]</math>

| <math>𝒈_4</math>

| {{rbra|233.985 2756.240}}

| [30.075 30.075 30.075 30.075]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ +1 & +1 \\ +1 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_7</math>

| {{rbra|238.133 2783.200}}

| [9.334 3.111 3.111 3.111]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ +1 & +1 \\ +1 & 0 \\ 0 & -1 \\ \end{array} \right]</math>

| <math>𝒈_2</math>

| {{rbra|238.612 2779.374}}  

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ +1 & +1 \\ -1 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_1</math>

| {{rbra|238.612 2793.254}}  

| [6.940 6.940 6.940 6.940]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ +1 & +1 \\ -1 & 0 \\ 0 & -1 \\ \end{array} \right]</math>

| <math>𝒈_4</math>

| {{rbra|233.985 2756.240}}

| [30.075 30.075 30.075 30.075]

| <math>\left[ \begin{array} {rrr} +1 & 0 \\ 0 & +1 \\ 0 & 0 \\ 0 & 0 \\ \end{array} \right]</math>

| n/a

| n/a

| n/a

| <math>\left[ \begin{array} {rrr} +1 & 0 \\ 0 & 0 \\ 0 & +1 \\ 0 & 0 \\ \end{array} \right]</math>

| <math>𝒈_8</math>

| {{rbra|240.000 2786.314}}

| [0.000 18.045 0.000 18.045]

| <math>\left[ \begin{array} {rrr} +1 & 0 \\ 0 & 0 \\ 0 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_9</math>

| {{rbra|240.000 2804.360}}

| [0.000 18.045 18.045 0.000]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ +1 & 0 \\ 0 & +1 \\ 0 & 0 \\ \end{array} \right]</math>

| <math>𝒈_{10}</math>

| {{rbra|237.744 2786.314}}

| [11.278 0.000 0.000 11.278]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ +1 & 0 \\ 0 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_{11}</math>

| {{rbra|237.744 2775.040}}

| [11.278 0.000 11.278 0.000]

| <math>\left[ \begin{array} {rrr} 0 & 0 \\ 0 & 0 \\ +1 & 0 \\ 0 & +1 \\ \end{array} \right]</math>

| <math>𝒈_{12}</math>

| {{rbra|238.612 2786.314}}

| [6.940 6.940 0.000 0.000]

| <math>𝒈_1</math>

| {{rbra|238.612 2793.254}}

| [6.940 6.940 6.940 6.940]

| 6.940

| <math>𝒈_2</math>

| {{rbra|238.612 2779.374}}

| [6.940 6.940 6.940 6.940]

| 6.940

| <math>𝒈_3</math>

| {{rbra|233.985 2816.390}}

| [30.075 30.075 30.075 30.075]

| 30.075

| <math>𝒈_4</math>

| {{rbra|233.985 2756.240}}

| [30.075 30.075 30.075 30.075]

| 30.075

| <math>𝒈_5</math>

| {{rbra|233.985 2696.090}}

| [30.075 30.075 90.225 30.075]

| 90.225

| <math>𝒈_6</math>

| {{rbra|239.215 2790.240}}

| [3.923 11.769 3.923 3.923]

| 11.769

| <math>𝒈_7</math>

| {{rbra|238.133 2783.200}}

| [9.334 3.111 3.111 3.111]

| 9.334

| <math>𝒈_8</math>

| {{rbra|240.000 2786.314}}

| [0.000 18.045 0.000 18.045]

| 18.045

| <math>𝒈_9</math>

| {{rbra|240.000 2804.360}}