Necessary conditions for discontinuities of multidimensional persistent Betti numbers

Topological persistence has proven to be a promising framework for dealing with problems concerning the analysis of data. In this context, it was originally introduced by taking into account 1‐dimensional properties of data, modeled by real‐valued functions. More recently, topological persistence has been generalized to consider multidimensional properties of data, coded by vector‐valued functions. This extension enables the study of multidimensional persistent Betti numbers, which provide a representation of data based on the properties under examination. In this contribution, we establish a new link between multidimensional topological persistence and Pareto optimality, proving that discontinuities of multidimensional persistent Betti numbers are necessarily pseudocritical or special values of the considered functions. Copyright © 2014 John Wiley & Sons, Ltd.     

Natural Pseudo-Distance and Optimal Matching between Reduced Size Functions

This paper studies the properties of a new lower bound for the natural pseudo-distance. The natural pseudo-distance is a dissimilarity measure between shapes, where a shape is viewed as a topological space endowed with a real-valued continuous function. Measuring dissimilarity amounts to minimizing the change in the functions due to the application of homeomorphisms between topological spaces, with respect to the L _∞-norm. In order to obtain the lower bound, a suitable metric between size functions, called matching distance, is introduced. It compares size functions by solving an optimal matching problem between countable point sets. The matching distance is shown to be resistant to perturbations, implying that it is always smaller than the natural pseudo-distance. We also prove that the lower bound so obtained is sharp and cannot be improved by any other distance between size functions.     

Approximations of Shape Metrics and Application to Shape Warping and Empirical Shape Statistics

This paper proposes a framework for dealing with several problems related to the analysis of shapes. Two related such problems are the definition of the relevant set of shapes and that of defining a metric on it. Following a recent research monograph by Delfour and Zolésio [11], we consider the characteristic functions of the subsets of R² and their distance functions. The L² norm of the difference of characteristic functions, the L and the W^1,2 norms of the difference of distance functions define interesting topologies, in particular the well-known Hausdorff distance. Because of practical considerations arising from the fact that we deal with image shapes defined on finite grids of pixels, we restrict our attention to subsets of ² of positive reach in the sense of Federer [16], with smooth boundaries of bounded curvature. For this particular set of shapes we show that the three previous topologies are equivalent. The next problem we consider is that of warping a shape onto another by infinitesimal gradient descent, minimizing the corresponding distance. Because the distance function involves an inf, it is not differentiable with respect to the shape. We propose a family of smooth approximations of the distance function which are continuous with respect to the Hausdorff topology, and hence with respect to the other two topologies. We compute the corresponding Gâteaux derivatives. They define deformation flows that can be used to warp a shape onto another by solving an initial value problem.We show several examples of this warping and prove properties of our approximations that relate to the existence of local minima. We then use this tool to produce computational definitions of the empirical mean and covariance of a set of shape examples. They yield an analog of the notion of principal modes of variation. We illustrate them on a variety of examples.     

Geometric Inference for Probability Measures

Data often comes in the form of a point cloud sampled from an unknown compact subset of Euclidean space. The general goal of geometric inference is then to recover geometric and topological features (e.g., Betti numbers, normals) of this subset from the approximating point cloud data. It appears that the study of distance functions allows one to address many of these questions successfully. However, one of the main limitations of this framework is that it does not cope well with outliers or with background noise. In this paper, we show how to extend the framework of distance functions to overcome this problem. Replacing compact subsets by measures, we introduce a notion of distance function to a probability distribution in ℝ ^d . These functions share many properties with classical distance functions, which make them suitable for inference purposes. In particular, by considering appropriate level sets of these distance functions, we show that it is possible to reconstruct offsets of sampled shapes with topological guarantees even in the presence of outliers. Moreover, in settings where empirical measures are considered, these functions can be easily evaluated, making them of particular practical interest.     

Betti numbers in multidimensional persistent homology are stable functions

Multidimensional persistence mostly studies topological features of shapes by analyzing the lower level sets of vector‐valued functions, called filtering functions. As is well known, in the case of scalar‐valued filtering functions, persistent homology groups can be studied through their persistent Betti numbers, that is, the dimensions of the images of the homomorphisms induced by the inclusions of lower level sets into each other. Whenever such inclusions exist for lower level sets of vector‐valued filtering functions, we can consider the multidimensional analog of persistent Betti numbers. Varying the lower level sets, we obtain that persistent Betti numbers can be seen as functions taking pairs of vectors to the set of non‐negative integers. In this paper, we prove stability of multidimensional persistent Betti numbers. More precisely, we prove that small changes of the vector‐valued filtering functions imply only small changes of persistent Betti numbers functions. This result can be obtained by assuming the filtering functions to be just continuous. Multidimensional stability opens the way to a stable shape comparison methodology based on multidimensional persistence. In order to obtain our stability theorem, some other new results are proved for continuous filtering functions. They concern the finiteness of persistent Betti numbers for vector‐valued filtering functions and the representation via persistence diagrams of persistent Betti numbers, as well as their stability, in the case of scalar‐valued filtering functions. Finally, from the stability of multidimensional persistent Betti numbers, we obtain a lower bound for the natural pseudo‐distance. Copyright © 2013 John Wiley & Sons, Ltd.     

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.     

Shape Dimension and Approximation from Samples

Abstract. There are many scientific and engineering applications where an automatic detection of shape dimension from sample data is necessary. Topological dimensions of shapes constitute an important global feature of them. We present a Voronoi-based dimension detection algorithm that assigns a dimension to a sample point which is the topological dimension of the manifold it belongs to. Based on this dimension detection, we also present an algorithm to approximate shapes of arbitrary dimension from their samples. Our empirical results with data sets in three dimensions support our theory.     

Shape Dimension and Approximation from Samples

   Abstract. There are many scientific and engineering applications where an automatic detection of shape dimension from sample data is necessary. Topological dimensions of shapes constitute an important global feature of them. We present a Voronoi-based dimension detection algorithm that assigns a dimension to a sample point which is the topological dimension of the manifold it belongs to. Based on this dimension detection, we also present an algorithm to approximate shapes of arbitrary dimension from their samples. Our empirical results with data sets in three dimensions support our theory.     

Geometrical shape comparison by size theory

Size Theory allows us to compare shapes of topological spaces and manifolds with respect to properties described by real functions. The main tools used in Size Theory are some pseudo-distances measuring the minimal changes of these real functions under the action of homeomorphisms. This method can be adapted to several different definitions of shape without changing its geometrical-topological framework. Some new results about this approach to shape comparison are illustrated. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

凸体形状匹配的参考点

本文研究了在平移变换下凸体形状的匹配．通过估计凸体形心与凸体内可测子集形心之间的距离的方法，得到了形心之间距离的不等式和形心是凸体在形状匹配下的参考点的结论．     

A spectral notion of Gromov–Wasserstein distance and related methods

We introduce a spectral notion of distance between objects and study its theoretical properties. Our distance satisfies the properties of a metric on the class of isometric shapes, which means, in particular, that two shapes are at 0 distance if and only if they are isometric when endowed with geodesic distances. Our construction is similar to the Gromov–Wasserstein distance, but rather than viewing shapes merely as metric spaces, we define our distance via the comparison of heat kernels. This allows us to establish precise relationships of our distance to previously proposed spectral invariants used for data analysis and shape comparison, such as the spectrum of the Laplace–Beltrami operator, the diagonal of the heat kernel, and certain constructions based on diffusion distances. In addition, the heat kernel encodes a natural notion of scale, which is useful for multi-scale shape comparison. We prove a hierarchy of lower bounds for our distance, which provide increasing discriminative power at the cost of an increase in computational complexity. We also explore the definition of other spectral metrics on collections of shapes and study their theoretical properties.     

Clustering reduced interval data using Hausdorff distance

Summary  In the last decade, factorial and clustering techniques have been developed to analyze multidimensional interval data (MIDs). In classic data analysis, PCA and clustering of the most significant components are usually performed to extract cluster structure from data. The clustering of the projected data is then performed, once the noise is filtered out, in a subspace generated by few orthogonal variables. In the framework of interval data analysis, we propose the same strategy. Several computational questions arise from this generalization. First of all, the representation of data onto a factorial subspace: in classic data analysis projected points remain points, but projected MIDs do not remains MIDs. Further, the choice of a distance between the represented data: many distances between points can be computed, few distances between convex sets of points are defined. We here propose optimized techniques for representing data by convex shapes, for computing the Hausdorff distance between convex shapes, based on an L ₂ norm, and for performing a hierarchical clustering of projected data.     

High dimensional data analysis using multivariate generalized spatial quantiles

High dimensional data routinely arises in image analysis, genetic experiments, network analysis, and various other research areas. Many such datasets do not correspond to well-studied probability distributions, and in several applications the data-cloud prominently displays non-symmetric and non-convex shape features. We propose using spatial quantiles and their generalizations, in particular, the projection quantile, for describing, analyzing and conducting inference with multivariate data. Minimal assumptions are made about the nature and shape characteristics of the underlying probability distribution, and we do not require the sample size to be as high as the data-dimension. We present theoretical properties of the generalized spatial quantiles, and an algorithm to compute them quickly. Our quantiles may be used to obtain multidimensional confidence or credible regions that are not required to conform to a pre-determined shape. We also propose a new notion of multidimensional order statistics, which may be used to obtain multidimensional outliers. Many of the features revealed using a generalized spatial quantile-based analysis would be missed if the data was shoehorned into a well-known probabilistic configuration.     

三角域上带两个形状参数的Bézier曲面的扩展

给出了三角域上带双参数λ1,λ2的类三次Bernstein基函数,它是三角域上三次Bernstein基函数的扩展.分析了该组基的性质并定义了三角域上带有两个形状参数λ1,λ2的类三次Bernstein-Bézier(B-B)参数曲面.该基函数及参数曲面分别具有与三次Bernstein基函数及三次B-B参数曲面类似的性质.当λ1,λ2取特殊的值时,可分别得到三次Bernstein基函数及三次B-B参数曲面以及参考文献中所定义的类三次Bernstein基函数及类三次B-B参数曲面.由实例可知,通过改变形状参数的取值,可以调整曲面的形状.     

基于剪枝信任度传播的手写体目标形状匹配方法

手写体识别中,目标形状的匹配是较为重要的工作.为了提高手写体目标形状的匹配速度,提出一种新的匹配方法.由于手写体目标形状的几何先验知识已知,并可以采用少量的参数进行表示,新方法采用参数化可变形模板匹配目标形状,确定其后验概率模型,并定义剪枝信任度空间,依据信任度传播算法的特性,首次将剪枝信任度传播算法应用于求解可变形模板与目标形状之间的最佳匹配.实验结果显示,在灰度图像中,对手写体目标形状的轮廓检测与定位速度显著提高.提出将剪枝信任度传播方法应用于手写体目标形状的匹配工作,能够使得目标形状填补空白,应用于相关性较为稀疏的图模型中.     

Multidimensional Jensen’s operator on a Hilbert space and applications

Motivated by a joint concavity of connections, solidarities and multidimensional weighted geometric mean, in this paper we extend an idea of convexity (concavity) to operator functions of several variables. With the help of established definitions, we introduce the so called multidimensional Jensen’s operator and study its properties. In such a way we get the lower and upper bounds for the above mentioned operator, expressed in terms of non-weighted operator of the same type. As an application, we obtain both refinements and converses for operator variants of some well-known classical inequalities. In order to obtain the refinement of Jensen’s integral inequality, we also consider an integral analogue of Jensen’s operator for functions of one variable.     

Gromov–Wasserstein Distances and the Metric Approach to Object Matching

This paper discusses certain modifications of the ideas concerning the Gromov–Hausdorff distance which have the goal of modeling and tackling the practical problems of object matching and comparison. Objects are viewed as metric measure spaces, and based on ideas from mass transportation, a Gromov–Wasserstein type of distance between objects is defined. This reformulation yields a distance between objects which is more amenable to practical computations but retains all the desirable theoretical underpinnings. The theoretical properties of this new notion of distance are studied, and it is established that it provides a strict metric on the collection of isomorphism classes of metric measure spaces. Furthermore, the topology generated by this metric is studied, and sufficient conditions for the pre-compactness of families of metric measure spaces are identified. A second goal of this paper is to establish links to several other practical methods proposed in the literature for comparing/matching shapes in precise terms. This is done by proving explicit lower bounds for the proposed distance that involve many of the invariants previously reported by researchers. These lower bounds can be computed in polynomial time. The numerical implementations of the ideas are discussed and computational examples are presented.     

Witnessed k-Distance

Distance functions to compact sets play a central role in several areas of computational geometry. Methods that rely on them are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced distance to a measure offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. A combinatorial explosion hinders working with distance to a measure as an ordinary power distance function. In this paper, we analyze an approximation scheme that keeps the representation linear in the size of the input, while maintaining the guarantees on the inference quality close to those for the exact but costly representation.     

A new type of the generalized Bézier curves

In this paper, we improve the generalized Bernstein basis functions introduced by Han, et al. The new basis functions not only inherit the most properties of the classical Bernstein basis functions, but also reserve the shape parameters that are similar to the shape parameters of the generalized Bernstein basis functions. The degree elevation algorithm and the conversion formulae between the new basis functions and the classical Bernstein basis functions are obtained. Also the new Q-Bézier curve and surface...