Sparse orthogonal matrices and the Haar wavelet

The sparsity of orthogonal matrices which have a column of nonzeros is studied. It is shown that the minimum number of nonzero entries in such an m×m orthogonal matrix is (⌊lg m⌋+3)m – 2^{⌊lg m⌋+1}, where lg denotes the dyadic logarithm. Matrices achieving this level of sparsity are characterized, and related to orthogonal matrices arising from the Haar wavelet. The analogous sparsity problem for m×n row-orthogonal matrices which have a column of nonzeros is studied, and it is shown that the minimum number of nonzero entries in such a matrix with n′ nonzero columns is (⌊lg m⌋+3)m – 2^{⌊lg m⌋+1} + (n′ – m).