Noiselet

Noiselets are functions which gives the worst case behavior for the Haar wavelet packet analysis. In other words, noiselets are totally incompressible by the Haar wavelet packet analysis.[1] Like the canonical and Fourier bases, which have an incoherent property, noiselets are perfectly incoherent with the Haar basis. In addition, they have a fast algorithm for implementation, making them useful as a sampling basis for signals that are sparse in the Haar domain.

Definition

The mother bases function $\chi (x)$ is defined as:

$\chi (x)={\begin{cases}1&x\in [0,1)\\0&{\text{otherwise}}\end{cases}}$

The family of noislets is constructed recursively as follows:

${\begin{alignedat}{2}f_{1}(x)&=\chi (x)\\f_{2n}(x)&=(1-i)f_{n}(2x)+(1+i)f_{n}(2x-1)\\f_{2n+1}(x)&=(1+i)f_{n}(2x)+(1-i)f_{n}(2x-1)\end{alignedat}}$

Property of f_n

$\{f_{j}|j=2^{N},\dots ,2^{N+1}-1\}$ is an orthogonal basis for $V_{N}$ , where $V_{N}$ is the space of all possible approximations at the resolution $2^{N}$ of functions in $L^{2}[0,1)$ .
For each $n\geq 1$ , $\int _{0}^{1}f_{n}(x)dx=1$

Matrix construction of noiselets[2]

Noiselet can be extended and discretized. The extended function $f_{m}(k,l)$ is defined as follows:

${\begin{alignedat}{2}f_{m}(1,l)&={\begin{cases}1&l=0,\dots ,2^{m}-1\\0&{\text{otherwise}}\end{cases}}\\f_{m}(2k,l)&=(1-i)f_{m}(k,2l)+(1+i)f_{m}(k,2l-2^{m})\\f_{m}(2k+1,l)&=(1+i)f_{m}(k,2l)+(1-i)f_{m}(k,2l-2^{m})\\\end{alignedat}}$

Use extended noiselet $f_{m}(k,l)$ , we can generate the $n\times n$ noiselet matrix $N_{n}$ , where n is a power of two $n=2^{q}$ :

${\begin{alignedat}{2}N_{1}&=[1]\\N_{2n}&={\frac {1}{2}}{\begin{bmatrix}1-i&1+i\\1+i&1-i\end{bmatrix}}\otimes N_{n}\\\end{alignedat}}$

Here $\otimes$ denotes the Kronecker product.

Suppose $2^{m}>n$ , we can find that $N_{n}(k,l)$ is equal $f_{m}(n+k,{\frac {2^{m}}{n}}l)$ .

The elements of the noiselet matrices take discrete values from one of two four-element sets:

${\begin{alignedat}{3}{\sqrt {n}}N_{n}(j,k)&\in \{1,-1,i,-i\}&{\text{for even }}q\\{\sqrt {2n}}N_{n}(j,k)&\in \{1+i,1-i,-1+i,-1-i\}&{\text{for odd }}q\\\end{alignedat}}$

2D noiselet transform

2D noiselet transforms are obtained through the Kronecker product of 1D noiselet transform:

$N_{n\times k}^{2D}=N_{k}\otimes N_{n}$

Applications

Noiselet has some properties that make them ideal for applications:

The noiselet matrix can be derived in $O(n\log n)$ .
Noiselet completely spread out spectrum and have the perfectly incoherent with Haar wavelets.
Noiselet is conjugate symmetric and is unitary.

The complementarity of wavelets and noiselets means that noiselets can be used in compressed sensing to reconstruct a signal (such as an image) which has a compact representation in wavelets.[3] MRI data can be acquired in noiselet domain, and, subsequently, images can be reconstructed from undersampled data using compressive-sensing reconstruction.[4]

References

R. Coifman, F. Geshwind, and Y. Meyer, Noiselets, Applied and Computational Harmonic Analysis, 10 (2001), pp. 27–44. doi:10.1006/acha.2000.0313.
T. Tuma; P. Hurley. "On the incoherence of noiselet and Haar bases" (PDF).
E. Candes and J. Romberg, Sparsity and incoherence in compressive sampling, 23 (2007), pp. 969–985. doi:10.1088/0266-5611/23/3/008.
K. Pawar, G. Egan, and Z. Zhang, Multichannel Compressive Sensing MRI Using Noiselet Encoding, 05 (2015), doi:10.1371/journal.pone.0126386.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[coifman01-1] R. Coifman, F. Geshwind, and Y. Meyer, Noiselets, Applied and Computational Harmonic Analysis, 10 (2001), pp. 27–44. doi:10.1006/acha.2000.0313.

[2] T. Tuma; P. Hurley. "On the incoherence of noiselet and Haar bases" (PDF).

[candes07-3] E. Candes and J. Romberg, Sparsity and incoherence in compressive sampling, 23 (2007), pp. 969–985. doi:10.1088/0266-5611/23/3/008.

[pawar01-4] K. Pawar, G. Egan, and Z. Zhang, Multichannel Compressive Sensing MRI Using Noiselet Encoding, 05 (2015), doi:10.1371/journal.pone.0126386.