Numerical methods for A-optimal designs with a sparsity constraint for ill-posed inverse problems

We consider the problem of experimental design for linear ill-posed inverse problems. The minimization of the objective function in the classic A-optimal design is generalized to a Bayes risk minimization with a sparsity constraint. We present efficient algorithms for applications of such designs to large-scale problems. This is done by employing Krylov subspace methods for the solution of a subproblem required to obtain the experiment weights. The performance of the designs and algorithms is illustrated with a one-dimensional magnetotelluric example and an application to two-dimensional super-resolution reconstruction with MRI data.     

Parallel solution of certain Toeplitz least-squares problems

We describe a systolic algorithm for solving a Toeplitz least-squares problem of special form. Such problems arise, for example, when Volterra convolution equations of the first kind are solved by regularization. The systolic algorithm is based on a sequential algorithm of Eldén, but we show how the storage requirements of Eldén's algorithm can be reduced from O(n²) to O(n). The sequential algorithm takes time O(n²); the systolic algorithm takes time O(n) using a linear systolic array of O(n) cells. We also show how large problems may be decomposed and solved on a small systolic array.     

Maximum entropy solution to ill-posed inverse problems with approximately known operator

We consider the linear inverse problem of reconstructing an unknown finite measure μ from a noisy observation of a generalized moment of μ defined as the integral of a continuous and bounded operator Φ with respect to μ. Motivated by various applications, we focus on the case where the operator Φ is unknown; instead, only an approximation Φm to it is available. An approximate maximum entropy solution to the inverse problem is introduced in the form of a minimizer of a convex functional subject to a sequence of convex constraints. Under several assumptions on the convex functional, the convergence of the approximate solution is established.     

Numerical solution of linear least-squares problems with linear equality constraints

In Ref. 1, a perturbation theory for the linear least-squares problem with linear equality constraints is presented. In this paper, the condition numbers of a general formula given in Ref. 1 are examined in order to compare them with the condition numbers of the two matrices of the problem. A class of test problems is also defined to study experimentally the numerical stability of three algorithms.This work was partially supported by the Ministero della Pubblica Istruzione, Rome, Italy.The authors thank the Centro Interdipartimentale di Calcolo Automatico e di Informatica Applicata of the University of Modena for having provided computing time on its VAX computer.     

Theory and the methods of solution of ill-posed problems

One gives a survey of the fundamental directions and results up to 1981, inclusively, regarding the topic mentioned in the title.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 20, pp. 116–178, 1982.     

The solution of large-scale least-squares problems on supercomputers

We discuss methods for solving medium to large-scale sparse least-squares problems on supercomputers, illustrating our remarks by experiments on the CRAY-2 supercomputer at Harwell. The method we are primarily concerned with is an augmented system approach which has the merit of both robustness and accuracy, in addition to a kernel operation that is just the solution of a symmetric indefinite system. We consider extensions to handle weighted and constrained problems, and include experiments on systems similar to those arising in the Karmarkar algorithm for linear programming. We indicate how recent improvements to the kernel software could greatly improve the performance of the least-squares code.This paper is based on an invited talk by the author at a Workshop on Supercomputers and Large-Scale Optimization held at the Minnesota Supercomputing Center on 16th to 18th May, 1988.     

Complexity of projective methods for the solution of ill-posed problems

We consider the problem of finite-dimensional approximation for solutions of equations of the first kind and propose a modification of the projective scheme for solving ill-posed problems. We show that this modification allows one to obtain, for many classes of equations of the first kind, the best possible order of accuracy for the Tikhonov regularization by using an amount of information which is far less than for the standard projective technique.     

Kernel polynomials for the solution of indefinite and ill-posed problems

We introduce a new family of semiiterative schemes for the solution of ill-posed linear equations with selfadjoint and indefinite operators. These schemes avoid the normal equation system and thus benefit directly from the structure of the problem. As input our method requires an enclosing interval of the spectrum of the indefinite operator, based on some a priori knowledge. In particular, for positive operators the schemes are mathematically equivalent to the so-called -methods of Brakhage. In a way, they can therefore be seen as appropriate extensions of the -methods to the indefinite case. This extension is achieved by substituting the orthogonal polynomials employed by Brakhage in the definition of the -methods by appropriate kernel polynomials. We determine the rate of convergence of the new methods and establish their regularizing properties.     

Asymptotics of orthogonal polynomials and the numerical solution of ill-posed problems

The paper reviews the impact of modern orthogonal polynomial theory on the analysis of numerical algorithms for ill-posed problems. Of major importance are uniform bounds for orthogonal polynomials on the support of the weight function, the growth of the extremal zeros, and asymptotics of the Christoffel functions.     

A statistical approach to the solution of ill-posed problems in geophysics

The article surveys the main results of the statistical approach to the solution of ill-posed problems of mathematical physics, in application to specific ill-posed inverse problems in geophysics.Invited paper presented at the International Seminar on Mathematical Foundations of the Interpretation of Geophysical Fields, Moscow, May–June 1972.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 79, pp. 67–81, 1978.     

Discrete weighted least-squares method for the Poisson and biharmonic problems on domains with smooth boundary

In this article a discrete weighted least-squares method for the numerical solution of elliptic partial differential equations exhibiting smooth solution is presented. It is shown how to create well-conditioned matrices of the resulting system of linear equations using algebraic polynomials, carefully selected matching points and weight factors. Two simple algorithms generating suitable matching points, the Chebyshev matching points for standard two-dimensional domains and the approximate Fekete points of Sommariva and Vianello for general domains, are described. The efficiency of the presented method is demonstrated by solving the Poisson and biharmonic problems with the homogeneous Dirichlet boundary conditions defined on circular and annular domains using basis functions in the form satisfying and in the form not satisfying the prescribed boundary conditions.     

Porosity of ill-posed problems

We prove that in several classes of optimization problems, including the setting of smooth variational principles, the complement of the set of well-posed problems is -porous.

     

Stability of semilinear ill-posed problems with a prescribed energy bound

In the present paper we discuss the stability of semilinear problems of the form A^αu + G^α(u) = ? under assumption of an a priori bound for an energy functional E^α(u) ? E, where α is a parameter in a metric space M. Following [11] the problem A^αu + G^α(u) = ?, E^α(u) ? E is called stable in a Hilbert space H at a point α ? M if for any ??H, E, ? > 0 there exists δ > 0 such that for any functions u^α1, u^α2 satisfying A^αju^αj + G^αj(u^αj) = ?^αj, E^αj(u^αj) ? E, j = 1,2 we have ‖u^α1 ? u^α2_H ? ? provided ρ_M(α_j, α) ? δ, ‖?^αj ? ?‖_H ? δ, j = 1,2. In the present paper we obtain stability conditions for the problem A^αu + G^α(u) = ?, E^α(u) ? E.     

Numerical method for a quadratic minimization problem with an ellipsoidal constraint and an a priori estimate for the solution norm

An algorithm for solving a quadratic minimization problem on an ellipsoidal set in a Hilbert space is proposed. The algorithm is stable to nonuniform perturbations of the operators. A key condition for its application is that we know an estimate for the norm of the exact solution. Applications to boundary control problems for the one-dimensional wave equation are considered. Numerical results are presented.     

Regularization of ill-posed problems with unbounded operators

Variational regularization and the method of quasisolutions are justified for unbounded closed operators.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Relationship of several variational methods for the approximate solution of ill-posed problems

A study is made of the relationship among three known methods for the approximate solution of linear operator equations of the first kind.Translated from Matematicheskie Zametki, Vol. 7, No. 3, pp. 265–272, March, 1970.I wish to express my deep gratitude to V. K. Ivanov for his interest in my work and for valuable remarks.