existence of l1 embedding using LP feasibility - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T00:10:29Z http://mathoverflow.net/feeds/question/62779 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62779/existence-of-l1-embedding-using-lp-feasibility existence of l1 embedding using LP feasibility andy 2011-04-23T21:55:37Z 2011-04-24T03:13:25Z <p>hello</p> <p>Let (A, d) be an n-point metric space</p> <p>for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t. $\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t*d(x,y)$ where $d_1$ denotes the $l_1$ norm.</p> <p>Is it possible to check if f exists, given t using linear programing?</p> <p>andy</p> http://mathoverflow.net/questions/62779/existence-of-l1-embedding-using-lp-feasibility/62802#62802 Answer by Henry Cohn for existence of l1 embedding using LP feasibility Henry Cohn 2011-04-24T03:13:25Z 2011-04-24T03:13:25Z <p>The question is slightly ambiguous, since it doesn't specify how large the linear program can be or how much preprocessing can be devoted to producing it. However, if everything is required to run in polynomial time, then the answer is no, assuming ${\rm P} \ne {\rm NP}$. Specifically, take $t=1$, so we are trying to determine whether there is an exact embedding in $\ell_1^m$. If we don't specify the dimension $m$, then this problem is NP-hard (see the book <em>Geometry of Cuts and Metrics</em> by Deza and Laurent). However, if any $m$ works, then we can take $m = \binom{n}{2}$ (this follows from basic facts about the cut cone; again see Deza and Laurent). Since linear programs can be solved in polynomial time, the embedding problem can't be reduced to a linear program.</p> <p>What makes this a little tricky is that it can halfway be done. Suppose we focus on two points $x$ and $y$ and introduce $2m$ variables $a_1,\dots,a_m$ and $b_1,\dots,b_m$ for the coordinates of $f(x)$ and $f(y)$. It's not hard to express the upper bounds on $d_1(f(x),f(y))$ via linear constraints. For example, we can add in $m$ more variables $c_1,\dots,c_m$ and the inequalities $a_i-b_i \le c_i$ and $b_i-a_i \le c_i$ (so that $|a_i-b_i| \le c_i$). Now the upper bound amounts to $c_1+\dots+c_m \le t d(x,y)$. This looks pretty good: we can do it for each pair of points, and thus encode in our linear program the constraint that the $\ell_1$ distances can't be too large.</p> <p>However, the other direction just doesn't work. There's a fundamental difference in how well linear programs can deal with absolute values in upper or lower bounds. You can encode $|u| \le v$ by the two constraints $u \le v$ and $-u \le v$, but $u \le |v|$ can't be handled similarly. (Its solution set isn't even convex. It amounts to requiring that $u \le v$ or $u \le -v$, but not both.) That ruins all straightforward attempts to solve this problem by linear programming, and the NP-hardness shows that the difficulty is real.</p>