# Joint Probabilistic Hypergraph Matching Labeled Multi-Bernoulli Filter for Rigid Target Tracking
## 2 Review of LMB Filer and Hypergraph Matching
### Hypergraph Matching  
Hypergraph representation is widely applied in many practical applications, such as target tracking, visual recognition. A hypergraph \(G=(V,E)\) is constructed by a set of vertices \(V\) and a set of hyperedges \(E\) which contains d-tuple of vertices. Vertices represent elementary units, hyperedge represents a relationship among a tuple of vertices. There are many hypergraph matching algorithms [33,34]. Probabilistic hypergraph matching method which derives hypergraph matching problem in a probabilistic setting [33] is used in this paper because it retains more possible association results than hard matching methods and it is reviewed below.  
Given two hypergraphs \(G=(V,E)\) and \(G^{\prime}=(V^{\prime},E^{\prime})\), each hyperedges contains d-tuple of vertices, then \(E\subseteq V^{d},E^{\prime}\subseteq V^{d}\). A hyperedge \(e_{i}\in E\) is denoted by \(e_{i}=(v_{i,1},v_{i,2},\ldots,v_{i,d})\), where \(v_{i,j}\in V\). The objective of matching between hypergraphs \(G\) and \(G^{\prime}\) is to seek an optimal vertex-to-vertex mapping \(m:V\to V^{\prime}\). In [33], the output of hypergraph matching is a vertex matching matrix \(\mathbf{X}\) with entries  
\[\mathbf{X}_{v,v^{\prime}}=P(m(v)=v^{\prime}|G,G^{\prime}), \tag{16}\]  
where \(P(m(v)=v^{\prime}|G,G^{\prime})\) means the matching probability between \(v\) and \(v^{\prime}\).  
The hard matching results can be obtained from \(\mathbf{X}\) easily. Hyperedge represents a relationship among a tuple of vertices, hyperedge matching can be induced by vertex matching \(m:E\to E^{\prime}\), because \(m(e_{i}\in E)=(m(v_{i,1}),m(v_{i,2}),\cdots,m(v_{i,d}))\in E^{\prime}\), then the relationship between vertex matching and hyperedge matching can be established, the input of hypergraph matching in [33] is a hyperedge matching matrix \(\mathbf{S}\) with entries  
\[\mathbf{S}_{e,e^{\prime}}=P(m(e)=e^{\prime}|G,G^{\prime}), \tag{17}\]  
where \(P(m(e)=e^{\prime}|G,G^{\prime})\) means the matching probability between \(e\) and \(e^{\prime}\).  
In this paper, \(\mathbf{S}_{e,e^{\prime}}=\exp(-|\partial-\partial^{\prime}|)\) is used, where \(\partial\) is the implementation of hyperedge \(e\), it is worth note that the implementation of hyperedge depends on specific applications. For example, the Euclidian distance between two vertices is an implementation of an edge with \(d=2\) when the scattering centers on a 2D rigid target are tracked.  
Because of Proposition 1 in [33], the connection between input and output is established.  
\[\mathbf{S}=\otimes^{d}\mathbf{X}, \tag{18}\]where \(\otimes^{d}X=\underbrace{X\otimes X...\otimes X}_{d}\otimes\) is the Kronecker product.  
From [33], hypergraph matching problem is transformed into a convex optimization problem, \(\mathbf{X}\) can be recovered from \(\mathbf{S}\) by minimizing the distance between \(\mathbf{S}\) and \(\otimes^{d}\mathbf{X}\):  
\[\begin{split}&\min_{\mathbf{X}}\text{dist}(\mathbf{S},\otimes^{d} \mathbf{X})\\ & s.t.\ \ \mathbf{X1}\leq 1,\mathbf{X^{T}1}\leq 1,\mathbf{X}\geq 0. \end{split} \tag{19}\]  
where \(\mathbf{1}\) is the column vector of which every elements is 1.  
The optimization problem is solved in the context of a relative entropy error measure, see more details in [33].