5
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.