On the Rudin-Shapiro transform (Q2425383)

The Rudin-Shapiro polynomials are orthogonal polynomials discovered by Rudin and Shapiro in 1951 that have desirable time-frequency localization properties. The purpose of this work is to give a historical review of the problems addressed by the construction of these polynomials and variants and then to focus on some properties of the (symmetric) Rudin-Shapiro transform (RST). The historical introduction focuses on flat polynomials and includes interesting perspectives both on the mathematical challenges and signal processing motivation. The main technical innovation of this work is a recursive construction of a symmetric RST matrix whose rows are essentially the coefficients of the Rudin-Shapiro polynomials but which also form an orthogonal basis for the corresponding Euclidean space. The RST is defined as follows. Define \({\mathbf{P}}_{j,m}: \mathbb{R}^{2^j}\to \mathbb{R}^{2^j}\) by \[ \left( \begin{matrix} y_k \\ y_{k+2^{j-1}} \end{matrix} \right) = {(-1)^{mk}\over \sqrt{2}}\left( \begin{matrix} 1 & (-1)^k \\ (-1)^m & -(-1)^{k+m} \end{matrix} \right)\left(\begin{matrix} x_{2k} \\ x_{2k+1} \end{matrix} \right) \] and let \[ {\mathbf{P}}_{j}^{J}= \left( \begin{matrix} {\mathbf{P}}_{j,0} & {} & 0 \\ {} & \ddots & {} \\ 0 & {} & {\mathbf{P}}_{j,2^{J-j}-1} \end{matrix} \right). \] The RST is defined as \({\mathbf{P}}^{(J)}= \prod_{j=1}^J {\mathbf{P}}_j^{(J)}\). It is shown that the matrix \({\mathbf{P}}^{(J)}\) is orthogonal and symmetric and that the corresponding polynomials \(P_m^{(J)}(\xi)= \sum_{n=0}^{2^J-1} p_{m,n}^{(J)} \text{ e}^{2\pi i n\xi}\) with coefficients the entries of \({\mathbf{P}}^{(J)}\) are ``near flat.'' A fast \(O(N\log N)\) (\(N=2^J\)) implementation of the RST is also provided and the RST is compared to the Walsh packet transform.