Definition of the problem

The theory of Compressed Sensing (CS), introduced by Donoho and
Candès and Tao, is now a versatile sampling paradigm in many real-world applications, e.g., Magnetic Resonance Imaging (MRI), fluorescence microscopy, and imaging. Mathematically, CS considers the problem of recovering a signal $\boldsymbol{x} \in \mathbb{C}^N$ from $M$ noisy measurements

$$\boldsymbol{y} = \boldsymbol{A} \boldsymbol{x} + \boldsymbol{n} \in \mathbb{C}^M, $$

where the matrix $\boldsymbol{A} \in \mathbb{C}^{M\times N}$ approximates the physical sensing process of $\boldsymbol{x}$, and $\boldsymbol{n}$ denotes an additive noise vector. A typical goal in CS is minimizing the number of measurements $M$ while guaranteeing the quality of the signal recovery. This is indeed a critical aspect of the applications of CS. For example, the number of measurements in computer tomography application can be translated into the X-ray dose, which has to be minimized.

Figure 1: An example of the 1-D Hadamard, $(\boldsymbol{\Phi}_{\rm had})_{k,k’}$, (left) and Haar wavelet, $(\boldsymbol{\Psi}_{\rm dhw})_{k,k’}$, (right) matrices of size $8 \times 8$.

In this project, we tackle an important problem in the applications of CS theory: recovering a signal from subsampled Hadamard measurements using the Haar wavelet sparsity basis. In particular, in a wide range of imaging modalities, e.g., optical multiplexing or single-pixel camera, the sensing process can be modeled as taking measurements from the Hadamard transform. Moreover, considering the Haar wavelet basis paves the way to study other wavelet bases in combination with the Hadamard matrix. In this context, the main question becomes: how to design an efficient sampling strategy for subsampling the Hadamard measurements.

The need for a non-uniform density sampling

Traditional CS relying on orthonormal sensing systems suggests selecting the rows of the sensing matrix (in our case, the Hadamard matrix) uniformly at random, i.e., according to a Uniform Density Sampling (UDS). Unfortunately, this approach fails when the target signal is sparse or compressible in a basis, called sparsity basis, that is too coherent with the sensing basis. One example of this failure is the Hadamard-Haar system, where the sensing basis (Hadamard) is maximally coherent with the sparsity basis (Haar wavelet). This drawback is often called the coherence barrier in the literature.

Nevertheless, this barrier can be broken. Several empirical and theoretical evidences suggest using a non-uniform density sampling strategy, which densifies the subsampling of the lower Hadamard frequencies, to obtain superior signal reconstruction quality. In a general context, Krahmer and Ward [1] and Adcock et al. [2] arguably began to replace the notion of global coherence with its local versions, i.e., local coherence and multilevel coherence parameters, respectively. The idea in these works is to discriminate the elements of the sensing basis (e.g., Hadamard) in favor of those that are highly coherent with all the elements of the sparsity basis (e.g., Haar).

Although there are other versions of non-uniform sampling strategies, we focus on the framework of Krahmer and Ward [1], called here Variable Density Sampling (VDS), and the one of Adcock et al. [2], called here Multilevel Density Sampling (MDS). These allow us to derive suitable sampling strategies for Hadamard-Haar systems. Note that the term VDS is often used in the literature for other non-uniform density sampling strategies, while we here use VDS and MDS terms to distinguish the frameworks of [1] and [2].

An important aspect of CS theory is the difference between uniform and non-uniform1 (or fixed signal) recovery guarantees. The former is tightly connected to the Restricted Isometry Property (RIP). Essentially, a uniform recovery guarantee claims that a single draw of the sampling matrix is, with high probability, sufficient for the recovery of all sparse signals. A non-uniform recovery guarantee asserts that a single draw of the sampling matrix is, with high probability, sufficient for recovery of a fixed sparse signal.

Our contributions

In this project we derive both uniform and non-uniform recovery guarantees for Hadamard-Haar systems and associated efficient sampling strategies. For uniform (and non-uniform) guarantee, we resort to the VDS framework of Krahmer and Ward [1] (respectively, MDS framework of Adcock et al. [2]).

The main contributions of this project are the followings:

  • We provide uniform and non-uniform recovery guarantees for compressive Hadamard-Haar systems that are stable with respect to non-sparse signals and robust to the measurement noise. We build our analysis upon [1] (for the uniform guarantee) and upon [2] (for the non-uniform guarantee).
  • The results cover the recovery of 1-D and 2-D signals. In the latter case, we treat two constructions of the 2-D Haar basis, i.e., using the tensor product and multi-resolution analysis. We prove that either construction results in a different efficient sampling strategy.
  • By computing the exact values of the local and multilevel coherence parameters for Hadamard-Haar systems, we provide tight sample complexity bounds relatively to the VDS and MDS frameworks.
  • A. Moshtaghpour, J. Bioucas-Dias, and L. Jacques, “Close encounters of the binary kind: Signal reconstruction guarantees for compressive Hadamard sampling with Haar wavelet basis,” ‘‘arXiv preprint arXiv:1907.09795,’’ 2019.
  • A. Moshtaghpour, J. Bioucas-Dias, and L. Jacques, “Performance of compressive sensing for Hadamard-Haar systems,” ‘‘in proceedings of the Signal Processing with Adaptive Sparse Structured Representations workshop (SPARS),’’ Toulouse, 2019.

External References

  • [1] F. Krahmer and R.Ward, ‘’“Stable and robust sampling strategies for compressive imaging,”’’ IEEE transactions on image processing, vol. 23, no. 2, pp. 612–622, 2014.
  • [2] B. Adcock, A. C. Hansen, C. Poon, and B. Roman, ‘’“Breaking the coherence barrier: A new theory for compressed sensing,”’’ in Forum of Mathematics, Sigma, vol. 5. Cambridge University Press, 2017.

Collaborators

  • José Bioucas-Dias (Instituto de Telecomunicações, Instituto Superior Técnico (IT-IST), Universidade de Lisboa, Lisbon, Portugal)