Given a set of $N$ $n \times n$ matrices $A_1,\ldots,A_N$, and two vectors $x,y$, the problem is to find a product of up to $K$ matrices $A = A_{j_1}A_{j_2}\cdots A_{j_k}$ so that $Ax$ is as close to $y$ as possible in terms of euclidean distance. The problem can be shown to be NP-hard e.g. by reduction from subset sum. However the problem seems so hard that I have a hard time believing there is even a polynomial time strong approximation algorithm. Also there is the issue of how to define the quality of the approximation. The problem is invariant under scaling $x$ and $y$ so probably we should assume $x$ has length $1$ and an approximation gets within distance $\epsilon ||y||$ of the optimal solution, where $y \neq 0$ and $\epsilon > 0$ can be chosen arbitrarily small.

Anyway like I said, I believe there is no polynomial time strong approximation algorithm but I'm having a hard time thinking of how a proof might go. If someone could help me resolve this question about whether a polynomial time strong approximation algorithm exists, that'd be great.

  • 1
    $\begingroup$ How do the $N$ matrices relate to the $K$ matrices? What is important about $A$ being a product of matrices? Why can't one directly optimize $A$? $\endgroup$ – jrennie Apr 27 '14 at 0:23
  • 1
    $\begingroup$ @jrennie the $K$ chosen matrices are chosen from the $N$ matrices (and they can have duplicates and be in any order) and then the $K$ chosen matrices are multiplied together and applied to $x$. We want to find the best product of $K$ matrices that transforms $x$ into as close as possible to $y$. As for why it's important I can't really say -- I found this problem on math.stackexhange where someone was asking for a fast solution, and I pointed out the problem was NP-hard so that ended that thread. But then I started thinking about approximation algorithms, which is why I posted here. $\endgroup$ – user2566092 Apr 27 '14 at 18:09

Your Answer

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

Browse other questions tagged or ask your own question.