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 ${\displaystyle \chi (x)}$ is defined as:

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

The family of noislets is constructed recursively as follows:

${\displaystyle {\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

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

Matrix construction of noiselets[2]

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

${\displaystyle {\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 ${\displaystyle f_{m}(k,l)}$, we can generate the ${\displaystyle n\times n}$ noiselet matrix ${\displaystyle N_{n}}$, where n is a power of two ${\displaystyle n=2^{q}}$:

${\displaystyle {\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 ${\displaystyle \otimes }$ denotes the Kronecker product.

Suppose ${\displaystyle 2^{m}>n}$, we can find that ${\displaystyle N_{n}(k,l)}$ is equal ${\displaystyle 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:

${\displaystyle {\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:

${\displaystyle 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 ${\displaystyle 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]

Here are few applications that noiselet has been implemented:

• Magnetic resonance imaging (MRI)

The noiselet encoding is a technique used in MRI to acquire images with reduced acquisition time. In MRI, the imaging process typically involves encoding spatial information using gradients. Traditional MRI acquisition relies on Cartesian encoding,[5] where the spatial information is sampled on a Cartesian grid. However, this methodology could be time consuming, especially in images with high resolution or dynamic imaging.

While noiselet encoding is part of the compressive sensing. It exploits the sparsity of images to obtain them in a more efficient way. In compressive sensing, the idea is to acquire fewer samples than dictated by the Nyquist-Shannon sampling theorem, under the assumption that the underlying signal or image is sparse in some domain. The overview of how noiselet encoding works in MRI is briefly explained as follow:

The noiselet encoding uses a noiselet transform matrix, which the produced coefficients effectively disperse the signal across both scale and time. Consequently, each subset of these transform coefficients captures specific information from the original signal. When these subsets are utilized independently with zero padding, each of them can be employed to reconstruct the original signal at a reduced resolution. As not all of the spatial frequency components are sampled by noiselet encoding, the undersampling allows the reconstruction of the image with fewer measurements, in other words, a more efficient imaging without sacrificing image quality significantly.

• Single-pixel imaging[6]

Single-pixel imaging is a form of imaging where a single detector is used to measure light levels after the sample has been illuminated with patterns to achieve efficient and compressive measurements. Noiselet is implemented to increase the computational efficiency by following the principle of compressive sensing. The following is an overview of how noiselet is applied to single-pixel imaging:

The noiselet transform matrix is applied to the structured illumination patterns, and spreads the signal information across the measurement space. The structured patterns leads to a sparse representation of the signal information. This allows the reconstruction step of the image from a reduced set of measurements, while still encapsulates the essential information required to reconstruct an image with good quality compared to the original's. The benefits brought by noiselet can be concluded as:

1. Reduced amount of measurements: fewer measurements required for computation
2. Compressed data: compressed representation of the image reduces the transmission time and storage
3. Faster imaging: The overall acquisition time being significantly reduced, making single-pixel imaging suitable for rapid imaging applications.

References

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).
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.
4. K. Pawar, G. Egan, and Z. Zhang, Multichannel Compressive Sensing MRI Using Noiselet Encoding, 05 (2015), doi:10.1371/journal.pone.0126386.
5. Pruessmann, Klaas P.; Weiger, Markus; Scheidegger, Markus B.; Boesiger, Peter (November 1999). "SENSE: Sensitivity encoding for fast MRI". Magnetic Resonance in Medicine. 42 (5): 952–962. doi:10.1002/(SICI)1522-2594(199911)42:5<952::AID-MRM16>3.0.CO;2-S. ISSN 0740-3194. PMID 10542355.
6. Pastuszczak, Anna; Szczygiel, Bartlomiej; Mikolajczyk, Michal; Kotynski, Rafal (2016). Modified noiselet transform and its application to compressive sensing with optical single-pixel detectors. pp. 1–4. doi:10.1109/ICTON.2016.7550361. ISBN 978-1-5090-1467-5. Retrieved 2023-12-27.