Examples of Saturated Convergence Rates for Tikhonov Regularization

Tikhonov regularization is one of the most popular methods for solving linear operator equations of the first kind Au = f with bounded operator, which are ill-posed in general (Fredholm's integral equation of the first kind is a typical example). For problems with inexact data (both the operator and the right-hand side) the rate of convergence of regularized solutions to the generalised solution u ₊ (i.e.the minimal-norm least-squares solution) can be estimated under the condition that this solution has the source form: u ₊ im(A*A). It is well known that for Tikhonov regularization the highest-possible worst-case convergence rates increase with only for some values of , in general not greater than one. This phenomenon is called the saturation of convergence rate. In this article the analysis of this property of the method with a criterion of a priori regularization parameter choice is presented and illustrated by examples constructed for equations with compact operators.This revised version was published online in October 2005 with corrections to the Cover Date.     

Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill‐posed problems

One of the most successful methods for solving the least‐squares problem min_x∥Ax?b∥₂ with a highly ill‐conditioned or rank deficient coefficient matrix A is the method of Tikhonov regularization. In this paper, we derive the normwise, mixed and componentwise condition numbers and componentwise perturbation bounds for the Tikhonov regularization. Our results are sharper than the known results. Some numerical examples are given to illustrate our results. Copyright © 2010 John Wiley & Sons, Ltd.     

Approximate source conditions in Tikhonov–Phillips regularization and consequences for inverse problems with multiplication operators

The object of this paper is threefold. First, we investigate in a Hilbert space setting the utility of approximate source conditions in the method of Tikhonov–Phillips regularization for linear ill‐posed operator equations. We introduce distance functions measuring the violation of canonical source conditions and derive convergence rates for regularized solutions based on those functions. Moreover, such distance functions are verified for simple multiplication operators in L²(0, 1). The second aim of this paper is to emphasize that multiplication operators play some interesting role in inverse problem theory. In this context, we give examples of non‐linear inverse problems in natural sciences and stochastic finance that can be written as non‐linear operator equations in L²(0, 1), for which the forward operator is a composition of a linear integration operator and a non‐linear superposition operator. The Fréchet derivative of such a forward operator is a composition of a compact integration and a non‐compact multiplication operator. If the multiplier function defining the multiplication operator has zeros, then for the linearization an additional ill‐posedness factor arises. By considering the structure of canonical source conditions for the linearized problem it could be expected that different decay rates of multiplier functions near a zero, for example the decay as a power or as an exponential function, would lead to completely different ill‐posedness situations. As third we apply the results on approximate source conditions to such composite linear problems in L²(0, 1) and indicate that only integrals of multiplier functions and not the specific character of the decay of multiplier functions in a neighbourhood of a zero determine the convergence behaviour of regularized solutions. Copyright © 2005 John Wiley & Sons, Ltd.     

Tikhonov regularization of nonlinear III-posed problems in hilbert scales

In this paper we consider nonlinear ill-posed problems F(x) = y ₀, where x and y ₀ are elements of Hilbert spaces X and Y, respectively. We solve these problems by Tikhonov regularization in a Hilbert scale. This means that the regularizing norm is stronger than the norm in X. Smoothness conditions are given that guarantee convergence rates with respect to the data noise in the original norm in X. We also propose a variant of Tikhonov regularization that yields these rates without needing the knowledge of the smoothness conditions. In this variant F is allowed to be known only approximately and X can be approximated by a finite-dimensional subspace. Finally, we illustrate the required conditions for a simple parameter estimation problem for regularization in Sobolev spaces.     

Fundamental Sets of Functions on Locally Compact Abelian Groups

Let G be a locally compact Abelian group, and let X be a compact set of G. Given a positive definite function ?: G × G → ? whose real part is continuous at neutral element of G, we research a necessary and sufficient setting for the linear span of the set {x ∈ X → ?(x ? y): y ∈ X} to be dense in C(X) in the topology of uniform convergence. The context treated that is abstract encompasses classical cases of the literature, while other examples are entirely new.     

A Modified Tikhonov Regularization for Linear Operator Equations

We construct with the aid of regularizing filters a new class of improved regularization methods, called modified Tikhonov regularization (MTR), for solving ill-posed linear operator equations. Regularizing properties and asymptotic order of the regularized solutions are analyzed in the presence of noisy data and perturbation error in the operator. With some accurate estimates in the solution errors, optimal convergence order of the regularized solutions is obtained by a priori choice of the regularization parameter. Furthermore, numerical results are given for several ill-posed integral equations, which not only roughly coincide with the theoretical results but also show that MTR can be more accurate than ordinary Tikhonov regularization (OTR).     

Finite-dimensional approximation of tikhonov regularized solutions of non-linear ill-posed problems

In this paper we consider non-linear ill-posed problems F(x)=y0 in a Hilbert space setting. We solve these problems with Tikhonov regularization combined with finite-dimensional approximation where the data y0 and the non-linear operator F are assumed to be known only approximately. Conditions are given that guarantee optimal convergence rates with respect to both, the data noise and the finite-dimensional approximation. Finally, we present some numerical results for parameter estimation problems that verify the theoretical results.     

Finite Groups Whose Second Maximal Subgroups are ℋ-QC-Subgroups

A group G is called an “?-QC-group” if for any element x of order 2 or 4 of G, ?x? ?y? = ?y? ?x? for all y in G. In this article, we investigate the structure of the groups G of the title. Suppose that G is non-2-closed and non-2-nilpotent, then it turns out that such a group is either S ₄ or a uniquely determined group of order 48 or A ₅ or SL(2,5). The corresponding problem for G 2-closed or 2-nilpotent is open but very difficult.     

Simplicity of Skew Group Rings of Abelian Groups

Necessary and sufficient conditions for simplicity of a general skew group ring A ?_σ G are not known. In this article, we show that a skew group ring A ?_σ G, of an abelian group G, is simple if and only if its centre is a field and A is G-simple. As an application, we show that a transformation group (X, G), where X is a compact Hausdorff space acted upon by an abelian group G, is minimal and faithful if and only if its associated skew group algebra C(X) ?_σ G is simple.     

On Galois Algebras Satisfying the Fundamental Theorem

Let B be a Galois algebra over a commutative ring R with Galois group G such that B ^H is a separable subalgebra of B for each subgroup H of G. Then it is shown that B satisfies the fundamental theorem if and only if B is one of the following three types: (1) B is an indecomposable commutative Galois algebra, (2) B = Re ⊕ R(1 ? e) where e and 1 ? e are minimal central idempotents in B, and (3) B is an indecomposable Galois algebra such that for each separable subalgebra A, V _B (A) = ?∑ _g∈G(A) J _g , and the centers of A and B ^G(A) are the same where V _B (A) is the commutator subring of A in B, J _g  = {b ∈ B | bx = g(x)b for each x ∈ B} for a g ∈ G, and G(A) = {g ∈ G | g(a) = a for all a ∈ A}.     

Crossing properties of graph reliability functions

Let G be a graph and p ϵ (0, 1). Let A(G, p) denote the probability that if each edge of G is selected at random with probability p then the resulting spanning subgraph of G is connected. Then A(G, p) is a polynomial in p. We prove that for every integer k ≥ 1 and every k‐tuple (m₁, m₂, … ,m_k) of positive integers there exist infinitely many pairs of graphs G₁ and G₂ of the same size such that the polynomial A(G₁, p) − A(G₂, p) has exactly k roots x₁ < x₂ < ··· < x_k in (0, 1) such that the multiplicity of x_i is m_i. We also prove the same result for the two‐terminal reliability polynomial, defined as the probability that the random subgraph as above includes a path connecting two specified vertices. These results are based on so‐called A‐ and T‐multiplying constructions that are interesting in themselves. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 206–221, 2000     

On Monomial Reduction and Polynomial Expressions with Respect to Binomial Ideals

Let I ? K[x ₁,…, x _n ] be an ideal and G be the reduced Gröbner basis of I with respect to lexicographic monomial order. We introduce the index of an expression of f ∈ K[x ₁,…, x _n ] with respect to G. A minimal expression is characterized as the one with zero G-index. In case where I is a binomial prime ideal, a new division algorithm with minimal and unique expression is presented. The application of our new method on benchmark polynomial systems cyclic-9 and cyclic-12 shows its superiority in comparison with the existing division algorithm.     

A New Characterization of A 10 by its Noncommuting Graph

Let G be a nonabelian group and associate a noncommuting graph ?(G) with G as follows: The vertex set of ?(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. In 1987, Professor J. G. Thompson gave the following conjecture.

Thompson's Conjecture. If G is a finite group with Z(G) = 1 and M is a nonabelian simple group satisfying N(G) = N(M), then G ? M, where N(G):={n ∈ ? | G has a conjugacy class of size n}.

In 2006, A. Abdollahi, S. Akbari, and H. R. Maimani put forward a conjecture (AAM's conjecture) in Abdollahi et al. (2006) as follows.

AAM's Conjecture. Let M be a finite nonabelian simple group and G a group such that ?(G) ? ? (M). Then G ? M.

In this short article we prove that if G is a finite group with ?(G) ? ? (A ₁₀), then G ? A ₁₀, where A ₁₀ is the alternating group of degree 10.     

Necessary and sufficient conditions for linear convergence of ℓ1‐regularization

Motivated by the theoretical and practical results in compressed sensing, efforts have been undertaken by the inverse problems community to derive analogous results, for instance linear convergence rates, for Tikhonov regularization with ℓ¹‐penalty term for the solution of ill‐posed equations. Conceptually, the main difference between these two fields is that regularization in general is an uncon strained optimization problem, while in compressed sensing a constrained one is used. Since the two methods have been developed in two different communities, the theoretical approaches to them appear to be rather different: In compressed sensing, the restricted isometry property seems to be central for proving linear convergence rates, whereas in regularization theory range or source conditions are imposed. The paper gives a common meaning to the seemingly different conditions and puts them into perspective with the conditions from the respective other community. A particularly important observation is that the range condition together with an injectivity condition is weaker than the restricted isometry property. Under the weaker conditions, linear convergence rates can be proven for compressed sensing and for Tikhonov regularization. Thus existing results from the literature can be improved based on a unified analysis. In particular, the range condition is shown to be the weakest possible condition that permits the derivation of linear convergence rates for Tikhonov regularization with a priori parameter choice. © 2010 Wiley Periodicals, Inc.     

A New Gradient Method for Ill-Posed Problems

In this paper, we present a new gradient method for linear and nonlinear ill-posed problems F(x) = y. Combined with the discrepancy principle as stopping rule it is a regularization method that yields convergence to an exact solution if the operator F satisfies a tangential cone condition. If the exact solution satisfies smoothness conditions, then even convergence rates can be proven. Numerical results show that the new method in most cases needs less iteration steps than Landweber iteration, the steepest descent or minimal error method.     

Finite Groups with Few TI-Subgroups

A subgroup A of a finite group G is called a TI-subgroup if either A ∩ A ^x  = 1 or A ∩ A ^x  = A holds for all x ∈ G. In this paper, finite group all of whose meta-cyclic subgroups are TI-subgroups are classified completely. In particular, such groups are solvable.     

Homological properties of Fourier algebras on homogeneous spaces

Let K be a compact subgroup of a locally compact group G. Completely complemented ideals in A(G/K) are characterised. Biprojectivity and biflatness for the Fourier algebra A(G/K) are studied. A(G/K) is operator biprojective precisely when K is open and if this happens, then G does not contain the free group on two generators as a closed subgroup.     

The Inverse Spectral Problem for the Sturm-Liouville Operators with Discontinuous Coefficients

We study the inverse spectral problem for the Sturm–Liouville operator whose piecewise constant coefficient A(x) has discontinuity points x _k , k=1,...,n, and jumps A _k =A(x _k +0)/A(x _k -0). We show that if the discontinuity points x ₁,...,x _n are noncommensurable, i.e., none of their linear combinations with integer coefficients vanishes; then the spectral function of the operator determines all discontinuity points x _k and jumps A _k uniquely. We give an algorithm for finding x _k and A _k in finitely many steps.     

P. Hall's covering group and embeddings of countable cc-groups

Let A be an elementary abelian group of order at least p ³ acting on a finite p′-group G that is soluble with derived length d. Assume that γ _c (C _G (a)) has exponent dividing m for any a ∈ A ^#. It is proved that there exist {p, d, c, m}-bounded numbers c ₁ and m ₁ such that γ _{c 1} (G) has exponent dividing m ₁.     

Fractional Tikhonov regularization for linear discrete ill-posed problems

Tikhonov regularization is one of the most popular methods for solving linear systems of equations or linear least-squares problems with a severely ill-conditioned matrix A. This method replaces the given problem by a penalized least-squares problem. The present paper discusses measuring the residual error (discrepancy) in Tikhonov regularization with a seminorm that uses a fractional power of the Moore-Penrose pseudoinverse of AA ^T as weighting matrix. Properties of this regularization method are discussed. Numerical examples illustrate that the proposed scheme for a suitable fractional power may give approximate solutions of higher quality than standard Tikhonov regularization.