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. 

Mathematical structure of quantum mechanics

• A quantum description consists of a Hilbert space of states
• Observables are self adjoint operators on the space of states
• Time evolution is given by a one-parameter group of unitary transformations on the Hilbert space of states
• Physical symmetries are realized by unitary transformations

Postulates of quantum mechanics

The mathematical framework can be traced back to the Dirac-von Neumann axioms

Tensor Calculus

• vector (contra-variant vector) - arrow in space
• covector (co-variant vector) - gradient 

Eigenvalues and Eigenvectors

• \(\lambda\in \lambda(A) \Leftrightarrow A-\lambda I \text{ is singular} \Leftrightarrow \text{det}(A-\lambda I)=0\)
• \(\{x\neq0|x\in \mathcal{N}(A-\lambda I)\}\) is the set of all eigenvectors associated with \(\lambda\).  
• \(\mathcal{N}(A-\lambda I)\) is the eigenspace for A.

Diagonalizability of a matrix

• A nilpotent matrix \(A=\{A\in M_n |A^2=0\}\) is not diagonalizable. 
• Two matrices \(A\) and \(B\) are similar whenever these exists a nonsingular matrix \(P\) such that \(P^{-1} AP=B\)
• A matrix can be diagonalized if it is similar to a diagonal matrix \(D\), i.e. \(P^{-1}AP=D\)
• Or equivalently, \(AP_{*,j}=\lambda_j P_{*,j}\)
• \(A\) is diagonalizable if and only if \(A\) possesses a complete set of eigenvectors.
• Or equivalently, the geometric multiplicity of \(\lambda_i\) is equal to the algebraic multiplicity of \(\lambda_i\) for each \(\lambda_i\in \lambda(A)\)

Orthogonality Principle for LS solution

Geometric condition for a Least-Squares Solutions: \(e=y-Ax\perp\mathcal{R}(A)\)

Geometric condition for a Minimum Norm LS Solution: \(x\in\mathcal{N}(A)^\perp\)

Notes on interesting mathematical objects

Banach space

• A complete linear vector space

Hilbert space

• A complete inner product space (also a Banach space)
• Well defined concept of orthogonality or angle
• Norm induced by the associated inner product

Closed set

• contains all its limit points
• complement of an open set

Complete set (M)

• every Cauchy sequence of points in M has a limit in M
• there are no points missing (inside or at the boundary)

Personalities in RMT

• Roman Vershynin, UMich
• http://www-personal.umich.edu/~romanv/
• Mark Rudelson, U of Missouri
• http://www.math.missouri.edu/~rudelson/
• Mérouane Debbah, Supelec, France
• http://www.flexible-radio.com/merouane-debbah
• Romain Couillet, Supelec, France
• http://couillet.romain.perso.sfr.fr/

On control and analysis of dynamical systems

• Even when simple feed-forward control of a linear, time invariant, first order plant was involved, the analysis of the resulting closed-loop dynamics could be involved - the equations becomes linear, time-varying equations.  
• Once feedback control is involved, the equations become nonlinear and time varying.

Interesting courses for fall 2014

• ECON 109 Game Theory
• MWF 12:00p-12:50p PCYNH 109 Newhouse, Herbert S
• MAE 281A/B Nonlinear Systems and Control (Prof. Krstic/Cortes)
• ... Not offered
• ECE 271A Statistical Learning I
• TuTh 12:30p-1:50p WLH 2205 Vasconcelos, Nuno 
• ECE 275A Parameter Estimation I
• TuTh 2:00p-3:20p PETER 104 Kreutz-Delgado, Kenneth
• ECE 251C Filter Banks and Wavelets
• TuTh 3:30p-4:50p WLH 2110 Rao, B
• ECE 293 Comm. Theory Seminar
• W 3:00p-3:50p EBU1 4309 Kim, Young-Han 
• CSE 250 Probabilistic Learning
• TuTh 12:30p-1:50p HSS 1330 Saul, Lawrence 
• MATH 245A Convex Analysis
• MWF 4:00p-4:50p APM 5829 Nie, Jiawang 
• MATH 271A/B/C Numerical Optimization (Philip E. Gill)
• ... Not offered
• MATH 280A Probability Theory 
• MW 5:00p-6:20p APM 6402 Williams, Ruth J 
• MATH 286 Stochastic Differential Equations
• MWF 4:00p-4:50p APM  B412 Schweinsberg, Jason

Notes on Clang

• Clang and LLVM disable RTTI.  As such the object files do not contain RTTI information.
• ensure the -fno-rtti flag is set

Good questions on C

• Difference between external linkage and internal linkage
• default linkage for non-const and const in C
• use of extern and static keyword
• Use of unnamed namespace in C++ vs static keyword

Building Clang (cont.)

gmake ENABLE_OPTIMIZED=1

Perform a Release (Optimized) build.

gmake ENABLE_OPTIMIZED=1 DISABLE_ASSERTIONS=1

Perform a Release (Optimized) build without assertions enabled.

gmake ENABLE_OPTIMIZED=0

Perform a Debug build.

gmake ENABLE_PROFILING=1

Perform a Profiling build.

gmake VERBOSE=1

Print what gmake is doing on standard output.

gmake TOOL_VERBOSE=1

Ask each tool invoked by the makefiles to print out what it is doing on the standard output. This also implies VERBOSE=1.

Relevant courses in Math Dept.

MATH 271 A,B,C

• Taught by Professor Philip E. Gill in 2013 (course link)
• NOTE: Not offered in 2014

MATH 245 A,B,C

• Offered and taught by Professor Nie in 2014
• Mostly concepts in convex optimization covered in ECE 273 by Prof. Lanckriet 

MATH 277 A,B

• Offered and taught by Professors {Saab, Leok} in 2014
• Not sure how applicable this is to the area of optimization 

MATH 250 A 251 B,C

• Differential geometric and theory of Lie groups (methods used in the paper by Steven Simon and Aris Moustakas to obtain capacity of MIMO correlated channels)
• Taught by Prof. Kemp (who also taught Random Matrix theory course)

How can I include a non-system C header file in my C++ code?

extern "C" {
#include "foo.h"
}

HDF5 storage

Look into this when I have a chance

Notes from David and Goliath

• You have to be "desperate enough" to re-frame your disadvantages into attributes that gives you advantages
• From AI for the game of Go, statistical (Monte Carlo methods) evaluation may have a better chance of winning when the search space is indefeasibly large.  

Notes on my Ubuntu 14.04 LTS setup

• Hostname
• sudo gvim /etc/hostname
• sudo gvim /etc/hosts
• Samba server
• sudo apt-get install samba
• sudo gvim /etc/samba/smb.conf

# Comment out password database stuff
# Add user name map
   security = user
   encrypt passwords = true
   username map = /etc/samba/smbusers

[homes]
   comment = Home Directories
   browseable = no
   read only = no

   create mask = 0644
   directory mask = 0755

• sudo smbpasswd -a user_name
• sudo restart smbd
• Apps
• RStudio (IDE for R)
• sudo apt-get install libjpeg62
• sudo dpkg -i rstudio-rel_num-amd64.deb
• Spyder (IDE for python)