An official website of the United States government
The Euclidean distance geometry (EDG) problem is a crucial machine learning task that appears in many applications. Utilizing the pairwise Euclidean distance information of a given point set, EDG reconstructs the configuration of the point system. When only partial distance information is available, matrix completion techniques can be incorporated to fill in the missing pairwise distances. In this paper, we propose a novel dual basis Riemannian gradient descent algorithm, coined RieEDG, for the EDG completion problem. The numerical experiments verify the effectiveness of the proposed algorithm. In particular, we show that RieEDG can precisely reconstruct various datasets consisting of 2- and 3-dimensional points by accessing a small fraction of pairwise distance information.
more »
« less
Geometric Invariants for Sparse Unknown View Tomography
In this paper, we study a 2D tomography problem for point source models with random unknown view angles. Rather than recovering the projection angles, we reconstruct the model through a set of rotation-invariant features that are estimated from the projection data. For a point source model, we show that these features reveal geometric information about the model such as the radial and pairwise distances. This establishes a connection between unknown view tomography and unassigned distance geometry problem (uDGP). We propose new methods to extract the distances and approximate the pairwise distance distribution of the underlying points. We then use the recovered distribution to estimate the locations of the points through constrained non-convex optimization. Our simulation results show that our point source reconstruction pipeline is robust to noise and outperforms the regularized expectation maximization (EM) baseline.
more »
« less
- Award ID(s):
- 1817577
- PAR ID:
- 10120564
- Date Published:
- Journal Name:
- ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
- Page Range / eLocation ID:
- 5027 to 5031
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The Euclidean distance geometry (EDG) problem is a crucial machine learning task that appears in many applications. Utilizing the pairwise Euclidean distance information of a given point set, EDG reconstructs the configuration of the point system. When only partial distance information is available, matrix completion techniques can be incorporated to fill in the missing pairwise distances. In this paper, we propose a novel dual basis Riemannian gradient descent algorithm, coined RieEDG, for the EDG completion problem. The numerical experiments verify the effectiveness of the proposed algorithm. In particular, we show that RieEDG can precisely reconstruct various datasets consisting of 2- and 3-dimensional points by accessing a small fraction of pairwise distance information.more » « less
-
We describe MPSE: a Multi-Perspective Simultaneous Embedding method for visualizing high-dimensional data, based on multiple pairwise distances between the data points. Specifically, MPSE computes positions for the points in 3D and provides different views into the data by means of 2D projections (planes) that preserve each of the given distance matrices. We consider two versions of the problem: fixed projections and variable projections. MPSE with fixed projections takes as input a set of pairwise distance matrices defined on the data points, along with the same number of projections and embeds the points in 3D so that the pairwise distances are preserved in the given projections. MPSE with variable projections takes as input a set of pairwise distance matrices and embeds the points in 3D while also computing the appropriate projections that preserve the pairwise distances. The proposed approach can be useful in multiple scenarios: from creating simultaneous embedding of multiple graphs on the same set of vertices, to reconstructing a 3D object from multiple 2D snapshots, to analyzing data from multiple points of view. We provide a functional prototype of MPSE that is based on an adaptive and stochastic generalization of multi-dimensional scaling to multiple distances and multiple variable projections. We provide an extensive quantitative evaluation with datasets of different sizes and using different number of projections, as well as several examples that illustrate the quality of the resulting solutions.more » « less
-
Nearest Neighbor Search (NNS) is a central task in knowledge representation, learning, and reasoning. There is vast literature on efficient algorithms for constructing data structures and performing exact and approximate NNS. This paper studies NNS under Uncertainty (NNSU). Specifically, consider the setting in which an NNS algorithm has access only to a stochastic distance oracle that provides a noisy, unbiased estimate of the distance between any pair of points, rather than the exact distance. This models many situations of practical importance, including NNS based on human similarity judgements, physical measurements, or fast, randomized approximations to exact distances. A naive approach to NNSU could employ any standard NNS algorithm and repeatedly query and average results from the stochastic oracle (to reduce noise) whenever it needs a pairwise distance. The problem is that a sufficient number of repeated queries is unknown in advance; e.g., a point may be distant from all but one other point (crude distance estimates suffice) or it may be close to a large number of other points (accurate estimates are necessary). This paper shows how ideas from cover trees and multi-armed bandits can be leveraged to develop an NNSU algorithm that has optimal dependence on the dataset size and the (unknown) geometry of the dataset.more » « less
-
In 1946, Erd\H{o}s posed the distinct distance problem, which seeks to findthe minimum number of distinct distances between pairs of points selected fromany configuration of $$n$$ points in the plane. The problem has since beenexplored along with many variants, including ones that extend it into higherdimensions. Less studied but no less intriguing is Erd\H{o}s' distinct angleproblem, which seeks to find point configurations in the plane that minimizethe number of distinct angles. In their recent paper "Distinct Angles inGeneral Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolfuse a logarithmic spiral to establish an upper bound of $$O(n^2)$ on the minimumnumber of distinct angles in the plane in general position, which prohibitsthree points on any line or four on any circle. We consider the question of distinct angles in three dimensions and providebounds on the minimum number of distinct angles in general position in thissetting. We focus on pinned variants of the question, and we examine explicitconstructions of point configurations in $$\mathbb{R}^3$$ which useself-similarity to minimize the number of distinct angles. Furthermore, westudy a variant of the distinct angles question regarding distinct angle chainsand provide bounds on the minimum number of distinct chains in $$\mathbb{R}^2$$and $$\mathbb{R}^3$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICASSP.2019.8682401
