Message passing on codes with cycles

Section 2.7 Modern coding theory

• Except for some degenerate cases, message passing in the presence of cycles is strictly suboptimal.
• For codes with cycles, message passing no longer performs MAP decoding.

Interesting courses Winter 2015

• ECE 275A Parameter Estimation II
• TuTh 5:00p-6:20p York 4050A Kreutz-Delgado, Kenneth
• ECE 285 Sparsity and Compressed Sensing
• MW 5:00p-6:20p WLH 2110 Rao, B
• ECE 259C Advanced Topics in Coding
• TuTh 5:00p-6:20p HSS 2305B Siegel, Paul
• CSE 250B Learning Algorithms
• TuTh 3:30p-4:50p CENTR 105 Dasgupta, Sanjoy
• MATH 245B Convex Analysis
• MWF 4:00p-4:50p APM 7421 Nie, Jiawang 
• MATH 251B Lie Groups
• MWF 1:00p-1:50p APM B412 Kemp, Todd 
• MATH 282B Applied Statistics II
• TuTh 11:30a-12:50p APM 5402 Arias-Castro, Ery
• MATH 280B Probability Theory 
• MW 5:00p-6:20p APM 5402 Williams, Ruth J 

Application of matrix congruence and similarity

A homework problem in statistical parameter estimation asks us to show that for two symmetric positive definite matrices $\Sigma_1$ and $\Sigma_2$.

If $\Sigma_1 \leq \Sigma_2$, then $\Sigma_1^{-1} \ge \Sigma_2^{-1}$

Note that by assumption $B=\Sigma_2 - \Sigma_1$ is positive semi-definite.  If I can show that the resolvent identity of  $\Sigma_1^{-1} - \Sigma_2^{-1}$, $\Sigma_2^{-1} (\Sigma_2 - \Sigma_1 ) \Sigma_1^{-1}$ is positive semi-definite, then the above statement is verified.

This requires the following two results:

Sylvester's Law of Inertia

Symmetric matrices $A$ and $B$ are congruent (i.e. there is a non-singular matrix $C$ such that $C^TAC=B$) if and only if $A$ and $B$ have the same inertia.  They have the same number of positive, negative and zero eigenvalues.

Theorem 1.

The product of a symmetric positive definite matrix $A$ and a symmetric matrix $B$ has the same inertia as $B$

Proof

Note that $A^{-1/2}ABA^{1/2} = A^{1/2}BA^{1/2}$.  The right hand side is similar to $AB$, which means they have the same eigenvalues.  Since $A^{1/2}$ is symmetric, the matrix $A^{1/2}BA^{1/2}$ is congruent to $B$.  By Sylvester's Law of inertia, the eignevalues of $B$ have the same inertia as $A^{1/2}BA^{1/2}$ and also of $AB$.

The main point from Theorem 1 is that multiplying a positive definite matrix $A$ to any symmetric matrix $B$ will not change the inertia of the result.  Note that $\Sigma_2^{-1}$ and $\Sigma_1^{-1}$ are positive definite. We let $\Sigma_2^{-1}= A_1$, $\Sigma_1^{-1}=A_2$ and $\Sigma_2-\Sigma_1 =B$, and applying Theorem 1 twice, leads to $\Sigma_2^{-1} (\Sigma_2 - \Sigma_1 ) \Sigma_1^{-1}$ positive semi-definite.  We have shown $\Sigma_1^{-1} - \Sigma_2^{-1}$ is indeed positive semi-definite.

Caution!

For real positive definite matrices, not all of them are symmetric!  For example, given a symmetric positive definite matrix $B$ and a anti-symmetric matrix $C$ ($C^T=-C$), the sum of which ($A=B+C$) is positive definite.   Extra care must be taken.  All references of positive definiteness are within the context of symmetric matrices.