Anyone know the name of this signal processing discovery? I’ve been using FST | Hacker News Reader

Anyone know the name of this signal processing discovery? I’ve been using FST

twitter.com

5 pointssillysaurusx5 comments

As the title says, I made a signal processing discovery that seems to be useful in a wide variety of contexts, much to my surprise. People have started saying they prefer it over FFT.

A friend recommended that I try to hunt down the right name for this formula. There must be one; it’s like DCT and FFT had a kid. Someone else before me must have noticed it and given it a name. But I haven’t been able to find anything so far, and no one seems to know.

The observation is that (1+1j)*x can be FFT’d, and then the imaginary component can be thrown out entirely. If you do that, it preserves all the information from the original signal — it’s still frequency space, just like you’d expect FFT to be — but it also acts as its own inverse: the same process gives the original signal.

(You have to divide by the square root of the the signal length.)

If not, I suppose I’ll try Math stack exchange. Thanks!

Does it still work to FST -> filter -> FST if you use an odd filter (or any filter that shifts the phase)? You are encoding the real part in the even part of the spectrum and the imaginary part in the odd, so I think it will go wrong with any kind of phase shift in the filter (equivalently, that would introduce an imaginary part in the time domain signal, which your solution doesn't allow).

So you need to add the condition of a symmetrical filter transfer function. Otherwise, it does seem like a useful shortcut. I have never seen it presented before, but that may be because of the caveats it would have.

Ahh, you're right. Thank you for spotting that. I was excited that the Hamming window seemed to work for filtering, but I never tried e.g. taking the FST of an impulse filter, multiplying by the FST of an image, then running the result through FST again. There do seem to be some behavior differences for even vs odd numbered filters. And the "identity" filter is very strange:

  >>> fst2(fst2(tensor([[5**0.5,0,0,0,0]])) * fst2(tensor([[0,1,2,3,4]])))
  [[0,1,2,3,4]]

Interestingly, there do seem to be equivalents for shifting around the components, e.g.

  >>> fst2(fst2(tensor([[0, 0, 1, 0]])) * fst2(tensor([[0,1,0,0]])))
  [[0,0,0,0.5]]

But, you're right, the relation is much less clear than I originally thought. I'll spend more time on this to try to work out what the exact equivalencies are.

What you describe is the Hartley transform. In your case it is the fast discrete Hartley transform.

It is an involuntory form of the FFT.

It is a very interesting find indeed.

Edit: fyi it retains all properties of the FFT of course.

Ah-HA! Thank you so much! You're absolutely right: https://en.wikipedia.org/wiki/Discrete_Hartley_transform

the inverse transformation, which allows one to recover the xn from the Hk, is simply the DHT of Hk multiplied by 1/N. That is, the DHT is its own inverse (involutory), up to an overall scale factor.

The DHT can be used to compute the DFT, and vice versa. For real inputs xn, the DFT output Xk has a real part (Hk + HN−k)/2 and an imaginary part (HN−k − Hk)/2. Conversely, the DHT is equivalent to computing the DFT of xn multiplied by 1 + i, then taking the real part of the result.

It's so cool to discover something like this in the wild, then find out it has a formal name (DHT) and that people have already done the hard work of figuring out all the useful properties and relations.

I wish I had a way of contacting you (mostly to thank you in person, but also to ask what you use DHT for / how you learned about it), but unfortunately your HN profile is empty. Feel free to DM me on twitter sometime to say hello (https://twitter.com/theshawwn). Otherwise, cheers for brilliantly pointing out the exact answer I was hoping for!

Reply on news.ycombinator.com