[ot][spam][random][crazy][random][crazy]

[Undescribed Horrific Abuse, One Victim & Survivor of Many]

why does the fft work?

i don't quite remember, not sure if i ever knew.

it clearly forms a linear recombination of the parts via sin().

each value is converted to an angle and scaled by many indices and frequencies
then what?

why is each operation a scaling by these things?

both the time domain and the frequency domain are scaled by e^(n*k),
where n is the index, and k is the frequency

so basically, there's a matrix of sinusoids, that multiplies the data.
when multiplied twice a certain way, it undoes itself.

each item gets multiplied by every frequency, and distributed
then each of these is again multiplied by every frequency, and
distributing it again restores the signal

what path does a single value go through?
it gets rotated to an angle, then summed with a bunch of stuff
then it gets rotated again, and resummed

one view is that the rotations undo each other. this seems reasonably
likely. i wonder if i can do an example by hand.

i can use numpy primitives to make this more likely to succeed.

1629
this shows the boomerang through the matix of angles

>>> mat = np.exp(np.outer(np.array([0,1]), 2j * np.pi * np.fft.fftfreq(2)))
>>> mat
array([[ 1.+0.0000000e+00j,  1.-0.0000000e+00j],
       [ 1.+0.0000000e+00j, -1.-1.2246468e-16j]])
>>> v=np.random.random(2)
>>> v
array([0.16463984, 0.36013487])
>>> ((v * mat).sum(axis=1) * mat.T).sum(axis=1) /2
array([0.16463984-2.20519010e-17j, 0.36013487+3.40225191e-17j])

the matrix is not complex.
it's basically [[1,1],[1,-1]]
it contrains only the DC offset and the nyquist frequency
the DC offset turns into an average when 1 is multiplied by all components
the nyquist frequency multiplies -1 by the 2nd sample, and 1 by the
first, and sums them.

so how does that undo?
there's a sum, and a difference.
to restore the values, the difference is added to the sum (via an average)
and the difference is subtracted from the sum (via another difference)
basically, the values have been turned into differences.

maybe i'll add one more frequency

1633

>>> np.fft.fftfreq(3)
array([ 0.        ,  0.33333333, -0.33333333])
>>> mat = np.exp(np.outer(np.array([0,1,2]), 2j * np.pi * np.fft.fftfreq(3)))
>>> mat
array([[ 1. +0.j       ,  1. +0.j       ,  1. -0.j       ],
       [ 1. +0.j       , -0.5+0.8660254j, -0.5-0.8660254j],
       [ 1. +0.j       , -0.5-0.8660254j, -0.5+0.8660254j]])

the first row and column are again a sum
but the other parts are done differently.
it's notable that the matrix is symmetrical, and the lower 4 items are
complex numbers that all have the same absolute angle (i checked this
with np.angle())
draft saved at 436p

they all also have the same magnitude of 1.0

so one could recast the 2-valued example as an angle, rather than a
negative value. a negative value has an angle of 180 degrees. when
multiplying by it, the item was rotated 180 degrees. summing it with
the other item then produced a vector sum.

multiplying back, the vector sum or normal sum was rotated 180
degrees, and summed again. walking back along the same old vectors.

this new matrix has angles of 120 degrees (2.094 radians). in each
column or row, one of them is 120, and another is -120.

i'm wondering if each item is unrotated by its previous angle, when
the transposed matrix is multiplied, not sure.
1639

in the time domain 3-valued vector, the first component is at angle 0,
the second at angle -159deg, and the third at angle 159deg. i infer
the 159 degrees is the angle you get when you go at 120 degrees by one
amonut, then at -120 degrees by another amount.

so it has a sum, and a walk of three steps, one at 0degrees, one at
120, one at -120.
then it has a walk of 0, -120, and 120.

if I use the old mat.T code to invert this 3-valued fftish, i get the
second and third values swapped. i can get them in the right number if
i negate the ifft and the output.
i recall from the formula that it's actually the angles that are
negated. is that the complex conjugate?

yeah, using mat.conj() instead of mat.T gets the right answer

>>> v
array([0.0335134 , 0.56891046, 0.869467  ])
>>> ((v * mat).sum(axis=1) * mat.conj()).sum(axis=1).real / 3
array([0.0335134 , 0.56891046, 0.869467  ])

1645

so, .conj() will negate all the angles. a single value is moved 0
degrees, 120 degrees, and -120 degrees, into frequency space. then it
does this again, by the negative angle, to move back into the time
domain, i think?

i'm considering 0.56891046. it's multiplied by 1, and by 120 degrees,
and by -120 degrees.
each element of the output is composed of a different pairing of
motions with values.
the first output is all the values moving at 0 degrees, summed.
the second output is the first value moving at 0, the second value at
120, and the third at -120.

so the second value moves at 0 into the first output, at 120 into the
second, and at -120 into the third.

when this is undone, the angles are negative.
so, it moves at 0 again in the first output, at -120 into the second,
and at +120 into the third.

each of these motions is added onto the motions of the other values,
and it starts at zero.

k close here, hard.
1651

when the second value is reconstructed, it's taken from all the other
ones. .... and this happens for every row of the matrix, not just one.

so, considering just one value again, it goes into every output.
then, the second output, is taken from every value.
the first value goes by 1 into the second output
the second value goes by -120 into the second output
and the third value goes by 120 into the second output

or somesuch

so that output by 1 gets returned by 1, using the other side of the matrix
the output by 120 is returned by -120
and the output by -120 is returned by 120
each of these angles restores the complex value to its full value again
and then the result is divided by 3 to reduce the magnitude of having
them all there.

so why does or doesn't it work to add a wonky angle in there?

1656

>>> mat = np.exp(np.outer(np.array([0,1,2]), 2j * np.pi * funny_angles))
>>> mat
array([[ 1.000000e+00+0.0000000e+00j,  1.000000e+00+0.0000000e+00j,
         1.000000e+00-0.0000000e+00j],
       [ 1.000000e+00+0.0000000e+00j,  6.123234e-17+1.0000000e+00j,
         6.123234e-17-1.0000000e+00j],
       [ 1.000000e+00+0.0000000e+00j, -1.000000e+00+1.2246468e-16j,
        -1.000000e+00-1.2246468e-16j]])
>>> ((v * mat).sum(axis=1) * mat.conj()).sum(axis=1).real / 3
array([0.0335134 , 0.39044477, 0.94774717])
>>> v
array([0.0335134 , 0.56891046, 0.869467  ])

>>> np.angle(mat) * 180 / np.pi
array([[   0.,    0.,   -0.],
       [   0.,   90.,  -90.],
       [   0.,  180., -180.]])

these frequencies i made up, don't counter each other when turned into
angles. the matrix is no longer symmetric.

i tried a higher set of frequencies, and the default matrix stays
symmetrical. it really seems like i'd need that matrix to be
symmetrical, so each of the values can return to where it came from.
1659

i'm noticing that the angles are evenly spaced around a circle. that
sounds important.

in fact, it's hard to come up with a way to do this evenly spaced
around a circle, that is any different at all from what is already
there.

1701

in my failing code, i have things that are purportedly evenly spaced
around a circle, although i could have made a mistake, but there is a
differing number of them than the number of indices.