Noise-Stable Rigid Graphs for Euclidean Embedding
We proposed a new criterion \textit{noise-stability}, which revised the classical rigidity theory, for evaluation of MDS algorithms which can truthfully represent the fidelity of global structure reconstruction; then we proved the noise-stability of the cMDS algorithm in generic conditions, which provides a rigorous theoretical guarantee for the precision and theoretical bounds for Euclidean embedding and its application in fields including wireless sensor network localization and satellite positioning. Furthermore, we looked into previous work about minimum-cost globally rigid spanning subgraph, and proposed an algorithm to construct a minimum-cost noise-stable spanning graph in the Euclidean space, which enabled reliable localization on sparse graphs of noisy distance constraints with linear numbers of edges and sublinear costs in total edge lengths. Additionally, this algorithm also suggests a scheme to reconstruct point clouds from pairwise distances at a minimum of $O(n)$ time complexity, down from $O(n^3)$ for cMDS.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Embedding Directed Graphs in Potential Fields Using FastMap-D
Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, E…
Transversally exponentially stable Euclidean space extension technique for discrete time systems
We propose a modification technique for discrete time systems for exponentially fast convergence to compact sets. The extension technique allows us to use tools defined on Euclidean spaces to systems evolving on manifold…
Complete Neural Networks for Complete Euclidean Graphs
Neural networks for point clouds, which respect their natural invariance to permutation and rigid motion, have enjoyed recent success in modeling geometric phenomena, from molecular dynamics to recommender systems. Yet, …
Graph Neural NetworkProperty PredictionRecommendation SystemsTight and fast generalization error bound of graph embedding in metric space
Recent studies have experimentally shown that we can achieve in non-Euclidean metric space effective and efficient graph embedding, which aims to obtain the vertices' representations reflecting the graph's structure in t…
Graph EmbeddingEmbedding Graphs on Grassmann Manifold
Learning efficient graph representation is the key to favorably addressing downstream tasks on graphs, such as node or graph property prediction. Given the non-Euclidean structural property of graphs, preserving the orig…
Graph EmbeddingGraph Property PredictionGraph Representation LearningProperty Prediction+1