Characterization of multispherical and block structures of Euclidean distance matrices

This paper presents some new characterizations of Euclidean distance matrices (EDMs) of special structures. More specifically, we discuss multispherical and block-structured EDMs, each of which can be viewed as a generalization of spherical EDM. We focus on a well-known inequality that characterizes spherical EDMs and extend it to the sets of multispherical and block-structured EDMs. Some related results are also presented.     

A remark on the faces of the cone of Euclidean distance matrices

A new characterization of the faces of the cone of Euclidean distance matrices (EDMs) was recently obtained by Tarazaga in terms of LGS(D), a special subspace associated with each EDM D. In this note we show that LGS(D) is nothing but the Gale subspace associated with EDMs.     

Computing the nearest Euclidean distance matrix with low embedding dimensions

Euclidean distance embedding appears in many high-profile applications including wireless sensor network localization, where not all pairwise distances among sensors are known or accurate. The classical Multi-Dimensional Scaling (cMDS) generally works well when the partial or contaminated Euclidean Distance Matrix (EDM) is close to the true EDM, but otherwise performs poorly. A natural step preceding cMDS would be to calculate the nearest EDM to the known matrix. A crucial condition on the desired nearest EDM is for it to have a low embedding dimension and this makes the problem nonconvex. There exists a large body of publications that deal with this problem. Some try to solve the problem directly and some are the type of convex relaxations of it. In this paper, we propose a numerical method that aims to solve this problem directly. Our method is strongly motivated by the majorized penalty method of Gao and Sun for low-rank positive semi-definite matrix optimization problems. The basic geometric object in our study is the set of EDMs having a low embedding dimension. We establish a zero duality gap result between the problem and its Lagrangian dual problem, which also motivates the majorization approach adopted. Numerical results show that the method works well for the Euclidean embedding of Network coordinate systems and for a class of problems in large scale sensor network localization and molecular conformation.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

An ordering of dependence for contingency tables

A majorization ordering is defined on matrices with the same row and column sums. This ordering is used as an ordering of dependence for contingency tables. Results are derived for maximal and minimal matrices with respect to the majorization ordering. This theory can be used to maximize and minimize Schur concave functions defined over matrices, when there are row and column sum constraints; in this paper, it is applied to the algorithm of Mehta and Patel (1983) for finding the P-value of Fisher's exact test.     

Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation

One of the challenging problems in collaborative position localization arises when the distance measurements contain non-line-of-sight (NLOS) biases. Convex optimization has played a major role in modelling such problems and numerical algorithm developments. One of the successful examples is the semi-definite programming (SDP), which translates Euclidean distances into the constraints of positive semidefinite matrices, leading to a large number of constraints in the case of NLOS biases. In this paper, we propose a new convex optimization model that is built upon the concept of Euclidean distance matrix (EDM). The resulting EDM optimization has an advantage that its Lagrangian dual problem is well structured and hence is conducive to algorithm developments. We apply a recently proposed 3-block alternating direction method of multipliers to the dual problem and tested the algorithm on some real as well as simulated data of large scale. In particular, the EDM model significantly outperforms the existing SDP model and several others.     

On Kendall-Ressel and related distributions

We delineate a connection of Kendall-Ressel and related laws with the lower real branch of Lambert W function. A characterization of the canonical member of Kendall-Ressel class is found. The Letac-Mora interpretation of the reciprocity of two specific NEFs is extended by considering two related reproductive EDMs. A local limit theorem on gamma convergence for the reproductive back-shifted Kendall-Ressel EDM is derived. Each member of this EDM is self-decomposable and unimodal, but not strongly unimodal. The coefficient of variation, skewness and kurtosis of each representative of this EDM are higher than the corresponding measures for the members of gamma and inverse Gaussian EDMs. An integral representation for the lower real branch of Lambert W function is given.     

Euclidean distance matrices: new characterization and boundary properties

In this article we give a new characterization of Euclidean distance matrices using known necessary conditions. We also relate this characterization with the faces of the cone and give new properties for the boundary. Finally, a new characterization of spherical/non-spherical matrices is proposed.     

Eigenstructure of distance matrices with an equal distance subset

We characterize the distance matrices with an equal distance subset in terms of eigenstructure and determine EDMs in this class by examination of a lower dimensional matrix.     

The coarea formula for real‐valued Lipschitz maps on stratified groups

We establish a coarea formula for real‐valued Lipschitz maps on stratified groups when the domain is endowed with a homogeneous distance and level sets are measured by the Q – 1 dimensional spherical Hausdorff measure. The number Q is the Hausdorff dimension of the group with respect to its Carnot–Carathéodory distance. We construct a Lipschitz function on the Heisenberg group which is not approximately differentiable on a set of positive measure, provided that the Euclidean notion of differentiability is adopted. The coarea formula for stratified groups also applies to this function, where the Euclidean one clearly fails. This phenomenon shows that the coarea formula holds for the natural class of Lipschitz functions which arises from the geometry of the group and that this class may be strictly larger than the usual one. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some Properties for the Euclidean Distance Matrix and Positive Semidefinite Matrix Completion Problems

The Euclidean distance matrix (EDM) completion problem and the positive semidefinite (PSD) matrix completion problem are considered in this paper. Approaches to determine the location of a point in a linear manifold are studied, which are based on a referential coordinate set and a distance vector whose components indicate the distances from the point to other points in the set. For a given referential coordinate set and a corresponding distance vector, sufficient and necessary conditions are presented for the existence of such a point that the distance vector can be realized. The location of the point (if it exists) given by the approaches in a linear manifold is independent of the coordinate system, and is only related to the referential coordinate set and the corresponding distance vector. An interesting phenomenon about the complexity of the EDM completion problem is described. Some properties about the uniqueness and the rigidity of the conformation for solutions to the EDM and PSD completion problems are presented.     

An extension of a result of Hwang and Pyo

In this paper, we extend a majorization result of Hwang and Pyo [LAA 332-334 (2001) pp. 15-21] from the ordinary majorization ordering to the class of group induced cone orderings induced by non-effective groups. The case of effective groups is also investigated. A particular attention is paid to positive operators.     

Bi-criteria evolution strategy in estimating weights from the AHP ratio-scale matrices

The problem of deriving weights from ratio-scale matrices in an analytic hierarchy process (AHP) is addressed by researchers worldwide. There are various ways to solve the problem that are generally grouped into simple matrix and optimization methods. All methods have received criticism regarding the accuracy of derived weights, and different criteria are in use to compare the weights obtained from different methods. Because the set of Pareto non-dominated solutions (weights) is unknown and for inconsistent matrices is indefinite, a bi-criterion optimization approach is proposed for manipulating such matrices. The problem-specific evolution strategy algorithm (ESA) is implemented for a robust stochastic search over a feasible indefinite solution space. The fitness function is defined as a scalar vector function composed of the common error measure, i.e. the Euclidean distance and a minimum violation error that accounts for no violation of the rank ordering. The encoding scheme and other components of the search engine are adjusted to preserve the imposed constraints related to the required normalized values of the weights. The solutions generated by the proposed approach are compared with solutions obtained by five well-known prioritization techniques for three judgment matrices taken from the literature. In these and other test applications, the prioritization method that uses the entitled weights estimation by evolution strategy algorithm (WEESA) appears to be superior to other methods if only two, the most commonly used methods, are applied: the Euclidean distance and minimum violation exclusion criteria.     

On properties of cell matrices

In this paper properties of cell matrices are studied. A determinant of such a matrix is given in a closed form. In the proof a general method for determining a determinant of a symbolic matrix with polynomial entries, based on multivariate polynomial Lagrange interpolation, is outlined. It is shown that a cell matrix of size n>1 has exactly one positive eigenvalue. Using this result it is proven that cell matrices are (Circum-)Euclidean Distance Matrices ((C)EDM), and their generalization, k-cell matrices, are CEDM under certain natural restrictions. A characterization of k-cell matrices is outlined.     

The Euclidean Distance Degree of an Algebraic Variety

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low-rank matrices, the Eckart–Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a general point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.     

Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming

Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming problem (SDP). Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed.     

Two theorems on Euclidean distance matrices and Gale transform

We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ(E−C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the cones

where is the elliptope (set of correlation matrices) and is the (closed convex) cone of EDMs.

The characterization is given using the Gale transform of the points generating D. We also show that given points , for any scalars λ₁,λ₂,…,λ_n such that

∑_j=1ⁿλ_jp^j=0, ∑_j=1ⁿλ_j=0,

we have

∑_j=1ⁿλ_jpⁱ−p^j2= forall i=1,…,n,

for some scalar independent of i.     

The euclidean distance degree of orthogonally invariant matrix varieties

The Euclidean distance degree of a real variety is an important invariant arising in distance minimization problems. We show that the Euclidean distance degree of an orthogonally invariant matrix variety equals the Euclidean distance degree of its restriction to diagonal matrices. We illustrate how this result can greatly simplify calculations in concrete circumstances.     

Intervals of totally nonnegative matrices

Totally nonnegative matrices, i.e., matrices having all their minors nonnegative, and matrix intervals with respect to the checkerboard ordering are considered. It is proven that if the two bound matrices of such a matrix interval are nonsingular and totally nonnegative (and in addition all their zero minors are identical) then all matrices from this interval are also nonsingular and totally nonnegative (with identical zero minors).     

A note on “Methods for constructing distance matrices and the inverse eigenvalue problem”

In this paper, a symmetric nonnegative matrix with zero diagonal and given spectrum, where exactly one of the eigenvalues is positive, is constructed. This solves the symmetric nonnegative eigenvalue problem (SNIEP) for such a spectrum. The construction is based on the idea from the paper Hayden, Reams, Wells, “Methods for constructing distance matrices and the inverse eigenvalue problem”. Some results of this paper are enhanced. The construction is applied for the solution of the inverse eigenvalue problem for Euclidean distance matrices, under some assumptions on the eigenvalues.