3
$\begingroup$

Excuses if my formulation is non-rigorous. I am not a mathematician by training.

I have a constrained optimization problem where each of my matrix valued parameters lives inside the Birkhoff Polytope. These matrices belong to the $\textit{partial doubly stochastic matrices }$:

$$ \mathcal{PDS}_{nm} \triangleq \Big\{ \mathbf{Y} \in \mathbb{R}^{n\times m} : 0 \leq Y_{ij} \leq 1,\, \mathbf{0} \leq \mathbf{Y}_{i}\mathbf{1} \leq \mathbf{1},\, \mathbf{Y}^{\top}_{j}\mathbf{1} = \mathbf{1} ,\, 1\leq i \leq n,\, 1\leq j \leq m\Big\} $$

where $\mathbf{Y}_{i}$ denotes the $i^\text{th}$ row of $\mathbf{Y}$, $\mathbf{1}$ is a vector of ones and similarly $\mathbf{0}$ is a zero column-vector.

I additionally know that by introducing slack variables into $\mathbf{Y}$, the projection onto $\mathcal{PDS}_{nm}$ can be converted to a projection onto $\mathcal{DS}_n$, the doubly stochastic matrices (the Birkhoff Polytope). Thus, it can be solved by the well known Sinkhorn iterations. The algorithm is given in the following work:

Yao Lu, Kaizhu Huang, and Cheng-Lin Liu. A Fast Projected Fixed-Point Algorithm for Large Graph Matching, Pattern Recognition 60 (2016): 971-982. https://arxiv.org/pdf/1207.1114.pdf

The authors also provide a projected algorithm for graph matching, where at each stage of minimization, the solution is projected onto $\mathcal{PDS}_{nm}$. What I would like to have instead is a retraction map, such that I could apply Riemannian optimization algorithms without resorting to projections. I highly suspect that a true exponential map is available, so a first order scheme would suffice.

In brief, I would like to know how one would obtain Riemannian operators for such constraint set. A similar operation is done here regarding the doubly stochastic matrices. So I am tended to use a Fisher information matrix, and write the tangent space as:

$$ \mathcal{T}_\mathbf{Y}\mathcal{PDS}_{nm} \triangleq \Big\{ \mathbf{Y} \in \mathbb{R}^{n\times m} : 0 \leq Y_{ij} \leq 1,\, \mathbf{Y}_{i}\mathbf{1} = \mathbf{0},\, \mathbf{Y}^{\top}_{j}\mathbf{1} = \mathbf{0} ,\, 1\leq i \leq n\Big\} $$

However this is just the same as the tangent space of $\mathbf{DS}_n$. So any help would be appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.