skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Localization From Structured Distance Matrices via Low-Rank Matrix Recovery
We study the problem of determining the configuration of n points by using their distances to m nodes, referred to as anchor nodes. One sampling scheme is Nystrom sampling, which assumes known distances between the anchors and between the anchors and the n points, while the distances among the n points are unknown. For this scheme, a simple adaptation of the Nystrom method, which is often used for kernel approximation, is a viable technique to estimate the configuration of the anchors and the n points. In this manuscript, we propose a modified version of Nystrom sampling, where the distances from every node to one central node are known, but all other distances are incomplete. In this setting, the standard Nystrom approach is not applicable, necessitating an alternative technique to estimate the configuration of the anchors and the n points. We show that this problem can be framed as the recovery of a low-rank submatrix of a Gram matrix. Using synthetic and real data, we demonstrate that the proposed approach can exactly recover configurations of points given sufficient distance samples. This underscores that, in contrast to methods that rely on global sampling of distance matrices, the task of estimating the configuration of points can be done efficiently via structured sampling with well-chosen reliable anchors. Finally, our main analysis is grounded in a specific centering of the points. With this in mind, we extend previous work in Euclidean distance geometry by providing a general dual basis approach for points centered anywhere.  more » « less
Award ID(s):
2208392
PAR ID:
10638645
Author(s) / Creator(s):
 ;  
Publisher / Repository:
Institute of Electrical and Electronics Engineers (IEEE)
Date Published:
Journal Name:
IEEE Transactions on Information Theory
Volume:
70
Issue:
12
ISSN:
0018-9448
Page Range / eLocation ID:
8929 to 8941
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, 59th Annual Conference on Information Sciences and Systems)
    This paper addresses the problem of estimating the positions of points from distance measurements corrupted by sparse outliers. Specifically, we consider a setting with two types of nodes: anchor nodes, for which exact distances to each other are known, and target nodes, for which complete but corrupted distance measurements to the anchors are available. To tackle this problem, we propose a novel algorithm powered by Nystro m method and robust principal component analysis. Our method is computationally efficient as it processes only a localized subset of the distance matrix and does not require distance measurements between target nodes. Empirical evaluations on synthetic datasets, designed to mimic sensor localization, and on molecular experiments, demonstrate that our algorithm achieves accurate recovery with a modest number of anchors, even in the presence of high levels of sparse outliers. 
    more » « less
  2. ; (, Proceedings of the 16th International Conference on Precision Agriculture)
    Wireless sensor networks play a pivotal role in a myriad of applications, including agriculture, health monitoring, tracking and structural health monitoring. One crucial aspect of these applications involves accurately determining the positions of the sensors. In this paper, we study a novel Nystrom based sampling protocol in which a selected group of anchor nodes, with known locations, establish communication with only a subset of the remaining sensor nodes. Leveraging partial distance information, we present an efficient algorithm for estimating sensor locations. To demonstrate the effectiveness of our approach, we provide empirical results using synthetic data and underscore the practical advantages of our sampling technique for precision agriculture. 
    more » « less
  3. ; ; ; (, ACM Web Science Conference)
    null (Ed.)
    In many network applications, it may be desirable to conceal certain target nodes from detection by a data collector, who is using a crawling algorithm to explore a network. For example, in a computer network, the network administrator may wish to protect those computers (target nodes) with sensitive information from discovery by a hacker who has exploited vulnerable machines and entered the network. These networks are often protected by hiding the machines (nodes) from external access, and allow only fixed entry points into the system (protection against external attacks). However, in this protection scheme, once one of the entry points is breached, the safety of all internal machines is jeopardized (i.e., the external attack turns into an internal attack). In this paper, we view this problem from the perspective of the data protector. We propose the Node Protection Problem: given a network with known entry points, which edges should be removed/added so as to protect as many target nodes from the data collector as possible? A trivial way to solve this problem would be to simply disconnect either the entry points or the target nodes – but that would make the network non-functional. Accordingly, we impose certain constraints: for each node, only (1 − r) fraction of its edges can be removed, and the resulting network must not be disconnected. We propose two novel scoring mechanisms - the Frequent Path Score and the Shortest Path Score. Using these scores, we propose NetProtect, an algorithm that selects edges to be removed or added so as to best impede the progress of the data collector. We show experimentally that NetProtect outperforms baseline node protection algorithms across several real-world networks. In some datasets, With 1% of the edges removed by NetProtect, we found that the data collector requires up to 6 (4) times the budget compared to the next best baseline in order to discover 5 (50) nodes. 
    more » « less
  4. ; ; (, ACM Transactions on Algorithms)
    Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks, and so forth. Differentcentralitymeasures have been proposed to capture the notion of node importance. For example, thecenterof a graph is a node that minimizes the maximum distance to any other node (the latter distance is theradiusof the graph). Themedianof a graph is a node that minimizes the sum of the distances to all other nodes. Informally, thebetweenness centralityof a nodewmeasures the fraction of shortest paths that havewas an intermediate node. Finally, thereach centralityof a nodewis the smallest distancersuch that anys-tshortest path passing throughwhas eithersortin the ball of radiusraroundw. The fastest known algorithms to compute the center and the median of a graph and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the numbernof nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time Õ(n3-δ) for some constant δ > 0.1 We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median, and Betweenness Centrality areequivalent under subcubic reductionsto APSP, i.e., that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any finite factor. Thus, the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP required essentially cubic time. On the positive side, our reductions for Reach Centrality imply an improved Õ(Mnω)-time algorithm for this problem in case of non-negative integer weights upper bounded byM, where ω is a fast matrix multiplication exponent. 
    more » « less
  5. ; ; ; ; (, 2018 IEEE International Conference on Industrial Internet (ICII))
    null (Ed.)
    Securely growing or de-growing nodes is a mandatory requirement to manage Wireless Body Area Networks (WBANs). This requirement raises significant challenges in node authentication, backward node authentication, initial node configuration, and node de-growth. Unlike the traditional approaches using pre-stored secrets or relying on special authentication hardware, we explore the characteristics of WBAN and wireless signal to develop an efficient scheme for adding/removing WBAN node securely and effectively. The major idea of the proposed scheme is to construct a 'virtual' dual-antennae proximity detection system by fully utilizing the existing legitimate nodes and the behavior of human body. We built a system prototype on wireless devices and verified our scheme through experiments. In addition, a data mining (clustering) algorithm is also applied to successfully detect newly joined legitimate node and identify potential attackers. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email