Entropy,Universal Coding,Approximation, and Bases Properties

We shall present here results concerning the metric entropy of spaces of linear and nonlinear approximation under very general conditions. Our first result computes the metric entropy of the linear and m-terms approximation classes according to a quasi-greedy basis verifying the Temlyakov property. This theorem shows that the second index r is not visible throughout the behavior of the metric entropy. However, metric entropy does discriminate between linear and nonlinear approximation. Our second result extends and refines a result obtained in a Hilbertian framework by Donoho, proving that under orthosymmetry conditions, m-terms approximation classes are characterized by the metric entropy. Since these theorems are given under the general context of quasi-greedy bases verifying the Temlyakov property, they have a large spectrum of applications. For instance, it is proved in the last section that they can be applied in the case of L _p norms for R ^d for 1 < p < \infty. We show that the lower bounds needed for this paper in fact follow from quite simple large deviation inequalities concerning hypergeometric or binomial distributions. To prove the upper bounds, we provide a very simple universal coding based on a thresholding-quantizing constructive procedure.     

First Order Approach and Index Theorems for Discrete and Metric Graphs

The aim of the present paper is to introduce a unified notion of Laplacians on discrete and metric graphs. In order to cover all self-adjoint vertex conditions for the associated metric graph Laplacian, we develop systematically a new type of discrete graph operators acting on a decorated graph. The decoration at each vertex of degree d is given by a subspace of , generalising the fact that a function on the standard vertex space has only a scalar value. We illustrate the abstract concept by giving classical examples throughout the article. Our approach includes infinite graphs as well. We develop the notion of exterior derivative, differential forms, Dirac and Laplace operators in the discrete and metric case, using a supersymmetric framework. We calculate the (supersymmetric) index of the discrete Dirac operator generalising the standard index formula involving the Euler characteristic of a graph. Finally, we show that for finite graphs, the corresponding index for the metric Dirac operator agrees with the discrete one.     

On completion of fuzzy metric spaces

Completions of fuzzy metric spaces (in the sense of George and Veeramani) are discussed. A complete fuzzy metric space Y is said to be a˜fuzzy metric completion of a˜given fuzzy metric space X if X is isometric to a˜dense subspace of Y. We present an example of a˜fuzzy metric space that does not admit any fuzzy metric completion. However, we prove that every standard fuzzy metric space has an (up to isometry) unique fuzzy metric completion. We also show that for each fuzzy metric space there is an (up to uniform isomorphism) unique complete fuzzy metric space that contains a˜dense subspace uniformly isomorphic to it.     

On the stability of Riemannian manifold with parallel spinors

Inspired by the recent work [HHM03], we prove two stability results for compact Riemannian manifolds with nonzero parallel spinors. Our first result says that Ricci flat metrics which also admit nonzero parallel spinors are stable (in the direction of changes in conformal structures) as the critical points of the total scalar curvature functional. Our second result, which is a local version of the first one, shows that any metric of positive scalar curvature cannot lie too close to a metric with nonzero parallel spinor. We also prove a rigidity result for special holonomy metrics. In the case of SU(m) holonomy, the rigidity result implies that scalar flat deformations of Calabi-Yau metric must be Calabi-Yau. Finally we explore the connection with a positive mass theorem of [D03], which presents another approach to proving these stability and rigidity results. Dedicated to Jeff Cheeger for his sixtieth birthday     

Ricci soliton homogeneous nilmanifolds

We study a notion weakening the Einstein condition on a left invariant Riemannian metric g on a nilpotent Lie groupN. We consider those metrics satisfying Ric for some and some derivationD of the Lie algebra ofN, where Ric denotes the Ricci operator of . This condition is equivalent to the metric g to be a Ricci soliton. We prove that a Ricci soliton left invariant metric on N is unique up to isometry and scaling. The following characterization is also given: (N,g) is a Ricci soliton if and only if (N,g) admits a metric standard solvable extension whose corresponding standard solvmanifold is Einstein. This gives several families of new examples of Ricci solitons. By a variational approach, we furthermore show that the Ricci soliton homogeneous nilmanifolds (N,g) are precisely the critical points of a natural functional defined on a vector space which contains all the homogeneous nilmanifolds of a given dimension as a real algebraic set. Received August 24, 1999 / Revised October 2, 2000 / Published online February 5, 2001     

The Center Conjecture for Spherical Buildings of Types F 4 and E 6

We prove that a convex subcomplex of a spherical building of type F ₄ or E ₆ is a sub-building or the automorphisms of the subcomplex fix a point on it. Our approach is differential-geometric and based on the theory of metric spaces with curvature bounded above. We use these techniques also to give another proof of the same result for the spherical buildings of classical type.     

Shape Optimization for Stokes Flows using Conformal Metrics

We derive a shape optimization approach for a two-dimensional Stokes flow problem. Our goal is to compute a geometry whose wall shear stress is L₂-close to a desired target stress. Computations are carried out on a fixed domain, while shape variations are described through conformal metric changes. Tools from differential geometry are used to handle metric dependent operators. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multipoint problem for hyperbolic equations with variable coefficients

By using the metric approach, we study the problem of classical well-posedness of a problem with multipoint conditions with respect to time in a tube domain for linear hyperbolic equations of order 2n (n ≥ 1) with coefficients depending onx. We prove metric theorems on lower bounds for small denominators appearing in the course of the solution of the problem.     

Existence,uniqueness, and algorithmic computation of general lilypond systems

The lilypond system based on a locally finite subset φ of the Euclidean space ?ⁿ is defined as follows. At time 0 every point of φ starts growing with unit speed in all directions to form a system of balls in which any particular ball ceases its growth at the instant that it collides with another ball. Based on a more formal definition of lilypond systems given in 1 , we will prove that these systems exist and are uniquely determined. Our approach applies to the far more general setting, where φ is a locally finite subset of some space ?? equipped with a pseudo‐metric d. We will also derive an algorithm approximating the system with at least linearly decreasing error. Several examples will illustrate our general results. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On geometric vector fields of Minkowski spaces and their applications

As it is well-known, a Minkowski space is a finite dimensional real vector space equipped with a Minkowski functional F. By the help of its second order partial derivatives we can introduce a Riemannian metric on the vector space and the indicatrix hypersurface S:=F⁻¹(1) can be investigated as a Riemannian submanifold in the usual sense.Our aim is to study affine vector fields on the vector space which are, at the same time, affine with respect to the Funk metric associated with the indicatrix hypersurface. We give an upper bound for the dimension of their (real) Lie algebra and it is proved that equality holds if and only if the Minkowski space is Euclidean. Criteria of the existence is also given in lower dimensional cases. Note that in case of a Euclidean vector space the Funk metric reduces to the standard Cayley-Klein metric perturbed with a nonzero 1-form.As an application of our results we present the general solution of Matsumoto's problem on conformal equivalent Berwald and locally Minkowski manifolds. The reasoning is based on the theory of harmonic vector fields on the tangent spaces as Riemannian manifolds or, in an equivalent way, as Minkowski spaces. Our main result states that the conformal equivalence between two Berwald manifolds must be trivial unless the manifolds are Riemannian.     

A maximumb-matching problem arising from median location models with applications to the roommates problem

We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Statistical morphisms and related invariance properties

Our aim is to investigate a way to characterize the elements of a statistical manifold (the metric and the family of connections) using invariance properties suggested by Le Cam's theory of experiments. We distinguish the case where the statistical manifold is flat. Then, there naturally exists an entropy and it is proven that experiment invariance is equivalent to entropy invariance. If the statistical manifold is not flat, we introduce a notion of local invariance of selected order associated to the asymptotic (on n observations, n tending to infinity) expansion of the power of the Neymann Pearson test in a contiguous neighborough of some point. This invariance provides a substantial number of morphisms. This was not always true for the entropy invariance: particularly, the case of Gaussian experiments is investigated where it can be proven that entropy invariance does not characterize a metric or a family of connections.     

The Socle of a Metric n-Lie Algebra

We define the socle of an n-Lie algebra as the sum of all the minimal ideals. An n-Lie algebra is called metric if it is endowed with an invariant nondegenerate symmetric bilinear form. We characterize the socle of a metric n-Lie algebra, which is closely related to the radical and the center of the metric n-Lie algebra. In particular, the socle of a metric n-Lie algebra is reductive, and a metric n-Lie algebra is solvable if and only if the socle coincides with its center. We also calculate the metric dimensions of simple and reductive n-Lie algebras and give a lower bound in the nonreductive case.     

Advances in metric embedding theory

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few. The mathematical theory of metric embedding is well studied in both pure and applied analysis and has more recently been a source of interest for computer scientists as well. Most of this work is focused on the development of bi-Lipschitz mappings between metric spaces. In this paper we present new concepts in metric embeddings as well as new embedding methods for metric spaces. We focus on finite metric spaces, however some of the concepts and methods are applicable in other settings as well.One of the main cornerstones in finite metric embedding theory is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with distortion. Bourgain?s result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is natural to ask: can an embedding do much better in terms of the average distortion? Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain?s theorem. In fact, our embedding possesses a much stronger property. We define the ?q-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible ?q-distortion for all 1?q?∞simultaneously.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension of the host space. The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain?s embedding. Our embedding methods achieve better dimension, and in fact, shed new light on another fundamental question in metric embedding, which is: whether the embedding dimension of a metric space is related to its intrinsic dimension? I.e., whether the dimension in which it can be embedded in some real normed space is related to the intrinsic dimension which is reflected by the inherent geometry of the space, measured by the space?s doubling dimension. The existence of such an embedding was conjectured by Assouad,⁴and was later posed as an open problem in several papers. Our embeddings give the first positive result of this type showing any finite metric space obtains a low distortion (and constant average distortion) embedding in Euclidean space in dimension proportional to its doubling dimension.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary finite metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results.The results presented in this paper⁵have been the basis for further developments both within the field of metric embedding and in other areas such as graph theory, distributed computing and algorithms. We present a comprehensive study of the notions and concepts introduced here and provide additional extensions, related results and some examples of algorithmic applications.     

Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

Wijsman topology on function spaces

LetC(X,Y) be the space of continuous functions from a metric space (X,d) to a metric space (Y, e).C(X, Y) can be thought as subset of the hyperspaceCL(X×Y) of closed and nonempty subsets ofX×Y by identifying each element ofC(X,Y) with its graph. We considerC(X,Y) with the topology inherited from the Wijsman topology induced onCL(X×Y) by the box metric ofd ande. We study the relationships between the Wijsman topology and the compact-open topology onC(X,Y) and also conditions under which the Wijsman topology coincide with the Fell topology. Sufficient conditions under which the compactopen topology onC(X,Y) is weaker than the Wijsman topology are given (IfY is totally bounded, then for every metric spaceX the compactopen topology onC(X,Y) is weaker than the Wijsman topology and the same is true forX locally connected andY rim-totally bounded). We prove that a metric spaceX is boundedly compact iff the Wijsman topology onC(X, ℝ) is weaker than the compact-open topology. We show that ifX is a σ-compact complete metric space andY a compact metric space, then the Wijsman topology onC(X,Y) is Polish.     

Global sufficiency of extreme order statistics in location models of Weibull type

Summary In Janssen and Reiss (1988) it was shown that in a location model of a Weibull type sample with shape parameter –1<a<1 thek(n) lower extremes are asymptotically local sufficient. In the present paper we show that even global sufficiency holds. Moreover, it turns out that convergence of the given statistical experiments in the deficiency metric does not only hold for compact parameter sets but for the whole real line.     

A Class of Homogeneous Einstein Manifolds

A Riemannian manifold (M, g) is called Einstein manifold if its Ricci tensor satisfies r = c·g for some constant c. General existence results are hard to obtain, e.g., it is as yet unknown whether every compact manifold admits an Einstein metric. A natural approach is to impose additional homogeneous assumptions. M. Y. Wang and W. Ziller have got some results on compact homogeneous space G/H. They investigate standard homogeneous metrics, the metric induced by Killing form on G/H, and get some classification results. In this paper some more general homogeneous metrics on some homogeneous space G/H are studies, and a necessary and sufficient condition for this metric to be Einstein is given. The authors also give some examples of Einstein manifolds with non-standard homogeneous metrics.     

On Average Distortion of Embedding Metrics into the Line

We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. The paper mostly deals with embeddings into the real line with a low (as much as it is possible) average distortion. Our main technical contribution is that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) undirected weighted graphs can be embedded into the line with constant average distortion. This has implications, e.g., on the value of the MinCut–MaxFlow gap in uniform-demand multicommodity flows on such graphs. A preliminary version of this paper has appeared at STOC’03, pp. 156–162. Supported in part by a grant ISF-247-02-10.5.     

Existence and Uniqueness of Green's Functions to Nonlinear Yamabe Problems

For a given finite subset S of a compact Riemannian manifold (M,g) whose Schouten curvature tensor belongs to a given cone, we establish a necessary and sufficient condition for the existence and uniqueness of a conformal metric on M\S such that each point of S corresponds to an asymptotically flat end and that the Schouten tensor of the conformal metric belongs to the boundary of the given cone. As a by-product, we define a purely local notion of Ricci lower bounds for continuous metrics that are conformal to smooth metrics and prove a corresponding volume comparison theorem. © 2022 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC.