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)

Building clang

In case I happen to try this again.  Linking clang is a memory intense task.  I gave my VM 6GB of memory and it is still disk swapping like mad...

R cheatsheet

Preliminaries

• install.packages("package_name",dependencies = TRUE) # install package
• library(package_name) # load package
• search() # list all packages attached
• ls() # list all objects in environment/package
• help(name) # help on package/function
• getwd() # get working directory
• list.files() # list files in working directory
• save.image() # save workspace to .Rdata
• savehistory() # save history to .Rhistory

Data types

• class(obj) # class of object
• dim() # dimension of matrix
• length() # length of array
• factor() # encode categorical variables using numeric storage (e.g. "red","orange","green")
  

Wish List for matlab parser

Parser features

• Add parsing of 1-D and 2-D arrays

Param registration

• Register params
• Attach to ParseTree
• Look up value based on hierarchical position of params

Vector dumping

• Hierarchical file names
• Header to include attributes and formats

Matlab parser notes

Matlab Grammar

 statements = statements (statements)*
 statement = declare | assign | expr
 clear = 'clear' id';'
 declare = 'global' id ';'
 assign = var '=' ( list | string | expr ) ';'
 var = id('.'id)* | id '(' expr (',' expr)* ')'
 literal = integer | float
 list = '[' expr (',' expr)* ']'
 expr = add_expr
 add_expr = mul_expr (('+'|'-') mul_expr )*
 mul_expr = primary (('*'|'/') primary )*
 primary = '(' expr ')' | var | list | literal | '-' primary

Token definition

 string = '[char]*'
 integer = [0:9]
 float = ...

Operator Precedence

You can build expressions that use any combination of arithmetic, relational, and logical operators. Precedence levels determine the order in which MATLAB® evaluates an expression. Within each precedence level, operators have equal precedence and are evaluated from left to right. The precedence rules for MATLAB operators are shown in this list, ordered from highest precedence level to lowest precedence level:

1. Parentheses ()
2. Transpose (.'), power (.^), complex conjugate transpose ('), matrix power (^)
3. Unary plus (+), unary minus (-), logical negation (~)
4. Multiplication (.*), right division (./), left division (.\), matrix multiplication (*), matrix right division (/), matrix left division (\)
5. Addition (+), subtraction (-)
6. Colon operator (:)
7. Less than (<), less than or equal to (<=), greater than (>), greater than or equal to (>=), equal to (==), not equal to (~=)
8. Element-wise AND (&)
9. Element-wise OR (|)
10. Short-circuit AND (&&)
11. Short-circuit OR (||)

Associativity of operators

• power (.^) is left associative in Matlab

Compressed sensing notes

• Classical sampling theory (Nyquist-Shannon framework) 
• Infinite length, continuous-time signals 
• Requires the sample at specific point in time 
• Signal recovery in the form of linear sinc interpolation 
• Compressed sensing framework 
• Finite-dimensional vectors in $\mathbb{R}^n$ 
• Acquires measurements in the form of an inner-products between the signal and a test function 
• Signal recovery achieved using highly nonlinear methods

Trying out Math on Blogger

The following under determined equation $Ax=b$ is an example.
Trying $x_1 = 3$
$$\begin{equation} \int_a^b \! f(x) \, \mathrm{d}x \label{eq.gaussian} \end{equation}$$ which we can later refer back to as $\eqref{eq.gaussian}$.
In equation $\eqref{eq:sample}$, we find the value of an interesting integral:
$$\begin{equation} \int_0^\infty \frac{x^3}{e^x-1}\,dx = \frac{\pi^4}{15} \label{eq:sample} \end{equation}$$ Very cool indeed.