Fixed point theorem of generalized quasi-contractive mapping in cone metric space

In this paper, we introduce the generalized quasi-contractive mapping f in a cone metric space (X,d). f is called a generalized quasi-contractive if there is a real λ∈[0,1) such that for all x,y∈X,

d(fx,fy)≤λs     

Geodesic methods in quantitative image analysis

Let X be a part of an image to be analysed. Given two arbitrary points x and y of X, let us define the number d_x(x, y) as follows: d_x(x, y) is the lower bound of the lengths of the arcs in X ending at points x and y, if such arcs exist, and + α if not. The function d_x is an X-intrinsic distance function, called ‘geodesic distance’. Note that if x and y belong to two disjoint connected components of X, d_x(x, y) = + α. In other words, d_x seems to be an appropriate distance function to deal with connectivity problems.In the metric space (X, d_x), all the classical morphological transformations (dilation, erosion, skeletonization, etc.) can be defined. The geodesic distance d_x also provides rigorous definitions of topological transformations, which can be performed by automatic image analysers with the help of parallel iterative algorithms.All these notions are illustrated by several examples (definition of the length of a fibre and of an effective length factor; automatic detection of cells having at least one nucleus or having one single nucleus; definitions of the geodesic center and of the ends of an object without a hole; etc.). The corresponding algorithms are described.     

Online Metric Tracking and Smoothing

We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Δ≥0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:?→?. Given a signal f ₁,f ₂,…∈X the tracker is responsible for producing a sequence a ₁,a ₂,… of elements of X that meet the proximity constraint: d(f _i ,a _i )≤Δ. To complicate matters, the tracker is on-line—the value a _i may only depend on f ₁,…,f _i —and wishes to minimize the cost of his travels, ∑c(d(a _i ,a _i+1)). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance. The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be ? ^k with the ? ₂ metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion).

We begin by studying arbitrary metric spaces with the “pay if you move” metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb _Δ)-competitive ratio, where b _Δ=max _x∈X |B _Δ(x)| is the maximum number of points appearing in any ball of radius Δ. We show that this bound is tight.

We then focus on the metric space ? with natural families of monotone cost functions c(x)=x ^p for some p≥0. We consider both the expansive case (p≥1) and the contractive case (p<1), and show that the natural lazy algorithm performs well in the expansive case. In the contractive case, we introduce and analyze a novel deterministic algorithm that achieves a constant competitive ratio depending only on p. Finally, we observe that by slightly relaxing the guarantee provided by the tracker, one can obtain natural analogues of these algorithms that work in continuous metric spaces.

     

The relation between information theory and the differential geometry approach to statistics

?encov has shown that the Riemannian metric on the probability simplex ∑x_i = 1 defined by $\text{(ds)}{}^2\text{=}\text{∑(dx}{}_{\mathrm{i}}\text{)}{}^2\text{x}{}_{\mathrm{i}}$ has an invariance property under certain probabilistically natural mappings. No other Riemannian metric has the same property. The geometry associated with this metric is shown to lead almost automatically to measures of divergence between probability distributions which are associated with Kullback, Bhattacharyya, and Matusita. Certain vector fields are associated in a natural way with random variables. The integral curves of these vector fields yield the maximum entropy or minimum divergence estimates of probabilities. Some other consequences of this geometric view are also explored.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Supremum metric on the space of fuzzy sets and common fixed point theorems for fuzzy mappings

This paper generalizes a classical result about the space of bounded closed sets with the Hausdorff metric, and establishes the completeness of CB(X) with respect to the completeness of the metric space X, where CB(X) is the class of fuzzy sets with nonempty bounded closed α-cut sets, equipped with the supremum metric d_∞ which takes the supremum on the Hausdorff distances between the corresponding α-cut sets. In addition, some common fixed point theorems for fuzzy mappings are proved and two examples are given to illustrate the validity of the main results in fixed point theory.     

Fast and accurate approximation of digital shape thickness distribution in arbitrary dimension

We present a fast and accurate approximation of the Euclidean thickness distribution computation of a binary shape in arbitrary dimension. Thickness functions associate a value representing the local thickness for each point of a binary shape. When considering with the Euclidean metric, a simple definition is to associate with each point x, the radius of the largest ball inscribed in the shape containing x. Such thickness distributions are widely used in many applications such as medical imaging or material sciences and direct implementations could be time consuming. In this paper, we focus on fast algorithms to extract such distribution on shapes in arbitrary dimension.     

Metric information filtering

The traditional problem of similarity search requires to find, within a set of points, those that are closer to a query point q, according to a distance function d. In this paper we introduce the novel problem of metric information filtering (MIF): in this scenario, each point x_i comes with its own distance function d_i and the task is to efficiently determine those points that are close enough, according to d_i, to a query point q. MIF can be seen as an extension of both the similarity search problem and of approaches currently used in content-based information filtering, since in MIF user profiles (points) and new items (queries) are compared using arbitrary, personalized, metrics. We introduce the basic concepts of MIF and provide alternative resolution strategies aiming to reduce processing costs. Our experimental results show that the proposed solutions are indeed effective in reducing evaluation costs.     

Computing monodromy via continuation methods on random Riemann surfaces

We consider a Riemann surface X defined by a polynomial f(x,y) of degree d, whose coefficients are chosen randomly. Hence, we can suppose that X is smooth, that the discriminant δ(x) of f has d(d−1) simple roots, Δ, and that δ(0)≠0, i.e. the corresponding fiber has d distinct points {y₁,…,y_d}. When we lift a loop 0∈γ⊂C−Δ by a continuation method, we get d paths in X connecting {y₁,…,y_d}, hence defining a permutation of that set. This is called monodromy.Here we present experimentations in Maple to get statistics on the distribution of transpositions corresponding to loops around each point of Δ. Multiplying families of “neighbor” transpositions, we construct permutations and the subgroups of the symmetric group they generate. This allows us to establish and study experimentally two conjectures on the distribution of these transpositions and on transitivity of the generated subgroups.Assuming that these two conjectures are true, we develop tools allowing fast probabilistic algorithms for absolute multivariate polynomial factorization, under the hypothesis that the factors behave like random polynomials whose coefficients follow uniform distributions.     

Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs

For an ordered subset W= w₁, w₂,?…?w_k of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W)=(d(u, w₁), d(u, w₂),?…?, d(u, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a local metric generator for G if every two adjacent vertices of G have distinct representations. A minimum local metric generator is called a local metric basis for G and its cardinality the local metric dimension of G. We show that the computation of the local metric dimension of a graph with cut vertices is reduced to the computation of the local metric dimension of the so-called primary subgraphs. The main results are applied to specific constructions including bouquets of graphs, rooted product graphs, corona product graphs, block graphs and chain of graphs.     

Controllability of general nonlinear systems

Consider the nonlinear system $$\dot x(t) = f(x(t)) + \sum\limits_{i = 1}^m {u_i (t)g_i (x(t)), x(0) = x_0 \in M}$$ whereM is aC ^∞ realn-dimensional manifold,f, g ₁,?.,g _m areC ^∞ vector fields onM, andu ₁ ,..,u _m are real-valued controls. Ifm=n?1 andf, g ₁ ,?,g _m are linearly independent, then the system is called a hypersurface system, and necessary and sufficient conditions for controllability are known. For a generalm, 1 ≤m ≤n?1, and arbitraryC ^∞ vector fields,f, g ₁ ,?,g _m , assume that the Lie algebra generated byf, g ₁ ,?,g _m and by taking successive Lie brackets of these vector fields is a vector bundle with constant fiber (vector space) dimensionp onM. By Chow's Theorem there exists a maximalC ^∞ realp-dimensional submanifoldS ofM containingx ₀ with the generated bundle as its tangent bundle. It is known that the reachable set fromx ₀ must contain an open set inS. The largest open subsetU ofS which is reachable fromx ₀ is called the region of reachability fromx ₀. IfO is an open subset ofS which is reachable fromx ₀,S we find necessary conditions and sufficient conditions on the boundary ofO inS so thatO = U. Best results are obtained when it is assumed that the Lie algebra generated byg ₁,?,g _m and their Lie brackets is a vector bundle onM.     

Knowledge extraction from trained neural network scour model at culvert outlets

Artificial neural networks (ANNs), due to their outstanding capabilities for modeling complex processes, have been successfully applied to a variety of problems in hydraulics. However, one of the major criticisms of ANNs is that they are just black-box models, since a satisfactory explanation of their behavior has not been offered. They, in particular, do not explain easily how the inputs are related to the output and also whether the selected inputs have any significant relationship with an output. In this paper, a perturbation analysis for determining the order of influence of the elements in the input vector on the output vector is discussed. The analyses of the results suggest that each variable in the input vector (d ₅₀/d ₀, F ₀, H/d ₀, σ_g, and W ₀/d ₀) influences the depth of scour in different ways. However, the magnitude of the influence cannot be clearly quantified by this approach. Further it adds that the selection of input vector based on linear measures between the variables of interest, which is commonly employed, may still include certain spurious elements that only increase the model complexity.     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

An optimal algorithm for constructing the weighted voronoi diagram in the plane

Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by d_e(x,p)/w(p) where d_e denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.An algorithm which constructs the weighted Voronoi diagram for S in O(n²) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n²) faces, edges and vertices.     

Efficient Euclidean projections via Piecewise Root Finding and its application in gradient projection

Recently, the gradient (subgradient) projection method, especially by incorporating the idea of Nesterov's method, has aroused more and more attention and achieved great successes on constrained optimization problems arising in the field of machine learning, data mining and signal processing. In the gradient projection method, a critical step is how to efficiently project a vector onto a constraint set. In this paper, we propose a unified method called Piecewise Root Finding (PRF) to efficiently calculate Euclidean projections onto three typical constraint sets: ?₁-ball, Elastic Net (EN) and the Intersection of a Hyperplane and a Halfspace (IHH). In our PRF method, we first formulate a Euclidean projection problem as a root finding problem. Then, a Piecewise Root Finding algorithm is applied to find the root and global convergence is guaranteed. Finally, the Euclidean projection result is obtained as a function of the found root in a closed form. Moreover, the sparsity of the projected vector is considered, leading to reduced computational cost for projection onto the ?₁-ball and EN. Empirical studies demonstrate that our PRF algorithm is efficient by comparing it with several state of the art algorithms for Euclidean projections onto the three typical constraint sets mentioned above. Besides, we apply our efficient Euclidean projection algorithm (PRF) to the Gradient Projection with Nesterov's Method (GPNM), which efficiently solves the popular logistic regression problem with the ?₁-ball/EN/IHH constraint. Experimental results on real-world data sets indicate that GPNM has a fast convergence speed.     

On the joint nonlinear filtering-smoothing of diffusion processes

The smoothing of diffusions dx_t = f(x_t) dt + σ(x_t) dw_t, measured by a noisy sensor dy_t = h(x_t) dt + dv_t, where w_t and v_t are independent Wiener processes, is considered in this paper. By focussing our attention on the joint p.d.f. of (x_τ x_t), 0 ≤ τ < t, conditioned on the observation path {y_s, 0 ≤ s ≤ t}, the smoothing problem is represented as a solution of an appropriate joint filtering problem of the process, together with its random initial conditions. The filtering problem thus obtained possesses a solution represented by a Zakai-type forward equation. This solution of the smoothing problem differs from the common approach where, by concentrating on the conditional p.d.f. of x_τ alone, a set of ‘forward and reverse’ equations needs to be solved.     

Solving nonlinear systems of functional equations with fuzzy adaptive simulated annealing

This paper proposes a method for finding solutions of arbitrarily nonlinear systems of functional equations through stochastic global optimization. The original problem (equation solving) is transformed into a global optimization one by synthesizing objective functions whose global minima, if they exist, are also solutions to the original system. The global minimization task is carried out by the stochastic method known as fuzzy adaptive simulated annealing, triggered from different starting points, aiming at finding as many solutions as possible. To demonstrate the efficiency of the proposed method, solutions for several examples of nonlinear systems are presented and compared with results obtained by other approaches. We consider systems composed of n   equations on Euclidean spaces ?n${?}^n$ (n variables: x₁, x₂, x₃, ? , x_n).     

Supermetric search

Metric search is concerned with the efficient evaluation of queries in metric spaces. In general, a large space of objects is arranged in such a way that, when a further object is presented as a query, those objects most similar to the query can be efficiently found. Most mechanisms rely upon the triangle inequality property of the metric governing the space. The triangle inequality property is equivalent to a finite embedding property, which states that any three points of the space can be isometrically embedded in two-dimensional Euclidean space. In this paper, we examine a class of semimetric space which is finitely four-embeddable in three-dimensional Euclidean space. In mathematics this property has been extensively studied and is generally known as the four-point property. All spaces with the four-point property are metric spaces, but they also have some stronger geometric guarantees. We coin the term supermetric¹space as, in terms of metric search, they are significantly more tractable. Supermetric spaces include all those governed by Euclidean, Cosine,² Jensen–Shannon and Triangular distances, and are thus commonly used within many domains. In previous work we have given a generic mathematical basis for the supermetric property and shown how it can improve indexing performance for a given exact search structure. Here we present a full investigation into its use within a variety of different hyperplane partition indexing structures, and go on to show some more of its flexibility by examining a search structure whose partition and exclusion conditions are tailored, at each node, to suit the individual reference points and data set present there. Among the results given, we show a new best performance for exact search using a well-known benchmark.     

The region approach for computing relative neighbourhood graphs in the Lp metric

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v ₁,v ₂, ...,v _n } of distinct points in atwo-dimensional space. The pointv _j is said to be arelative neighbour ofv _i ifd _p (v _i ,v _j )≤max{d _p (v _j ,v _k ),d _p (v _j ,v _k )} for allv _k ∈V, whered _p denotes the distance in theL _p metric, 1≤p≤∞. After dividing the space around the pointv _i into eight sectors (regions) of equal size, a closest point tov _i in some region is called anoctant (region, orgeographic) neighbour ofv _i. For anyL _p metric, a relative neighbour ofv _i is always an octant neighbour in some region atv _i. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointv _i ofV, first search for the octant neighbours ofv _i in each region, and then for each octant neighbourv _j found check whether the pointv _j is also a relative neighbour ofv _i. In theL _p metric, 1<p<∞, the total number of octant neighbours is shown to be θ(n) for any set ofn points; hence, even a straightforward implementation of the above method runs in θn ²) time. In theL ₁ andL _∞ metrics the method can be refined to a θ(n logn+m) algorithm, wherem is the number of relative neighbours in the output,n-1≤m≤n(n-1). TheL ₁ (L _∞) algorithm is optimal within a constant factor.