# Inverse Problems via the “Generalized Collage Theorem” for Vector-Valued Lax-Milgram-Based Variational Problems

Authors: H. Kunze; D. La Torre; K. Levere; M. Ruiz Galán
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We present an extended version of the Generalized Collage Theorem to deal with inverse problems
for vector-valued Lax-Milgram systems. Numerical examples show how the method works in
practical cases.


---

## Body

## 1. Inverse Problems via the Collage Theorem

In recent years a great deal of attention has been paid to the inverse problems in distributed systems, that is, the determination of unknown parameters in the functional form of the governing model of the phenomenon under study [1–4]. The literature is rich in papers studying ad hoc methods to address ill-posed inverse problems by minimizing a suitable approximation error along with utilizing some regularization techniques [5–7].Many inverse problems may be recast as the approximation of a target elementx in a complete metric space (X,d) by the fixed point x¯ of a contraction mapping T:X→X. Thanks to a simple consequence of Banach’s fixed point theorem known as theCollage Theorem, most practical methods of solving the inverse problem for fixed point equations seek an operator T for which thecollage distanced(x,Tx) is as small as possible.Theorem 1 (“Collage Theorem” [8]).
Let(X,d) be a complete metric space and T:X→X a contraction mapping with contraction factor c∈[0,1). Then, for any x∈X, (1)dx,x¯≤11-cdx,Tx,where x¯ is the fixed point of T.This vastly simplifies this type of inverse problem as it is much easier to estimated(x,Tx) than to find the fixed point x¯ and then compute d(x,x¯). One now seeks a contraction mapping T that minimizes the so-calledcollage errord(x,Tx), in other words, a mapping that sends the target x as close as possible to itself. This is the essence of the method ofcollage coding which has been the basis of most, if not all, fractal image coding and compression methods. Barnsley [8, 9] was the first to see the potential of using the Collage Theorem above for the purpose offractal image approximation andfractal image coding. In practical applications, from a family of contraction mappings Tλ, λ∈Λ⊂Rn, one wishes to find the parameter λ¯ for which the approximation error d(x,x¯λ) is as small as possible. In practice the feasible set is often taken to be Λc=λ∈Rn:0≤cλ≤c<1 which guarantees the contractivity of Tλ for any λ∈Λc. A difference between the “collage” approach and the one based on Tikhonov regularization is the following: in the collage approach, the constraint λ∈Λc guarantees that Tλ is a contraction and, therefore, replaces the effect of the regularization term in the Tikhonov approach (see [4, 7]). The collage approach works well for low-dimensional parametrization in particular, while Tikhonov regularization is a fundamentally nonparametric methodology. The collage-based inverse problem can be formulated as an optimization problem as follows: (2)minλ∈Λc⁡dx,Tλx.This is a nonlinear and nonsmooth optimization model that can often be reduced to a quadratic optimization program. Several algorithms can be used to solve it including penalization methods and particle swarm ant colony techniques.This method ofcollage coding may be applied in other situations where contractive mappings are encountered. These ideas have been extended to inverse problems for Initial Value Problems (IVP) in [10]. In this setting, the contractive Picard operator plays the role of T and the space X contains continuous and appropriately bounded functions on a closed interval of observation. Given a target function, perhaps the interpolation of observational data points, the Collage Theorem can be applied to find the Picard operator within a prescribed class that minimizes the collage distance. We have applied this technique to inverse problems involving several families of differential equations and application to different areas (see [10–15]).Example 2.
We present the results to an IVP inverse problem solved using collage coding, Tikhonov regularization, and the Landweber-Fridman method. Consider the following steady-state heat equation onΩ¯=[0,1]:(3)ddxκxdudxx=-fx,inΩ=0,1,u0=0,u1=0,where κ(x) is the variable thermal diffusivity of the medium at x∈Ω, f(x) represents a heat source or sink at each x∈Ω, and u(x) denotes the temperature at x∈Ω. The inverse problem we look at is to estimate the variable thermal diffusivity κ(x) given r uniformly distributed values of u(x), with low-amplitude Gaussian noise added, and the forcing function f(x). For this example, we assume that u(x)=4x(1-x) and that f(x)=96x3+12x2+48x-8, corresponding to κ(x)=κTrue(x)=3x3+2x2+4x+1. Morozov’s discrepancy principle was used to find the value of the Tikhonov regularization parameter, with our discrepancy below a tolerance level of 10-8. Table 1 presents the results; the subscripts indicate the method used to solve the inverse problem.Table 1
Recovered diffusivity using collage coding, Tikhonov regularization, and Landweber-Fridman iteration, withr being the number of uniformly distributed sample points in [0,1], ϵ being the amplitude of the relative noise added, and the true value of κ(x)=1+4x+2x2+3x3.
r
ϵ
κ
collage
(
x
)
κ
collage
-
κ
True
L
2
(
Ω
)
10
0
1.0145
+
3.7757
x
+
2.7627
x
2
+
2.4460
x
3
0.00222
0.01
1.0129
+
3.7815
x
+
2.7685
x
2
+
2.4525
x
3
0.00295
0.1
0.9971
+
3.8350
x
+
2.8023
x
2
+
2.5362
x
3
0.00175
15
0
1.0145
+
3.7757
x
+
2.7627
x
2
+
2.4460
x
3
0.00152
0.01
1.0186
+
3.7915
x
+
2.7777
x
2
+
2.4619
x
3
0.00276
0.1
1.0578
+
3.9525
x
+
2.8989
x
2
+
2.6151
x
3
0.00878
r
ϵ
κ
Tikhonov
(
x
)
κ
Tikhonov
-
κ
True
L
2
(
Ω
)
10
0
1.2496
+
4.3996
x
-
4.2951
x
2
+
10.924
x
3
0.65853
0.01
1.2489
+
4.3982
x
-
4.3003
x
2
+
10.930
x
3
0.65772
0.1
1.2428
+
4.3863
x
-
4.3472
x
2
+
10.986
x
3
0.65165
15
0
1.0434
+
6.6156
x
-
9.5908
x
2
+
14.118
x
3
0.59133
0.01
1.0397
+
6.6132
x
-
9.5858
x
2
+
14.054
x
3
0.58914
0.1
1.0351
+
6.6057
x
-
9.5614
x
2
+
14.022
x
3
0.57156
r
ϵ
κ
Landweber
(
x
)
κ
Landweber
-
κ
True
L
2
(
Ω
)
10
0
1.2496
+
4.3996
x
-
4.2951
x
2
+
10.924
x
3
0.65853
0.01
1.2490
+
4.3932
x
-
4.2856
x
2
+
10.921
x
3
0.65812
0.1
1.2441
+
4.3362
x
-
4.2004
x
2
+
10.899
x
3
0.65663
15
0
1.0469
+
6.6156
x
-
9.5908
x
2
+
14.118
x
3
0.59133
0.01
1.0460
+
6.6133
x
-
9.5758
x
2
+
14.105
x
3
0.59103
0.1
1.0377
+
6.5920
x
-
9.4409
x
2
+
13.993
x
3
0.58968In a manner analogous to the Collage Theorem we have also formulated a Generalized Collage Theorem for solving Boundary Value Problems (BVP), replacing the minimization of the true error by the minimization of something akin to the collage distance. In place of Banach’s fixed point theorem for contraction maps on a complete metric space, we have appealed to the Lax-Milgram representation theorem.These results have been extended to a wider class of elliptic equations problems in [16, 17], by considering not only Hilbert but also reflexive Banach spaces and even replacing the primal variational formulation of such a problem with a more general constrained variational one. Let us mention that this kind of formulation arises, for instance, when the boundary constraints are weakly imposed.The paper is organized as follows. Section2 is concerned with an extension of theCollage Theorem stated in [16, Corollary 4.2] to a finite-dimensional vector-valued context, as well as a discretization scheme based on the use of suitable Schauder bases. Section 3 presents three different numerical examples which show how to solve inverse problems for systems of elliptic differential equations.


## 2. Vector-Valued Lax-Milgram and the Inverse Problem

In this section we deal with a Lax-Milgram theorem stated in terms of a system of suitable variational equations and with a collage type result that follows from it. We refer to [18–21] for some recent vectorial versions of the Lax-Milgram theorem and some applications to the study of mixed variational equations.The first result is the following vector-valued version of the Lax-Milgram theorem, which is a direct consequence of the characterization of the solvability of systems with infinitely many variational equations given in [22, Theorem 3.2]—specifically of its finite-dimensional case [22, Corollary 4.6]—and of the fact that if N≥1, E, F1,…,FN are real vector spaces, a1:E×F1→R,…,aN:E×FN→R are bilinear forms, and y1∗:F1→R,…,yN∗:FN→R are linear forms such that the system (4)x∈Ewithy1∗=a1x,·⋮yN∗=aNx,·admits a solution, then such a solution is unique if, and only if, the corresponding homogeneous problem has one and only one solution.Given a real normed spaceG, we write G∗ for its topological dual space.Theorem 3.
Suppose thatE is a real reflexive Banach space, N≥1, F1,…,FN are real Banach spaces, and a1:E×F1→R,…,aN:E×FN→R are continuous bilinear forms. Then for all y1∗∈F1∗,…,yN∗∈FN∗ there exists a unique x0∈E such that (5)y1∗=a1x0,·⋮yN∗=aNx0,·if, and only if, (6)x∈E,y1∗=a1x0,·⋮yN∗=aNx0,·⟹x=0and there exists ρ>0 satisfying (7)y1,…,yN∈F1×⋯×FN⟹ρ∑k=1Nyk≤∑k=1Nak·,yk.Moreover, if these equivalent conditions hold and x0∈E is the unique solution, then (8)x0≤1ρmaxk=1,…,N⁡yk∗.The aforementioned generalization of the collage type result [16, Corollary 4.2] for a finite number of variational equations is stated in these terms.Corollary 4.
LetE be a real reflexive Banach space, let N≥1, let F1,…,FN be real Banach spaces, let y1∗∈F1∗,…,yN∗∈FN∗, and let Λ be a nonempty set such that for all λ∈Λ there exist N continuous bilinear forms a1λ:E×F1→R,…,aNλ:E×FN→R and ρλ>0 with (9)x∈E,y1∗=a1λx0,·⋮yN∗=aNλx0,·⟹x=0,y1,…,yN∈F1×⋯×FN⟹ρλ∑k=1Nyk≤∑k=1Nakλ·,yk.Let us also suppose that, for all λ∈Λ, xλ∈E is the unique solution of the variational system (10)x∈E,y1∗=a1λx,·⋮yN∗=aNλx,·.Then for each x0∈E and for all λ∈Λ the inequality (11)xλ-x0≤1ρλmaxk=1,…,N⁡yk∗-akλx0,·is valid.Proof.
The unisolvency and continuous dependence on the initial data of the solution in Theorem3 imply the announced result. Indeed, let λ∈Λ and notice that xλ-x0 is a solution of the system of variational equations (12)x∈E,y1∗-a1λx0,·=a1λx,·⋮yN∗-aNλx0,·=aNλx,·.Then, in view of Theorem 3, we conclude that (13)xλ-x0≤1ρλmaxk=1,…,N⁡yk∗-akλx0,·.Let us observe that if one wants to approximate the solutionx0 in the sense of the collage distance, that is, minimize {xλ-x0:λ∈Λ}, according to Corollary 4, it suffices to minimize (14)1ρλmaxk=1,…,N⁡yk∗-akλx0,·:λ∈Λ,although if (15)ρ≔infλ∈Λ⁡ρλ>0,then we only need to minimize (16)maxk=1,…,N⁡yk∗-akλx0,·:λ∈Λ.Under such an assumption, ρ>0, and suppose that each space Fk  (k=1,…,N) has a Schauder basis {Υki}i≥1, in such a way that if {Υki∗}i≥1 denotes its sequence of biorthogonal functionals, then the nonrestrictive condition (17)M≔maxk=1,…,Nsupi≥1⁡Υki∗<∞holds. In order to discretize our optimization problem, let us also assume that E admits a Schauder basis {Θi}i≥1 and define for each n≥1 and k=1,…,N(18)En≔span⁡Θ1,…,Θn,⁡Fkn≔span⁡Υk1,…,Υknand let Pn be the nth-projection of E onto En; that is, for all x∈E, (19)Pnx≔∑i=1nΘi∗xΘi.We also suppose that for all λ∈Λ, k=1,…,N, and n≥1(20)x∈En,0=a1λx,·⋮0=aNλx,·⟹x=0,and there exists ρλn>0 such that (21)y1,…,yN∈F1n×⋯×FNn⟹ρλn∑k=1Nyk≤∑k=1Nakλ·,yk.Then, Theorem 3 guarantees the existence of unique xjn∈En such that (22)y1,….yN∈F1n×FnN⟹y1∗y1=a1xjn,y1⋮yN∗yN=aNxjn,yN.Corollary 4, when applied to this vector-valued variational problem, implies (23)xλn-Pnx0≤Mρλnmaxk=1,…,N⁡∑i=1ny0∗Υki-akλPnx0,Υki,and if (24)γ≔supλ∈Λ,n≥1⁡ρλn>0,then it suffices to minimize (25)φnj≔maxk=1,…,N⁡∑i=1ny0∗Υki-akλPnx0,Υkior equivalently the discrete objective function (26)Φnj≔∑k=1N∑i=1ny0∗Υki-akλPnx0,Υki2,which is easier to minimize.


## 3. Numerical Examples

In this section we present three different numerical examples.Example 1.
We consider the linear system(27)-ddxκxdudx+Au=fx,0<x<1,u0=0,u1=0,with(28)κx=5+2x,u=u1u2,A=3,fx=f1xf2x=8x1.We solve the linear system, sample each solution component at M uniformly distributed data points in [0,1], add relative noise of ɛ, and fit 6th-degree polynomials to the resulting data to produce a target solution u~. Figure 1 shows the numerical solution u and the target functions u~i with M=20 and ϵ=0.05. We consider the inverse problem: Given u~ and f(x), approximate κ(x) and the coefficient A such that the resulting system admits u~ as an approximate solution. We set(29)κx=∑i=1Nλixi.With ξii=1n equal to the n-dimensional “hat basis” of [0,1], for various values of M, noise ɛ, κ degree N, and basis dimension n, we construct the objective function in (26) and minimize it to find λ=(A,λ0,…,λN). The results are presented in Table 2.Table 2
Recovered parameter values for Example1. True values are λ=(3,5,2,0).
M
n
ε
Recoveredλ
N
=
1
N
=
2
10
20
0
(3.0000, 4.9999, 2.0002)
(3.0000, 4.9999, 2.0001, 0.0001)
10
20
0.01
(2.9628, 4.9411, 2.1213)
(3.0259, 4.9717, 1.7660, 0.3278)
10
20
0.03
(2.9108, 4.8174, 2.3647)
(3.0879, 4.9132, 1.2916, 0.9902)
10
20
0.05
(2.8898, 4.6858, 2.6078)
(3.1637, 4.8520, 0.8091, 1.6614)
30
40
0
(3.0001, 4.9998, 2.0003)
(3.0001, 4.9998, 2.0002, 0.0001)
30
40
0.01
(2.9250, 4.9758, 2.0816)
(3.0265, 5.0203, 1.5585, 0.4778)
30
40
0.03
(2.8888, 4.8936, 2.2519)
(3.1537, 5.0431, 0.6498, 1.4600)
30
40
0.05
(3.0083, 4.7664, 2.4290)
(3.3781, 5.0415, −0.2832, 2.4671)Figure 1
For Example1: (a) the numerical solution u, (b) the noised target u~1, and (c) the noised target u~2, with 5% relative noise added.
(a)
(b)
(c)Example 2.
We consider the coupled system(30)-ddxκxdudx+Lu=fx0<x<1,u0=0,u1=0,with(31)κx=5+2x,L=02-30,fx=f1xf2x=x-3/51-x-3/5.Note that the forcing functions f1(x) and f2(x) are not Hilbertian, living instead in W01,3/2(0,1), for example. We work in the reflexive framework of Section 2. (In [16], we observed that the Hilbert space solution framework failed to work for a single equation with forcing function f1(x).) Following [23, Proposition 4.8], we can construct a Schauder basis {en}n∈N in the Sobolev space W01,p(0,1) by integrating the Haar system of Lp(0,1).
The BVP has singularities atx=0 and x=1, since at each endpoint one of f1(x) or f2(x) is undefined. The forward problem can be solved numerically by using collocation techniques. We use COMSOL to solve it. Figure 2 presents the numerical solution. Next, we represent the solution in the subspace E511 generated by the first 511 terms of the Schauder basis; call these representations u~1(x) and u~2(x). We consider the inverse problem: find K(x) such that u~ is admitted as an approximate solution to (30) with κ(x) replaced by K(x).
We solve the inverse problem by constructing the objective function in (26) with n=511, ξi equal to the ith element of the Schauder basis, and K(x)=∑i=0N‍λixi. With these choices, we have that (32)a1λu~,ξi=∫01Kxξi′xu~1′xdx+2∫01u~2xξixdx,a2λu~,ξi=∫01Kxξi′xu~2′xdx-3∫01u~1xξixdx,T01λξi=∫01fixξixdx.When N=1 upon minimizing the objective function we obtain, to four decimal places, λ0=5.0893 and λ1=1.7920. When N=2, we find λ0=5.0698, λ1=1.9840, and λ2=-0.1929.Figure 2
The numerical solution at 511 points for Example2.Example 3.
We consider the 2D linear system(33)-∇·κx,y∇u+Au=fx,y,0<x<1,0<y<1,u0,y=0,u1,y=0,ux,0=0,ux,1=0,with(34)κx=10+2x+3y0010+2x+3y,u=u1u2,A=-13-24,fx=f1xf2x,where f1(x,y) and f2(x,y) have been chosen so that the actual solution to the system is(35)u=14xy1-x1-y18xy1-x1-y.Analogous to the process followed in Example 1, we sample each solution component at M×M uniformly distributed data points in [0,1]×[0,1] and add relative noise of ɛ to each of these data points. A target solution u~ is constructed using these data points together with our basis functions, ξij (hexagonal-based pyramids in this 2D case):(36)u1x,y=∑i=1M∑j=1Mu1ijξij,u2x,y=∑i=1M∑j=1Mu2ijξij,fori,j=1,…,M.
We consider the inverse problem: Givenu~, A, and f(x,y), approximate κ(x,y) such that the resulting system admits u~ as an approximate solution. We set(37)κx,y=∑i=0p∑j=0qλijxiyj∑i=0p∑j=0qγijxiyj.For various values of M, noise ɛ, κ degree 1, and basis dimension n=M, we construct the objective function in (26) and minimize it to find λij,γij, for i=1,…,p and j=1,…,q. The results are presented in Table 3.Table 3
Recovered parameter values for Example3. True values are λ=γ=(10,2,3,0).
M
ε
Recoveredλ
Recoveredγ
10
0
(9.9282, 1.9728, 2.9134, 0.0068)
(9.9242, 1.9264, 2.9625, −0.0068)
10
0.01
(9.9268, 1.9641, 2.9096, −0.0097)
(9.9233, 1.9257, 2.9594, −0.0087)
10
0.03
(9.9246, 1.9653, 2.9065, −0.0157)
(9.9219, 1.9218, 2.9573, −0.0127)
10
0.05
(9.9232, 1.9685, 2.7664, −0.0221)
(9.9213, 1.7821, 2.9567, −0.0170)
20
0
(9.9581, 1.9899, 2.9921, −0.0018)
(9.9574, 1.9919, 2.9878, 0.0001)
20
0.01
(9.9575, 1.9886, 2.9780, 0.0002)
(9.9565, 1.9827, 2.9867, −0.0018)
20
0.03
(9.9481, 1.9814, 2.9786, 0.0065)
(9.9456, 1.9241, 2.9801, 0.0063)
20
0.05
(9.9378, 1.9682, 2.9141, 0.0156)
(9.9228, 1.9152, 2.9680, 0.0153)
30
0
(10.004, 1.9954, 2.9904, 0.0000)
(9.9954, 1.9984, 2.9957, 0.0000)
30
0.01
(9.9796, 1.9965, 2.9809, −0.0008)
(9.9761, 1.9830, 3.0148, −0.0008)
30
0.03
(9.9663, 2.0146, 3.0216, −0.0059)
(9.9656, 1.9816, 2.9944, −0.0059)
30
0.05
(9.9643, 2.0533, 2.9785, −0.0220)
(9.9640, 2.0321, 3.0554, −0.0219)



---

*Source: 764643-2015-07-01.xml*