Lagrangean Approximation for Combinatorial Inverse Problems

Various combinatorial problems are effectively modelled in terms of (0,1) matrices. Origins are coming from n-cube geometry, hypergraph theory, inverse tomography problems, or directly from different models of application problems. Basically these problems are NP-complete. The paper considers a set of such problems and introduces approximation algorithms for their solutions applying Lagragean relaxation and related set of techniques.

The Inverse Jacobian Control Method Applied to a Four Degree of Freedom Confined Space Robot

Thesis (Master's)--University of Washington, 2016-06

Tensor Completion for Multidimensional Inverse Problems with Applications to Magnetic Resonance Relaxometry

This thesis deals with tensor completion for the solution of multidimensional inverse problems. We study the problem of reconstructing an approximately low rank tensor from a small number of noisy linear measurements. New recovery guarantees, numerical algorithms, non-uniform sampling strategies, and parameter selection algorithms are developed. We derive a fixed point continuation algorithm for tensor completion and prove its convergence. A restricted isometry property (RIP) based tensor recovery guarantee is proved. Probabilistic recovery guarantees are obtained for sub-Gaussian measurement operators and for measurements obtained by non-uniform sampling from a Parseval tight frame. We show how tensor completion can be used to solve multidimensional inverse problems arising in NMR relaxometry. Algorithms are developed for regularization parameter selection, including accelerated k-fold cross-validation and generalized cross-validation. These methods are validated on experimental and simulated data. We also derive condition number estimates for nonnegative least squares problems. Tensor recovery promises to significantly accelerate N-dimensional NMR relaxometry and related experiments, enabling previously impractical experiments. Our methods could also be applied to other inverse problems arising in machine learning, image processing, signal processing, computer vision, and other fields.

Variational and learning models for image and time series inverse problems

Inverse problems are at the core of many challenging applications. Variational and learning models provide estimated solutions of inverse problems as the outcome of specific reconstruction maps. In the variational approach, the result of the reconstruction map is the solution of a regularized minimization problem encoding information on the acquisition process and prior knowledge on the solution. In the learning approach, the reconstruction map is a parametric function whose parameters are identified by solving a minimization problem depending on a large set of data. In this thesis, we go beyond this apparent dichotomy between variational and learning models and we show they can be harmoniously merged in unified hybrid frameworks preserving their main advantages. We develop several highly efficient methods based on both these model-driven and data-driven strategies, for which we provide a detailed convergence analysis. The arising algorithms are applied to solve inverse problems involving images and time series. For each task, we show the proposed schemes improve the performances of many other existing methods in terms of both computational burden and quality of the solution. In the first part, we focus on gradient-based regularized variational models which are shown to be effective for segmentation purposes and thermal and medical image enhancement. We consider gradient sparsity-promoting regularized models for which we develop different strategies to estimate the regularization strength. Furthermore, we introduce a novel gradient-based Plug-and-Play convergent scheme considering a deep learning based denoiser trained on the gradient domain. In the second part, we address the tasks of natural image deblurring, image and video super resolution microscopy and positioning time series prediction, through deep learning based methods. We boost the performances of supervised, such as trained convolutional and recurrent networks, and unsupervised deep learning strategies, such as Deep Image Prior, by penalizing the losses with handcrafted regularization terms.

Factorization by invariant embedding of elliptic problems: circular and star-shaped domains

Dissertação apresentada para obtenção do grau de Doutor em Matemática na especialidade de Equações Diferenciais, pela Universidade Nova de Lisboa,Faculdade de Ciências e Tecnologia

Direct and inverse transient eddy current problems

Die vorliegende Arbeit behandelt Vorwärts- sowie Rückwärtstheorie transienter Wirbelstromprobleme. Transiente Anregungsströme induzieren elektromagnetische Felder, welche sogenannte Wirbelströme in leitfähigen Objekten erzeugen. Im Falle von sich langsam ändernden Feldern kann diese Wechselwirkung durch die Wirbelstromgleichung, einer Approximation an die Maxwell-Gleichungen, beschrieben werden. Diese ist eine lineare partielle Differentialgleichung mit nicht-glatten Koeffizientenfunktionen von gemischt parabolisch-elliptischem Typ. Das Vorwärtsproblem besteht darin, zu gegebener Anregung sowie den umgebungsbeschreibenden Koeffizientenfunktionen das elektrische Feld als distributionelle Lösung der Gleichung zu bestimmen. Umgekehrt können die Felder mit Messspulen gemessen werden. Das Ziel des Rückwärtsproblems ist es, aus diesen Messungen Informationen über leitfähige Objekte, also über die Koeffizientenfunktion, die diese beschreibt, zu gewinnen. In dieser Arbeit wird eine variationelle Lösungstheorie vorgestellt und die Wohlgestelltheit der Gleichung diskutiert. Darauf aufbauend wird das Verhalten der Lösung für verschwindende Leitfähigkeit studiert und die Linearisierbarkeit der Gleichung ohne leitfähiges Objekt in Richtung des Auftauchens eines leitfähigen Objektes gezeigt. Zur Regularisierung der Gleichung werden Modifikationen vorgeschlagen, welche ein voll parabolisches bzw. elliptisches Problem liefern. Diese werden verifiziert, indem die Konvergenz der Lösungen gezeigt wird. Zuletzt wird gezeigt, dass unter der Annahme von sonst homogenen Umgebungsparametern leitfähige Objekte eindeutig durch die Messungen lokalisiert werden können. Hierzu werden die Linear Sampling Methode sowie die Faktorisierungsmethode angewendet.

Gebietserkennung mit der Faktorisierungsmethode

In der vorliegenden Arbeit wird die Faktorisierungsmethode zur Erkennung von Gebieten mit sprunghaft abweichenden Materialparametern untersucht. Durch eine abstrakte Formulierung beweisen wir die der Methode zugrunde liegende Bildraumidentität für allgemeine reelle elliptische Probleme und deduzieren bereits bekannte und neue Anwendungen der Methode. Für das spezielle Problem, magnetische oder perfekt elektrisch leitende Objekte durch niederfrequente elektromagnetische Strahlung zu lokalisieren, zeigen wir die eindeutige Lösbarkeit des direkten Problems für hinreichend kleine Frequenzen und die Konvergenz der Lösungen gegen die der elliptischen Gleichungen der Magnetostatik. Durch Anwendung unseres allgemeinen Resultats erhalten wir die eindeutige Rekonstruierbarkeit der gesuchten Objekte aus elektromagnetischen Messungen und einen numerischen Algorithmus zur Lokalisierung der Objekte. An einem Musterproblem untersuchen wir, wie durch parabolische Differentialgleichungen beschriebene Einschlüsse in einem durch elliptische Differentialgleichungen beschriebenen Gebiet rekonstruiert werden können. Dabei beweisen wir die eindeutige Lösbarkeit des zugrunde liegenden parabolisch-elliptischen direkten Problems und erhalten durch eine Erweiterung der Faktorisierungsmethode die eindeutige Rekonstruierbarkeit der Einschlüsse sowie einen numerischen Algorithmus zur praktischen Umsetzung der Methode.

An alternating boundary integral based method for a Cauchy problem for the Laplace equation in semi-infinite regions

We consider a Cauchy problem for the Laplace equation in a two-dimensional semi-infinite region with a bounded inclusion, i.e. the region is the intersection between a half-plane and the exterior of a bounded closed curve contained in the half-plane. The Cauchy data are given on the unbounded part of the boundary of the region and the aim is to construct the solution on the boundary of the inclusion. In 1989, Kozlov and Maz'ya [10] proposed an alternating iterative method for solving Cauchy problems for general strongly elliptic and formally self-adjoint systems in bounded domains. We extend their approach to our setting and in each iteration step mixed boundary value problems for the Laplace equation in the semi-infinite region are solved. Well-posedness of these mixed problems are investigated and convergence of the alternating procedure is examined. For the numerical implementation an efficient boundary integral equation method is proposed, based on the indirect variant of the boundary integral equation approach. The mixed problems are reduced to integral equations over the (bounded) boundary of the inclusion. Numerical examples are included showing the feasibility of the proposed method.

Inverse analysis FOR two-dimensional structures using the boundary element method

Inverse analysis is currently an important subject of study in several fields of science and engineering. The identification of physical and geometric parameters using experimental measurements is required in many applications. In this work a boundary element formulation to identify boundary and interface values as well as material properties is proposed. In particular the proposed formulation is dedicated to identifying material parameters when a cohesive crack model is assumed for 2D problems. A computer code is developed and implemented using the BEM multi-region technique and regularisation methods to perform the inverse analysis. Several examples are shown to demonstrate the efficiency of the proposed model. (C) 2010 Elsevier Ltd. All rights reserved,

Certified Rapid Solution of Parametrized Linear Elliptic Equations: Application to Parameter Estimation

We present a technique for the rapid and reliable evaluation of linear-functional output of elliptic partial differential equations with affine parameter dependence. The essential components are (i) rapidly uniformly convergent reduced-basis approximations — Galerkin projection onto a space WN spanned by solutions of the governing partial differential equation at N (optimally) selected points in parameter space; (ii) a posteriori error estimation — relaxations of the residual equation that provide inexpensive yet sharp and rigorous bounds for the error in the outputs; and (iii) offline/online computational procedures — stratagems that exploit affine parameter dependence to de-couple the generation and projection stages of the approximation process. The operation count for the online stage — in which, given a new parameter value, we calculate the output and associated error bound — depends only on N (typically small) and the parametric complexity of the problem. The method is thus ideally suited to the many-query and real-time contexts. In this paper, based on the technique we develop a robust inverse computational method for very fast solution of inverse problems characterized by parametrized partial differential equations. The essential ideas are in three-fold: first, we apply the technique to the forward problem for the rapid certified evaluation of PDE input-output relations and associated rigorous error bounds; second, we incorporate the reduced-basis approximation and error bounds into the inverse problem formulation; and third, rather than regularize the goodness-of-fit objective, we may instead identify all (or almost all, in the probabilistic sense) system configurations consistent with the available experimental data — well-posedness is reflected in a bounded "possibility region" that furthermore shrinks as the experimental error is decreased.

Numerical approximation of the one-dimensional inverse Cauchy–Stefan problem using a method of fundamental solutions

We investigate an application of the method of fundamental solutions (MFS) to the one-dimensional parabolic inverse Cauchy–Stefan problem, where boundary data and the initial condition are to be determined from the Cauchy data prescribed on a given moving interface. In [B.T. Johansson, D. Lesnic, and T. Reeve, A method of fundamental solutions for the one-dimensional inverse Stefan Problem, Appl. Math Model. 35 (2011), pp. 4367–4378], the inverse Stefan problem was considered, where only the boundary data is to be reconstructed on the fixed boundary. We extend the MFS proposed in Johansson et al. (2011) and show that the initial condition can also be simultaneously recovered, i.e. the MFS is appropriate for the inverse Cauchy-Stefan problem. Theoretical properties of the method, as well as numerical investigations, are included, showing that accurate results can be efficiently obtained with small computational cost.

An alternating boundary integral based method for a Cauchy problem for the Laplace equation in a quadrant

We study the Cauchy problem for the Laplace equation in a quadrant (quarter-plane) containing a bounded inclusion. Given the values of the solution and its derivative on the edges of the quadrant the solution is reconstructed on the boundary of the inclusion. This is achieved using an alternating iterative method where at each iteration step mixed boundary value problems are being solved. A numerical method is also proposed and investigated for the direct mixed problems reducing these to integral equations over the inclusion. Numerical examples verify the efficiency of the proposed scheme.

The method of fundamental solutions for free surface Stefan problems

In this paper, free surface problems of Stefan-type for the parabolic heat equation are investigated using the method of fundamental solutions. The additional measurement necessary to determine the free surface could be a boundary temperature, a heat flux or an energy measurement. Both one- and two-phase flows are investigated. Numerical results are presented and discussed.

A variational method for identifying a spacewise-dependent heat source

The inverse problem of determining a spacewise-dependent heat source for the parabolic heat equation using the usual conditions of the direct problem and information from one supplementary temperature measurement at a given instant of time is studied. This spacewise-dependent temperature measurement ensures that this inverse problem has a unique solution, but the solution is unstable and hence the problem is ill-posed. We propose a variational conjugate gradient-type iterative algorithm for the stable reconstruction of the heat source based on a sequence of well-posed direct problems for the parabolic heat equation which are solved at each iteration step using the boundary element method. The instability is overcome by stopping the iterative procedure at the first iteration for which the discrepancy principle is satisfied. Numerical results are presented which have the input measured data perturbed by increasing amounts of random noise. The numerical results show that the proposed procedure yields stable and accurate numerical approximations after only a few iterations.

On Modified Method of Simplest Equation for Obtaining Exact Solutions of Nonlinear PDEs: Case of Elliptic Simplest Equation

2010 Mathematics Subject Classification: 74J30, 34L30.