Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2503.24329 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910899917291520 |
|---|---|
| author | Li, Rongxuan |
| author_facet | Li, Rongxuan |
| contents | The graph matching problem is a significant special case of the Quadratic Assignment Problem, with extensive applications in pattern recognition, computer vision, protein alignments and related fields. As the problem is NP-hard, relaxation and regularization techniques are frequently employed to improve tractability. However, most existing regularization terms are nonconvex, posing optimization challenges. In this paper, we propose a linear reweighted regularizer framework for solving the relaxed graph matching problem, preserving the convexity of the formulation. By solving a sequence of relaxed problems with the linear reweighted regularization term, one can obtain a sparse solution that, under certain conditions, theoretically aligns with the original graph matching problem's solution. Furthermore, we present a practical version of the algorithm by incorporating the projected gradient method. The proposed framework is applied to synthetic instances, demonstrating promising numerical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_24329 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Reweighted Regularization Algorithms for Graph Matching Problem Li, Rongxuan Optimization and Control The graph matching problem is a significant special case of the Quadratic Assignment Problem, with extensive applications in pattern recognition, computer vision, protein alignments and related fields. As the problem is NP-hard, relaxation and regularization techniques are frequently employed to improve tractability. However, most existing regularization terms are nonconvex, posing optimization challenges. In this paper, we propose a linear reweighted regularizer framework for solving the relaxed graph matching problem, preserving the convexity of the formulation. By solving a sequence of relaxed problems with the linear reweighted regularization term, one can obtain a sparse solution that, under certain conditions, theoretically aligns with the original graph matching problem's solution. Furthermore, we present a practical version of the algorithm by incorporating the projected gradient method. The proposed framework is applied to synthetic instances, demonstrating promising numerical results. |
| title | Linear Reweighted Regularization Algorithms for Graph Matching Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.24329 |