Continuous-Domain Solutions of Linear Inverse Problems With Tikhonov Versus Generalized TV Regularization

Harshit Gupta, Julien Fageot, Michael Unser

TL;DR

This paper tackles linear inverse problems by reformulating them in a continuous domain, moving beyond traditional discrete basis approaches. It derives "representer theorems" for Tikhonov (smooth solutions) and generalized Total Variation (gTV, sparse solutions) regularization, showing that gTV solutions are more data-independent and sparse, akin to their discrete $l_1$ counterparts.

What Problem Does This Paper Address?

Linear inverse problems, common in fields like medical imaging (e.g., MRI), aim to reconstruct an unknown signal from limited, noisy measurements. Traditionally, these problems are discretized by assuming the signal can be represented as a sum of basis functions. This choice of basis can be arbitrary and limit the solution's properties. The paper addresses this by formulating the inverse problem directly in the continuous domain, imposing regularization on the function itself rather than its discrete representation. This allows for a more natural derivation of solution properties and potentially better reconstructions, especially for sparse signals.

Methods

The core of the paper lies in deriving representer theorems for continuous-domain regularization. These theorems provide a parametric form for the solution to the inverse problem. The authors analyze two key regularization types:

  • Tikhonov (Quadratic) Regularization: This method penalizes the squared norm of a transformed signal (e.g., its derivative). The paper shows this leads to smooth, spline-based solutions that are constrained to a subspace determined by the measurement operator.
  • Generalized Total Variation (gTV) Regularization: This method penalizes the $l_1$ norm of the transformed signal. The key insight here is that gTV regularization in the continuous domain leads to sparse solutions composed of a few "dictionary elements" (related to the Green's function of the regularization operator). Crucially, the number of these elements is bounded by the number of measurements and is independent of the measurement operator itself, mirroring the behavior of discrete $l_1$ regularization.

They also develop an exact discretization scheme for these continuous-domain problems and propose an algorithm combining FISTA and a simplex method to find sparse solutions, particularly when the gTV problem has multiple solutions.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses synthetic data for illustrations.

Key Insights and Ideas

  • Continuous-Domain Formulation is Powerful: By moving the regularization to the continuous domain, the paper shows it naturally leads to spline solutions and reveals deeper connections between the regularization operator and the solution structure.
  • gTV Leads to Data-Independent Sparsity: A major finding is that gTV regularization naturally produces sparse solutions where the "atoms" (dictionary elements) are independent of the measurement operator. This is a significant advantage over Tikhonov, where the solution's structure is tied to both the regularization and measurement operators.
  • Representer Theorems Bridge Continuous and Discrete: The derived representer theorems provide a direct link between the continuous-domain problem and its finite-dimensional parameter search, making numerical solutions tractable.
  • Splines as Natural Solutions: Both Tikhonov and gTV regularization, when formulated in the continuous domain, yield solutions that are splines, albeit with different properties (smooth vs. piecewise constant/linear).

Key Results

  • Parametric Forms for Solutions: The paper provides explicit parametric forms (representer theorems) for Tikhonov and gTV regularized solutions.
  • gTV Solutions are Sparse and Data-Independent: The gTV solutions are shown to be composed of a limited number of dictionary elements (splines related to the Green's function of L), with the number of elements bounded by the number of measurements and independent of the measurement operator.
  • Algorithm for Sparse gTV Solutions: An algorithm is proposed to find sparse extreme-point solutions for the gTV case, especially when multiple solutions exist.
  • Experimental Validation: Illustrations in 1D demonstrate the theoretical findings, showing that gTV regularization recovers sparse signals more effectively than Tikhonov, while Tikhonov can be better for smoother signals.

Limitations and Future Work

  • Computational Complexity: While the paper proposes an algorithm for sparse solutions, the discretization of the continuous domain can still lead to large systems, especially for high-dimensional problems.
  • Non-unique gTV Solutions: The paper acknowledges that gTV regularization can lead to non-unique solutions and provides an algorithm to find an extreme point. However, selecting the "best" among multiple solutions might require further criteria.
  • Future Work: The authors suggest exploring the application of these continuous-domain formulations to more complex measurement models (e.g., tomography, MRI) and investigating the theoretical properties of these splines in more detail. The paper also hints at extensions to other regularization norms.

Summary updated

Abstract

We consider one-dimensional (1-D) linear inverse problems that are formulated in the continuous domain. The object of recovery is a function that is assumed to minimize a convex objective functional. The solutions are constrained by imposing a continuous-domain regularization. We derive the parametric form of the solution (representer theorems) for Tikhonov (quadratic) and generalized total-variation (gTV) regularizations. We show that, in both cases, the solutions are splines that are intimately related to the regularization operator. In the Tikhonov case, the solution is smooth and constrained to live in a fixed subspace that depends on the measurement operator. By contrast, the gTV regularization results in a sparse solution composed of only a few dictionary elements that are upper-bounded by the number of measurements and independent of the measurement operator. Our findings for the gTV regularization resonates with the minimization of the $\ell _1$ norm, which is its discrete counterpart and also produces sparse solutions. Finally, we find the experimental solutions for some measurement models in one dimension. We discuss the special case when the gTV regularization results in multiple solutions and devise an algorithm to find an extreme point of the solution set which is guaranteed to be sparse.
BibTeX
@article{gupta2018continuous,
  author = {Harshit Gupta and Julien Fageot and Michael Unser},
  title = {{Continuous-Domain Solutions of Linear Inverse Problems With Tikhonov Versus Generalized TV Regularization}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  doi = {10.1109/tsp.2018.2860549},
}

Loading related content...

Figure