Search

We present an extension of the linear sampling method for solving the sound-soft inverse acoustic scattering problem with randomly distributed point sources. The theoretical justification of our sampling method is based on the Helmholtz-Kirchhoff identity, the cross-correlation between measurements, and the volume and imaginary near-field operators, which we introduce and analyze. Implementations in MATLAB using boundary elements, the SVD, Tikhonov regularization, and Morozov's discrepancy principle are also discussed. We demonstrate the robustness and accuracy of our algorithms with several numerical experiments in two dimensions. [ABSTRACT FROM AUTHOR]

Subspace recycling techniques have been used quite successfully for the acceleration of iterative methods for solving large-scale linear systems. These methods often work by augmenting a solution subspace generated iteratively by a known algorithm with a fixed subspace of vectors which are "useful" for solving the problem. Often, this has the effect of inducing a projected version of the original linear system to which the known iterative method is then applied, and this projection can act as a deflation preconditioner, accelerating convergence. Most often, these methods have been applied for the solution of well-posed problems. However, they have also begun to be considered for the solution of ill-posed problems. In this paper, we consider subspace augmentation-type iterative schemes applied to linear ill-posed problems in a continuous Hilbert space setting, based on a recently developed framework describing these methods. We show that under suitable assumptions, a recycling method satisfies the formal definition of a regularization, as long as the underlying scheme is itself a regularization. We then develop an augmented subspace version of the gradient descent method and demonstrate its effectiveness, both on an academic Gaussian blur model and on problems arising from the adaptive optics community for the resolution of large sky images by ground-based extremely large telescopes. [ABSTRACT FROM AUTHOR]

We investigate the convergence theory of several known as well as new heuristic parameter choice rules for convex Tikhonov regularization. The success of such methods is dependent on whether certain restrictions on the noise are satisfied. In the linear theory, such conditions are well understood and hold for typically irregular noise. In this paper, we extend the convergence analysis of heuristic rules using noise restrictions to the convex setting and prove convergence of the aforementioned methods therewith. The convergence theory is exemplified for the case of an ill-posed problem with a diagonal forward operator in 'q spaces. Numerical examples also provide further insight. [ABSTRACT FROM AUTHOR]

Block coordinate descent (BCD) methods approach optimization problems by performing gradient steps along alternating subgroups of coordinates. This is in contrast to full gradient descent, where a gradient step updates all coordinates simultaneously. BCD has been demonstrated to accelerate the gradient method in many practical large-scale applications. Despite its success no convergence analysis for inverse problems is known so far. In this paper, we investigate the BCD method for solving linear inverse problems. As the main theoretical result, we show that for operators having a particular tensor product form, the BCD method combined with an appropriate stopping criterion yields a convergent regularization method. To illustrate the theory, we perform numerical experiments comparing the BCD and the full gradient descent method for a system of integral equations. We also present numerical tests for a nonlinear inverse problem not covered by our theory, namely one-step inversion in multispectral X-ray tomography. [ABSTRACT FROM AUTHOR]

This paper presents a modified quasi-reversibility method for computing the exponentially unstable solution of a nonlocal terminal-boundary value parabolic problem with noisy data. Based on data measurements, we perturb the problem by the so-called filter regularized operator to design an approximate problem. Different from recently developed approaches that consist in the conventional spectral methods, we analyze this new approximation in a variational framework, where the finite element method can be applied. To see the whole skeleton of this method, our main results lie in the analysis of a semilinear case and we discuss some generalizations where this analysis can be adapted. As is omnipresent in many physical processes, there are likely myriad models derived from this simpler case, such as source localization problems for brain tumors and heat conduction problems with nonlinear sinks in nuclear science. With respect to each noise level, we benefit from the Faedo--Galerkin method to study the weak solvability of the approximate problem. Relying on the energy-like analysis, we provide detailed convergence rates in L2-H1 of the proposed method when the true solution is sufficiently smooth. Depending on the dimensions of the domain, we obtain an error estimate in Lr for some r > 2. Proof of the backward uniqueness for the quasi-linear system is also depicted in this work. To prove the regularity assumptions acceptable, several physical applications are discussed. [ABSTRACT FROM AUTHOR]

In digital tomosynthesis imaging, multiple projections of an object are obtained along a small range of different incident angles in order to reconstruct a pseudo-3D representation of the object. In this paper we discuss a mathematical model for polyenergetic digital breast tomosynthesis image reconstruction that explicitly takes into account various materials composing the object and the polyenergetic nature of the x-ray beam. Our model allows for computing weight fractions of the individual materials that make up the object, which can then be used to reconstruct pseudo-3D images. The reconstruction process requires solving a large-scale inverse problem, which is done with a gradient descent iteration. Regularization is enforced by truncating the iteration. The mathematical model is described in detail, as is an efficient approach to compute the gradient of the objective function. The effectiveness of our approach is illustrated with real data taken of an object with known materials that simulates an actual breast. [ABSTRACT FROM AUTHOR]

We give new global stability estimates for monochromatic inverse acoustic scattering. These estimates essentially improve estimates of [P. Hä hner, T. Hohage, SIAM J. Math. Anal., 33 (2001), pp. 670-685] and can be considered as a solution of an open problem formulated in the aforementioned work. [ABSTRACT FROM AUTHOR]

In this paper we consider the simultaneous reconstruction and segmentation of a function f from measurements g = K f, where K is a linear operator. Assuming that the inversion of K is ill-posed, regularization methods have to be used for the inversion process in case of inexact data. We propose using a Mumford-Shah-type functional for the stabilization of the inversion. Restricting our analysis to the recovery of piecewise constant functions, we investigate the existence of minimizers, their stability, and the regularization properties of our approach. Finally, we present a numerical example from single photon emission computed tomography (SPECT). [ABSTRACT FROM AUTHOR]

For solving linear ill-posed problems, regularization methods are required when the right-hand side and/or the operator are corrupted by some noise. In the present paper, regularized solutions are constructed using regularized total least squares (RTLS) and dual regularized total least squares (DRTLS). We discuss computational aspects and provide order optimal error bounds that characterize the accuracy of the regularized solutions. The results extend earlier results where the operator is exactly given. We also present some numerical experiments, which shed light on the relationship between RTLS, DRTLS, and the standard Tikhonov regularization. [ABSTRACT FROM AUTHOR]

We present a multilevel method for discrete ill-posed problems arising from the discretization of Fredholm integral equations of the first kind. In this method, we use the Haarwavelet transform to define restriction and prolongation operators within a multigrid-type iteration. The choice of the Haar wavelet operator has the advantage of preserving matrix structure, such as Toeplitz, between grids, which can be exploited to obtain faster solvers on each level where an edge preserving Tikhonov regularization is applied. Finally, we present results that indicate the promise of this approach for restoration of signals and images with edges. [ABSTRACT FROM AUTHOR]

This paper investigates the use of cascadic multiresolution methods for image deblurring. Iterations with a conjugate gradient-type method are carried out on each level, and terminated by a stopping rule based on the discrepancy principle. Prolongation is carried out by nonlinear edge-preserving operators, which are defined via PDEs associated with Perona-Malik or total variation-type models. Computed examples demonstrate the effectiveness of the methods proposed. [ABSTRACT FROM AUTHOR]

This paper proves convergence of variations of the unsymmetric kernel-based collocation method introduced by Kansa in 1986. Since then, this method has been very successfully used in many applications, though it may theoretically fail in special situations, and though it had no error bound or convergence proof up to now. Thus it is necessary to add assumptions or to make modifications. Our modifications prevent numerical failure by dropping strict collocation and allow a rigorous mathematical analysis proving error bounds and convergence rates. These rates improve with the smoothness of the solution, the domain, and the kernel providing the trial spaces, but they are currently not yet optimal and deserve refinement. They are based on rates of approximation to the residuals by nonstationary meshless kernel-based trial spaces, and they are independent of the type of differential operator. The results are applicable to large classes of linear problems in strong form, provided that there is a smooth solution and the test and trial discretizations are chosen with some care. Our analysis does not require assumptions like ellipticity, and it can be extended to ill-posed problems. [ABSTRACT FROM AUTHOR]

We introduce a class of stabilizing Newton-Kaczmarz methods for nonlinear ill-posed problems and analyze their convergence and regularization behavior. As usual for iterative methods for solving nonlinear ill-posed problems, conditions on the nonlinearity (or the derivatives) have to be imposed in order to obtain convergence. As we shall discuss in general and in some specific examples, the nonlinearity conditions obtained for the Newton-Kaczmarz methods are less restrictive than those for previously existing iteration methods and can be verified for several practical applications. We also discuss the discretization and efficient numerical solution of the linear problems arising in each step of a Newton-Kaczmarz method, and we carry out numerical experiments for two model problems. [ABSTRACT FROM AUTHOR]

For any linear system Ax ≈ b we define a set of core problems and show that the orthogonal upper bidiagonalization of [b, A] gives such a core problem. In particular we show that these core problems have desirable properties such as minimal dimensions. When a total least squares problem is solved by first finding a core problem, we show the resulting theory is consistent with earlier generalizations, but much simpler and clearer. The approach is important for other related solutions and leads, for example, to an elegant solution to the data least squares problem. The ideas could be useful for solving ill-posed problems. [ABSTRACT FROM AUTHOR]

We consider a regularization concept for the solution of ill-posed operator equations, where the operator is composed of a continuous and a discontinuous operator. A particular application is level set regularization, where we develop a novel concept of minimizers. The proposed level set regularization is capable of handling changing topologies. A functional analytic framework explaining the splitting of topologies is given. The asymptotic limit of the level set regularization method is an evolution process, which is implemented numerically, and the quality of the proposed algorithm is demonstrated by solving an inverse source problem. [ABSTRACT FROM AUTHOR]

We study the efficiency of the approximate solution of ill-posed problems, based on discretized noisy observations, which we assume to be given beforehand. A basic purpose of the paper is the consideration of stochastic noise, but deterministic noise is also briefly discussed. We restrict ourselves to problems which can be formulated in Hilbert scales. Within this framework we shall quantify the degree of ill-posedness, provide general conditions on projection schemes to achieve the best possible order of accuracy. We pay particular attention on the problem of self-regularization vs. Tikhonov regularization. Moreover, we study the information complexity. Asymptotically, any method which achieves the best possible order of accuracy must use at least such amount of noisy observations. [ABSTRACT FROM AUTHOR]

Numerical solution of ill-posed problems is often accomplished by discretization (projection onto a finite dimensional subspace) followed by regularization. If the discrete problem has high dimension, though, typically we compute an approximate solution by projecting the discrete problem onto an even smaller dimensional space, via iterative methods based on Krylov subspaces. In this work we present a common framework for efficient algorithms that regularize after this second projection rather than before it. We show that determining regularization parameters based on the final projected problem rather than on the original discretization has firmer justification and often involves less computational expense. We prove some results on the approximate equivalence of this approach to other forms of regularization, and we present numerical examples. [ABSTRACT FROM AUTHOR]

Many ill-posed problems are solved using a discretization that results in a least squares problem or a linear system involving a Toeplitz matrix. The exact solution to such problems is often hopelessly contaminated by noise, since the discretized problem is quite ill conditioned, and noise components in the approximate null-space dominate the solution vector. Therefore we seek an approximate solution that does not have large components in these directions. We use a preconditioned conjugate gradient algorithm to compute such a regularized solution. A unitary change of coordinates transforms the Toeplitz matrix to a Cauchy-like matrix, and we choose our preconditioner to be a low rank Cauchy-like matrix determined in the course of Gu's fast modified complete pivoting algorithm. We show that if the kernel of the ill-posed problem is smooth, then this preconditioner has desirable properties: the largest singular values of the preconditioned matrix are clustered around one, the smallest singular values, corresponding to the lower subspace, remain small, and the upper and lower spaces are relatively unmixed. The preconditioned algorithm costs only O(n lg n) operations per iteration for a problem with n variables. The effectiveness of the preconditioner for filtering noise is demonstrated on three examples. [ABSTRACT FROM AUTHOR]

Let a probability law on [a,b] be absolutely continuous with respect to another probability law μ (specified), equivalent to the Lebesgue measure λ on [a,b]. We seek to approximate the density dv⁄dμ (assumed to be in Lμ2([a,b])) in the least square sense, given the values of the distribution function (v[a,t]) at fixed points {tj : 1 ≤ j ≤ p}. We obtain a convenient solution of this ill-posed problem via a Hilbert space embedding, and the associated discretized problem is solved by using regularization methods. This problem is connected with sedimentological topics such as sediment transport and changes of scale. As an example, a weight frequency cumulative curve is processed. [ABSTRACT FROM AUTHOR]

Tikhonov­Phillips regularization is one of the best-known regularization methods for inverse problems. A posteriori criteria for determining the regularization parameter α require solving (∗) (A* A + αI)x= A*yδ for different values of α. We investigate two methods of accelerating the standard cd-algorithm for solving the family of systems (∗). The first one utilizes a stopping criterion for the cg-iterations which depends on α and δ. The second method exploits the shifted structure of the linear systems (∗), which allows us to solve (∗) simultaneously for different values of α. We present numerical experiments for three test problems which illustrate the practical efficiency of the new methods. The experiments as well as theoretical considerations show that run times are accelerated by a factor of at least 3.

This paper examines a wide class of ill-posed initial value problems for partial differential equations, and surveys logarithmic convexity results leading to Hölder-continuous dependence on data for solutions satisfying prescribed bounds. The discussion includes analytic continuation in the unit disc, time-reversed parabolic equations in L p spaces, the time-reversed Navier-Stokes equations, as well as a large class of nonlocal evolution equations that can be obtained by randomizing the time variable in abstract Cauchy problems. It is shown that in many cases, the resulting Hölder- continuity is too weak to permit useful continuation from imperfect data. However, considerable reduction in the growth of errors occurs, and continuation becomes feasible, for solutions satisfying the slow evolution from the continuation boundary constraint, previously introduced by the author. [ABSTRACT FROM AUTHOR]

Ill-conditioned matrices with block Toeplitz, Toeplitz block (BTTB) structure arise from the discretization of certain ill-posed problems in signal and image processing. We use a preconditioned conjugate gradient algorithm to compute a regularized solution to this linear system given noisy data. Our preconditioner is a Cauchy-like block diagonal approximation to a unitary transformation of the BTTB matrix. We show that the preconditioner has desirable properties when the kernel of the ill-posed problem is smooth: the largest singular values of the preconditioned matrix are clustered around one, the smallest singular values remain small, and the subspaces corresponding to the largest and smallest singular values, respectively, remain unmixed. For a system involving np variables, the preconditioned algorithm costs only O(np(lg n + lg p)) operations per iteration. We demonstrate the effectiveness of the preconditioner on three examples. [ABSTRACT FROM AUTHOR]

Some three-dimensional analogues of the plane Darboux problems for hyperbolic equations with degeneracy are investigated. In 1954, Protter initiated the study of such three- dimensional problems, and it is now well known that for an infinite number of smooth right-hand sides these problems have solutions with a strong power-type singularity on the characteristic cone. This effect appears even for small perturbations of certain C&infin:0 right-hand sides. Using Friedrichs' theory of symmetric positive operators, we find and investigate a nonlocal problem which is a regularizer, in some sense, of these ill-posed problems. [ABSTRACT FROM AUTHOR]