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.