4 ms·

A somehow-much-less-popular way to come at representation theory is via generalized Fourier transforms. The irreducible representations are basically different

A somehow-much-less-popular way to come at representation theory is via generalized Fourier transforms. The irreducible representations are basically different "frequencies" which you can use to decompose functions on a group. And in fact, all of the major Fourier theorems carry over perfectly... There's even analogues of the fast Fourier transform, via chains of subgroups.

memexy 6y ago
Are there any good references for this approach (via generalized Fourier transforms)?
- kcoul 6y ago
  I wouldn’t call this 3blue1brown video a reference, but until I watched this (coming from an audio background), I didn’t quite grasp that a continuous stencil of any complex silhouette could be described in terms of a set of contributing vectors. Helped click that there is a perfect visual analogy to the deconstruction of complex audio to sine waves. https://youtu.be/r6sGWTCMz2k https://youtu.be/r6sGWTCMz2k
- pathsjs 6y ago
  Yes: Folland, A course in abstract harmonic analysis, CRC press
- bollu 6y ago
  There is a thesis by Kondor: "Group theoretical methods for machine learning" - https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf which provides links to the associated literature. The documentation of his library (SnOB) is great: http://www.gatsby.ucl.ac.uk/~risi/SnOB/SnOB/SnOB.pdf http://www.gatsby.ucl.ac.uk/~risi/SnOB/SnOB/SnOB.pdf introductory slides on representation theory in machine learning: http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/symmetric.pdf http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/symmetric.p... Full mini course: http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/mini08.html http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/mini08.html
  - memexy 6y ago
    Thanks. These all look very readable.
- sdenton4 6y ago
  Persi Diaconis' book is excellent. You come away with the proof that it takes seven shuffles to fully randomize a deck of cards... https://www.amazon.com/Group-Representations-Probability-Statistics-Lecture/dp/0940600145 https://www.amazon.com/Group-Representations-Probability-Sta...
Xcelerate 6y ago
Interesting you mention this. I wrote a Julia library a few years ago to generate both real and unitary irreducible representations for O3 and the symmetric group. It also implements the Fourier transform for the symmetric group and the fast Fourier transform for O3. I really miss that type of interesting work in grad school... unfortunately I don't have any projects that involve representation theory in industry anymore :(
- abdullahkhalids 6y ago
  Is the library publicly available? I would be interested in playing and learning from it.
cosmic_ape 6y ago
Well, it depends. Some people would say, justly I think, the way to come at Fourier transform is as a commutative representation theory.
openasocket 6y ago
Yeah, I've always found generalized Fourier transforms and harmonic analysis to be really interesting! For those interested in reading more, some of the foundational work is the notion of a Haar measure and the Pontryagin duality. Basically, for any locally compact abelian group you can define a Fourier transform, and this Fourier transform is unique up to multiplicative identity. If you use this definition on the group of real numbers under addition you get the continuous Fourier transform, and if you use it on the group of integers under addition you get the discrete Fourier transform! And you can define the Fourier transform for more exotic groups, like on elliptic curves. In fact, this is how Shor's algorithm is able to factor large numbers, solve the discrete log problem, and break elliptic curve cryptography all in one algorithm: the algorithm is essentially just taking the Fourier transform of said function and measuring. Thanks to harmonic analysis, you can define a Fourier transform for elliptic curves and just plug that into Shor's algorithm
- stainforth 6y ago
  Will harmonic analysis play into P!=NP then, if its usable in quantum math?
  - openasocket 6y ago
    I mean it could be, but not in the way you're talking about. There's a common misconception that quantum algorithms being able to factor integers and solve the discrete log problem in polynomial time has some implications for P vs NP. However, integer factoring and the discrete log problems are NOT NP complete problems, and there is no quantum algorithm published that can solve an NP complete problem in polynomial time. It's actually an open problem if quantum computers, in terms of computability classes, are any more powerful than classical computers (I think even assuming P!=NP, but I'm not a computing theory person haven't looked into more recent work on it).
biddlesby 6y ago
That sounds really interesting - thank you

memexy 6y ago

Are there any good references for this approach (via generalized Fourier transforms)?

kcoul 6y ago
I wouldn’t call this 3blue1brown video a reference, but until I watched this (coming from an audio background), I didn’t quite grasp that a continuous stencil of any complex silhouette could be described in terms of a set of contributing vectors. Helped click that there is a perfect visual analogy to the deconstruction of complex audio to sine waves. https://youtu.be/r6sGWTCMz2k https://youtu.be/r6sGWTCMz2k
pathsjs 6y ago
Yes: Folland, A course in abstract harmonic analysis, CRC press
bollu 6y ago
There is a thesis by Kondor: "Group theoretical methods for machine learning" - https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf https://people.cs.uchicago.edu/~risi/papers/KondorThesis.pdf which provides links to the associated literature. The documentation of his library (SnOB) is great: http://www.gatsby.ucl.ac.uk/~risi/SnOB/SnOB/SnOB.pdf http://www.gatsby.ucl.ac.uk/~risi/SnOB/SnOB/SnOB.pdf introductory slides on representation theory in machine learning: http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/symmetric.pdf http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/symmetric.p... Full mini course: http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/mini08.html http://www.gatsby.ucl.ac.uk/~risi/courses/mini08/mini08.html
- memexy 6y ago
  Thanks. These all look very readable.
sdenton4 6y ago
Persi Diaconis' book is excellent. You come away with the proof that it takes seven shuffles to fully randomize a deck of cards... https://www.amazon.com/Group-Representations-Probability-Statistics-Lecture/dp/0940600145 https://www.amazon.com/Group-Representations-Probability-Sta...

Xcelerate 6y ago

Interesting you mention this. I wrote a Julia library a few years ago to generate both real and unitary irreducible representations for O3 and the symmetric group. It also implements the Fourier transform for the symmetric group and the fast Fourier transform for O3. I really miss that type of interesting work in grad school... unfortunately I don't have any projects that involve representation theory in industry anymore :(

abdullahkhalids 6y ago
Is the library publicly available? I would be interested in playing and learning from it.

cosmic_ape 6y ago

Well, it depends. Some people would say, justly I think, the way to come at Fourier transform is as a commutative representation theory.

openasocket 6y ago

Yeah, I've always found generalized Fourier transforms and harmonic analysis to be really interesting! For those interested in reading more, some of the foundational work is the notion of a Haar measure and the Pontryagin duality. Basically, for any locally compact abelian group you can define a Fourier transform, and this Fourier transform is unique up to multiplicative identity. If you use this definition on the group of real numbers under addition you get the continuous Fourier transform, and if you use it on the group of integers under addition you get the discrete Fourier transform! And you can define the Fourier transform for more exotic groups, like on elliptic curves. In fact, this is how Shor's algorithm is able to factor large numbers, solve the discrete log problem, and break elliptic curve cryptography all in one algorithm: the algorithm is essentially just taking the Fourier transform of said function and measuring. Thanks to harmonic analysis, you can define a Fourier transform for elliptic curves and just plug that into Shor's algorithm

stainforth 6y ago
Will harmonic analysis play into P!=NP then, if its usable in quantum math?
- openasocket 6y ago
  I mean it could be, but not in the way you're talking about. There's a common misconception that quantum algorithms being able to factor integers and solve the discrete log problem in polynomial time has some implications for P vs NP. However, integer factoring and the discrete log problems are NOT NP complete problems, and there is no quantum algorithm published that can solve an NP complete problem in polynomial time. It's actually an open problem if quantum computers, in terms of computability classes, are any more powerful than classical computers (I think even assuming P!=NP, but I'm not a computing theory person haven't looked into more recent work on it).

biddlesby 6y ago

That sounds really interesting - thank you