{'fraction_non_alphanumeric': 0.05417433097964754, 'fraction_numerical': 0.014596807690025514, 'mean_word_length': 4.125912408759124, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-Parameter Tikhonov Regularization -- An Augmented Approach

We study multi-parameter regularization (multiple penalties) for solving linear inverse problems to promote simultaneously distinct features of the sought-for objects. We revisit a balancing principle for choosing regularization parameters from the viewpoint of augmented Tikhonov regularization, and derive a new parameter choice strategy called the \textit{balanced discrepancy principle}. A priori and a posteriori error estimates are provided to theoretically justify the principles, and numerical algorithms for efficiently implementing the principles are also provided. Numerical results on denoising are presented to illustrate the feasibility of the balanced discrepancy principle.

objects exhibit distinct multiple features/structures. However, one single penalty generally favors one feature over others, and thus unsuitable for promoting multiple distinct features. For example, total variation (TV) is well suited to reconstructing piecewise constant structures, however, it results in significant staircases in gray regions. One may improve TV-reconstruction by introducing an additional penalty, say L 1 norm of ∆u where ∆ is the Laplacian operator. Hence, a reliable recovery of several distinct features naturally calls for multiple penalties, and it is not surprising that the idea of multi-parameter regularization has been pursued earlier. For instance, in [9] the authors proposed a model to preserve both flat and gray regions in natural images by combining TV with Sobolev smooth penalty. We refer interested readers to [17,15] (imaging), [19] (microarray data analysis), [18] (geodesy) and [13] (machine learning) for other interesting applications.
However, a general theory of multi-parameter regularization remains under development [1,4,13,7]. In [1] the L-hypersurface was suggested for determining regularization parameters for finite-dimensional linear systems, but without any theoretical justification. In [4], a multi-resolution analysis for ill-posed linear operator equations was analyzed, and some convergence results were established. Lu et al. [13] discussed the discrepancy principle for Hilbert space scales, and derived some error estimates. However, the parameter selection is vastly nonunique due to lack of constraints and thus not directly applicable in practice, for which later a quasi-optimality criterion was suggested [14]. Recently, the authors [7] investigated the discrepancy principle and a balancing principle for general convex variational models. However, the nonuniqueness of the discrepancy principle remains unresolved, and further, there is still no theory for the balancing principle for multi-parameter regularization.
The present work extends our earlier work [7], and includes the following essential contributions. We first revisit the balancing principle in [7] from the viewpoint of augmented Tikhonov regularization [12], and established the equivalence. Then we derive a novel hybrid principle, the balanced discrepancy principle, by incorporating constraints into the augmented approach, which partially resolves the nonuniqueness issue. Further, a priori and a posterior error estimate are derived for both principles. The estimate in Theorem 2.4 was stated in [7] without a proof. Finally, we develop efficient algorithms for implementing these principles, and briefly discuss their properties.
The rest of the paper is organized as follows. In §2, we derive the balancing principle and the new hybrid principle, and develop relevant error estimates. In §3 we discuss efficient implementations of the two principles. Finally, we provide some numerical results to illustrate the hybrid principle in §4.
2. An augmented approach. The augmented Tikhonov (a-Tikhonov) regularization is one principled framework for choosing regularization parameters [12]. Here we describe the augmented approach for multi-parameter models, and derive the balancing principle and a novel balanced discrepancy principle.
2.1. Derivation of the principles.
The functional J(u, τ, λ) is derived under the assumption that the scalars λ i and τ have Gamma distributions with known parameter pairs. The parameter pairs (α, β) and (α 0 , β 0 ) are related to the shape parameters in the statistical priors on the prior precision λ i and noise precision τ , respectively. The special case β 0 = β = 0 is known as noninformative prior and customarily adopted in practice. Hence we focus our derivation on this case. Upon letting η i = λi τ , the necessary optimality condition of any minimizer (u δ η , λ i , τ ) to the a-Tikhonov functional J(u, τ, {λ i }) is given by .
The optimality system (2.2) reveals the mechanism of the augmented approach: it selects an optimal regularization parameter η in the model (1.2) by balancing the penalty ψ with the fidelity φ, from which the term balancing principle follows. We note the term balancing principle here should not be confused with Lepskii's principle, which is also sometimes called a balancing principle [16]. The Lepskii's principle does require a knowledge of noise level. Next we characterize (2.2) using the value function F (η) [8] defined by The function F (η) is continuous, and it is almost everywhere differentiable, cf. Lemma 2.1. We denote by F ηi the partial derivative of F (η) with respect to η i . The proof is analogous to [8], and hence omitted. Lemma 2.1. The function F (η) is monotone and concave, and hence almost everywhere differentiable. Further, if it is differentiable, then there holds F ηi (η) = ψ i (u δ η ). Next we provide an alternative characterization of (2.2). First we define the function Φ γ (η) by The necessary optimality condition for Φ γ (η), provided that F (η) is differentiable, reads which, upon noting Lemma 2.1, is equivalent to Solving the system with respect to η i yields η i = 1 γ φ(u δ η ,g δ ) ψi(u δ η ) . Hence, the optimality system of the function Φ γ coincides with that of the functional J(u, τ, λ). In summary, we have shown our first main result. Proposition 2.1. Let the value function F (η) be differentiable. Then all critical points of the function Φ γ are solutions to system (2.2).
Remark 2.1. Two remarks on the function Φ γ are in order. First, it is very flexible in that the free-parameter γ may be calibrated to achieve specific desirable properties. Second, by the concavity in Lemma 2.1, F (η) is continuous and thus the problem of minimizing Φ γ over any bounded and closed region in R 2 + is well defined. These observations remain valid for a general fidelity. 2.1.2. Balanced discrepancy principle. To solve stably and accurately problem (1.1), one should use all prior information, e.g., the noise level φ(u † , g δ ) = c := 1 2 c 2 m δ 2 for some c m ≥ 1, and other relevant knowledge, whenever it is available. This can be realized by incorporating constraints into the augmented approach, and then deriving the corresponding optimal system. For instance, for the constraint φ(u, g δ ) ≤ c, the Lagrangian approach gives the following a-Tikhonov functional where the unknown scalar µ ≥ 0 is the Lagrange multiplier for the inequality constraint φ(u, g δ ) ≤ c. Its optimality system reads Hence the constraint φ(x, g δ ) ≤ c and the balancing principle are both fulfilled: In the case of one single penalty, identity (2.4) does not provide any additional constraint since the multiplier µ is also unknown. We observe that the active constraint, i.e., Ku δ η − g δ = c m δ, is exactly the discrepancy principle [5]. The constraint is active under certain conditions [10]. Nonetheless, in case of multiple penalties, the discrepancy principle alone cannot uniquely determine η. Hence we include also system (2.4), which might help resolve the nonuniqueness issue. Upon simplification, this yields a new hybrid principle The principle can be interpreted as the augmented approach with the constraint {u : Ku − g δ = c m δ}, c m ≥ 1. Hence it integrates the classical discrepancy principle Ku δ η −g δ = c m δ with the balancing principle, and we shall name the new rule (2.5) balanced discrepancy principle. One noteworthy feature of (2.5) is that it does not involve the free parameter γ.
2.2.1. Balanced discrepancy principle. In this part, we discuss the consistency and an a priori error estimate for the hybrid principle (2.5). To this end, we make the following assumption.
Assumption 2.1. There exists a τ -topology such that for any η > 0, the functional J η (u) is coercive and its level set {u ∈ C : J η (u) ≤ c} for any c > 0 is compact in τ -topology, and the functionals φ and ψ i are τ lower semi-continuous.
Remark 2.2. The τ -topology is naturally induced by the penalty functional ψ, and it is not arbitrarily in order to ensure the lower semicontinuity.
Now we can state a consistency result. The line of proof is standard [7], and thus omitted.
Next we have the following convergence rate, i.e., the distance between the approximation u δ η and the true solution u † (in Bregman distance [3]) in terms of the noise level δ. We denote the subdifferential of a convex functional ψ(u) at u † by ∂ψ(u † ), i.e., Now we can state a convergence rates result. Theorem 2.2. Let the exact solution u † satisfy the source condition: for any t ∈ [0, 1], there exists . Then for any η * determined by the principle (2.5) and with t * = t(η * ) = Proof. The line of proof is again well known, but we include a sketch for completeness. In view of the minimizing property of the approximation u δ η * and the constraint Ku δ From this and the Cauchy-Schwarz inequality, we deduce This shows the desired estimate.
Remark 2.4. In Theorem 2.2, the order of convergence relies solely on the constraint Ku δ η − g δ = c m δ, while the weight t * in the estimate is determined by the balancing principle. Hence the reduced system (2.4) does help resolve the vast nonuniqueness issue in the discrepancy principle.

Balancing principle in Hilbert spaces.
We derive a posteriori estimates for the balancing principle Φ γ (2.3), i.e., the distance between the approximation u δ η * and the exact solution u † in terms of the noise level δ = g δ − g † and the realized residual δ * = Ku δ η * − g δ etc. We first treat quadratic regularizations ψ i (u) = 1 2 L i u 2 with linear operators L i fulfilling ker(L i ) ∩ ker(K) = {0}, i = 1, 2, and each induces a semi-norm. One typical choice is that ψ 1 and ψ 2 impose the L 2 -norm and higher-order Sobolev smoothness, e.g., ψ 1 (u) = 1 2 u 2 L 2 and ψ 2 (u) = 1 2 u 2 H 1 . We shall utilize a weighted (semi-)norm · t defined by where the weight t ≡ t(η) ∈ [0, 1] is defined as before, and by Q t = tL * We note that the adjoint K * (and hence K * t ) depends on the value t.
Theorem 2.3. Let µ ∈ (0, 1] be fixed, and the exact solution u † satisfy the source condition: for any t ∈ [0, 1], there exists a w t ∈ Y such that L t u † = ( K * t K t ) µ w t . Then for any parameter η * selected by , and bound the two terms separately. First we estimate the error u δ η − u η . It follows from the optimality conditions for u η and u δ η that Multiplying the identity with u η − u δ η and using the Cauchy-Schwarz and Young's inequalities give Next let s = η 1 + η 2 . Then we get Meanwhile, the minimizing property of η * to the rule Φ γ implies that for any η In particular, we may take η = δ 2 2µ+1 e and arrive at Next we estimate the approximation error u η − u † . To this end, we observe Consequently, we deduce from the source condition and the moment inequality [5] where the constant c depends only on the maximum of r s (t) = s s+t over [0, K t 2 ]. Further, we note the relation Hence, we deduce By combining these two estimates, we arrive at the desired inequality.

2.2.3.
Balancing principle in Banach space. Lastly, we turn to the balancing principle for general convex regularization ψ. We first recall the following technical lemma [11] for single convex regularization ψ. The first estimates the propagation error, and the second plays the role of a triangle inequality.
Lemma 2.2 ( [11]). Let the exact solution u † satisfy the following source condition: there exists a w ∈ Y such that K * w = ξ ∈ ∂ψ(u † ), and let ξ η = K * (g † − Ku η )/η. Then there hold Now we can state an estimate for the balancing principle (2.3) in Banach spaces. The estimate has been stated in [7] but without a proof.
Theorem 2.4. Let the exact solution u † satisfy the source condition: for any t ∈ [0, 1] there exists a w t ∈ Y such that K * w t = ξ t ∈ ∂ [t, 1 − t] t · ψ(u † ) . Then for every η * selected by (2.3) and with with t * = t(η * ) = η * 1 (δ) η * 1 (δ)+η * 2 (δ) , the following estimate holds Proof. For any t ∈ [0, 1], let ψ t (u † ) = [t, 1 − t] t · ψ(u † ) and ξ t ∈ ∂ψ t (u † ), with ξ t and w t being the subgradient and the representer in the source condition, respectively. By Lemma 2.2, we have that for η where ξ η = −K * (K(u η ) − g † )/s ∈ ∂ψ t (u η ) and s = η 1 + η 2 . It suffices to bound the terms involving Bregman distance. We first estimate the approximation error d ξt (u η , u † ). To this end, observe by the minimizing property of the element u η , i.e., This inequality, the definition of d ξt (u η , u † ), the source condition and Lemma 2.2 implies Next we estimate the term d ξη (u δ η , u η ). In view of Lemma 2.2, we have Meanwhile, the minimizing property of η to the rule Φ γ gives that for any η Upon letting η = δe and combining the preceding two inequalities, we get Now combining these three estimates gives the desired assertion. The a posteriori error estimate in Theorem 2.4 coincides with that for the a priori choice, e.g., η ∼ δe, provided that the realized discrepancy δ * is of the same order with the exact noise level δ.
3. Numerical algorithms. Now we describe algorithms for numerically realizing the hybrid principle and the balancing principle, i.e., Broyden's method and fixed-point algorithm, and discuss their properties.

Broyden's method.
In practice, the application of the hybrid principle invokes solving the nonlinear system (2.5), which is nontrivial due to its potential nonsmoothness and high degree of nonlinearity. We propose using Broyden's method [2] for its efficient solution; see Algorithm 1 for a complete description.
For the numerical treatment, we reformulate system (2.5) equivalently as The system is numerically more amenable than (2.4). In Algorithm 1, the Jacobian J 0 can be approximated by finite difference.
Step 7 represents the celebrated Broyden update. The stopping criterion is based on monitoring the residual norm T(η) . Note that each iteration involves evaluating T(η), which in turn incurs solving one optimization problem of minimizing J η . Our experiences indicate that it converges fast and steadily, however, a convergence analysis is still missing.

8:
Check the stopping criterion. 9: end for 10: Output the solution 3.2. Fixed point algorithm. In this part, we describe a fixed point algorithm for computing the minimizer of the rule Φ γ . The algorithm was originally introduced in [7], but without any analysis. One basic version is listed in Algorithm 2, where the subscript −i refers to the index different from i. The stopping criterion at Step 4 can be based on monitoring the relative change of the regularization parameter η or the inverse solution u δ η .
4: Check the stopping criterion.
We shall analyze Algorithm 2. First, we introduce a fixed point operator T by We shall also need the next result [8, Lem. 2.1 and Cor. 2.3]. Lemma 3.1. The function ψ i (u δ η ) is monotonically decreasing in η i , and the following relations hold We have the next monotone result for the fixed point operator T. Proposition 3.1. Let the function F (η) be twice differentiable. Then the map T(η) is monotone if Proof. Let A(η) = φ + η 2 ψ 2 and B(η) = φ + η 1 ψ 1 . By Lemma 3.1, there hold With the help of these two relations, we deduce where we have used the relation ∂F ∂η2 = ψ 2 from Lemma 2.1. Similarly, we have ∂ ∂η 2 Therefore, the Jacobian ∇T of the operator T is given by Now Lemma 3.1 implies that − ∂ψi ∂ηi ≥ 0. Hence, it suffices to show that the determinant |∇T| > 0. By Lemma 2.1, the identity ∂ψ1 ∂η2 = F η1η2 = ∂ψ2 ∂η1 holds, and thus |∇T| is given by Hence, the nonnegativity of |∇T| follows from the assumption This concludes the proof.

Conclusions.
We have studied multi-parameter regularization from the viewpoint of augmented Tikhonov regularization, and shown a unified way to derive the balancing principle and balanced discrepancy principle. A priori and a posteriori error estimates for the principles were provided, and efficient numerical algorithms (Broyden's method and fixed point algorithm) were presented and discussed. Numerical results were presented to illustrate the feasibility of the balanced discrepancy principle.