Identification of the relaxation kernel in diffusion processes and viscoelasticity with memory via deconvolution

We present an algorithm for the identification of the relaxation kernel in the theory of diffusion systems with memory (or of viscoelasticity), which is linear, in the sense that we propose a linear Volterra integral equation of convolution type whose solution is the relaxation kernel. The algorithm is based on the observation of the flux through a part of the boundary of a body. The identification of the relaxation kernel is ill posed, as we should expect from an inverse problem. In fact, we shall see that it is mildly ill posed, precisely as the deconvolution problem which has to be solved in the algorithm we propose. Copyright © 2016 John Wiley & Sons, Ltd.     

A Study of the stability of solutions to inverse problems of dynamics of control systems under perturbations of initial data

A novel dual approach to the problem of optimal correction of first-kind improper linear programming problems with respect to their right-hand sides is proposed. It is based on the extension of the traditional Lagrangian by introducing additional regularization and barrier components. Convergence theorems are given for methods based on the augmented Lagrangian, an informal interpretation of the obtained generalized solution is suggested, and results of numerical experiments are presented.     

On the condition number of the antireflective transform

Deconvolution problems with a finite observation window require appropriate models of the unknown signal in order to guarantee uniqueness of the solution. For this purpose it has recently been suggested to impose some kind of antireflectivity of the signal. With this constraint, the deconvolution problem can be solved with an appropriate modification of the fast sine transform, provided that the convolution kernel is symmetric. The corresponding transformation is called the antireflective transform. In this work we determine the condition number of the antireflective transform to first order, and use this to show that the so-called reblurring variant of Tikhonov regularization for deconvolution problems is a regularization method. Moreover, we establish upper bounds for the regularization error of the reblurring strategy that hold uniformly with respect to the size n of the algebraic system, even though the condition number of the antireflective transform grows with n. We briefly sketch how our results extend to higher space dimensions.     

Confidence Intervals for Discrete Approximations to Ill-Posed Problems

We consider the linear model Y = Xβ + ε that is obtained by discretizing a system of first-kind integral equations describing a set of physical measurements. The n vector β represents the desired quantities, the m x n matrix X represents the instrument response functions, and the m vector Y contains the measurements actually obtained. These measurements are corrupted by random measuring errors ε drawn from a distribution with zero mean vector and known variance matrix. Solution of first-kind integral equations is an ill-posed problem, so the least squares solution for the above model is a highly unstable function of the measurements, and the classical confidence intervals for the solution are too wide to be useful. The solution can often be stabilized by imposing physically motivated nonnegativity constraints. In a previous article (O'Leary and Rust 1986) we developed a method for computing sets of nonnegatively constrained simultaneous confidence intervals. In this article we briefly review the simultaneous intervals and then show how to compute nonnegativity constrained one-at-a-time confidence intervals. The technique gives valid confidence intervals even for problems with m < n. We demonstrate the methods using both an overdetermined and an underdetermined problem obtained by discretizing an equation of Phillips (Phillips 1962).     

Necessary and sufficient conditions for convergence of regularization methods for solving linear operator equations of the first kind

In this paper, we give necessary and sufficient conditions for weak and strong convergence of general regularization methods for the solution of linear ill-posed problems in Hilbert space. As special cases we obtain convergence criteria for Tychonoff regularization, for a regularization method based on Showalter's integral formula, and for regularization by truncated iteration     

LOCAL REGULARIZATION METHODS FOR THE STABILIZATION OF LINEAR ILL-POSED EQUATIONS OF VOLTERRA TYPE

Inverse problems based on first-kind Volterra integral equations appear naturally in the study of many applications, from geophysical problems to the inverse heat conduction problem. The ill-posedness of such problems means that a regularization technique is required, but classical regularization schemes like Tikhonov regularization destroy the causal nature of the underlying Volterra problem and, in general, can produce oversmoothed results. In this paper we investigate a class of local regularization methods in which the original (unstable) problem is approximated by a parameterized family of well-posed, second-kind Volterra equations. Being Volterra, these approximating second-kind equations retain the causality of the original problem and allow for quick sequential solution techniques. In addition, the regularizing method we develop is based on the use of a regularization parameter which is a function (rather than a single constant), allowing for more or less smoothing at localized points in the domain. We take this approach even further by adopting the flexibility of an additional penalty term (with variable penalty function) and illustrate the sequential selection of the penalty function in a numerical example.     

A new Tikhonov regularization method

The numerical solution of linear discrete ill-posed problems typically requires regularization, i.e., replacement of the available ill-conditioned problem by a nearby better conditioned one. The most popular regularization methods for problems of small to moderate size, which allow evaluation of the singular value decomposition of the matrix defining the problem, are the truncated singular value decomposition and Tikhonov regularization. The present paper proposes a novel choice of regularization matrix for Tikhonov regularization that bridges the gap between Tikhonov regularization and truncated singular value decomposition. Computed examples illustrate the benefit of the proposed method.     

An extrapolated TSVD method for linear discrete ill-posed problems with Kronecker structure

This paper describes a new numerical method for the solution of large linear discrete ill-posed problems, whose matrix is a Kronecker product. Problems of this kind arise, for instance, from the discretization of Fredholm integral equations of the first kind in two space-dimensions with a separable kernel. The available data (right-hand side) of many linear discrete ill-posed problems that arise in applications is contaminated by measurement errors. Straightforward solution of these problems generally is not meaningful because of severe error propagation. We discuss how to combine the truncated singular value decomposition (TSVD) with reduced rank vector extrapolation to determine computed approximate solutions that are fairly insensitive to the error in the data. Exploitation of the structure of the problem keeps the computational effort quite small.     

An integral equation involving the confluent hypergeometric function of several complex variables †

In the present note the author establishes an inversion theorem for a convolution transform whose kernel involves a confluent hypergeometric function of several complex variables. It is shown how the main result can be specialized to solve a number of integral equations involving special functions of interest in applied problems. An extension of the method to a general class of integral equations is also considered.     

Efficient and stable solution of structured Hessenberg linear systems arising from difference equations

This paper is concerned with the efficient solution of (block) Hessenberg linear systems whose coefficient matrix is a Toeplitz matrix in (block) Hessenberg form plus a band matrix. Such problems arise, for instance, when we apply a computational scheme based on the use of difference equations for the computation of many significant special functions and quantities occurring in engineering and physics. We present a divide‐and‐conquer algorithm that combines some recent techniques for the numerical treatment of structured Hessenberg linear systems. Our approach is computationally efficient and, moreover, in many practical cases it can be shown to be componentwise stable. Copyright © 2000 John Wiley & Sons, Ltd.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

A generalization of Cooke's integral inversion formula with application to remote-sensing theory

The remote sensing of environmental particulate pollutants, particularly their size distribution, frequently leads to the solution of first-kind Fredholm integral equations. The corresponding physical kernel tends to smooth the behavior of the required function for all values of the dependent variable. Thus, the problem is ill posed and needs regularization by the introduction of constraints on the solution (closure condition). However, under physically realistic conditions, the original problem can be transformed so that it presents a unique and stable solution. One such condition is the so-called anomalous-diffraction approximation, for which we provide two alternate inversion formulae. We derive a new inversion formula (see our theorem) which generalizes that of Cooke and which also provides, as a special case, one of Titchmarsh's formulae. We propose a unifying viewpoint for a number of known integral inversion formulae, including those of Fox (his first theorem), Hardy, Hankel, Titchmarsh, Cooke, and our own, along with the mutual interrelationships that exist between them (Fig. 1 and Table 1). One solution to the particulate sounding problem is then obtained from a direct application of our formula [Eq. (25)]. An alternate solution is likewise obtained by applying Titchmarsh's formula (II) [Eq. (27)]. Both solutions can be independently recovered from Fox's first theorem, although under somewhat more restrictive conditions. They are shown to be identical, and to provide the unique solution to the remote sensing problem considered.     

Analytical and regularized solutions of the synchrotron integral equation

In suitable conditions on the radiation source the synchrotron process can be described by a Fredholm integral equation whose integral kernel is expressed in terms of a modified Bessel function of the second kind. We present a completely general solution of this equation. We point out that the linear inverse problem of determining the electron distribution function in the source from the knowledge of the emitted photon spectrum at discrete frequencies is strongly ill-conditioned. In order to reduce the numerical instability due to the presence of noise on the datum, we apply Tikhonov regularization method to some simulated spectra. In particular, the formulation of the method in a suitable Sobolev space allows the use of a priori information on the solution to improve the restoration accuracy. The case of a real spectrum is also considered.     

Numerical computation of the Tau approximation for the Volterra-Hammerstein integral equations

In this work, we propose an extension of the algebraic formulation of the Tau method for the numerical solution of the nonlinear Volterra-Hammerstein integral equations. This extension is based on the operational Tau method with arbitrary polynomial basis functions for constructing the algebraic equivalent representation of the problem. This representation is an special semi lower triangular system whose solution gives the components of the vector solution. We will show that the operational Tau matrix representation for the integration of the nonlinear function can be represented by an upper triangular Toeplitz matrix. Finally, numerical results are included to demonstrate the validity and applicability of the method and some comparisons are made with existing results. Our numerical experiments show that the accuracy of the Tau approximate solution is independent of the selection of the basis functions.     

Optimization of Weighted Monte Carlo Methods with Respect to Auxiliary Variables

We consider the problems whose mathematical model is determined by some Markov chain terminating with probability one; moreover, we have to estimate linear functionals of a solution to an integral equation of the second kind with the corresponding substochastic kernel and free term [1]. To construct weighted modifications of numerical statistical models, we supplement the coordinates of the phase space with auxiliary variables whose random values functionally define the transitions in the initial chain. Having implemented each auxiliary random variable, we multiply the weight by the ratio of the corresponding densities of the initial and numerically modeled distributions. We solve the minimization problem for the variances of estimators of linear functionals by choosing the modeled distribution of the first auxiliary random variable.     

On regularization methods based on dynamic programming techniques

In this article, we investigate the connection between regularization theory for inverse problems and dynamic programming theory. This is done by developing two new regularization methods, based on dynamic programming techniques. The aim of these methods is to obtain stable approximations to the solution of linear inverse ill-posed problems. We follow two different approaches and derive a continuous and a discrete regularization method. Regularization properties for both methods are proved as well as rates of convergence. A numerical benchmark problem concerning integral operators with convolution kernels is used to illustrate the theoretical results.     

On the regularity of trust region-cg algorithm: With application to deconvolution problem

Deconvolution problem is a main topic in signal processing. Many practical applications are required to solve deconvolution problems. An important example is image reconstruction. Usually, researchers like to use regularization method to deal with this problem. But the cost of computation is high due to the fact that direct methods are used. This paper develops a trust region-cg method, a kind of iterative methods to solve this kind of problem. The regularity of the method is proved. Based on the special structure of the discrete matrix, FFT can be used for calculation. Hence combining trust region-cg method with FFT is suitable for solving large scale problems in signal processing.     

On the reduction of Tikhonov minimization problems and the construction of regularization matrices

Tikhonov regularization replaces a linear discrete ill-posed problem by a penalized least-squares problem, whose solution is less sensitive to errors in the data and round-off errors introduced during the solution process. The penalty term is defined by a regularization matrix and a regularization parameter. The latter generally has to be determined during the solution process. This requires repeated solution of the penalized least-squares problem. It is therefore attractive to transform the least-squares problem to simpler form before solution. The present paper describes a transformation of the penalized least-squares problem to simpler form that is faster to compute than available transformations in the situation when the regularization matrix has linearly dependent columns and no exploitable structure. Properties of this kind of regularization matrices are discussed and their performance is illustrated.     

Circulant preconditioners for discrete ill-posed Toeplitz systems

Circulant preconditioners are commonly used to accelerate the rate of convergence of iterative methods when solving linear systems of equations with a Toeplitz matrix. Block extensions that can be applied when the system has a block Toeplitz matrix with Toeplitz blocks also have been developed. This paper is concerned with preconditioning of linear systems of equations with a symmetric block Toeplitz matrix with symmetric Toeplitz blocks that stem from the discretization of a linear ill-posed problem. The right-hand side of the linear systems represents available data and is assumed to be contaminated by error. These kinds of linear systems arise, e.g., in image deblurring problems. It is important that the preconditioner does not affect the invariant subspace associated with the smallest eigenvalues of the block Toeplitz matrix to avoid severe propagation of the error in the right-hand side. A perturbation result indicates how the dimension of the subspace associated with the smallest eigenvalues should be chosen and allows the determination of a suitable preconditioner when an estimate of the error in the right-hand side is available. This estimate also is used to decide how many iterations to carry out by a minimum residual iterative method. Applications to image restoration are presented.     

On the convergence of a numerical method for a hypersingular integral equation on a closed surface

We consider a linear integral equation with a hypersingular integral treated in the sense of the Hadamard finite value. This equation arises in the solution of the Neumann boundary value problem for the Laplace equation with a representation of a solution in the form of a double-layer potential. We consider the case in which the interior or exterior boundary value problem is solved in a domain; whose boundary is a smooth closed surface, and an integral equation is written out on that surface. For the integral operator in that equation, we suggest quadrature formulas like the method of vortical frames with a regularization, which provides its approximation on the entire surface for the use of a nonstructured partition. We construct a numerical scheme for the integral equation on the basis of suggested quadrature formulas, prove an estimate for the norm of the inverse matrix of the related system of linear equations and the uniform convergence of numerical solutions to the exact solution of the hypersingular integral equation on the grid.