spyrit.core.torch.fwht

spyrit.core.torch.fwht(x, order=True, dim=-1)

Fast Walsh-Hadamard transform of x

Args:

x (torch.tensor): *-by-n input signal, where n is a power of two.

order (bool or list, optional): True for sequency order (default), False for natural order. When order is a list, it defines the permutation indices to use. Default is True.

dim (int, optional): The dimension along which to apply the transform. Default is -1.

Returns:

torch.tensor: *-by-n transformed signal

Example:

Example 1: Fast sequency-ordered (i.e., Walsh) Hadamard transform

>>> import torch
>>> import spyrit.core.torch as st
>>> x = torch.tensor([1, 3, 0, -1, 7, 5, 1, -2])
>>> x = x[None,:]
>>> y = st.fwht(x)
>>> print(y)
tensor([[14, -8, -8, 18, -4, -2, -6,  4]])

Example 2: Fast Hadamard transform

>>> import torch
>>> import spyrit.core.torch as st
>>> x = torch.tensor([1, 3, 0, -1, 7, 5, 1, -2])
>>> x = x[None,:]
>>> y = st.fwht(x, False)
>>> print(y)
tensor([[14,  4, 18, -4, -8, -6, -8, -2]])

Example 3: Permuted fast Hadamard transform

>>> import numpy as np
>>> import torch
>>> import spyrit.core.torch as st
>>> x = torch.tensor([1, 3, 0, -1, 7, 5, 1, -2])
>>> ind = [1, 0, 3, 2, 7, 4, 5, 6]
>>> y = st.fwht(x, ind)
>>> print(y)
tensor([ 4, 14, -4, 18, -2, -8, -6, -8])

Example 4: Comparison with the numpy transform

>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> import torch
>>> import spyrit.core.torch as st
>>> x = np.array([1, 3, 0, -1, 7, 5, 1, -2])
>>> y_np = wh.fwht(x)
>>> x_torch = torch.from_numpy(x).to(torch.device('cpu'))
>>> y_torch = st.fwht(x_torch)
>>> print(y_np)
[14 -8 -8 18 -4 -2 -6  4]
>>> print(y_torch)
tensor([14, -8, -8, 18, -4, -2, -6,  4]...)

Example 5: Computation times for a signal of length 2**12

>>> import timeit
>>> import numpy as np
>>> import spyrit.misc.walsh_hadamard as wh
>>> import torch
>>> import spyrit.core.torch as st
>>> x = np.random.rand(2**12)
>>> t = timeit.timeit(lambda: wh.fwht(x,False), number=2000)
>>> print(f"Fast Hadamard transform numpy CPU (2000x): {t:.4f} seconds")
Fast Hadamard transform numpy CPU (2000x): ... seconds
>>> x_torch = torch.from_numpy(x)
>>> t = timeit.timeit(lambda: st.fwht(x_torch,False), number=2000)
>>> print(f"Fast Hadamard transform pytorch CPU (2000x): {t:.4f} seconds")
Fast Hadamard transform pytorch CPU (2000x): ... seconds

Example 6: CPU vs GPU: Computation times for 512 signals of length 2**12

>>> import timeit
>>> import torch
>>> import spyrit.core.torch as st
>>> x_cpu = torch.rand(512,2**12)
>>> t = timeit.timeit(lambda: st.fwht(x_cpu,False), number=50)
>>> print(f"Fast Hadamard transform pytorch CPU (50x): {t:.4f} seconds")
Fast Hadamard transform pytorch CPU (50x): ... seconds

Example 7: Repeating the Walsh-ordered transform using input indices is faster

>>> import timeit
>>> import torch
>>> import spyrit.core.torch as st
>>> x = torch.rand(256,2**12).to(torch.device('cpu'))
>>> t = timeit.timeit(lambda: st.fwht(x), number=100)
>>> print(f"No indices as inputs (100x): {t:.3f} seconds")
No indices as inputs (100x): ... seconds
>>> ind = st.sequency_perm(x).shape[-1]
>>> t = timeit.timeit(lambda: st.fwht(x,ind), number=100)
>>> print(f"With indices as inputs (100x): {t:.3f} seconds")
With indices as inputs (100x): ... seconds