We develop a preconditioner for a family $(G + \alpha A)x = b$ of symmetric positive definite matrices arising in the numerical treatment of ill-posed operator equations $\sK x = z$ via regularized least-squares. Here, $x$ and $b$ are discrete approximations of functions in $L^2(\Omega)$, $\Omega \subset R^n$, $n\geq 2$, and the matrix $G$ is a discrete approximation of a $\sK^*\sK$, the matrix $A$ is an approximation of a self-adjoint elliptic operator arising from the use of total variation Tikhonov regularization and $\alpha>0$ is a parameter governing the amount of regularization. Depending on the level of discretization, the size of the system $(G + \alpha A)x = b$ may be very large, so that iterative methods such as preconditioned conjugate gradients may be necessary. However, although $A$ is sparse, the matrix $G$ is generally dense, so that sparse-matrix preconditioning techniques are not appropriate for this problem. We develop a new preconditioner for this problem which is based on a low-rank, low-storage approximation of $G$. This approximation is constructed in the course of the iterations via a quasi-Newton update scheme, and on the action of $A^{-1}$ which is assumed to be readily available. The construction of the preconditioner, some mathematical analysis, and a numerical example are presented. The analysis and numerics indicate that this preconditioner significantly enchances the conditioning of the system and can be easily implemented in practice, and that the overall scheme is efficient and effective for regularized ill-posed problems.

We consider a low-rank approximation $H$ of a symmetric positive semidefinite matrix $G$ which are constructed from knowledge of the action of $G$ on a given collection of vectors. The approximation $H$ is mathematically identical to approximate Hessian generated by Broyden's ``symmetric rank-one update'' alpgorithm applied to quadratic optimization problems. We present a new result for this approximation which gives a norm bound on $G-H$ as well as an estimate of how well the eigensystem of $H$ approximates that of $G$; the result is particularly meaningful when $G$ is large and ill-conditioned. A numerical example illustrating this observation is provided at the end.

A preconditioner for a family $({\cal K}^*{\cal K} + \alpha A)x = b$ of linear equations arising in the numerical treatment of ill-posed operator equations ${\cal K} x = z$ is discussed. Here, $x$ and $z$ are discrete approximations of functions in $L^2(\Omega)$, $\Omega \subset R^n$, $n\geq 2$, and the matrix ${\cal K}$ is a discrete approximation of a compact linear operator with unbounded pseudoinverse. The matrix $A$ is an approximation of a self-adjoint elliptic operator arising from the use of total variation (TV) regularization, and $\alpha>0$ is a parameter governing the amount of regularization. Depending on the level of discretization, the size of the system $({\cal K}^*{\cal K} + \alpha A)x = b$ may be very large, so that iterative methods such as preconditioned conjugate gradients may be necessary. However, although $A$ is sparse, the matrix ${\cal K}$ is generally dense, so that sparse-matrix preconditioning techniques are not appropriate for this problem. In this talk, the use of a new preconditioner is discussed. It is based on a low-rank, low-storage approximation of ${\cal K}$ quasi-Newton update scheme, and on the action of $A^{-1}$ which is assumed to be readily available. The construction of the preconditioner and some mathematical analysis are discussed, and a numerical example, using Backward Heat Equation, is presented. The analysis and numerics indicate that this preconditioner significantly enchances the conditioning of the system and can be easily implemented in practice, and that the overall scheme is efficient and effective for regularized ill-posed problems.

The goal in inverse conductivity problems is to approximately determine the spatially varying conductivity parameter in the interior of some region given certain boundary data. We formulate it as a least-squares minimization problem with total variation regularization to attenuate the ill-posedness. We outline a numerical approach to this minimization problem, based on the Gauss-Newton idea.

Our main results of this paper have to do with the continuity, regularity and approximability of the forward map underlying the inverse problem in a topology for which total variation regularization induces compact subsets of the parameter space. Specifically, we show that the forward map is Fr\'echet differentiable in this topology, and we show that standard Galerkin approximations of the Fr\'echet derivative are convergent. Numerical examples are provided.

Hardcopy available upon request.

We study the dependence on a vector--valued parameter $q$ of a collection of analytic semigroups $\{T(t;q),t\geq 0\}$ arising, for example, from a collection of diffusion-convection equations whose infinitesimal generators are abstract elliptic operators defined in terms of sesquilinear forms in a ``Gelfand triple'' or ``pivot space'' framework.

Within a mathematical framework slightly more general than the one set forth below, Banks and Ito (Banks, H.~T. and Ito, K., ``A unified framework for approximation in inverse problems for distributed parameter systems'', Control---Theory and Advanced Technology, {\bf 4}(1988), pp. 73--90) have shown, as an application of the Trotter-Kato Theorem, that the map $q\mapsto T(t;q)$ is continuous in the strong operator topology. In this paper, we establish the analyticity of this map in the uniform operator topology, and exhibit its Fr\'echet derivative both as a contour integral and as the solution of a particular initial-value problem.

Postscript file or hardcopy available upon request.

Electrical impedance tomography (EIT) is a nondestructive imaging technique whereby spatial variations in the electrical conductivity of a medium can be determined from measurements of the electric current and potential on the boundary of the medium. The EIT problem is naturally viewed as a distributed parameter inverse problem, and in this paper it is formulated as a least-squares minimization problem for the unknown conductivity function. The main focus is on a mathematical and numerical ``adjoint'' approach whereby the the derivatives of least-squares function may be computed efficiently when the number of degrees of freedom in the conductivity is large. Numerical examples are provided.

Hardcopy available upon request.

Distributed parameter estimation problems typically involve attempts to invert infinite dimensional nonlinear compact operators. In this case the derivative, or Jacobian, is a compact linear operator. Via the Hilbert-Schmidt Theorem one can construct, from a truncated specral decomposition consisting of the largest eigenvalues and corresponding eigenfunctions, a uniformly convergent sequence of finite rank operator approximations to the Jacobian. This decomposition can be computed using a variety of iterative methods, including Subspace Iteration and the Lanczos method \cite{P}. The approximate Jacobians can then be incorporated into a quasi-Newton scheme for solving the nonlinear problem. The purpose of this paper is to demonstrate that by combining Subspace Iteration with costate, or adjoint, ideas similar to those in \cite{VW2}, one can efficiently solve large-scale distributed parameter estimation problems.

Postscript file or hardcopy available upon request.

A widely used approach to parameter identification is the output least-squares formulation. Numerical methods for solving the resulting minimization problem almost invariably require the computation of the gradient of the output least-squares functional. When the identification problems involves time dependent distributed parameter systems (or approximations thereof), numerical evaluation of the gradient can be extremely time consuming. The costate method can greatly reduce the cost of computing these gradients. However, questions have been raised concerning the accuracy and convergence of costate approximations, even when the numerical methods being used are known to converge rapidly on the forward problem.

In this paper we show that the use of time-marching schemes which yield high order accuracy on the forward problem does not necessarily lead to high order accurate costate approximations. In fact in some cases these approximations do not converge at all. However, under certain circumstances, rapidly converging gradient approximations do result because of rapid weak-star type of convergence of the costate approximations. We treat these issues both theoretically and numerically.

Postscript file or hardcopy available upon request.

Very large matrices with rapidly decaying singular values commonly arise in the numerical solution of ill-posed problems. The Singular Value Decomposition (SVD) is a basic tool for both the analysis and computation of solutions to such problems. In most applications, it suffices to obtain a partial SVD consisting of only the largest singular values and their corresponding singular vectors. In this paper, two separate approaches---one based on Subspace Iteration and the other based on the Lanczos Method---are considered for the efficient iterative computation of partial SVD's. In the context of ill-posed problems, an analytical and numerical comparison of these two methods is made and the role of the regularization operator in convergence acceleration is explored.

Offprint available upon request.