Coherence estimates between Hadamard matrices and Daubechies wavelets

Abstract

Traditionally the compressive sensing theory have been focusing on the three principles of sparsity, incoherence and uniform random subsampling. Recent years research have shown that these principles yield insufficient results in many practical setups. This has lead to the development of the principles of asymptotic sparsity, asymptotic incoherence and multilevel random subsampling. As a result of these principles, the current theory is limited to unitary sampling and sparsifying operators. For large scale reconstruction, the theory is further restricted to operators whose product can be computed in O(N log N) operations, due to memory constraints of computers. Accordingly this has increased the popularity of the Fourier and Hadamard sampling operators, for applications where these operators can model the underlying sampling structure. As the sparsifying operator the wavelet transform have proven to yield satisfactory results in most setups. Since all of these operators needs to be unitary, this have restricted us to only consider Daubechies compactly supported orthonormal wavelets. By using wavelets as the sparsifying transform it has been proven that a Fourier sampling basis will be asymptotically incoherent to a unitary wavelet basis. The same result can easily be calculated numerically between a Hadamard sampling basis and a Daubechies wavelet basis. However, any theoretical result of this fact have been lacking. The purpose of this text is to provide such a theoretical result.