Incorporating Domain Knowledge in Matching Problems via Harmonic Analysis.

Area of Science:

• Machine Learning
• Computer Vision
• Optimization

Background:

• Object matching is a common task in machine learning and computer vision.
• This task often simplifies to the quadratic assignment problem (QAP), which is computationally challenging.
• Existing QAP solutions struggle with complexity and practical application.

Purpose of the Study:

• To investigate if prior knowledge of QAP instances from the same application and their solutions can mitigate the problem's difficulty.
• To develop a new approach for accelerating QAP solutions using learned parameters.

Main Methods:

• Proposed a novel method for solving QAPs by learning parameters for a modified objective function from prior instances.
• Utilized the algebraic structure of permutations and Fourier space optimization techniques.
• Optimized functions over the symmetric group in Fourier space.

Main Results:

• The proposed learning-based approach demonstrated improved performance compared to existing methods in practical domains.
• The method effectively leverages additional information about QAP instances and their solutions.
• Significant acceleration in solving QAP instances was observed.

Conclusions:

• Learning parameters from prior QAP instances can significantly accelerate solutions.
• The approach effectively combines permutation algebra and Fourier analysis for optimization.
• This method offers a practical advantage over existing techniques for specific QAP applications.