TGTigran Galstyan

Tigran Galstyan

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Tigran Galstyan has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Optimality of the Least Sum of Logarithms in the Problem of Matching Map Recovery in the Presence of Noise and Outliers

    by Tigran Galstyan, Arshak Minasyan

    We consider the problem of estimating the matching map between two sets of feature-vectors observed in a noisy environment and contaminated by outliers. It was already known in the literature that in the outlier-free setting, the least sum of squares (LSS) and the least sum of logarithms (LSL) are both minimax-rate-optimal. It has been recently proved that the optimality properties of the LSS continue to hold in the case the data sets contain outliers. In this work, we show that the same is true for the LSL as well. Therefore, LSL has the same desirable properties as the LSS, and, in addition, it is minimax-rate-optimal in the outlier-free setting with heteroscedastic noise.

  • Open Access

    Matching Map Recovery with an Unknown Number of Outliers

    by Arshak Minasyan, Tigran Galstyan, Sona Hunanyan, Arnak Dalalyan

    We consider the problem of finding the matching map between two sets of $d$-dimensional noisy feature-vectors. The distinctive feature of our setting is that we do not assume that all the vectors of the first set have their corresponding vector in the second set. If $n$ and $m$ are the sizes of these two sets, we assume that the matching map that should be recovered is defined on a subset of unknown cardinality $k^*\le \min(n,m)$. We show that, in the high-dimensional setting, if the signal-to-noise ratio is larger than $5(d\log(4nm/\alpha))^{1/4}$, then the true matching map can be recovered with probability $1-\alpha$. Interestingly, this threshold does not depend on $k^*$ and is the same as the one obtained in prior work in the case of $k = \min(n,m)$. The procedure for which the aforementioned property is proved is obtained by a data-driven selection among candidate mappings $\{\hat\pi_k:k\in[\min(n,m)]\}$. Each $\hat\pi_k$ minimizes the sum of squares of distances between two sets of size $k$. The resulting optimization problem can be formulated as a minimum-cost flow problem, and thus solved efficiently. Finally, we report the 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 algorithms studied in this work.

  • Open Access

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

    by Tigran Galstyan, Arshak Minasyan, Arnak Dalalyan

    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.