Here's the way I was thinking of doing the "polynomial
approximation" method I mentioned. Bear in mind that it all has to
do with vectors, not functions of a continuous variable, so that the word
"polynomials" might be slightly out of place, but I'll continue to use
it since I think it makes things easier to understand.
(Apologies for any typos---I keep finding new ones each time I go
thru this! Finally went thru it without finding one, so I'm sending it
off.)
Notation: write the tune, or tune part, as a sequence of notes of
equal length, (1/32 notes in abc2mtex) and reduce this to a vector V =
(v(1), v(2),...,v(n)), where v(j) is the number of semitones the jth note
is above middle C, or some other arbitrary reference note. (The reference
note will drop out of things later.) We also eliminate triplets by
dropping the middle note. Choose a weighting w(1),w(2),...,w(n), where
each w(i) > 0 and, for simplicity, w(1) + ... + w(n) = 1. (These can be
used to weight the main beats more than the others if wished. Or they
could be chosen to be all equal. In any case, we use the same weighting
for all our calculations.)
Let W be the n x n diagonal matrix which has w(1),...,w(n) on the
main diagonal.
Define the length of the vector V to be |V| = sqrt( V^tWV). (I'm
considering V as a column vector, and use V^t for the transpose of V.) The
inner product of two vectors U and V is defined to be U.V = U^tWV.
(1) Define vectors X_0=(1,...,1), X_1 = (1,2,...,n),
X_2 = (1,2^2,3^2,...,n^2) , .. up to X_k = (1,2^k,...,n^k).
(These correspond to the functions 1, x , x^2,...,x^k. This is the
_only_ place in the procedure where polynomials enter.)
(2) Use the Gram-Schmidt procedure to form an orthonormal set of
vectors U_0, U_1,..., U_k. (The procedure is this: Let U_0 = X_0. This
has length one since the sum of the w(i) is one. Proceed by induction: if
U_0,...,U_j have been defined, take X_{j+1} and subtract a linear
combination of U_0,...,U_j from it to make the result orthogonal to all of
U_0,...,U_j. Then divide by its length to get U_{j+1}. So U_0 = X_0, U_1
= (X_1 - (X_0.U_0)U_0)/(|X_1| - |X_1.U_0|), etc.)
We end up with vectors U_0, ... ,U_k such that |U_j| = 1, and, if i
is not equal to j, U_i.U_j = 0. [The U_j correspond to a set of
orthogonal polynomials relative to the weight function W. The other
important thing about them is that U_0 is just a scalar times X_0.]
(3) Drop U_0, and form the n x k matrix S whose first column is
U_1, second column U_2, ... and kth column is U_k.
(4) Let P be the n x n matrix P = SS^tW. (P is the projection
matrix onto the space spanned by X_1, ... ,X_k, i.e. it projects onto
the space of kth degree polynomials. However, since we have dropped U_0,
all of these will be orthogonal to the constant vector X_0, and thus
to U_0. Notice that this means that PU_0 = 0.)
(5) If our tune vector is V, the "best polynomial approximation"
of V is Y = PV. (More exactly, Y minimizes |V-Z| over all vectors Z in
the space spanned by X_0,...,X_n which also satisfy Z.X_0 = 0.)
(6) Define the "distance between tunes U and V" to be |PU - PV|.
Actually, we don't have to compute PU and PV separately, since once we
compute P^tP, |Pu - PV| is equal to the square root of
(U-V)^t(P^tWP)(U-V). So in fact, that is the only matrix multiplication
one has to perform to measure the distance.
Remarks: The bit about "subtracting off the mean" is done
implicitly; it comes from the fact we dropped the constant vector U_0.
The result is that if U and V are vectors coming from transpositions
of the same tune, the above distance between them is zero: i.e. PU = PV,
since U and V only differ by a multiple of U_0 = (1,1,...,1), while
PX_0 = 0.
Steps (1)--(4) are done once, in the very beginning, and the matrix
P^tWP is stored. Then the only thing necessary to measure the tune
distance is to form the tune vectors U and V above, subtract them, and
do the vector-times-matrix-times-vector multiplication in step (6).
The only place that polynomials enter the picture is at step one. If
one wanted to use Fourier series, one would just replace (1,2^j, ... ,n^j)
by, say (cos(2\pi j/n),..., cos(2k\pi j/n)) and the same with the sines.
Actually, a choice which would probably be at least as good as
either of the above would be to use the "tent functions". Suppose we
wanted to smooth out the notes in, say, groups of four. Assume n is
divisible by 4. Then we take u_j(i) = maximum(0,1-|i-j|/4), i=1,...,n. (If
you plot this, it looks like a little tent of height 1 and width 8
centered at j. It's ascii graph is _____/\_____ with the apex of the tent
at j. We'll toss in the two half-tents centered at the endpoints, u_1 and
u_n: \_____ and ____/ , along with the constant u_0 = (1,...,1). Then
take u_0, u_1, u_4, ,u_8,..., u_{n-4}, u_n, in place of X_0,...,X_k in
(1). [Note that any sum of these is a continuous piecewise-linear
function---just a polygonal path.] If we go thru the entire
orthogonalization procedure as above (remembering to drop u_0), our
procedure will give the best piecewise-linear approximation which is
orthogonal to u_0 (and u_0 = X_0 = (1,...,1)). (And it's probably not too
far from what you'd get if you just drew lines by eyeball on the staff
notation. By the way, if anyone here has done numerical solutions of PDE's
via the finite element method, they will have run into these functions.)
Cheers,
John Walsh
To subscribe/unsubscribe, point your browser to: http://www.tullochgorm.com/lists.html
