{'fraction_non_alphanumeric': 0.03371792321464094, 'fraction_numerical': 0.006763477222995823, 'mean_word_length': 4.667700112739571, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Realizability of Planar Point Embeddings from Angle Measurements

Localization of a set of nodes is an important and a thoroughly researched problem in robotics and sensor networks. This paper is concerned with the theory of localization from inner-angle measurements. We focus on the challenging case where no anchor locations are known. Inspired by Euclidean distance matrices, we investigate when a set of inner angles corresponds to a realizable point set. In particular, we find linear and non-linear constraints that are provably necessary, and we conjecture also sufficient for characterizing realizable angle sets. We confirm this in extensive numerical simulations, and we illustrate the use of these constraints for denoising angle measurements along with the reconstruction of a valid point set.


INTRODUCTION
Euclidean distance matrices (EDMs) are built from pairwise distances between points in Euclidean space [1,2,3]. They have a welldefined structure and properties, such as a rank constraint, which allows partial and noisy EDMs to be completed and denoised. This has been exploited in numerous applications including psychometrics, machine learning and room geometry reconstruction, to name a few. Since EDMs consider pairwise distances between arbitrary points, they correspond to localization problems of multiple nodes without anchors. These problems occur in various static and dynamic settings, for instance when the nodes are sensor networks [4], collaborating drone swarms [5] or firefighters [6].
In many applications, angle measurements can be exploited, complementing or replacing distances. For example, in localization, distances are estimated from received signal strength (RSS) or time of flight (TOF), whereas angles can be estimated from phase differences in multi-antenna systems. Angles have the advantage of removing the necessity of synchronization between nodes, and degrade less with distance than for instance RSS. Angle of arrival (AoA) will appear in the next Bluetooth standard [7] and will be an interesting alternative for Internet of Things (IoT) applications.
For inner-angle measurements, no exhaustive theory exists that can be exploited to denoise and complete angle measurements in a similar way. In this paper, we attempt to characterize inner angles between points in Euclidean space. In particular, we are interested in the question of realizability, which tells us if we can find a point set in a given dimension that exactly satisfies a given set of angle measurements.
This paper makes three main contributions. a) We find necessary conditions for inner-angle measurements to be realizable, consisting of linear and non-linear constraints which we exactly characterize. b) We observe that the proposed conditions are also sufficient in extensive simulations. c) By exploiting the above conditions, we construct an angle denoising and point recovery algorithm. Using this algorithm, we characterize the noise regimes in which angle measurements are preferred over distance measurements in simulation.

RELATED WORK
When measuring dissimilarities between points in terms of distances, a rich literature on distance geometry, and in particular EDMs, can be exploited for purposes such as denoising, completion, and point recovery [2,8]. In particular, it was shown that a matrix D ∈ R N ×N is an EDM if and only if − 1 2 J DJ is positive semi-definite, where J ∈ R N ×N is the geometric centering matrix, and N is the number of points [1]. By definition, if D is an EDM, there exists a point embedding in some dimension d for which Dij = pi − pj 2 , with pi, pj ∈ R d . Thanks to this property, point coordinates can be recovered from complete pairwise distances through a simple SVD, or via semi-definite programs (SDPs) for the incomplete case. The question we ask in this paper is if we can provide a similar characterization for angles: given a set of angle measurements, can these angles be realized by a point set?
Various methods have been proposed that incorporate both distance and angle information in point recovery algorithms [9,10,11,12,13,14]. For instance, the concept of edge kernels was introduced in [10], and the authors show that the angle and distance information can be estimated through matrix factorization. Although elegant, this concept does not address realizability. In fact, it was shown in [11] that the recovered angles cannot in general be realized, and additional linear constraints are added to the optimization problem to remedy this. Other methods have shown improved performance over distance-based SDPs by adding hyperplane-based constraints [12] or constraints based on the cosine law [13].
Localization from angles only has also been studied thoroughly. In vision-based systems, bearing-only localization is solved through trilateration [15]. In robot and sensor networks, distributed methods [16,17,18], Simultaneous Localization and Mapping (SLAM)based solutions [19,20], and centralized approaches [5,13] have been proposed. In the latter, a central processing unit collects data from all nodes and recovers their locations in a global manner. In distributed approaches, the nodes are self-localizing, and in most SLAM-based algorithms, the location of an active device and a (usually passive) map of landmarks are iteratively updated.
In this paper, we focus on the complete, centralized localization problem, meaning that we globally process all inner angles at once. We do not require knowledge of the node's orientations or any anchor nodes. In practice we rarely have access to all measurements, in which case the proposed theory can be used for completion and denoising. Our work is close in nature to an early work on anglebased planar graph embedding [21]. The authors prove conditions recovery from distances recovery from inner angles for an angle set to correspond to a planar and convex planar graph with no crossing edges. We relax these assumptions to graphs lying in 2 dimensions, with arbitrary edge layouts. By doing so, we can construct an optimization problem on angles only, which characterizes the maximum likelihood estimator under a Gaussian noise assumption, and ensures realizability.

Problem setup
We denote by P = pi ∈ R d |i = 1 . . . N the point embedding that we aim to recover, where d is the (known) dimension of the embedding space and N is the number of points. We focus on the two-dimensional case, but we use the general notation d where applicable. The non-directed inner angle measured at point pi between two points pj and pk is denoted by θi(j, k) = θi(k, j) ∈ [0, π]. As we only consider inner angles, we drop the "inner" attribute in what follows. We introduce the index set I, which contains all triplets (i, j, k) of angles, with |I| = N (N − 1)(N − 2)/2 := M . By introducing an order on I, denoted by m(i, j, k) = 1 . . . M , we stack all angles in a vector denoted by θ ∈ R M . In this work we do not address the labeling problem, so we assume we know the indices (i, j, k) for each m.
For the scope of this paper, we rule out degenerate point sets in which any angle θm is exactly either zero or π. When randomly choosing points, such setups occur with probability zero, and in practice they should be avoided because of ill-conditioning.
We define the notion of a point set's equivalency class as follows: Two point sets belong to the same equivalency class if each node has the the same circular clockwise sequence of edges in both point sets. The same notion was introduced in [21]. As we will see later, this helps in setting up linear constraints since the linear constraints matrix A is the same for all point sets in the same class.
We conclude this section by defining the notion of a realizable angle vector, which is the main concept we study. Definition 1. An angle vector θ is realizable if and only if there exists a point embedding P such that ∠(pj − pi, pk − pi) = θ m(i,j,k) for all index triplets in I.

Degrees of freedom of realizable angles
When we measure the relative dissimilarities of points using distances or angles, some information is irrecoverably lost, as visualized in Figure 1. Using distances, the absolute translation (d parameters), orientation and reflection (d(d − 1)/2 parameters) of the point set are lost. Although N points in d-dimensional space have N d degrees of freedom, the pairwise differences only retain N d − d − d(d − 1)/2 = N d − d(d + 1)/2 degrees of freedom. When measuring only angles, we additionally lose scale information, leading to one degree of freedom less: We can conclude that we need at least DOF angle measurements to accurately recover a point embedding, up to a rigid transformation and scale -the best that can be done from angle measurements.

Recovering points from angles
To recover point sets from the given angles θ, we apply the following standard build-up algorithm (similar algorithms have been studied using distances [22] or angles [9]). We start by fixing the first two points (p1, p2) arbitrarily. The subsequent points pn, n = 3 . . . d + 1 can be found using n − 1 angles from the previous points. Finally, all remaining points are uniquely defined using d + 1 angle measurements. Note that the minimum number of measurements required in the described algorithm is which is exactly N + d + 1 more than the lower bound DOF . We stress that, given a full angle vector θ, this build-up algorithm only uses a subset of the angles for reconstruction. Unless the angles are realizable, the reconstruction accuracy thus depends on the (arbitrary) choice of angles used for reconstruction, and there might be a discrepancy between the non-used measured and reconstructed angles. In the next section, we provide constraints on the angles in vector θ that must be satisfied for them to correspond to a valid point set. These constraints can be used to find the closest realizable angle vector. By doing this denoising before applying the build-up algorithm, every selection of angles results in the same reconstruction (up to scale and rigid transformation).

CHARACTERIZATION OF REALIZABLE ANGLES
The intuition of our realizability conditions is the following: Since an angle vector has M elements but only DOF degrees of freedom, M − DOF of the measurements are redundant. In what follows, we construct a set of L linear constraints and K non-linear constraints on the angles, such that the M − DOF residual degrees of freedom are correctly eliminated (L + K = M − DOF).

Linear constraints
We can impose two types of linear constraints on angles: the first type addresses angles measured at a single point, and the second type addresses angles in convex polygons. For all angles measured from one point, any subset of adjacent angles must sum up to form the bigger angle. In convex polygons of size m ≥ 3, the angles must sum up to (m − 2)π. Numerous such constraints exist, but not all of them are linearly independent. For example, we can consider only triangles, as they are the building blocks of higher-order polygons. We provide a method that constructs exactly the maximum number of linearly-independent constraints, defined by L = L single + L triangle , with For the single constraints at each node n, we define an order of the outgoing edges, k = 1 . . . N − 1, and the number of considered angles = 2 . . . N − 1. Then, for each starting index k = 1 . . . N −1− we impose that k+ i=k θn(i, i+1) = θn(k, k+ ), or that k+ i=k θn(i, i + 1) = 2π. The order and condition can be determined through a combinatorial algorithm or from prior knowledge. Moving to the triangle constraints, one can find all constraints linearly independent from the single constraints by choosing one single corner and imposing the constraint in all triangles involving that corner. We represent the obtained linear constraints in matrix form

Automatic creation of linear constraints
Constructing the constraints matrix A, with the previously proposed combinatorial algorithm, can be time consuming. If we know the equivalency class of our point set, we can greatly speed up the process by learning the constraints matrix from simulations. If the equivalency class is not known a priori, it can be determined through a rough initial point estimate using the noisy or partially denoised angles.
We learn the constraints matrix by randomly generating at least T ≥ L point sets in the correct equivalency class, and reading off the angles θ (t) , t = 1 . . . T . Since all points sets have the same order of edges per node, they share the same linear conditions and Aθ (t) = b, must be satisfied for each angle vector. Therefore we can write ΘC = 0, with In order to determine C , we can find a basis of the null space of the matrix Θ. A valid basis can be found by extracting the L last columns of V from the SVD given by C = U ΣV . As opposed to the combinatorally-obtained matrix A, the learned matrix is not sparse. Since each constraint acts on all angles, this matrix leads to smoother denoising when incrementally adding constraints (see Section 6.1).

Non-linear constraints
As the linear constraints are not enough to eliminate the residual degrees of freedom, we need to resort to non-linear constraints. To this end, we can impose the sine law (or equivalently, the cosine law) in each triangle. In order to remove the distance parameters, we process two adjacent triangles together, which allows to eliminate the distances and obtain sin θc(a, d) sin θc(a, b) where a to d denote the four corners of the kth quadrilateral. Repeating this for all quadrilaterals, we obtain a total of K = N 4 non-linear constraints.

Guarantees
Summing the number of linear and non-linear constraints found with the DOF of realizable angles gives the number of angles M , as desired: Figure 2 visualizes the different components of this equation. We can see that the majority of measurements can be constrained through linear constraints, so one might argue that the non-linear constraints are negligible. As we show in Section 6, these constraints are however crucial for angle realizability, and for good reconstruction accuracy.
We conclude by establishing necessary and sufficient guarantees for angle realizability. The proposed constraints are induced from well-known geometry laws, thus the following proposition holds: Proposition 1. If θ is realizable, then both linear and non-linear constraints are satisfied: Aθ = b and fi(θ) = 0 for i = 1 . . . K.
We have seen that by combining the proposed constraints, we get exactly L + K = M − DOF constraints. We thus constrain all redundant measurements, and we can put forward the following conjecture.
Conjecture 1. If both linear and non-linear constraints are satisfied, then the angle set θ is realizable.
We provide extensive simulation results that empirically verify this conjecture in Section 6.1. If the conjecture is true, it follows that the constraints provided here are sufficient and necessary, as stated in the following result.

DENOISING AND RECOVERY ALGORITHM
Possible applications of Conjecture 2 include outlier rejection (removing spurious measurements which do not satisfy the conditions), labeling (finding an order of angles such that the constraints are satisfied) and completion (filling in missing angle measurements such that they satisfy the constraints). For the purpose of this paper, we propose a denoising and point recovery algorithm.
Given a noisy angle vector θ, we want to find a point embedding with angles as close to the measurements as possible. Thanks to Conjecture 2 we can solve this in two steps: first, we find the The non-linear constraints render this problem non-convex, and no existing algorithm is guaranteed to find its optimum. As we see in Section 6, standard solvers do however show good performance and convergence properties. Knowing that the resulting angle setθ is realizable, we use the simple build-up algorithm as described in Section 3.3 for point recovery. If knowledge of some anchor points is provided, we align and scale the obtained point set to the anchor points using the orthogonal Procrustes transform [23].

SIMULATION RESULTS
In this section, we validate the theory established in Section 4 through extensive numerical simulations and evaluate the algorithm's performance. 1 We generate random point sets by uniformly picking points from a square of given side length. Simulated noise is always assumed zero-mean Gaussian. To avoid numerical issues we ignore point sets that have at least one angle smaller than 1 × 10 −3 rad in absolute value. We use the SLSQP solver provided by scipy [24] to solve (7).

Realizability study
To study the validity of Conjecture 2, we design the following experiment: Given angles corrupted by zero-mean Gaussian noise of variance σ 2 a , we denoise the angles using (7) and recover the point set using the build-up algorithm from Section 3.3. From the obtained point set, we read off the angles. Clearly, the angles used for reconstruction equal the denoised angles. The unused angles, however, only equal the denoised angles if the constraints in Conjecture 2 are sufficient. We report the results of this experiment in the top row of Figure 3. We define the discrepancy error as the MAE between the denoised and reconstructed angles, and calculate this error for 20 1 The code is available at github.com/duembgen/AngleRealizability. random realizations of each parameter set. We confirm that the discrepancy only approaches zero when all constraints are added. The learned constraints (right column) lead to a more gradual decrease than analytical constraints, because they are not sparse. Finally, we note that the difference in errors can be explained by the convergence to different local minima of (7). We conclude that the combination of the proposed constraints leads to realizable angles.

Evaluation of proposed algorithm
We also evaluate the performance of the proposed recovery algorithm in terms of point reconstruction accuracy, and report results in the second row of Figure 3. To this end, we fit the obtained point set with orthogonal Procrustes [23] to the true locations (including rescaling), and calculate the MSE. We observe that the reconstruction accuracy increases with the number of constraints. Indeed, the plot in the bottom of Figure 3, shows a clear correlation between the number of added constraints and reconstruction accuracy. Finally, we provide insight into when angle measurements are preferable over distances. For the distance-based reconstruction, we implement the standard multi-dimensional scaling algorithm [2]. We fix N = 5 and assume three different noise levels on distances, denoted by σ d , and plot the average accuracy over 20 random realizations for a range of angle noise σa. As angle-based recovery is sensitive to the scale of the setup, we show results for different area sizes. Figure 4 confirms that accuracy decreases with area size and noise, but that for a large regime of angle noise, angle-based localization is more accurate than distance-based localization.

CONCLUSION AND FUTURE WORK
We have proposed necessary and sufficient constraints for the realizability of inner-angle measurements. The constraints are related to well-known trigonometric properties and we show how to construct them both analytically and numerically, given minimal prior knowledge of the point set's topology. We exploit the conditions for a denoising and recovery algorithm and show regimes in which angle-based recovery is preferred over distance-based recovery.
The required prior knowledge of an equivalency class can be constraining in certain situations, therefore future work will focus on establishing end-to-end algorithms which exploit different levels of constraints in a hierarchical fashion to recover the equivalency class along the way. Partial knowledge of anchor locations could also be exploited to alleviate this problem. Another natural extension of the present work is the incorporation of the realizability conditions in novel methods for outlier rejection, completion, and labeling.