# Significance of sequency ordering in Walsh-Hadamard matrices

So I've been doing some reading into Hadamard and related matrices (Slant, Walsh, , and have observed that there are three typical "orderings" of the rows based on various criterion. E.g. "Natural", "Dyadic", "Walsh" (or Sequency http://fourier.eng.hmc.edu/e161/lectures/wht/node3.html).

One of the books I'm reading is "Introduction to orthogonal transforms with applications in data processing and analysis" by Ruye Wang (of which a copy can be accessed freely here http://fourier.eng.hmc.edu/book/lectures/mybook.pdf )

In this book there is a chapter (8) dedicated to some of these matrices. In particular is the Hadamard matrix. It states a definition of sequency:

"..the sequency s of each row, defined as the number of zero-crossings or sign changes in the row. Similar to frequency, sequency also measures the rate of changes or variations in a signal. However, sequency can measure non-periodic signals as well as periodic ones"

Later on in the discussion of making the Hadamard matrix into a seqeuency ordered Walsh-Hadamard matrix it states:

"The rows (or columns) of the WHT matrix H, ... , are not arranged in the order of the sequencies, while it is desireable to arrange them according to the sequencies in a low-to-high order, similar to how the DFT coefficients are arrange."

In the section on the Haar transform, it makes a brief explanation comparing the Fourier, Walsh-Hadamard, and Haar transforms:

"It is interesting to compare the Haar transform with other orthogonal transforms such as the Fourier, cosine, Walsh-Hadamard, and slant transforms discussed before. What all of these transforms, as well as the Haar transform, have in common is that their coefficients represent some types of detail contained in the signal, in terms of different frequencies (Fourier transform and cosine transform), sequencies (Walsh-Hadamard transform), or scales (Haar transform), in the sense that more detailed information is represented by coefficients for higher frequencies, sequencies, or scales"

One can observe an analogy between the fourier and sequency ordering ( Aittokallio et al, 2001 - Testing for Periodicity in Signals: An Application to Detect Partial Upper Airway Obstruction During Sleep:

Walsh functions with even and odd orders are called the cal and sal functions, respectively, and they correspond to the cosine and sine functions in Fourier analysis. One should note, that in contrast to harmonic functions the

TLDR

Now, i've been seeing the Walsh-Hadamard matrix in various papers regarding locality sensitive hashing, and approximate randomization, random projections etc. Returning to the Walsh-Hadamard, my confusion is that I'm trying to form an intuition behind the significance of using a sequency ordered Hadamard matrix as opposed to just a standard Hadamard matrix, in general, and in instances when the WH matrix is combined with other matricies to induce randomization (e.g. see Subsampled Randomized Transform, e.g. Tropp 2010 - IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM)

## 2 Answers

There isn't much significance. Except for few very particular applications like auto-focusing where you might try to adjust the lens such that the higher sequency components has maximum magnitude. The FFT of a particular sequency isn't bandwith limited. Therefore sequency has very limited meaning. You should indeed be looking at the applications like random projections, locality sensitive hashing, associative memory and neural networks: WHT applications

Matrix operations, or linear expressions, have some properties preserved when the terms are mixed, or rows or columns of a matrix are shuffled. This can be dealt with through permutation matrices for instance.

Sometimes, when it comes to actual computations, especially in designing fast algorithms, or for interpretation, some indexing or ordering of the components are more of less natural or useful. For instance, when performing data analysis, interpreting variations from slower to faster phenomena (similarly to Fourier) seems more intuitive. Linear approximations of signals often use sequency or frequency ordering, while this is not necessary in non-linear approximation.

Similarly, the recursive construction of Hadamard matrices is simpler than a direct construction, but sorting has a computational cost. So, ordering often matters more when effectively computing.