Solution of a multiple Nevanlinna-Pick problem via orthogonal rational functions

We consider a Nevanlinna-Pick type interpolation problem for Carathéodory functions, where the values of the function and its derivatives up to certain orders are given at finitely many points of the unit disk. The set of all solutions of this problem is described by means of the orthogonal rational functions which play here a similar role as the orthogonal polynomials on the unit circle in the classical case of the trigonometric moment problem. In particular, we use a connection between Szegö and Schur parameters which in the classical situation was discovered by Ja.L. Geronimus.     

Solution of a multiple Nevanlinna–Pick problem for Carathéodory functions via orthogonal rational functions in the matrix case

We consider an interpolation problem of Nevanlinna–Pick type for matrix‐valued Carathéodory functions, where the values of the functions and its derivatives up to certain orders are given at finitely many points of the open unit disk. For the non‐degenerate case, i.e., in the particular situation that a specific block matrix (which is formed by the given data in the problem) is positive Hermitian, the solution set of this problem is described in terms of orthogonal rational matrix‐valued functions. These rational matrix functions play here a similar role as Szegő's orthogonal polynomials on the unit circle in the classical case of the trigonometric moment problem. In particular, we present and use a connection between Szegő and Schur parameters for orthogonal rational matrix‐valued functions which in the primary situation of orthogonal polynomials was found by Geronimus. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

统计模拟在几何概率问题中应用的注解

设D为R²上的一个紧集, X 为D上的一个随机覆盖过程的统计量. 由于问题复杂, X的均 值、方差、分布函数均没有解析表达式. 统计模拟可以帮助我们找到它们的近似解. 为了在D上做统 计模拟, 需要D的代表点. 产生代表点的不同方法, 会影响统计模拟的结果. 若D不是一个矩形, 如 何选择合适的代表点至关重要. 文献中研究了一个在单位圆上的随机覆盖问题, 提出在单位圆上产生 代表点的四种方法, 并对这四种方法给予评估. 本文考虑两个随机圆的随机覆盖问题, 给出覆盖面积 的理论公式, 使比较四种产生代表点的方法有一个基准. 我们的研究结果和文献中的结论一致, 并发现 其中两种方法使覆盖面积均值的估计有偏, 且有较大的方差, 这是一个新的结果. 本文进一步指出覆 盖面积的分布可由 β 分布来拟合.     

On the distribution of points in projective space of bounded height

In this paper we consider the uniform distribution of points in compact metric spaces. We assume that there exists a probability measure on the Borel subsets of the space which is invariant under a suitable group of isometries. In this setting we prove the analogue of Weyl's criterion and the Erdös-Turán inequality by using orthogonal polynomials associated with the space and the measure. In particular, we discuss the special case of projective space over completions of number fields in some detail. An invariant measure in these projective spaces is introduced, and the explicit formulas for the orthogonal polynomials in this case are given. Finally, using the analogous Erdös-Turán inequality, we prove that the set of all projective points over the number field with bounded Arakelov height is uniformly distributed with respect to the invariant measure as the bound increases.

     

The Fermat–Torricelli Problem, Part I: A Discrete Gradient-Method Approach

We give a discrete geometric (differential-free) proof of the theorem underlying the solution of the well known Fermat–Torricelli problem, referring to the unique point having minimal distance sum to a given finite set of non-collinear points in d-dimensional space. Further on, we extend this problem to the case that one of the given points is replaced by an affine flat, and we give also a partial result for the case where all given points are replaced by affine flats (of various dimensions), with illustrative applications of these theorems.     

正交设计的最新发展和应用(Ⅱ)—均匀正交设计

方开泰等．正交设计的最新发展和应用（Ⅱ）—均匀正交设计．令Ｌ（ｎ;ｑｓ）为一切正交表Ｌｎ（ｑｓ）之集合,Ｍ为试验点分布于试验区域的均匀性测度。给定（ｎ,ｑ,ｓ）,在Ｌ（ｎ;ｑｓ）上具有最好均匀性（在测度ＭＦ）的设计称为无匀正交设计,并表为ＵＬｎ（ｑｓ）。本讲座以ＵＬ９（３４）为例说明均匀正交设计在估计和混杂方面的优良性质。在附录中列出了七个均匀正交表,它们都是最近获得的     

正交设计的最新发展和应用(Ⅱ)-均匀正交设计

方开泰等．正交设计的最新发展和应用（Ⅱ）—均匀正交设计．令Ｌ（ｎ;ｑｓ）为一切正交表Ｌｎ（ｑｓ）之集合,Ｍ为试验点分布于试验区域的均匀性测度。给定（ｎ,ｑ,ｓ）,在Ｌ（ｎ;ｑｓ）上具有最好均匀性（在测度ＭＦ）的设计称为无匀正交设计,并表为ＵＬｎ（ｑｓ）。本讲座以ＵＬ９（３４）为例说明均匀正交设计在估计和混杂方面的优良性质。在附录中列出了七个均匀正交表,它们都是最近获得的     

Incomplete total least squares

Fitting data points with some model function such that the sum of squared orthogonal distances is minimized is well-known as TLS, i.e. as total least squares, see Van Huffel (1997). We consider situations where the model is such that there might be no perpendiculars from certain data points onto the model function and where one has to replace certain orthogonal distances by shortest ones, e.g. to corner or border line points. We introduce this considering the (now incomplete) TLS fit by a finite piece of a straight line. Then we study general model functions with linear parameters and modify a well-known descent algorithm (see Seufer (1996), Seufer/Sp?th (1997), Sp?th (1996), Sp?th (1997a) and Sp?th (1997b)) for fitting with them. As applications (to be used in computational metrology) we discuss incomplete TLS fitting with a segment of a circle, the area of a circle in space, with a cylinder, and with a rectangle (see also Gander/Hrebicek (1993)). Numerical examples are given for each case. Received August 27, 1997 / Revised version received February 23, 1998     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

Varying Jacobi–Krall orthogonal polynomials: local asymptotic behaviour and zeros

Krall orthogonal polynomials are well known and they constitute a generalization of classical orthogonal polynomials obtained by addition of positive masses located at some points on the real line. In this contribution we consider two families of Krall polynomials already known in the literature, but now the corresponding absolutely continuous measure is perturbed by a sequence of nonnegative masses located at the point 1 in the Jacobi case and at the end points of the interval of orthogonality in the Gegenbauer case. We analyze the asymptotic behaviour of these varying Krall orthogonal polynomials in the neighbourhood of the points where the perturbation has been done. To do this we use Mehler–Heine type asymptotic formulae. As a consequence we can establish limit relations between the zeros of these polynomials and the ones of the Bessel functions of the first kind (or linear combinations of them). We do some numerical experiments to illustrate the results.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

The String Method as a Dynamical System

This paper is devoted to the theoretical analysis of the zero-temperature string method, a scheme for identifying minimum energy paths (MEPs) on a given energy landscape. By definition, MEPs are curves connecting critical points on the energy landscape which are everywhere tangent to the gradient of the potential except possibly at critical points. In practice, MEPs are mountain pass curves that play a special role, e.g., in the context of rare reactive events that occur when one considers a steepest descent dynamics on the potential perturbed by a small random noise. The string method aims to identify MEPs by moving each point of the curve by steepest descent on the energy landscape. Here we address the question of whether such a curve evolution necessarily converges to an MEP. Surprisingly, the answer is no, for an interesting reason: MEPs may not be isolated, in the sense that there may be families of them that can be continuously deformed into one another. This degeneracy is related to the presence of critical points of Morse index 2 or higher along the MEP. In this paper, we elucidate this issue and completely characterize the limit set of a curve evolving by the string method. We establish rigorously that the limit set of such a curve is again a curve when the MEPs are isolated. We also show under the same hypothesis that the string evolution converges to an MEP. However, we identify and classify situations where the limit set is not a curve and may contain higher dimensional parts. We present a collection of examples where the limit set of a path contains a 2D region, a 2D surface, or a region of an arbitrary dimension up to the dimension of the space. In some of our examples the evolving path wanders around without converging to its limit set. In other examples it fills a region, converging to its limit set, which is not an MEP.     

Probabilistic analysis of some euclidean clustering problems

We are given n points distributed randomly in a compact region D of R^m. We consider various optimisation problems associated with partitioning this set of points into k subsets. For each problem we demonstrate lower bounds which are satisfied with high probability. For the case where D is a hypercube we use a partitioning technique to give deterministic upper bounds and to construct algorithms which with high probability can be made arbitrarily accurate in polynomial time for a given required accuracy.     

Non-autonomous Julia sets with escaping critical points

We consider non-autonomous iteration which is a generalization of standard polynomial iteration where we deal with Julia sets arising from composition sequences for arbitrarily chosen polynomials with uniformly bounded degrees and coefficients. In this paper, we look at examples where all the critical points escape to infinity. In the classical case, any example of this type must be hyperbolic and there can be only one Fatou component, namely the basin at infinity. This result remains true in the non-autonomous case if we also require that the dynamics on the Julia set be hyperbolic or semi-hyperbolic. However, in general it fails and we exhibit three counterexamples of sequences of quadratic polynomials all of whose critical points escape but which have bounded Fatou components.     

Scagnostics Distributions

Scagnostics is a Tukey neologism for the term scatterplot diagnostics. Scagnostics are characterizations of the 2D distributions of orthogonal pairwise projections of a set of points in multidimensional Euclidean space. These characterizations include such measures as density, skewness, shape, outliers, and texture. We introduce a set of scagnostics measures based on graph theory and we analyze their distributions and performance. Our analysis is based on a restrictive set of criteria that must be met in order to have scagnostics measures that can be used effectively in exploratory data analysis.     

Least Squares Isotonic Regression in Two Dimensions

Given a finite partially-ordered set with a positive weighting function defined on its points, it is well known that any real-valued function defined on the set has a unique best order-preserving approximation in the weighted least squares sense. Many algorithms have been given for the solution of this isotonic regression problem. Most such algorithms either are not polynomial or they are of unknown time complexity. Recently, it has become clear that the general isotonic regression problem can be solved as a network flow problem in time O(n⁴) with a space requirement of O(n²), where n is the number of points in the set. Building on the insights at the basis of this improvement, we show here that, in the case of a general two-dimensional partial ordering, the problem can be solved in O(n³) time and, when the two-dimensional set is restricted to a grid, the time can be further improved to O(n²).     

Extension and Restriction Principles for the HRT Conjecture

The HRT (Heil–Ramanathan–Topiwala) conjecture asks whether a finite collection of time-frequency shifts of a non-zero square integrable function on \(\mathbb {R}\) is linearly independent. This longstanding conjecture remains largely open even in the case when the function is assumed to be smooth. Nonetheless, the conjecture has been proved for some special families of functions and/or special sets of points. The main contribution of this paper is an inductive approach to investigate the HRT conjecture based on the following. Suppose that the HRT is true for a given set of N points and a given function. We identify the set of all new points such that the conjecture remains true for the same function and the set of \(N+1\) points obtained by adding one of these new points to the original set. To achieve this we introduce a real-valued function whose global maximizers describe when the HRT is true. To motivate this new approach we re-derive a special case of the HRT for sets of 3 points. Subsequently, we establish new results for points in (1, n) configurations, and for a family of symmetric (2, 3) configurations. Furthermore, we use these results and the refinements of other known ones to prove that the HRT holds for certain families of 4 points.

     

ON THE SPACES OF THE MAXIMAL POINTS

For a continuous domain D, some characterization that the convex powerdomain CD is a domain hull of Max(CD) is given in terms of compact subsets of D. And in this case, it is proved that the set of the maximal points Max(CD) of CD with the relative Scott topology is homeomorphic to the set of all Scott compact subsets of Max(.D) with the topology induced by the Hausdorff metric derived from a metric on Max(D) when Max(D) is metrizable.     

Implicit Surface Fitting Using Directional Constraints

A commonly used technique for fitting curves and surfaces to measured data is that known as orthogonal distance regression, where the sum of squares of orthogonal distances from the data points to the surface is minimized. An alternative has recently been proposed for curves and surfaces which are parametrically defined, which minimizes the sum of squares in given directions which depend on the measuring process. In addition to taking account of that process, it is claimed that this technique has the advantage of complying with traditional fixed-regressor assumptions, enabling standard inference theory to apply. Here we consider extending this idea to curves and surfaces where the only assumption made is that there is an implicit formulation. Numerical results are given to illustrate the algorithmic performance.This revised version was published online in October 2005 with corrections to the Cover Date.     

Geometric fit of a point set by generalized circles

In our paper we approximate a set of given points by a general circle. More precisely, given two norms k ₁ and k ₂ and a set of points in the plane, we consider the problem of locating and scaling the unit circle of norm k ₁ such that the sum of weighted distances between the circumference of the circle and the given points is minimized, where the distance is measured by a norm k ₂. We present results for the general case. In the case that k ₁ and k ₂ are both polyhedral norms, we are able to solve the problem by investigating a finite candidate set.