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
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)