# Effective algorithm of searching the “nearest” doubly stochastic matrix

Given a data matrix $D$, is there any effective algorithm to solve the optimization problem

$\min_Q || D - Q ||_F$

such that

• $Qe=e$,
• $e^TQ=e^T$, and
• $Q_{i,j} \geq 0$ $\forall i,j$,

where $||\cdot||_F$ is the Frobenius norm of matrix.

p.s. I also posted this question on the Mathematicss exchange.

• Concurrent cross posting is not allowed. Vote to close. – Tyson Williams Jan 28 '13 at 13:28
• I think this is better suited here. Maybe Rein can flag the Math@SE question for closing? – Sasho Nikolov Jan 28 '13 at 16:19
• Sorry for cross posting, I already flagged the post in Math.SE to close. – Rein Jan 29 '13 at 2:29
• Because this is a convex quadratic program (by considering the Frobenius norm squared), it can be approximated to exponential precision in polynomial time. – Tsuyoshi Ito Feb 1 '13 at 0:43

## 1 Answer

This is a special case of the following problem: given a polytope $P$ specified by linear constraints and a point $x$ find $y \in P$ that minimizes $\|x - y\|_2^2$.

If you are ok with a small additive approximation to $\|x - y\|_2^2$, you can try using the Frank-Wolfe algorithm. This is a sort of gradient descent algorithm. You start from a point $y_0 \in P$ (in your case this could be say the $n \times n$ matrix with $1/n$ in every coordinate) and in each steps you compute $y_{i+1}$ from $y_i$ as follows:

1. Let $w = x - y_i$.
2. Let $v$ be the vertex of $P$ that maximizes $w^Tz$ for $z \in P$ (can be found by LP).
3. Find the point on the line through $y_i$ and $v$ that is closest to $x$ (this is quadratic optimization in a single variable). This point is $y_{i+1}$.

Ken Clarkson has analyzed this simple algorithm. In $t$ steps, the additive approximation is bounded by $d(P)^2/t$, where $d(P)$ is the diameter of $P$. In your case, I believe $d(P) \leq \sqrt{n}$, as the vertices of $P$ are permutation matrices and they all have Frobenius norm $\sqrt{n}$. So in $O(n/\epsilon)$ iterations of the above algorithm you can get $Q$ such that $\|D - Q\|_F^2 \leq \|D - Q^*\|_F^2 + \epsilon$, where $Q^*$ is the optimal solution.