# Multinomial doubly stochastic matrices

Manifolds.AbstractMultinomialDoublyStochasticType
AbstractMultinomialDoublyStochastic{N} <: AbstractEmbeddedManifold{ℝ, DefaultIsometricEmbeddingType}

A common type for manifolds that are doubly stochastic, for example by direct constraint MultinomialDoubleStochastic or by symmetry MultinomialSymmetric, as long as they are also modeled as DefaultIsometricEmbeddingType AbstractEmbeddedManifolds.

source
Manifolds.MultinomialDoubleStochasticType
MultinomialDoublyStochastic{n} <: AbstractMultinomialDoublyStochastic{N}

The set of doubly stochastic multinomial matrices consists of all $n×n$ matrices with stochastic columns and rows, i.e.

\begin{aligned} \mathcal{DP}(n) \coloneqq \bigl\{p ∈ ℝ^{n×n}\ \big|\ &p_{i,j} > 0 \text{ for all } i=1,…,n, j=1,…,m,\\ & p\mathbf{1}_n = p^{\mathrm{T}}\mathbf{1}_n = \mathbf{1}_n \bigr\}, \end{aligned}

where $\mathbf{1}_n$ is the vector of length $n$ containing ones.

The tangent space can be written as

$$$T_p\mathcal{DP}(n) \coloneqq \bigl\{ X ∈ ℝ^{n×n}\ \big|\ X = X^{\mathrm{T}} \text{ and } X\mathbf{1}_n = X^{\mathrm{T}}\mathbf{1}_n = \mathbf{0}_n \bigr\},$$$

where $\mathbf{0}_n$ is the vector of length $n$ containing zeros.

More details can be found in Section III[DouikHassibi2019].

Constructor

MultinomialDoubleStochastic(n)

Generate the manifold of matrices $\mathbb R^{n×n}$ that are doubly stochastic and symmetric.

source
ManifoldsBase.projectMethod
project(
M::AbstractMultinomialDoublyStochastic,
p;
maxiter = 100,
tolerance = eps(eltype(p))
)

project a matrix p with positive entries applying Sinkhorn's algorithm. Note that this projct method – different from the usual case, accepts keywords.

source
ManifoldsBase.projectMethod
project(M::MultinomialDoubleStochastic{n}, p, Y) where {n}

Project Y onto the tangent space at p on the MultinomialDoubleStochastic M, return the result in X. The formula reads

$$$\operatorname{proj}_p(Y) = Y - (α\mathbf{1}_n^{\mathrm{T}} + \mathbf{1}_nβ^{\mathrm{T}}) ⊙ p,$$$

where $⊙$ denotes the Hadamard or elementwise product and $\mathbb{1}_n$ is the vector of length $n$ containing ones. The two vectors $α,β ∈ ℝ^{n×n}$ are computed as a solution (typically using the left pseudo inverse) of

$$$\begin{pmatrix} I_n & p\\p^{\mathrm{T}} & I_n \end{pmatrix} \begin{pmatrix} α\\ β\end{pmatrix} = \begin{pmatrix} Y\mathbf{1}\\Y^{\mathrm{T}}\mathbf{1}\end{pmatrix},$$$

where $I_n$ is the $n×n$ unit matrix and $\mathbf{1}_n$ is the vector of length $n$ containing ones.

source
ManifoldsBase.retractMethod
retract(M::MultinomialDoubleStochastic, p, X, ::ProjectionRetraction)

compute a projection based retraction by projecting $p\odot\exp(X⨸p)$ back onto the manifold, where $⊙,⨸$ are elementwise multiplication and division, respectively. Similarly, $\exp$ refers to the elementwise exponentiation.

source
ManifoldsBase.vector_transport_toMethod
vector_transport_to(M::MultinomialDoubleStochastic, p, X, q)

transport the tangent vector X at p to q by projecting it onto the tangent space at q.

source

## Literature

• DouikHassibi2019

A. Douik, B. Hassibi: AbstractManifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry, IEEE Transactions on Signal Processing 67(22), pp. 5761–5774, 2019. doi: 10.1109/tsp.2019.2946024, arXiv: 1802.02628.