1 of 42

Faster Walsh-Hadamard Transform from Matrix Non-Rigidity

Josh Alman (Columbia)

Based on joint work with Yunfeng Guan (Toronto), Baitian Li (Columbia), Jingxun Liang (CMU), Ashwin Padaki (Penn), Kevin Rao (Open AI)

2 of 42

Walsh-Hadamard Transform (WHT)

  •  

3 of 42

Walsh-Hadamard Transform (WHT)

  •  

 

4 of 42

Fast Walsh-Hadamard Transform

  •  

 

5 of 42

Fast WHT as a Sparse Matrix Factorization

  •  

6 of 42

  •  

Fast WHT as a Sparse Matrix Factorization

 

7 of 42

Results

  •  

 

 

8 of 42

Results

  •  

Can also be used to speed up FFT!

9 of 42

Short Interlude: FFT Algorithms�

FFT Algorithm

​

Cooley-Tukey �[1965]

5

Split Radix �[Yavne 1968]

4

“Modified” Split Radix �[Van Buskirk 2007]

3.777

“Further Modified” Split Radix �[Sergeev 2017]

3.769

New WHT-based Algorithm �[A-Rao 2023]

3.75

 

 

10 of 42

Results

  •  

11 of 42

Results

  •  

12 of 42

Kronecker Product

  •  

13 of 42

Two Key Facts about Kronecker Product

  •  

14 of 42

Depth-2 Version of �Fast Walsh-Hadamard Transform (fWHT)

  •  

15 of 42

Improved Depth-2 Circuit Plan

  •  

16 of 42

Matrix Rigidity

  •  

 

 

 

This Talk:�Use Rigidity Upper Bounds for Kronecker Products to give linear circuit upper bounds

17 of 42

 

  •  

 

18 of 42

 

  •  

 

 

 

19 of 42

 

  •  

 

9

8

8

9

8

8

20 of 42

 

  •  

 

9

8

8

9

8

8

 

21 of 42

Rebalancing: Improving the Symmetrization �[A-Guan-Padaki `23], [A-Li `25]

 

 

Analysis gets messy; [A-Li `25] uses a connection with the “Asymptotic Spectrum” of Strassen [1987]

22 of 42

Results

  •  

23 of 42

High-Level Idea

  •  

24 of 42

Starting point: Rigidity upper bound

 

 

25 of 42

Starting point: Rigidity upper bound

  •  

 

26 of 42

Starting point: Rigidity upper bound

  •  

 

 

27 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

28 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

29 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

30 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

31 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

32 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

33 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

34 of 42

Starting point: Rigidity upper bound

  •  

 

 

 

 

35 of 42

 

36 of 42

 

37 of 42

Fast Walsh-Hadamard Transform

  •  

38 of 42

 

  •  

 

39 of 42

 

  •  

 

40 of 42

 

  •  

 

41 of 42

 

  •  

 

 

42 of 42

Barriers to Further Improvements

  •  

 

Thank you!