Hadamard Transforms¶

spectrans.transforms.hadamard ¶

Hadamard transform implementations for spectral neural networks.

This module provides fast implementations of the Walsh-Hadamard Transform and related orthogonal transforms that use only +1 and -1 basis functions. These transforms provide alternatives to Fourier transforms, requiring only addition and subtraction operations without multiplications.

Hadamard transforms provide simplicity, orthogonality, and fast mixing operations for spectral neural networks.

Classes:

Name	Description
`HadamardTransform`	Fast Walsh-Hadamard Transform for efficient orthogonal mixing.
`HadamardTransform2D`	2D Hadamard Transform for image-like data processing.
`SequencyHadamardTransform`	Sequency-ordered Hadamard Transform with frequency-like interpretation.
`SlantTransform`	Slant transform with sawtooth basis functions.

Examples:

Basic Hadamard Transform:

>>> import torch
>>> from spectrans.transforms.hadamard import HadamardTransform
>>> hadamard = HadamardTransform(normalized=True)
>>> # Input size must be power of 2
>>> signal = torch.randn(32, 512)  # 512 = 2^9
>>> transformed = hadamard.transform(signal, dim=-1)
>>> reconstructed = hadamard.inverse_transform(transformed, dim=-1)

2D Hadamard for image processing:

>>> from spectrans.transforms.hadamard import HadamardTransform2D
>>> hadamard2d = HadamardTransform2D(normalized=True)
>>> # Both dimensions must be powers of 2
>>> image = torch.randn(32, 64, 64)  # 64 = 2^6
>>> transformed_image = hadamard2d.transform(image, dim=(-2, -1))

Sequency-ordered transform:

>>> from spectrans.transforms.hadamard import SequencyHadamardTransform
>>> seq_hadamard = SequencyHadamardTransform(normalized=True)
>>> seq_coeffs = seq_hadamard.transform(signal, dim=-1)
>>> # Coefficients ordered by sequency (analog of frequency)

Slant transform for edge detection:

>>> from spectrans.transforms.hadamard import SlantTransform
>>> slant = SlantTransform(normalized=True)
>>> slant_coeffs = slant.transform(signal, dim=-1)

Notes

Mathematical Properties:

Walsh-Hadamard Transform:

The Hadamard matrix \(\mathbf{H}_n\) for size \(n=2^k\) is defined recursively:

\[ \mathbf{H}_1 = [1], \quad \mathbf{H}_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \]

\[ \mathbf{H}_{2n} = \begin{bmatrix} \mathbf{H}_n & \mathbf{H}_n \\ \mathbf{H}_n & -\mathbf{H}_n \end{bmatrix} \]

Orthogonality:

\(\mathbf{H}_n \cdot \mathbf{H}_n^T = n \cdot \mathbf{I}\) (unnormalized)
\(\mathbf{H}_n \cdot \mathbf{H}_n^T = \mathbf{I}\) (normalized by \(\frac{1}{\sqrt{n}}\))
Perfect reconstruction: \(\mathbf{H}^{-1} = \mathbf{H}^T / n\)

Computational Advantages:

Only requires +1 and -1 multiplications
Fast \(O(n \log n)\) algorithm similar to FFT
Memory efficient: can be computed in-place
Highly parallel: suitable for vector operations

Sequency Ordering: Standard Hadamard ordering is not frequency-like. Sequency ordering rearranges coefficients by their "sequency" (number of sign changes), providing a more intuitive frequency-domain interpretation.

Applications in Spectral Transformers:

Efficient Mixing: Hadamard transforms provide orthogonal mixing with minimal computational cost (only additions/subtractions)
Binary Neural Networks: Natural fit for binary/quantized networks due to {+1, -1} basis functions
Compressive Sensing: Hadamard matrices provide good measurement matrices for sparse signal recovery
Pattern Recognition: Walsh functions capture different pattern frequencies useful for classification tasks

Implementation Details:

Fast Algorithm: Uses recursive butterfly structure similar to FFT
Power-of-2 Constraint: Input size must be \(2^k\) for fast algorithm
Bit-Reversal: Efficient implementation uses bit-reversed indexing
Normalization: Supports both normalized and unnormalized variants
Gradient Support: Full autodiff compatibility for neural networks

Performance Characteristics:

Time Complexity: \(O(n \log n)\) for fast algorithm
Space Complexity: \(O(1)\) additional memory (algorithm supports in-place computation)
Operations: Only additions and subtractions (no multiplications)
Memory Bandwidth: Regular access patterns

Limitations:

Input size must be power of 2 for fast algorithm
Less frequency selectivity compared to Fourier transforms
Binary nature may not suit all signal types

References

Jacques Hadamard. 1893. Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques, 17:240-246.

Joseph L. Walsh. 1923. A closed set of normal orthogonal functions. American Journal of Mathematics, 45(1):5-24.

K. R. Rao and P. Yip. 1990. Discrete Cosine Transform: Algorithms, Advantages, Applications. Academic Press, Boston.

Classes¶

HadamardTransform ¶

HadamardTransform(normalized: bool = True)

Bases: OrthogonalTransform

Fast Walsh-Hadamard Transform.

The Hadamard transform is an orthogonal transform using only +1 and -1 values. The transform size must be a power of 2.

Parameters:

Name	Type	Description	Default
`normalized`	`bool`	Whether to normalize by 1/sqrt(n) for orthogonality.	`True`

Methods:

Name	Description
`transform`	Apply Fast Walsh-Hadamard Transform.
`inverse_transform`	Apply inverse Hadamard transform.

Source code in spectrans/transforms/hadamard.py

def __init__(self, normalized: bool = True):
    super().__init__()
    self.normalized = normalized

Functions¶

transform ¶

transform(x: Tensor, dim: int = -1) -> Tensor

Apply Fast Walsh-Hadamard Transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Input tensor. Size along dim must be power of 2.	required
`dim`	`int`	Dimension along which to apply transform.	`-1`

Returns:

Type	Description
`Tensor`	Hadamard transformed tensor.

Raises:

Type	Description
`ValueError`	If size along dim is not a power of 2.

Source code in spectrans/transforms/hadamard.py

def transform(self, x: Tensor, dim: int = -1) -> Tensor:
    """Apply Fast Walsh-Hadamard Transform.

    Parameters
    ----------
    x : Tensor
        Input tensor. Size along dim must be power of 2.
    dim : int, default=-1
        Dimension along which to apply transform.

    Returns
    -------
    Tensor
        Hadamard transformed tensor.

    Raises
    ------
    ValueError
        If size along dim is not a power of 2.
    """
    n = x.shape[dim]

    # Check if n is power of 2
    if n & (n - 1) != 0:
        raise ValueError(f"Hadamard transform requires size to be power of 2, got {n}")

    # Move dimension to last for easier processing
    if dim != -1 and dim != x.ndim - 1:
        x = x.transpose(dim, -1)

    # Apply Fast Walsh-Hadamard Transform
    result = self._fwht(x)

    # Normalize if requested
    if self.normalized:
        result = result / math.sqrt(n)

    # Move dimension back
    if dim != -1 and dim != x.ndim - 1:
        result = result.transpose(dim, -1)

    return result

inverse_transform ¶

inverse_transform(x: Tensor, dim: int = -1) -> Tensor

Apply inverse Hadamard transform.

The Hadamard transform is self-inverse (up to normalization).

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Hadamard coefficients.	required
`dim`	`int`	Dimension along which to apply inverse transform.	`-1`

Returns:

Type	Description
`Tensor`	Inverse transformed tensor.

Source code in spectrans/transforms/hadamard.py

def inverse_transform(self, x: Tensor, dim: int = -1) -> Tensor:
    """Apply inverse Hadamard transform.

    The Hadamard transform is self-inverse (up to normalization).

    Parameters
    ----------
    x : Tensor
        Hadamard coefficients.
    dim : int, default=-1
        Dimension along which to apply inverse transform.

    Returns
    -------
    Tensor
        Inverse transformed tensor.
    """
    n = x.shape[dim]

    # For orthogonal Hadamard, inverse is same as forward
    if self.normalized:
        return self.transform(x, dim)
    else:
        # Without normalization, need to scale by 1/n
        result = self.transform(x, dim)
        return result / n

HadamardTransform2D ¶

HadamardTransform2D(normalized: bool = True)

Bases: SpectralTransform2D

2D Fast Walsh-Hadamard Transform.

Applies Hadamard transform along two dimensions.

Parameters:

Name	Type	Description	Default
`normalized`	`bool`	Whether to normalize for orthogonality.	`True`

Methods:

Name	Description
`transform`	Apply 2D Hadamard transform.
`inverse_transform`	Apply inverse 2D Hadamard transform.

Source code in spectrans/transforms/hadamard.py

def __init__(self, normalized: bool = True):
    super().__init__()
    self.normalized = normalized
    self.hadamard = HadamardTransform(normalized=False)  # Handle normalization here

Functions¶

transform ¶

transform(x: Tensor, dim: tuple[int, int] = (-2, -1)) -> Tensor

Apply 2D Hadamard transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Input tensor. Sizes along both dims must be powers of 2.	required
`dim`	`tuple[int, int]`	Dimensions along which to apply transform.	`(-2, -1)`

Returns:

Type	Description
`Tensor`	2D Hadamard transformed tensor.

Source code in spectrans/transforms/hadamard.py

def transform(self, x: Tensor, dim: tuple[int, int] = (-2, -1)) -> Tensor:
    """Apply 2D Hadamard transform.

    Parameters
    ----------
    x : Tensor
        Input tensor. Sizes along both dims must be powers of 2.
    dim : tuple[int, int], default=(-2, -1)
        Dimensions along which to apply transform.

    Returns
    -------
    Tensor
        2D Hadamard transformed tensor.
    """
    # Apply along first dimension
    result = self.hadamard.transform(x, dim=dim[0])
    # Apply along second dimension
    result = self.hadamard.transform(result, dim=dim[1])

    if self.normalized:
        n1 = x.shape[dim[0]]
        n2 = x.shape[dim[1]]
        result = result / math.sqrt(n1 * n2)

    return result

inverse_transform ¶

inverse_transform(x: Tensor, dim: tuple[int, int] = (-2, -1)) -> Tensor

Apply inverse 2D Hadamard transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Hadamard coefficients.	required
`dim`	`tuple[int, int]`	Dimensions along which to apply inverse transform.	`(-2, -1)`

Returns:

Type	Description
`Tensor`	Inverse transformed tensor.

Source code in spectrans/transforms/hadamard.py

def inverse_transform(self, x: Tensor, dim: tuple[int, int] = (-2, -1)) -> Tensor:
    """Apply inverse 2D Hadamard transform.

    Parameters
    ----------
    x : Tensor
        Hadamard coefficients.
    dim : tuple[int, int], default=(-2, -1)
        Dimensions along which to apply inverse transform.

    Returns
    -------
    Tensor
        Inverse transformed tensor.
    """
    if self.normalized:
        return self.transform(x, dim)
    else:
        result = self.transform(x, dim)
        n1 = x.shape[dim[0]]
        n2 = x.shape[dim[1]]
        return result / (n1 * n2)

SequencyHadamardTransform ¶

SequencyHadamardTransform(normalized: bool = True)

Bases: OrthogonalTransform

Sequency-ordered Hadamard Transform.

The sequency ordering arranges basis functions by number of zero-crossings, similar to frequency ordering in Fourier transforms.

Parameters:

Name	Type	Description	Default
`normalized`	`bool`	Whether to normalize for orthogonality.	`True`

Methods:

Name	Description
`transform`	Apply sequency-ordered Hadamard transform.
`inverse_transform`	Apply inverse sequency-ordered Hadamard transform.

Source code in spectrans/transforms/hadamard.py

def __init__(self, normalized: bool = True):
    super().__init__()
    self.normalized = normalized
    self.hadamard = HadamardTransform(normalized=normalized)

Functions¶

transform ¶

transform(x: Tensor, dim: int = -1) -> Tensor

Apply sequency-ordered Hadamard transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Input tensor. Size along dim must be power of 2.	required
`dim`	`int`	Dimension along which to apply transform.	`-1`

Returns:

Type	Description
`Tensor`	Sequency-ordered Hadamard coefficients.

Source code in spectrans/transforms/hadamard.py

def transform(self, x: Tensor, dim: int = -1) -> Tensor:
    """Apply sequency-ordered Hadamard transform.

    Parameters
    ----------
    x : Tensor
        Input tensor. Size along dim must be power of 2.
    dim : int, default=-1
        Dimension along which to apply transform.

    Returns
    -------
    Tensor
        Sequency-ordered Hadamard coefficients.
    """
    # Apply standard Hadamard transform
    result = self.hadamard.transform(x, dim)

    # Reorder to sequency ordering
    n = x.shape[dim]
    indices = self._get_sequency_indices(n).to(x.device)

    result = result[..., indices] if dim == -1 else torch.index_select(result, dim, indices)

    return result

inverse_transform ¶

inverse_transform(x: Tensor, dim: int = -1) -> Tensor

Apply inverse sequency-ordered Hadamard transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Sequency-ordered Hadamard coefficients.	required
`dim`	`int`	Dimension along which to apply inverse transform.	`-1`

Returns:

Type	Description
`Tensor`	Inverse transformed tensor.

Source code in spectrans/transforms/hadamard.py

def inverse_transform(self, x: Tensor, dim: int = -1) -> Tensor:
    """Apply inverse sequency-ordered Hadamard transform.

    Parameters
    ----------
    x : Tensor
        Sequency-ordered Hadamard coefficients.
    dim : int, default=-1
        Dimension along which to apply inverse transform.

    Returns
    -------
    Tensor
        Inverse transformed tensor.
    """
    n = x.shape[dim]

    # Get inverse permutation
    indices = self._get_sequency_indices(n).to(x.device)
    inverse_indices = torch.zeros_like(indices)
    inverse_indices[indices] = torch.arange(n, device=x.device)

    # Reorder from sequency to natural ordering
    if dim == -1:
        x_reordered = x[..., inverse_indices]
    else:
        x_reordered = torch.index_select(x, dim, inverse_indices)

    # Apply inverse Hadamard
    return self.hadamard.inverse_transform(x_reordered, dim)

SlantTransform ¶

SlantTransform(normalized: bool = True)

Bases: OrthogonalTransform

Slant Transform.

The Slant transform is similar to Hadamard but with varying basis function slopes, providing better energy compaction for certain signals.

Parameters:

Name	Type	Description	Default
`normalized`	`bool`	Whether to normalize for orthogonality.	`True`

Methods:

Name	Description
`transform`	Apply Slant transform.
`inverse_transform`	Apply inverse Slant transform.

Source code in spectrans/transforms/hadamard.py

def __init__(self, normalized: bool = True):
    super().__init__()
    self.normalized = normalized

Functions¶

transform ¶

transform(x: Tensor, dim: int = -1) -> Tensor

Apply Slant transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Input tensor. Size along dim should be power of 2.	required
`dim`	`int`	Dimension along which to apply transform.	`-1`

Returns:

Type	Description
`Tensor`	Slant transformed tensor.

Source code in spectrans/transforms/hadamard.py

def transform(self, x: Tensor, dim: int = -1) -> Tensor:
    """Apply Slant transform.

    Parameters
    ----------
    x : Tensor
        Input tensor. Size along dim should be power of 2.
    dim : int, default=-1
        Dimension along which to apply transform.

    Returns
    -------
    Tensor
        Slant transformed tensor.
    """
    n = x.shape[dim]

    # Check if n is power of 2
    if n & (n - 1) != 0:
        raise ValueError(f"Slant transform works best with size as power of 2, got {n}")

    # Create Slant matrix
    slant_matrix = self._create_slant_matrix(n, x.device, x.dtype)

    # Apply transform via matrix multiplication
    if dim == -1 or dim == x.ndim - 1:
        result = torch.matmul(x, slant_matrix.T)
    else:
        x_moved = x.transpose(dim, -1)
        result = torch.matmul(x_moved, slant_matrix.T)
        result = result.transpose(dim, -1)

    return result

inverse_transform ¶

inverse_transform(x: Tensor, dim: int = -1) -> Tensor

Apply inverse Slant transform.

Parameters:

Name	Type	Description	Default
`x`	`Tensor`	Slant coefficients.	required
`dim`	`int`	Dimension along which to apply inverse transform.	`-1`

Returns:

Type	Description
`Tensor`	Inverse transformed tensor.

Source code in spectrans/transforms/hadamard.py

def inverse_transform(self, x: Tensor, dim: int = -1) -> Tensor:
    """Apply inverse Slant transform.

    Parameters
    ----------
    x : Tensor
        Slant coefficients.
    dim : int, default=-1
        Dimension along which to apply inverse transform.

    Returns
    -------
    Tensor
        Inverse transformed tensor.
    """
    n = x.shape[dim]

    # Create Slant matrix (orthogonal, so inverse is transpose)
    slant_matrix = self._create_slant_matrix(n, x.device, x.dtype)

    # Apply inverse transform
    if dim == -1 or dim == x.ndim - 1:
        result = torch.matmul(x, slant_matrix)
    else:
        x_moved = x.transpose(dim, -1)
        result = torch.matmul(x_moved, slant_matrix)
        result = result.transpose(dim, -1)

    return result