Distributed distance estimation for manifold learning and dimensionality reduction

Given a network of N nodes with the i-th sensor's observation χi ε R^M, the matrix containing all Euclidean distances among measurements ||χi - χj || ∀i, j ε {1, . . . , N} is a useful description of the data. While reconstructing a distance matrix has wide range of applications, we are particularly interested in the manifold reconstruction and its dimensionality reduction for data fusion and query. To make this map available to the all of the nodes in the network, we propose a fully decentralized consensus gossiping algorithm which is based on local neighbor communications, and does not require the existence of a central entity. The main advantage of our solution is that it is insensitive to changes in the network topology and it is fully decentralized. We describe the proposed algorithm in detail, study its complexity in terms of the number of inter-node radio transmissions and showcase its performance numerically.