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.