def fwht()

in srht.py [0:0]

• 21 lines of code
• 9 McCabe index (conditional complexity)

def fwht(A):
    """
    Fast Walsh–Hadamard Transform of each column of matrix A.

    Equivalent to the multiplication on the left of A
    by the Hadamard matrix of order A.shape[0].
    No normalization factor.
    The output has is dense and has the same shape as the input.

    If the input is a row vector of shape (1, m).
    The function applies the Hadamard transform to
    the input vector and not the identity.

    Parameters
    ----------
    A : numpy.ndarray or scipy.sparse array
        Input matrix to transform.

    Returns
    -------
    B : numpy.ndarray
        Hadamard transform of A. Output has the same shape as input.
    """
    if not np.log2(A.shape[0]).is_integer():
        raise ValueError("Size of the sequence must be a power of 2.")

    if sparse.issparse(A):
        B = A.toarray()
    else:
        B = A.copy()

    # Reshape if 2D row vector: (1, n) to (n,)
    if A.shape[0] == 1:
        B = B.reshape(-1,)

    h = 1
    while h < B.shape[0]:
        for i in range(0, B.shape[0], h * 2):
            for j in range(i, i + h):
                x = B[j].copy()
                y = B[j + h].copy()

                B[j] = x + y
                B[j + h] = x - y
        h *= 2

    # Reshape back (n,) to row vector (1, n)
    if A.shape[0] == 1:
        B = B.reshape(1, -1)
    return B