Cheap and Secure Web Hosting Provider : See Now

A certain submatrix of the correlation polytope

, , No Comments
Problem Detail: 

I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

  • Firstly given that the author wanted to look at quadratic multilinear functions on $\{0,1\}^n$ why is he finding it enough to look at functions of the form, $f(x) = a_0 + \sum_{i,j} A_{ij}(xx^T)_{ij}$ for some real symmetric matrix $A$ and a real number $a_0$?

    These $f$s won't have any linear term and doesn't that mean a loss of generality?

  • The author defines the set $QML_n^+$ as the set of functions of the above type which are non-negative on the Boolean hypercube. Isn't this set an uncountably infinite set?

    Because I don't understand how the author now hopes to define a matrix $M_n$ whose rows seem indexes by $f \in QML_n^+$ and the columns seem indexed by $x \in \{0,1\}^n$ and the entries are $M_n(f,x) = f(x)$.

    How does this make sense as a matrix (of finite dimensions!)?

  • Given everything above how is it obvious that this matrix $M_n$ is a submatrix of some slack matrix of the correlation polytope $conv(\{ xx^T \vert x \in\{0,1\}^n \})$ ?

Asked By : gradstudent
Answered By : Yuval Filmus

Every quadratic multilinear polynomial can be written as $$ a_0 + \sum_i a_{ii} x_i + \sum_{i \neq j} a_{ij} x_i x_j = a_0 + \sum_i a_{ii} x_i^2 + \sum_{i \neq j} a_{ij} x_i x_j, $$ using the fact that $x_i^2 = x_i$ for every $x_i \in \{0,1\}$. This clearly equals $a_0 + \sum_{ij} A_{ij} x_i x_j$, which in turn is the same as what you wrote.

Regarding the matrix $M_n$, it is indeed infinite. For the proof that it is a submatrix of some slack matrix of the correlation polytope, see Lemma 2.8 of these lecture notes by James Lee.

If you have any more questions on the Bonn lecture notes, I suggest looking in the cited lecture notes, which seem to be more thorough.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54155

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback