Multinomial symmetric matrices

MultinomialSymmetric{T} <: AbstractMultinomialDoublyStochastic

The multinomial symmetric matrices manifold consists of all symmetric $n×n$ matrices with positive entries such that each column sums to one, i.e.

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

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

It is modeled as IsIsometricEmbeddedManifold. via the AbstractMultinomialDoublyStochastic type, since it shares a few functions also with AbstractMultinomialDoublyStochastic, most and foremost projection of a point from the embedding onto the manifold.

The tangent space can be written as

\[T_p\mathcal{SP}(n) \coloneqq \bigl\{ X ∈ ℝ^{n×n}\ \big|\ X = X^{\mathrm{T}} \text{ and } X\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 IV [DH19].



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

rand(::MultinomialSymmetric; vector_at=nothing, σ::Real=1.0, kwargs...)

Generate random points on the MultinomialSymmetric manifold or tangent vectors at the point vector_at if that is not nothing.

Let $n×n$ denote the matrix dimension of the MultinomialSymmetric.

When vector_at is nothing, this is done by generating a random matrix rand(n, n) with positive entries and projecting it onto the manifold. The kwargs... are passed to this projection.

When vector_at is not nothing, a random matrix in the ambient space is generated and projected onto the tangent space

Y = riemannian_Hessian(M::MultinomialSymmetric, p, G, H, X)
riemannian_Hessian!(M::MultinomialSymmetric, Y, p, G, H, X)

Compute the Riemannian Hessian $\operatorname{Hess} f(p)[X]$ given the Euclidean gradient $∇ f(\tilde p)$ in G and the Euclidean Hessian $∇^2 f(\tilde p)[\tilde X]$ in H, where $\tilde p, \tilde X$ are the representations of $p,X$ in the embedding,.

The Riemannian Hessian can be computed as stated in Corollary 3 [DH19].

check_vector(M::MultinomialSymmetric p, X; kwargs...)

Checks whether X is a valid tangent vector to p on the MultinomialSymmetric M. This means, that p is valid, that X is of correct dimension, symmetric, and sums to zero along any row.

project(M::MultinomialSymmetric, p, Y)

Project Y onto the tangent space at p on the MultinomialSymmetric M, return the result in X.

The formula from [DH19], Sec. VI 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 vector $α ∈ ℝ^{n×n}$ is given by solving

\[ (I_n+p)α = Y\mathbf{1},\]

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

retract(M::MultinomialSymmetric, p, X, ::ProjectionRetraction)

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



A. Douik and B. Hassibi. Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry. IEEE Transactions on Signal Processing 67, 5761–5774 (2019), arXiv:1802.02628.