A Weighted 𝓁1-Minimization Approach For Wavelet Reconstruction of Signals and Images

Joseph Daws Jr., Armenak Petrosyan, Hoang Tran, Clayton G. WebsterarXiv 2019 · arXiv

TL;DR

This paper introduces a novel weighted $\ell_1$-minimization approach for reconstructing sparse signals and images from incomplete or noisy data. By carefully choosing weights that exploit the inherent structure of wavelet coefficients, their method achieves more accurate and robust reconstructions compared to standard unweighted $\ell_1$-minimization, particularly for signals with structured sparsity.

What Problem Does This Paper Address?

Reconstructing signals and images from limited measurements (e.g., subsampled data or noisy observations) is a fundamental problem in many scientific and engineering fields. Wavelet transforms are powerful tools for representing signals and images efficiently, especially if they are sparse or compressible in a wavelet basis. Traditional methods like $\ell_1$-minimization excel at recovering sparse signals but can struggle when the sparsity is structured in a particular way, leading to the recovery of spurious coefficients. This paper addresses the challenge of improving reconstruction accuracy and robustness by leveraging the known structured sparsity patterns often found in wavelet coefficients of real-world signals and images.

Methods

The core of this work is a convex optimization problem formulated as a weighted $\ell_1$-minimization:

$$ \min_{\mathbf{c}} ||\mathbf{c}||_{w,1} + ||A\mathbf{c} - \mathbf{f}||_2^2 $$

where $\mathbf{c}$ represents the wavelet coefficients, $A$ is a measurement matrix, $\mathbf{f}$ is the observed data, and $||\cdot||_{w,1} = \sum_v w_v |c_v|$ is the weighted $\ell_1$-norm. The novelty lies in the choice of weights ($w_v$). The authors propose a specific weight assignment inspired by the structure of wavelet coefficients, which often exhibit a tree-like dependency (parent-child relationships). Their primary weight choice assigns higher weights to coefficients associated with shallower levels in the wavelet tree, promoting a "lower set" structure similar to that found in polynomial approximations.

They also introduce an adaptive weighting scheme, a modification of the iteratively reweighted $\ell_1$-minimization (IRW-$\ell_1$) method. This adaptive approach updates weights based on both the scale (level) of the coefficient and its magnitude from the previous iteration, aiming to better capture intra-scale correlations.

Datasets

The paper evaluates its method on synthetic data with known structured sparsity (e.g., coefficients supported on a "closed tree") and real-world signals and images, including:

  • A piecewise smooth function.
  • A rational polynomial $f(x) = 1/(1 + 25x^2)$.
  • A HeaviSine function.
  • A cameraman image.
  • A house image.
  • A wallpaper image with a repeating pattern.
  • An image of flamingos.
  • Surface temperature data of the Atlantic oceans.
  • Hyperspectral images.

No new datasets were introduced; rather, standard datasets and synthetic signals were used to demonstrate the effectiveness of the proposed method.

Key Insights and Ideas

  • Structured Sparsity is Key: The paper strongly advocates that exploiting the inherent structured sparsity of wavelet coefficients (e.g., parent-child relationships in a wavelet tree) is crucial for improving reconstruction performance beyond simple sparsity.
  • Weighting Matters: The choice of weights in $\ell_1$-minimization significantly impacts the recovery of structured sparse signals. Their proposed weighting scheme, which prioritizes coefficients based on their position in the wavelet tree, leads to more accurate reconstructions.
  • Adaptive Weights Improve Performance: The adaptive weighting scheme, which iteratively refines weights based on recovered coefficients, offers a further improvement, though at the cost of increased computation.
  • Robustness to Noise and Subsampling: The weighted approach demonstrates superior performance in both denoising (recovering from noisy measurements) and inpainting/subsampling (recovering from incomplete data) compared to unweighted methods.
  • Framelets Offer Advantages: For signals that are not perfectly compressible in standard wavelet bases, framelet representations, combined with weighted $\ell_1$-minimization, show promise in reducing artifacts.

Key Results

  • Improved Reconstruction Accuracy: Numerical experiments consistently show that weighted $\ell_1$-minimization outperforms unweighted $\ell_1$-minimization and standard IRW-$\ell_1$ for recovering signals and images with structured wavelet sparsity. For example, in the reconstruction of a rational polynomial from subsampled data, the weighted approach achieved an RMSE of 0.0072 compared to 0.3100 for the unweighted method.
  • Better Denoising: For a noisy HeaviSine function, the weighted method achieved a PSNR of 27.6637, comparable to a specialized wavelet shrinkage method (PSNR 29.2454) and significantly better than unweighted $\ell_1$-minimization.
  • Effective Image Recovery: For image reconstruction from a small percentage of pixels (e.g., 15% for a house image), weighted $\ell_1$-minimization yielded substantially better results, with higher PSNR values and sharper details compared to unweighted methods.
  • Adaptive Weights Show Marginal Gains: The proposed wavelet-aware adaptive weighting scheme provided slight improvements over the fixed weighting scheme but required solving multiple optimization problems.

Limitations and Future Work

  • Theoretical Guarantees: While the paper provides theoretical insights into sampling complexity for structured sparsity (closed tree assumption), the derived guarantees for wavelet bases are noted as still "too demanding" and do not fully reflect the observed practical performance, especially for underdetermined systems. The authors plan to address this in future work.
  • Computational Cost: Adaptive weighting schemes, while potentially offering better results, increase the computational burden due to the iterative nature of the optimization.
  • Generalization to Other Bases: The current work focuses on wavelet bases and frames. Future work could explore applying these weighted $\ell_1$-minimization techniques to other representation systems.
  • Application to PDEs: The authors suggest exploring the recovery of wavelet coefficients for functions that are solutions to partial differential equations as a promising future direction.

Summary updated

Abstract

In this effort, we propose a convex optimization approach based on weighted $\ell_1$-regularization for reconstructing objects of interest, such as signals or images, that are sparse or compressible in a wavelet basis. We recover the wavelet coefficients associated to the functional representation of the object of interest by solving our proposed optimization problem. We give a specific choice of weights and show numerically that the chosen weights admit efficient recovery of objects of interest from either a set of sub-samples or a noisy version. Our method not only exploits sparsity but also helps promote a particular kind of structured sparsity often exhibited by many signals and images. Furthermore, we illustrate the effectiveness of the proposed convex optimization problem by providing numerical examples using both orthonormal wavelets and a frame of wavelets. We also provide an adaptive choice of weights which is a modification of the iteratively reweighted $\ell_1$-minimization method.
BibTeX
@misc{jr2019weighted,
  author = {Joseph Daws Jr. and Armenak Petrosyan and Hoang Tran and Clayton G. Webster},
  title = {{A Weighted 𝓁1-Minimization Approach For Wavelet Reconstruction of Signals and Images}},
  year = {2019},
  eprint = {1909.07270},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.07270},
}

Loading related content...

Figure