August 29, 2009

(Aug 27 3-5pm) Meeting Summary: Wainwright / Jordan, ch 9, 10

Filed under: Uncategorized — umassliving @ 4:40 pm
Tags: ,

This section describes how to use moment matrics and conic programming, semidefinite programming(SDP) and second-order cone programming(SOCP) to construct variational relaxations.

We spent a good amount of time going over the background information in the section.  First we discussed the definition of a moment matrix and the property that any valid moment matrix is positive semidefinite.  Next we looked at the definition of two different bases, the multinomial base and the indicator base and went trhough the lemma that shows that it is always possible to convert between the two.  Lastly, we looked at the new definition of the marginal polytope for hypergraphs in terms of the multinomial base.

Next we went over how the Lasserre sequence(moment matrices) provides a nested hierarchy of outer bounds on the marginal polytope.  For any hypergraph on m nodes, the S_t  where t=m provides and exact characterization of the margional polytope.

The last section discussed an alternate second-order cone relaxation technique, which we deffered discussing until next week’s meeting.


1 Comment »

  1. The proof in appendix E.2 is not too difficult to follow, but there are a few typos on page 288 that can initially be confusing.

    In the very first equation on the page, the second B should be B^T (\delta, \beta). This changes the last summation to be over \delta such that \beta \subseteq \delta and not the other way around, and the last exponent is |\delta \setminus \beta| rather than the other way around.

    Then in equation (E.7), the b in the exponent should be \delta, as in |\delta \setminus \beta|.

    One point which I initially glossed over, but which is important, is why it is necessary in the equation before (E.7) that i \in \gamma \setminus \beta and not simply i \not\in \beta.

    Comment by Gary — September 1, 2009 @ 3:02 pm | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at

%d bloggers like this: