# Riemannian Manifold for the Partial Doubly Stochastic Matrices

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.