The “weighted value function rule” and analysis of the L1-TGV2 model

In this post I would like to comment on two papers I “stumbled upon”, one in regularization theory and one in image processing.

The first one is A regularization parameter for nonsmooth Tikhonov regularization by Kazufumi Ito, Bangti Jin and Tomoya Takeuchi. As the title announces, the paper addresses the problem of determining suitable regularization parameter for some kind of Tikhonov regularization. In particular, the authors propose a new heuristic method, i.e. method which does not use any estimate of the noise level in the data. This is an interesting and important topic for several reasons:

1. Practically, estimates on the noise level are rarely available and if they are, they are not too reliable.
2. Strictly speaking, these kind of rules are “bad” since there is the “Bakushinksii Veto”: Such rules only provide regularizations (e.g. in the sense of Engl, Hanke, Neubauer for problems which are well-posed (as a great service, the authors state and prove this statement as Theore 3.2).
3. Despite this veto, several heuristic rules produce excellent results in practice.

Note that the last second points are not in contradiction. They merely say that the notion of “regularization” may be too strict. Usually, it uses a worst case estimate which may practically never observed.

The paper contributes a new rule and state that it is applicable to a broad range of problems. They use very general Tikhonov functional:

and do not assume that or are smooth. They use the value function

and propose the following rule for : For some choose such that

is minimal. I do not have any intuition for this rule (however, from they proofs you see that they work, at least for “partially smooth cases”, see below). Lacking a name for this rule, one may use the term “weighted value function rule”.

They prove several nice properties of the value function (continuity, monotonicity and concavity) with loose assumptions on and (especially they do not even need existence of minimizers for , only that the minimum exists). However, when it comes to error estimates, they only obtain results for a specific discrepancy measure, namely a squares Hilbert space norm:

It seems that, for general convex and lower-semicontinuous penalties they build upon results from my paper with Bangti Jin on the Hanke-Raus rule and the quasi-optimality principle.

Another contribution of the paper is that it gives an algorithm that realizes the weighted value function rule (a thing which I omitted in my paper with Bangti). Their numerical experiments demonstrate that the weighted value function rule and the proposed algorithm works well for academic examples.

The next paper I want to discuss is the preprint Properties of : The one-dimensional case by Kristian Bredies, Karl Kunisch and Tuomo Valkonen. There the authors analyze the somehow recent generalization “total generalized variation” of the omnipresent total variation. The TGV has been proposed by Bredies, Kunisch and Pock in this paper recently and Kristian and me also briefly described it in our book on mathematical image processing. Loosely speaking, the TGV shall be a generalization of the usual total variation which does not lead to “staircasing”. While one may observe from the construction of the TGV functional, that staircasing is not to be expected, the authors in this paper give precise statements. By restricting to the one dimensional case they prove several interesting properties of the TGV functional, most notably that it leads to an equivalent norm of the space .

Maybe I should state the definitions here: The total variation of a function is

leading the the -norm

The seminorm for a parameter tuple is

and the associated norm is

In Lemma 3.3 they prove that and are equivalent norms on . In Section 4 they show that minimizers of

obey staircasing of degree 0, i.e. the solution is piecewise constant when it is not equal to . For the minimizers of

one has staircasing of degree 1: is affine linear where it is not equal to .

These two facts combined (norm equivalence of and and the staircasing of degree 1) seem quite remarkable to me. They somehow show that staircasing is not related to the space of functions of bounded variation but only to the specific semi-norm. This is somehow satisfying since I still remember the thorough motivation of L. Rudin in his 1987 thesis for the usage of the space in image processing: If there where images which are not in we could not observe them. (He even draws an analogy to the question: How many angles can dance on the point of a needle?) Moreover, he further argues that is not too large in the sense that its elements are still accessible to analysis (e.g. in defining a weak notion of curvature although they may be discontinuous). The -model shows that it is possible to overcome the undesired effect of staircasing while staying in the well founded and mathematically sound and appealing framework of .

The paper contains several more interesting results (e.g. on preservation of continuity and “affinity” and on convergence of with respect to which I do not collect here.

 

Ivanov and the method of quasi-solutions

Coming back to regularization, especially Ivanov regularization. Recall that I used the term Ivanov regularization for the minimization problem

I again stumbled upon some reference: It seems that in the case that the constraint defines a compact set, this method is usually referred to as “method of quasi solutions”. More precisely, I found this in “Elements of the theory of inverse problems” by A.M. Denisov, Chapter 6. There he uses metric spaces and proves the following:

Theorem 1 Let be metric spaces with metrics , , respectively and continuous. Furthermore let be compact, be in the range of and assume that is the unique solution of which lies in . Finally for a with define and . Then it holds for that

Remark 1 Before we prove this theorem, we relate is to what I called Ivanov regularization above: The set is encoded in~(1) as and the “discrepancy measure” is simply the metric . Hence, let denote a solution of

Because is feasible for this problem it follows from that . Hence, . In other words: Ivanov regularization produces one element in the set . Now, the theorem says that every element in is a good approximation for (at least asymptotically).

Proof: We take a sequence and assume to the contrary that there exist such that for every there exists such that it holds that . Since all lie in which is compact, there is a convergent subsequence with limit . We obtain . However, this contradicts the assumption: d_Y(A\bar x,Ax^\dagger) & = &d_Y(A\bar x,y^\dagger) = \lim_{n\rightarrow \infty} d_Y(Ax_{\delta_n},y^\dagger) \nonumber
& \leq &\lim_{n\rightarrow \infty} d_Y(Ax_{\delta_n},y^{\delta_n}) + d_Y(y^{\delta_n},y^\dagger) \leq \lim_{n\rightarrow\infty}2\delta_n =0.

Coming back to the interpretation of the Theorem~1 and Ivanov regularization: Instead of Ivanov regularization, one could also use the following feasibility problem: Find an such that both and . For the case of vector spaces and and a convex set , this would be a convex feasibility problem which one may attack by available methods.

A further important remark is that we did not assume any linearity on (of course: we did not even assume a linear structure on or ). Hence, the theorem seem very powerful: There is no regularization parameter involved and one still gets convergence to the true solution! However, one of the assumptions in the theorem is somehow strong: The uniqueness of . To illustrate this we consider a special case:

Example 1 Let and be real (or complex) vector spaces and be linear with non-trivial null space. Furthermore, assume that is convex and compact and consider scaled versions for . Then the set of solutions of is an affine space in and there are three cases for the intersection of this set and :

1. The intersection is empty.
2. The intersection is a convex set and contains infinitely many elements.
3. The intersection contains exactly one element.

The last case occurs precisely, when the affine space of solution is tangential to . Loosely speaking, one may say that this case only occurs, if the set is scaled precisely to the right size such that is only touches the affine space of solutions.

Another strong assumption in Theorem~1 is that the set is compact. First there is a way to somehow relax this condition. Basically, we only need compactness to obtain the converging subsequence. Hence, one could try to work with a weaker topology on (which would result in a weaker notion of compactness) and then obtain a limit of a subsequence which converges in the weaker sense only. Then one would need some tool to deduce that the weak limit is indeed a solution. This strategy work, for example in Banach spaces:

Example 2 Let and be reflexive Banach spaces and be linear, bounded and one-to-one. We use the set as prior knowledge on the solution of . Moreover, we use the metrics induced the norms of and , respectively: and .

Obviously, is not compact (if is of infinite dimension) but it is weakly compact (and by the Eberlein-Smulian theorem also weakly-sequentially compact). In the situation of the proof of Theorem~1 we only get a weakly converging subsequence . However, a linear operator is also weak-to-weak linear, and hence . While we only have a weakly converging sequence, we still can obtain the contradiction in~(0) since the norm is weakly lower semicontinuous.

Another way to justify the assumption that the solution is in a known compact set, is that in practice we always use a representation of the solution which only use a finite number of degrees of freedom (think of a Galerkin ansatz for example). However, this interpretation somehow neglects that we are interested in finding the true solution to the true infinite dimensional problem and that the discretization of the problem should be treated as a different issue. Just building on the regularizing effect of discretization will almost surely result in a method which stability properties depend on the resolution of the discretization.

Finally: Another good reference of these somehow ancient results in regularization theory is one of the first books on this topics: “Solutions of ill-posed problems” by Tikhonov and Arsenin (1977). While it took me some time to get used the type of presentation, I have to admit that it is really worth to read this book (and other translation of Russian mathematical literature).

 

Optimal control of PDEs and/vs. Inverse problems

Recently Arnd Rösch and I organized the minisymposium “Parameter identification and nonlinear optimization” at the SIAM Conference on Optimization. One of the aims of this symposium was, to initiate more connections between the communities in optimal control of PDEs on the one hand and regularization of ill-posed problems on the other hand. To give a little bit of background, let me somehow formulate the “mother problems” in both fields:

Example 1 (Mother problem in optimal control of PDEs) We consider a bounded Lipschitz domain in (or ). Assume that we are given a target (or desired state) which is a real valued function of . Our aim is to find a function (or control) (also defined on ) such that the solution of the equation

Moreover, our solution (or control) shall obey some pointwise bounds

This motivates the following constrained optimization problem

Often, also the regularized problem is considered: For a small solve:

(This problem is also extensively treated section 1.2.1 in the excellent book “Optimal Control of Partial Differential Equations” by Fredi Tröltzsch.)

For inverse problems we may formulate:

Example 2 (Mother problem in inverse problems) Consider a bounded and linear operator between two Hilbert spaces and assume that has non-closed range. In this case, the pseudo-inverse is not a bounded operator. Consider now, that we have measured data that is basically a noisy version of “true data” . Our aim is, to approximate a solution of by the knowledge of . Since does no have a closed range, it is usually the case that is not in the domain of the pseudo inverse and simply does not make sense. A widely used approach, also treated in my previous post is Tikhonov regularization, that is solving for a small regularization parameter

Clearly both mother problems have a very similar mathematical structure: We may use the solution operator of the PDE, denote it by , and restate the mother problem of optimal control of PDEs in a form similar to the mother problem of inverse problems. However, there are some important conceptual differences:

Desired state vs. data: In Example 1 is a desired state which, however, may not be reachable. In Example 2 is noisy data and hence, shall not reached as good as possible.

Control vs. solution: In Example 1 the result is an optimal control. It’s form is not of prime importance, as long as it fulfills the given bounds and allows for a good approximation of . In Example 2 the result is the approximate solution itself (which, of course shall somehow explain the measured data ). It’s properties are itself important.

Regularization: In Example 1 the regularization is mainly for numerical reasons. The problem itself also has a solution for . This is due to the fact that the set of admissible for a weakly compact set. However, in Example 2 one may not choose : First because the functional will not have a minimizer anymore and secondly one really does not want as small as possible since is corrupted by noise. Especially, the people from inverse problems are interested in the case in which both and . However, in optimal control of PDEs, is often seen as a model parameter which ensures that the control has somehow a small energy.

These conceptual difference sometimes complicate the dialog between the fields. One often runs into discussion dead ends like “Why should we care about decaying —it’s given?” or “Why do you need these bounds on ? This makes your problem worse and you may not reach to state as good as possible\dots”. It often takes some time until the involved people realize that they really pursue different goals, that the quantities which even have similar names are something different and that the minimization problems can be solved with the same techniques.

In our minisymposium we had the following talks:

• “Identification of an Unknown Parameter in the Main Part of an Elliptic PDE”, Arnd Rösch
• “Adaptive Discretization Strategies for Parameter Identification Problems in PDEs in the Context of Tikhonov Type and Newton Type Regularization”, Barbara Kaltenbacher
• “Optimal Control of PDEs with Directional Sparsity”, Gerd Wachsmuth
• “Nonsmooth Regularization and Sparsity Optimization” Kazufumi Ito
• “ Fitting for Nonlinear Parameter Identification Problems for PDEs”, Christian Clason
• “Simultaneous Identification of Multiple Coefficients in an Elliptic PDE”, Bastian von Harrach

Finally, there was my own talk “Error Estimates for joint Tikhonov and Lavrentiev Regularization of Parameter Identification Probelms” which is based on a paper with the similar name which is at http://arxiv.org/abs/0909.4648 and published in Applicable Analysis. The slides of the presentation are here (beware, there may be some wrong exponents in the pdf…).

In a nutshell, the message of the talk is: Bound both on the control/solution and the state/data may be added also to a Tikhonov-regularized inverse problem. If the operator has convenient mapping properties then the bounds will eventually be inactive if the true solution has the same property. Hence, the known estimates for usual inverse problems are asymptotically recovered.

 

Ivanov regularization

Some time ago I picked up the phrase Ivanov regularization. Starting with an operator between to Banach spaces (say) one encounters the problem of instability of the solution of if has non-closed range. One dominant tool to regularize the solution is called Tikhonov regularization and consists of minimizing the functional . The meaning behind these terms is as follows: The term is often called discrepancy and it should be not too large to guarantee, that the “solution” somehow explains the data. The term is often called regularization functional and shall not be too large to have some meaningful notion of “solution”. The parameter is called regularization parameter and allows weighting between the discrepancy and regularization.

For the case of Hilbert space one typically chooses and gets a functional for which the minimizer is given more or less explicitly as

.

The existence of this explicit solution seems to be one of the main reasons for the broad usage of Tikhonov regularization in the Hilbert space setting.

Another related approach is sometimes called residual method, however, I would prefer the term Morozov regularization. Here one again balances the terms “discrepancy” and “regularization” but in a different way: One solves

That is, one tries to find an with minimal norm which explains the data up to an accuracy . The idea is, that reflects the so called noise level, i.e. an estimate of the error which is made during the measurment of . One advantage of Morozov regularization over Tikhonov regularization is that the meaning of the parameter is much clearer that the meaning of . However, there is no closed form solution for Morozov regularization.

Ivanov regularization is yet another method: solve

Here one could say, that one wants to have the smallest discrepancy among all which are not too “rough”.

Ivanov regularization in this form does not have too many appealing properties: The parameter does not seem to have a proper motivation and moreover, there is again no closed for solution.

However, recently the focus of variational regularization (as all these method may be called) has shifted from using norms, to the use of more general functionals. One even considers Tikhonov in an abstract form as minimizing

with a “general” similarity measure and a general regularization term , see e.g. the dissertation of Christiane Pöschl (which can be found here, thanks Christiane) or the works of Jens Flemming. Prominent examples for the similarity measure are of course norms of differences or the Kullback-Leibler divergence or the Itakura-Saito divergence which are both treated in this paper. For the regularization term one uses norms and semi-norms in various spaces, e.g. Sobolev (semi-)norms, Besov (semi-)norms, the total variation seminorm or norms.

In all these cases, the advantage of Tikhonov regularization of having a closed form solution is not there anymore. Then, the most natural choice would be, in my opinion, Morozov regularization, because one may use the noise level directly as a parameter. However, from a practical point of view one also should care about the problem of calculating the minimizer of the respective problems. Here, I think that Ivanov regularization is important again: Often the similarity measure is somehow smooth but the regularization term is nonsmooth (e.g. for total variation regularization or sparse regularization with -penalty). Hence, both Tikhononv and Morozov regularization have a nonsmooth objective function. Somehow, Tikhonov regularization is still a bit easier, since the minimization is unconstrained. Morozov regularization has a constraint which is usually quite difficult to handle. E.g. it is usually difficult (is it probably even ill posed?) to project onto the set defined by . Ivanov regulaization has a smooth objective functional (at least if the similarity measure is smooth) and a constraint which is usually somehow simple (i.e. projections are not too difficult to obtain).

Now, I found, that all thee methods, Tikhonov, Morozov and Ivanov regularizazion are all treated in the book “Theory of linear ill-posed problems and its applications” by V. K. Ivanov,V. V. Vasin and Vitaliĭ Pavlovich Tanana in section 3.2, 3.3 and 3.4 respectively. Ivanov regularization goes under the name “method of quasi solutions” (section 3.2) and Morozov regularization is called “Method of residual”(section 3.4). Well, I think I should read these sections a bit closer now…