Surface Comparison with Mass Transportation. (arXiv:0912.3488v1 [math.NA])

We use mass-transportation as a tool to compare surfaces (2-manifolds). In
particular, we determine the "similarity" of two given surfaces by solving a
mass-transportation problem between their conformal densities. This mass
transportation problem differs from the standard case in that we require the
solution to be invariant under global M"obius transformations. Our approach
provides a constructive way of defining a metric in the abstract space of
simply-connected smooth surfaces with boundary (i.e. surfaces of disk-type);
this metric can also be used to define meaningful intrinsic distances between
pairs of "patches" in the two surfaces, which allows automatic alignment of the
surfaces. We provide numerical experiments on "real-life" surfaces to
demonstrate possible applications in natural sciences.

Published by

Original source : http://arxiv.org/abs/0912.3488...

An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems. (arXiv:0912.3481v1 [math.OC])

We propose a new fast algorithm for solving one of the standard approaches to
ill-posed linear inverse problems (IPLIP), where a (possibly non-smooth)
regularizer is minimized under the constraint that the solution explains the
observations sufficiently well. Although the regularizer and constraint are
usually convex, several particular features of these problems (huge
dimensionality, non-smoothness) preclude the use of off-the-shelf optimization
tools and have stimulated a considerable amount of research. In this paper, we
propose a new efficient algorithm to handle one class of constrained problems
(often known as basis pursuit denoising) tailored to image recovery
applications. The proposed algorithm, which belongs to the family of augmented
Lagrangian methods, can be used to deal with a variety of imaging IPLIP,
including deconvolution and reconstruction from compressive observations (such
as MRI), using either total-variation or wavelet-based (or, more generally,
frame-based) regularization. The proposed algorithm is an instance of the
so-called "alternating direction method of multipliers", for which convergence
sufficient conditions are known; we show that these conditions are satisfied by
the proposed algorithm. Experiments on a set of image restoration and
reconstruction benchmark problems show that the proposed algorithm is a strong
contender for the state-of-the-art.

Published by

Original source : http://arxiv.org/abs/0912.3481...

Convergence rates to deflation of simple shift strategies. (arXiv:0912.3376v1 [math.NA])

The computation of eigenvalues of real symmetric tridiagonal matrices
frequently proceeds by a sequence of QR steps with shifts. We introduce simple
shift strategies, functions sigma satisfying natural conditions, taking each n
x n matrix T to a real number sigma(T). The strategy specifies the shift to be
applied by the QR step at T. Rayleigh and Wilkinson's are examples of simple
shift strategies. We show that if sigma is continuous then there exist initial
conditions for which deflation does not occur, i.e., subdiagonal entries do not
tend to zero. In case of deflation, we consider the rate of convergence to zero
of the (n, n-1) entry: for simple shift strategies this is always at least
quadratic. If the function sigma is smooth in a suitable region and the
spectrum of T does not include three consecutive eigenvalues in arithmetic
progression then convergence is cubic. This implies cubic convergence to
deflation of Wilkinson's shift for generic spectra. The study of the algorithm
near deflation uses tubular coordinates, under which QR steps with shifts are
given by a simple formula.

Published by

Original source : http://arxiv.org/abs/0912.3376...

Iterative solution of piecewise linear systems for the numerical solution of obstacle problems. (arXiv:0912.3222v1 [math.NA])

We investigate the use of piecewise linear systems, whose coefficient matrix
is a piecewise constant function of the solution itself. Such systems arise,
for example, from the numerical solution of linear complementarity problems and
in the numerical solution of free-surface problems. In particular, we here
study their application to the numerical solution of both the (linear)
parabolic obstacle problem and the obstacle problem. We propose a class of
effective semi-iterative Newton-type methods to find the exact solution of such
piecewise linear systems. We prove that the semiiterative Newton-type methods
have a global monotonic convergence property, i.e., the iterates converge
monotonically to the exact solution in a finite number of steps. Numerical
examples are presented to demonstrate the effectiveness of the proposed
methods.

Published by

Original source : http://arxiv.org/abs/0912.3222...