Hadamard Row-Wise Generation Algorithm
Brayan Monroy Jorge Bacca






Hadamard Row-Wise Generation Algorithm
    Brayan Monroy & Jorge Bacca

Universidad Industrial de Santander, Bucaramanga, Colombia

<https://github.com/bemc22/hadamard-spc>






    September 9, 2024
===========================================================================================================================================




§ ABSTRACT 
We present an efficient algorithm for generating specific Hadamard rows, addressing the memory demands of pre-computing the entire matrix. Leveraging Sylvester's recursive construction, our method generates the required i-th row on demand, significantly reducing computational resources. The algorithm uses the Kronecker product to construct the desired row from the binary representation of the index without creating the full matrix. This approach is particularly useful for single-pixel imaging systems that need only one row at a time.  
 





§ METHOD



Computing the i-th row h_i of a Hadamard matrix H of order 2^n usually requires pre-computing the entire matrix. This process can be memory-intensive, particularly when n is large. However, in certain applications, such as Hadamard single-pixel imaging, only individual Hadamard rows are needed at any given time <cit.>. To address this, we have developed an algorithm for row-wise generation that calculates the specific coefficients of the i-th row without generating the entire matrix. Specifically, following Sylvester's construction, a Hadamard matrix of order 2^n can be recursively constructed from a base matrix of order two and Kronecker products as follows 
    H_2^n = 
        [   H_2^n-1   H_2^n-1;   H_2^n-1 - H_2^n-1 ] = H_2 ⊗H_2^n-1,
 with 2 ≤ n ∈ℕ where ⊗ denotes the Kronecker product. Hence, each row of the Hadamard matrix of order 2^n can be expressed as the Kronecker product of the first or second row of the Hadamard matrix of order 2. The sequence of Kronecker products is derived from the binary representation i_10 = (b_nb_n-1… b_1 b_0)_2 of the i-th row as follows


    h_i = ⊗_k=n^0 h_b_k = h_b_n⊗h_b_n-1⊗⋯⊗h_b_1⊗h_b_0


In this context, we present the Algorithm <ref>, which involves setting the base 2-order Hadamard matrix and mapping the specified index to its binary representation. An iterative loop processes the binary digits to select the appropriate rows of the 2-order Hadamard matrix, ultimately constructing the desired Hadamard row via the cumulative Kronecker product as presented in Figure <ref>. Additionally, this algorithm can be adapted for other Hadamard ordering strategies, as it relies mainly on permuting ordering indexes. The code implementation is available on GitHub.

It is important to note that the generation of a Hadamard matrix row without constructing the entire matrix is less discussed in the literature, although it is a natural extension of their recursive nature, as proposed in <cit.>. We believe that the algorithm provided contributes to a more detailed documentation of this strategy.

Computational complexity.  The computational complexity of Algorithm <ref> relies on the complexity in compute n times Kronecker product of vector of size 2. In this sense, for each Kronecker product between the vector of size 2^k-1 (resulting from the previous k-1 Kronecker products) and a vector of size 2, the number of multiplication required is 2 × 2^k-1 = 2^k. Thus, the total computational complexity 𝒞(n) for performing n Kronecker products is the sum of the number of multiplications for each step

    𝒞(n) = 2^1 + 2^2 + 2^3 +  ⋯ + 2^n = ∑_k=1^n 2^k,

which consists of a geometric series that can be simplified as 𝒞(n) = 2^n+1 - 2, with the dominant term in 𝒞(n) being 2^n+1, so the asymptotic computational complexity of Algorithm <ref> is 𝒪(2^n+1) ∼𝒪(2^n). 


 





ieee_fullname



