<p>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$. </p>

<p>If you are ok with a small <em>additive</em> 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:</p>

<ol>
<li>Let $w = x - y_i$.</li>
<li>Let $v$ be the vertex of $P$ that maximizes $w^Tz$ for $z \in P$ (can be found by LP).</li>
<li>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}$.</li>
</ol>

<p>Ken Clarkson has <a href="http://dl.acm.org/citation.cfm?doid=1824777.1824783" rel="nofollow">analyzed</a> 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.</p>

CC BY-SA 3.0
2013-01-28T16:43:38.237Z
2013-01-28T19:13:15.330Z
2013-01-28T19:13:15.330Z
Sasho Nikolov
<p>Given a data matrix $D$, is there any effective algorithm to solve the optimization problem</p>

<p>$\min_Q || D - Q ||_F$</p>

<p>such that</p>

<ul>
<li>$Qe=e$,</li>
<li>$e^TQ=e^T$, and</li>
<li>$Q_{i,j} \geq 0 $  $\forall i,j$,</li>
</ul>

<p>where $||\cdot||_F$ is the Frobenius norm of matrix.</p>

<p>p.s. I also <a href="https://math.stackexchange.com/questions/288860/effective-algorithm-of-searching-the-nearest-doubly-stochastic-matrix">posted</a> this question on the Mathematicss exchange.</p>

CC BY-SA 3.0
2013-01-28T13:28:35.183Z
Concurrent cross posting is not allowed. Vote to close.
Tyson Williams
CC BY-SA 3.0
2013-01-28T16:19:56.630Z
I think this is better suited here. Maybe Rein can flag the Math@SE question for closing?
Sasho Nikolov
CC BY-SA 3.0
2013-01-29T02:29:42.460Z
Sorry for cross posting, I already flagged the post in Math.SE to close.
Rein
CC BY-SA 3.0
2013-02-01T00:43:00.677Z
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
<optimization><matrices>
Effective algorithm of searching the "nearest" doubly stochastic matrix
Rein
# Effective algorithm of searching the "nearest" doubly stochastic matrix

(Asked by: username_0 on 2013-01-28)

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](https://math.stackexchange.com/questions/288860/effective-algorithm-of-searching-the-nearest-doubly-stochastic-matrix) this question on the Mathematicss exchange.

**Tags:** optimization, matrices

> **Comments:**
> **username_1**: Concurrent cross posting is not allowed. Vote to close.  
> **username_2**: I think this is better suited here. Maybe username_0 can flag the Math@SE question for closing?  
> **username_0**: Sorry for cross posting, I already flagged the post in Math.SE to close.  
> **username_3**: Because this is a convex quadratic program (by considering the Frobenius norm squared), it can be approximated to exponential precision in polynomial time.  

---

## 1 answers

### Answer by username_2 on 2013-01-28. Score: 6 | Accepted 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](http://dl.acm.org/citation.cfm?doid=1824777.1824783) 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.


---

