Conversion of deviation and its use for determining a coordinate system from a set of distances

Introduction


Applied mathematics can be considered as a set of tools that allow you to solve certain problems that arise in practice. In this article we will consider one of such tools - the deviation transformation as applied to the analysis of the Euclidean distance matrix . The spectrum of the resulting matrix allows you to judge the dimension of the source data and calculate the coordinates of the source points relative to its own center of coordinates.

Suppose we have n > 2 points and all the distances between them are known. The potential dimension of space is n-1 . It is necessary to determine the space of which dimension the given points belong, as well as the coordinates of the points in this space.
One of the indirect methods for determining the dimensionality of space based on the distances between points is to calculate the Cayley-Menger determinant (CM) . However, this method is of little use for the analysis of spaces of large dimension.

1. Conversion of deviation


So, we have at the input a certain symmetric matrix M of dimension N with zero trace (the elements of the main diagonal are equal to zero). We need to define the transformation into some new matrix the U . In this case, the values ​​of the original matrix should be calculated from the new one according to the rules of addition of distances:



Then the values ​​of the matrix M can be expressed in terms of the spectrum U as the weighted sum of the difference of the squares of the components of the eigenvectors:



Here is the set of eigenvalues ​​of the matrix U , and is the matrix of eigenvectors corresponding to the eigenvalues. The length of the vectors is normalized to 1. The
general form of the matrix Usatisfying condition (1.1) is the expression:



Here is an arbitrary vector, and is an arbitrary constant. To determine these values, additional conditions must be specified. Such a condition is a requirement laplasianopodobiya matrix of the U . In the Laplacian matrix, the elements of the main diagonal are equal to the sum of the elements of the corresponding column (row) with the opposite sign:



Substituting (1.3) into (1.4) taking into account the symmetry of M , we obtain the identity:



from which we determine the desired expressions for the vector and constants:




Thus, the vector in (1.3) is the vector of the average values ​​of the row (column) of the original matrix (in terms of graphs, the average cardinality / degree of the vertex of the graph), and the constant is the average value of the matrix as a whole (average degree of the vertices of the entire graph):



Transformation (1.3 ' ) we called the deviation transformation , since it reflects the deviation (deviation) of the values ​​of the original matrix from the average values. The result of the transformation will be called the deviation matrix .

2. Properties of the deviation matrix


The matrix is ​​degenerate (zero determinant and one of the eigenvalues) - a consequence of the requirement of Laplacianism.
Elements of the main deviation diagonal reflect the average values ​​of the original matrix:



The deviation trace is associated with the average value of the original matrix and can be expressed in terms of the sum of the eigenvalues:



The product of the eigenvalues ​​is proportional to the potential of the deviation — the nonzero minor of the matrix:



Deviation is reversible. Based on the deviation matrix, you can restore the original one:



Note that the deviation transformation is abstract and is not connected specifically with the metric matrix. So, applying the deviation transform to a resistive distance matrixallows you to get the inverse Laplacian matrix of the conductivity matrix. That is, in the end, restore the conductivity matrix from the matrix of resistive distances.

Next, we consider the application of the deviation transform to a metric matrix (Euclidean distances).

3. Distance deviation, own coordinate system


So, let at the entrance we have many points with given distances between them. All distances are known — between any pair — the distance graph is complete. Here we consider the direct problem - it is necessary to determine the dimensionality of the space to which the points and their coordinates in this space belong.

The initial set of distances can be represented as a symmetric matrix of squares of distances between points. We denote this matrix as D2 , where two denotes a square. Applying the deviation operation to the matrix of squares of distances gives the matrix of deviation of distances G :



This matrix and its spectrum have remarkable properties. Namely:
  • The number of nonzero eigenvalues ​​(matrix rank) coincides with the dimensionality of the space in which the starting points are located.
  • The values ​​of the eigenvectors are the coordinates of the points in the new space.
  • The symmetry of the eigenvalues ​​reflects the symmetry of the relative positions of the points.

Thus, the spectrum of the distance deviation matrix determines its own coordinate system of the initial set of points. The weight of each coordinate is determined by the value of the spectrum (eigenvalue). The center of the new coordinate system is called the centroid . On the main diagonal of the deviation matrix are the squares of the distance from the centroid to the vertices:



The sum of all such distances (trace of deviation) determines the average radius of the set R2 . This radius is equal to the sum of the spectrum values ​​and is associated with the average value of the original distance matrix in accordance with formula (2.2):



Set centroid minimizes average set radius. That is, for any other centroid position, the average set radius will be of greater importance. Adding the centroid itself to the original set of points does not change the spectrum, since the centroid of the new set coincides with the old one.

4. Spectra of some sets


Spectra of three peaks (triangles)


So, a hammer appeared in our hands. We are looking for nails.
For one / two points, the deviation matrix does not make much sense. Two non-identical points always belong to one straight line, that is, to one-dimensional space.
But for three points already appear options. The simplest case is the vertices of an equilateral triangle. If the side length is 1, then the deviation matrix will look like: The



trace of this matrix is ​​1, and the potential is (1/3) ^ 2 - (1/6) ^ 2 = 1/9 - 1/36 = 1/12.
We consider the spectrum (in brackets are the squares of the distances between the points):



Here, on the left, the eigenvalues ​​of the spectrum are shown, and on the right are the corresponding values ​​of the vectors (coordinates).
We see that:
  • The spectrum has two meanings. This is understandable - a non-degenerate triangle always belongs to a 2-dimensional space (plane).
  • Both eigenvalues ​​are equal. This is a consequence of the symmetry of an equilateral triangle.

Let's check the properties of the spectrum: the sum of the eigenvalues ​​is 1, the product is 1/2 * 1/2 = 1/4 = 1/12 * 3. That's right.

In passing, we note that the spectrum of the three vertices is related to the area of ​​the triangle formed by them (a variation of the Heron formula):



Accordingly, the square of the area of ​​an equilateral 1-triangle is 3/4 * 1/4 = 3/16.

Moving on. If the points belong to one line, then the spectrum should contain only one value.
We calculate the spectrum value for three points of the segment (two at the edges and one in the middle) . We



get : Indeed, the spectrum contains only one component. The centroid is in the middle of the line, as expected.

Now we ask a tricky question - to which space does the impossible triangle belong, that is, the one in which the brokentriangle inequality ?

The answer is obvious to those who know it.
For a “triangle” of the form, the spectrum will consist of two values ​​- one positive (4.5), and the other negative (-0.833).

If the spectrum contains negative values, then this means that in Euclidean space a set of points with such characteristics cannot be realized — the coordinates of the points become imaginary. You can use this spectrum property to check the validity of the distance matrix.

Respite


We pause and look around. We defined the deviation transformation and applied it to the squares matrix of distances. The resulting distance deviation matrix reflects the space properties of the original set of points.

To numerically verify the described properties for small matrices, you can interactively use spreadsheets and the wolframalpha service to calculate eigenvalues ​​/ vectors.

If there are no big objections, then in the next article we will continue to consider the spectral properties of some standard sets of geometric points — lattices, shapes, lines, and also look at the spectra of sets of shapes.

To be continued ...

Also popular now: