Investigation and Implementation of Matrix Permanent Algorithms for Identity Resolution
Abstract
Identification of tracks/targets forms a cornerstone of Maritime Situational Awareness (MSA) in both tactical and operational settings. Resolving the identities of unknown targets often demands significant resources, and thus it is highly desirable to improve automatic vessel identification to the greatest extent that is computationally possible. Recent work at Defence Research and Development Canada (DRDC), Atlantic Research Centre has studied the statistical identification problem and found that it depends crucially on calculation of the permanent of a matrix whose dimension is a function of target count. However, the optimal approach for computing the permanent is presently unclear. The primary objective of this project was to determine the optimal computing strategy(-ies) for the matrix permanent in tactical and operational scenarios. As the exact calculation is #P-hard, approximation methods are necessary. However, many new and promising methods lack characterization, particularly in regard to their suitability for MSA applications. The present work seeks to clarify the computational options available and includes the following elements: (1.) Identification and characterization of algorithms described in the scientific literature. (2.) Implementation of those algorithms most suited for MSA.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2014
- Accession Number
- AD1004183
Entities
People
- Marie-odette St-hilaire
- Mathieu Lavallee
- Olivier Audet
Organizations
- OODA Technologies Inc.