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.


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.