Optimal detection of the feature matching map in presence of noise and outliers

• URL: http://arxiv.org/abs/2106.07044v1
• Date: Sun, 13 Jun 2021 17:08:29 GMT
• Title: Optimal detection of the feature matching map in presence of noise and outliers
• Authors: Tigran Galstyan, Arshak Minasyan, Arnak Dalalyan
• Abstract summary: We consider the problem of finding the matching map between two sets of $d$ dimensional vectors from noisy observations. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of finding the matching map between two sets of $d$ dimensional vectors from noisy observations, where the second set contains outliers. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated. The main result shows that, in the high-dimensional setting, a detection region of unknown injection can be characterized by the sets of vectors for which the inlier-inlier distance is of order at least $d^{1/4}$ and the inlier-outlier distance is of order at least $d^{1/2}$. These rates are achieved using the estimated matching minimizing the sum of logarithms of distances between matched pairs of points. We also prove lower bounds establishing optimality of these rates. Finally, we report results of numerical experiments on both synthetic and real world data that illustrate our theoretical results and provide further insight into the properties of the estimators studied in this work.

Related papers

• Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search [14.821492155733555]
  We propose a graph-based ANNS algorithm for dense-sparse hybrid vectors. We show that our algorithm achieves 8.9x$sim$11.7x throughput at equal accuracy compared to existing hybrid vector search algorithms.
  arXiv  Detail & Related papers  (2024-10-27T09:12:51Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  We consider the sign-function-based comparison feedback model and analyze the convergence rates with batched and multiway comparisons. Our work is the first to study the problem of convex optimization with multiway preferences and analyze the optimal convergence rates.
  arXiv  Detail & Related papers  (2023-12-19T01:52:13Z)
• A Distribution-Based Threshold for Determining Sentence Similarity [0.0]
  We present a solution to a semantic textual similarity (STS) problem in which it is necessary to match two sentences containing, as the only distinguishing factor, highly specific information. The solution revolves around the use of a neural network, based on the siamese architecture, to create the distributions of the distances between similar and dissimilar pairs of sentences.
  arXiv  Detail & Related papers  (2023-11-28T10:42:35Z)
• Optimal Discrimination Between Two Pure States and Dolinar-Type Coherent-State Detection [8.901073744693315]
  We consider the problem of discrimination between two pure quantum states. It is well known that the optimal measurement under both the error-probability and log-loss criteria is a projection. We present a unified approach which finds the optimal measurement under any distortion measure.
  arXiv  Detail & Related papers  (2023-11-04T10:29:35Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality [3.1219977244201056]
  This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model. We show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram'er-Rao lower bound. We explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples.
  arXiv  Detail & Related papers  (2023-04-13T21:14:30Z)
• Matching Map Recovery with an Unknown Number of Outliers [0.0]
  We consider the problem of finding the matching map between two sets of $d$-dimensional noisy feature-vectors. We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than $5(dlog(4nm/alpha))1/4$, the true matching map can be recovered with probability $1-alpha$.
  arXiv  Detail & Related papers  (2022-10-24T15:59:10Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.