Tigran Galstyan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Tigran Galstyan has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Arnak S. Dalalyan
ENSAE Paristech-CREST ENSAE Paristech-CREST
2 shared publications - Arshak Minasyan
CREST, ENSAE, IP Paris
2 shared publications - Arshak Minasyan
Yerevan State University YerevaNN 9 Charents street 0025 Yerevan
1 shared publication - Sona Hunanyan1 shared publication
Latest Publications
- Open Access
- 30 March 2023
- Published by National Academy of Sciences of the Republic of Armenia in Armenian Journal of Mathematics
- Vol. 15 (5) , 1-9
Optimality of the Least Sum of Logarithms in the Problem of Matching Map Recovery in the Presence of Noise and Outliers
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.
- 30 March 2023
- Published by National Academy of Sciences of the Republic of Armenia in Armenian Journal of Mathematics
- Vol. 15 (5) , 1-9
Open AccessOptimality of the Least Sum of Logarithms in the Problem of Matching Map Recovery in the Presence of Noise and Outliers
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
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 AccessMatching Map Recovery with an Unknown Number of Outliers
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
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.Open AccessOptimal detection of the feature matching map in presence of noise and outliers
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.