Image recovery via total variation minimization and related problems

Summary. We study here a classical image denoising technique introduced by L. Rudin and S. Osher a few years ago, namely the constrained minimization of the total variation (TV) of the image. First, we give results of existence and uniqueness and prove the link between the constrained minimization problem and the minimization of an associated Lagrangian functional. Then we describe a relaxation method for computing the solution, and give a proof of convergence. After this, we explain why the TV-based model is well suited to the recovery of some images and not of others. We eventually propose an alternative approach whose purpose is to handle the minimization of the minimum of several convex functionals. We propose for instance a variant of the original TV minimization problem that handles correctly some situations where TV fails. Received December 21, 1995 / Revised version February 26, 1996     

TRACING A PLANAR ALGEBRAIC CURVE

In this paper, an algorithm that determines a real algebraic curve is outlined. Its basicstep is to divide the plane into subdomain1s that include only simple branches of the algebraic curvewithout singular points. Each of the branches is then stably and efficiently traced in the particularsubdomain. Except for tracing, the algorithm requires only a couple of simple operations on poly-nomials that ran be carried out exacrly if the coefficients are rational, and the determination of the real roots of several univariate polynomials.     

Simultaneous representation of interval and interval-containment orders

We characterize the polysemic interval pairs—pairs of posets that admit simultaneous interval and interval-containment representations—and present algorithms to recoginze them and construct polysemic interval representations.This work, supported in part by NSF grant CCR-9300079, also appears in the author's doctoral thesis [9], written at the Johns Hopkins University under the supervision of Professors Edward R. Scheinerman and Michael T. Goodrich.     

Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions

Algorithms are developed, based on topological principles, to evaluate the boundary and “internal structure” of the Minkowski sum of two planar curves. A graph isotopic to the envelope curve is constructed by computing its characteristic points. The edges of this graph are in one-to-one correspondence with a set of monotone envelope segments. A simple formula allows a degree   to be assigned to each face defined by the graph, indicating the number of times its points are covered by the Minkowski sum. The boundary can then be identified with the set of edges that separate faces of zero and non-zero degree, and the boundary segments corresponding to these edges can be approximated to any desired geometrical accuracy. For applications that require only the Minkowski sum boundary, the algorithm minimizes geometrical computations on the “internal” envelope edges, that do not contribute to the final boundary. In other applications, this internal structure is of interest, and the algorithm provides comprehensive information on the covering degree for different regions within the Minkowski sum. Extensions of the algorithm to the computation of Minkowski sums in R³${\mathbb{R}}^3$, and other forms of geometrical convolution, are briefly discussed.     

Piecewise linear prewavelets on arbitrary triangulations

This paper studies locally supported piecewise linear prewavelets on bounded triangulations of arbitrary topology. It is shown that a concrete choice of prewavelets form a basis of the wavelet space when the degree of the vertices in the triangulation is not too high. Received December 29, 1997 / Revised version received April 14, 1998     

Greedy Algorithm Computing Minkowski Reduced Lattice Bases with Quadratic Bit Complexity of Input Vectors

The authors present an algorithm which is a modification of the Nguyen-Stehle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}} {{2^n }})^{\tfrac{n} {2}} \cdot (\tfrac{4} {3})^{\tfrac{{n(n - 1)}} {4}} \cdot (\tfrac{3} {2})^{\tfrac{{n^2 (n - 1)}} {2}} \cdot \log ^2 A) , where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O(log² A) algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n! · 3 ⁿ (log A) ^O(1) algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n! · (log A) ^O(1) by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.     

On the stability of polynomial transformations between Taylor,Bernstein and Hermite forms

The stability of transformations between Taylor and Hermite and Bernstein and Hermite forms of the polynomials are investigated. The results are analogous to Farouki's concerning the stability of the transformation between Taylor and Bernstein form. An exact asymptotic is given for the condition numbers in thel ¹ case.Research was partially supported by the Copernicus grant RECCAD 94-1068 and by the National Research Foundation of the Hungarian Academy of Sciences grant 16420.     

The stability analysis of dynamic SPECT systems

Summary. SPECT (Single Photon Emission Computed Tomography) techniques have been applied to a wide range of medical studies. The stability of a SPECT model depends strongly upon the data collected. We show that a SPECT model is full rank and well-conditioned (stable) if the projection data are large enough. Condition number estimates for a linear model are given. Numerical results for a class of linear models confirm our theoretical analysis. Received February 1, 1996 / Revised version received August 2, 1996     

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

O (c+d) steps using constant-size queues, where c is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lovász Local Lemma and was not constructive. In this paper, we show how to find such a schedule in time, with probability , for any positive constant β, where is the sum of the lengths of the paths taken by the packets in the network, and m is the number of edges used by some packet in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lovász Local Lemma discovered by Beck. Received: July 8, 1996     

An always successful method in univariate convex C^2 interpolation

Summary. We consider convex interpolation with cubic splines on grids built by adding two knots in each subinterval of neighbouring data sites. The additional knots have to be variable in order to get a chance to always retain convexity. By means of the staircase algorithm we provide computable intervals for the added knots such that all knots from these intervals allow convexity preserving spline interpolation of continuity. Received May 31, 1994 / Revised version received December 22, 1994     

Blowing up: application to $G^2$-continuous 8-sided filling patch

Summary. We propose a method for filling a n-sided hole, , that interpolates n connected boundary curves of a given net of patches. This method allows the joining with patches defined in many different ways. A new class of blowing up pole-functions is introduced in order to build a G-continuous n-sided filling surface. This filling surface is in one piece, image of . Received February 21, 2000 / Revised version received January 2, 2001 / Published online December 18, 2001     

On parametrization of interpolating curves

In parametric curve interpolation there is given a sequence of data points and corresponding parameter values (nodes), and we want to find a parametric curve that passes through data points at the associated parameter values. We consider those interpolating curves that are described by the combination of control points and blending functions. We study paths of control points and points of the interpolating curve obtained by the alteration of one node. We show geometric properties of quadratic Bézier interpolating curves with uniform and centripetal parameterizations. Finally, we propose geometric methods for the interactive modification and specification of nodes for interpolating Bézier curves.     

Hyperellipticity of offsets to rational plane curves

In this paper, we prove irreducible offsets to rational plane curves are hyperelliptic in general and compute the genus of them. We also give a criterion for deciding the irreducibility of offsets to rational plane curves.     

Instanton moduli on the quaternion Kähler manifold of type ${\mathbf G_2}$ and singular set

We prove the completeness of an instanton moduli space on quaternion-K?hler manifold . A point in the boundary of the moduli represents an ASD bundle with a particular singular set. It is shown that the singular set is a quaternion submanifold of and the Poincaré dual of the homology class represented by is the second Chern class o f the instanton bundle. Received: 4 July 2000 / Published online: 2 December 2002 Current Address: Faculty of Mathematics, Kyushu University, Ropponmatsu, Fukuoka, 810-8560, Japan (e-mail: nagatomo@math.kyushu-u.ac.jp)     

Macro-elements and stable local bases for splines on Clough-Tocher triangulations

Summary. Macro-elements of arbitrary smoothness are constructed on Clough-Tocher triangle splits. These elements can be used for solving boundary-value problems or for interpolation of Hermite data, and are shown to be optimal with respect to spline degree. We conjecture they are also optimal with respect to the number of degrees of freedom. The construction provides local bases for certain superspline spaces defined over Clough-Tocher refinements of arbitrary triangulations. These bases are shown to be stable as a function of the smallest angle in the triangulation, which in turn implies that the associated spline spaces have optimal order approximation power. Received November 18, 1999 / Published online October 16, 2000