Notes on duality

Given a standard form problem (not necessarily convex)
\begin{align*}
\text{minimize} \quad  &f_0(x) \\
\text{subject to} \quad &f_i(x)\leq 0, &i=1,\cdots,m \\
                            &h_i(x) = 0,    &i=1,\cdots,p
\end{align*}
variable \(x\in \mathbb{R}^n\), domain \(\mathcal{D}\), optimal value \(p^*\)
with Lagrangian:
\[ L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \]
and the (Lagrange) dual function:
\[ g(\lambda,\nu) = \inf_{x\in \mathcal{D}} L(x,\lambda,\nu)\]
Properties:

• \(g\) is concave over \(\lambda, \nu\) since it is the infimum of a family of affine functions.
• Lower bound property: if \(\lambda \succeq 0\) then \(g(\lambda,\nu) \leq p^*\)

since, if \(\tilde{x}\) is feasible and \(\lambda \succeq 0\), then
\[ g(\lambda,\nu) = \inf_{x\in \mathcal{D}} L(x,\lambda,\nu) \leq L(\tilde{x}, \lambda, \nu) \leq f_0(\tilde{x})\] minimizing over all feasible \(\tilde{x}\) gives \( g(\lambda,\nu) \leq p^*\)

Lagrange dual and conjugate function

Given an optimization problem with linear inequality and equality constraints
\begin{align*}
     \text{minimize}\quad &f_0(x) \\
     \text{subject to}\quad &Ax\preceq b \\
                                 &Cx=d.
\end{align*}
Using the definition of \(f^* = \sup_{x\in \text{dom }f} (y^T x - f(x))\), we can write the dual function as:
\begin{align*}
    g(\lambda,\nu)\quad &= \quad \underset{x}{\inf} (f_0(x) + \lambda^T (Ax-b) + \nu^T(Cx=d)) \\
                             &= \quad -b^T \lambda - d^T \nu + \underset{x}{\inf} (f_0(x) + (A^T \lambda + C^T \nu)^T x)\\
                             &= \quad -b^T \lambda - d^T \nu - f^* (-A^T \lambda - C^T \nu)
\end{align*} with domain
\[ \text{dom }g = \{ (\lambda,\nu) \;|\; -A^T \lambda - C^T \nu \in \text{dom } f_0^* \} \]

• simplifies derivation of dual if conjugate of \(f_0\) is known

The dual problem (finding the greatest lower bound for the primal problem)
\begin{align*}
    \text{maximize}\quad &g(\lambda,\nu) \\
    \text{subject to}\quad  &\lambda \succeq 0
\end{align*}

• a convex optimization problem; optimal value denoted \(d^*\)
• \(\lambda,\nu\) are dual feasible if \(\lambda \succeq 0, (\lambda,\nu)\in \text{dom }g\)

Weak duality: \(d^* \leq p^*\)

• always holds (for convex and nonconvex problems)
• can be used to find lower bounds for difficult problems

Strong duality: \(d^* = p^*\) (zero duality gap)

• does not hold in general
• (usually) holds for convex problems
• constraint qualifications assert conditions that guarantee strong duality in convex problems (e.g. Slater's constraint qualification)

Notes on dual norm

Dual norm is defined as
\[ \|z\|_* = \sup \{z^Tx \;|\; \|x\| \leq 1\}\] The dual norm can be interpreted as the operator norm of \(z^T\), interpreted as a \(1\times n\) matrix with the norm \(\|\cdot\|\) on \(\mathbf{R}^n\).

From the definition of dual norm we obtain the inequality
\[ z^Tx \leq \|x\| \|z\|_*\]
The conjugate of any norm \(f(x)=\|x\|\) is the indicator function of the dual norm unit ball
\[f^*(y) = \left\{ \begin{array}
                             00      & \|y\|_* \leq 1 \\
                             \infty     & \text{otherwise}
                         \end{array}
 \right. \]
Proof. If \(\|y\|_* \gt 1\), then by definition of the dual norm, there is a \(z\in \mathbf{R}^n\) with \(\|z\| \leq 1\) and \(y^T z \gt 1\).  Taking \(x=tz\) and letting \(t \rightarrow \infty\), we have
\[ y^T x - \|x\| = t(y^Tz - \|z\|) \rightarrow \infty\] which shows that \(f^*(y) = \infty\).  Conversely, if \(\|y\|_*\leq 1\), then we have \(y^Tx \leq \|x\| \|y\|^*\) for all \(x\), which implies for all \(x\), \(y^Tx - \|x\| \leq 0\).  Therefore \(x=0\) is the value that maximizes \(y^Tx - \|x\|\), with maximum value 0.

Schur complement: characterizations of positive definiteness for block matrices

Let a block matrix \(X\in \mathbf{S}^n\) be partitioned as

\[ X = \begin{bmatrix}
                 A      &B \\
                 B^T  &C
           \end{bmatrix} \] where \(A\in \mathbf{S}^k\).  If \(\det A \neq 0\), the schur complement is
\[ S =C - B^TA^{-1}B \] The following characterizations of positive definiteness can be derived

• \(X\succ 0\) iff \(A\succ 0\) and \(S\succ 0\)
• If \(A\succ 0\), then \(X\succeq 0\) iff \(S\succeq 0\)

Example:
\begin{align*}
&A^TA \preceq t^2I, \quad &t\ge 0 \\
\Longleftrightarrow \quad &tI-t^{-1}A^T I A \succeq 0, \quad &t\ge 0 \\
\Longleftrightarrow \quad &
  \begin{bmatrix}
     tI & A \\
     A^T & tI
  \end{bmatrix} \succeq 0
\end{align*}

Notes on optimization problem

Optimality criterion for differentiable \(f_0\)
Given a convex optimization problem with objective \(f_0\).  \(x\) is optimal iff it is feasible and
\[ \nabla f_0(x)^T (y-x) \ge 0 \quad \text{for all feasible } y \]

if \(\nabla f_0(x) \neq 0 \), it means that \( -\nabla f_0(x) \) defines a supporting hyperplane to the feasible set at \(x\).

Unconstrained problem: \(x\) is optimal iff
\[ x\in \text{dom }f_0, \quad \nabla f_0(x) = 0 \]
Equality constrained problem:
\[ \text{minimize } f_0(x) \quad \text{ subject to } Ax=b  \]
\(x\) is optimal iff there exists a \(\nu\) such that
\[ x\in \text{dom }f_0, \quad Ax=b, \quad \nabla f_0(x)+A^T\nu = 0\]
Note: Lagrange multiplier optimality condition.

Minimization over nonnegative orthant
\[ \text{minimize } f_0(x) \quad \text{ subject to } x\succeq 0  \]
\(x\) is optimal iff
\[ x\in\text{dom }f_0, \quad x\succeq 0, \quad  \left\{ \begin{array}{lr}
                                                                                                \nabla f_0(x)_i \ge 0, \quad &x_i = 0  \\
                                                                                                \nabla f_0(x)_i = 0, \quad &x_i \ge 0
                                                                                      \end{array} \right.   \]
Note: The last condition is a complementarity condition.

Notes on conjugate function (Fenchel conjugate)

The conjugate function (Fenchel conjugate)

• Counterpart to Fourier transform in Convex Analysis

The conjugate of \(f\) (\(f\) not necessarily convex):

\[ f^*(y) = \underset{x\in \text{dom }f}{\sup} (y^Tx - f(x)) \]

The domain of \(f^*\) consists of \(y\in \mathbb{R}^n\) for which the supermum is finite, i.e. for which the difference \(y^T x - f(x)\) is bounded above on \(\text{dom }f\).

\(f^*\) is convex, since it is the pointwise supremum of a family of affine functions of \(y\).

Examples:

• Affine function. \(f(x)=ax+b\).  \(f^*(y) = yx-ax-b = (y-a)x-b\).  

\[ f^*(y)  =  \left\{ \begin{array}
                                     -b    &y=a\\
                                   \infty &\text{otherwise}
                              \end{array}  \right. \] with \(\text{dom }f^* = \{a\}\).

• Negative logarithm. \(f(x) = -\log x\), with \(\text{dom }f=\mathbb{R}_{++}\).  

The function \(xy + \log x\) is unbound above if \(y\ge 0\) and reaches its max at \(x=-1/y\) otherwise.
\[ f^*(y) =  \left\{ \begin{array}
                                   -1-\log (-y)    &y\lt 0\\
                                   \infty           &\text{otherwise}
                              \end{array}  \right. \] with \(\text{dom }f^* = \{y\; |\; y\lt 0 \}\)

Fenchel's inequality

Fenchel's inequality can be obtained from the definition of conjugate function

\[  f(x) + f^*(y) \ge x^T y , \quad \forall x,y\]
since for each \(y\),
\[  f^*(y) \ge x^Ty - f(x) \Leftrightarrow  f(x) + f^*(y) \ge x^Ty \]

Notes on convex functions

Basic Properties

[TODO]

Examples

• Affine functions are both convex and concave
• All norms are convex (e.g. Frobenius norm, Spectral norm)
• Max function \(f(x) = \max_i x_i\) is convex on \(\mathbb{R}^n\)
• Quadratic-over-linear function \(f(x,y)=x^2/y\) is convex on \(\text{dom }f=\mathbb{R}\times\mathbb{R}_{++}\)
• Log-sum-exp \(f(x)=\log \sum^n_{i=1}e^{x_i}\) is convex on \(\mathbb{R}^n\)
• Geometric mean \(f(x)=(\prod^n_{i=1}x_i)^{1/n}\) is concave on \(\text{dom }f=\mathbb{R}^n_{++}\)
• Log-det is concave on \(\text{dom }f=\mathbf{S}^n_{++}\)

Restriction of a convex function to a line

\(f:\mathbb{R}^n \rightarrow \mathbb{R}\) is convex iff the function \(g:\mathbb{R} \rightarrow \mathbb{R}\), 

\[ g(t) = f(x+tv), \quad \text{dom } g = \{ t\; |\; x + tv \in \text{dom } f \} \]

is convex in \(t\) for any \(x \in  \text{dom } f\), \(v \in \mathbf{R}^n\)

Upshot: can check convexity of \(f\) by checking convexity of functions of one variable.

Epigraph and sublevel set 

\(\alpha\)-sublevel set of \(f:\mathbb{R}^n \rightarrow \mathbb{R}\), is defined as all x for which the value of \(f(x)\) is less then \(\alpha\)

\[ C_\alpha = \{ x \in \text{dom } f \; | \; f(x) \leq \alpha \} \]

Property: sublevel sets of convex functions are convex (converse is false)

epigraph of \(f:\mathbb{R}^n \rightarrow \mathbb{R}\):

\[ \text{epi } f = \{ (x,t) \in \mathbb{R}^{n+1} \; | \; x \in \text{dom } f, f(x) \leq t \} \]

Property: \(f\) is convex iff  \(\text{epi }f\) is a convex set

Operations that perserve convexity

methods for establishing convexity of a function

1. verify definition (often simplified by restricting to a line)
2. for twice differentiable functions, show \(\nabla^2 f(x) \succeq 0\)
3. show that \(f\) is obtained from simple convex functions by operations that preserve convexity
• nonnegative weighted sum
• composition with affine function
• pointwise maximum and supremum
• composition
• minimization
• perspective

Notes on convex sets

Cones

Definition of a cone is quite general:

A set \(C\) is a cone if for every \(x\in C\) and \(\theta\ge 0\), we have \(\theta x \in C\).  (Note that, a subspace is a cone since all (non-negative) combination of points in the subspace belongs to the subspace)

A set \(C\) is a convex cone if it is convex and a cone.

A proper cone on the other hand is more strict.

A cone \(K \subseteq \mathbb{R}^n\) is a proper cone if it satisfies the following

• \(K\) is convex
• \(K\) is closed
• \(K\) is solid, which means it has nonempty interior.
• \(K\) is pointed, which means that it contains no line.

Dual cones and generalized inequalities

Dual cones of a cone \(K\):
\[ K^* = \{y\; |\; y^T x\ge 0 \text{ for all } x \in K \} \]

Dual cones of proper cones are proper, so a dual cone defines generalize inequalities in the dual domain

\[ y \succeq_{K^*} 0 \quad \Longleftrightarrow \quad y^T x\ge 0 \text{ for all } x\succeq_K 0  \]

Characterization of minimum and minimal elements via dual inequalities

minimum element w.r.t. \( \preceq_K\)

Definition: \(x\) is minimum element of \(S\) iff for all \(\lambda \succeq_{K^*} 0\), \(x\) is the unique minimizer of \(\lambda^T z\) over \(S\)

minimal element w.r.t. \( \preceq_K \)

Definitions:

• if \(x\) minimizes \(\lambda^T z\) over \(S\) for some \(\lambda \succ_{K^*} 0\), then \(x\) is minimal
• if \(x\) is a minimal element of a convex set \(S\), then there exists a nonzero \(\lambda \succeq_{K^*} 0\) such that \(x\) minimizes \(\lambda^T z\) over \(S\)

Useful Matrix properties

Theorem

Let \(A\) be \(m\times n\) matrix, \(B\) and \(C\) \(n\times n\) matrices, with \(B\) symmetric, \(x\) \(n\times 1\) vector

1. \(Ax=0 \; \forall x\) if and only if \(A=0\),
2. \(x^TAx \; \forall x\) if and only if \(B=0\),
3. \(x^TCx \; \forall x\) if and only if \(C^T=-C\) (skew symmetric).

Concentration of measure

To characterize the deviation of a random quantity (typically a general function of weakly correlated variables) from it's mean.  

One can look at

• the tail end probability (moment method and chernoff's bound)
• the stability about it's mean (i.e. )
• the bounded difference ()

Circularly symmetric complex Gaussian

Special case: scalar variable \(Z\sim\mathcal{CN}(0,1)\)
\begin{aligned}
f_Z(z) &= \frac{1}{\pi}e^{-|z|^2} \\
f_{|Z|,\Theta}(|z|,\theta) &= \frac{1}{\pi} |z| e^{-|z|^2}
\end{aligned}
Note that the distribution is a function of the magnitude of \(Z\), and therefore constant over all angles \(\theta\).  To get the distribution of the magnitude of Z, we integrate over all angles \( -\pi \le \theta \le \pi\).
\begin{aligned}
f_{|Z|}(|z|) &= \int f_{|Z|,\Theta}(|z|,\theta) d\theta \\
                  &= \int_{-\pi}^\pi d\theta \; \frac{1}{\pi} |z| e^{-|z|^2} \\
                  &= 2 |z| e^{-|z|^2} ,\; |z| > 0
\end{aligned}
Define \(Y=|Z|\) then,
\[ f_Y(y) = 2 y e^{-y^2}, \quad y > 0\]
For magnitude squared distribution, we can perform a change of variable, with \(X=Y^2=g(Y)\), since \( P( \{-\sqrt{x}, x > 0\} ) = 0 \), we only have one region (the set \(\{ \sqrt{x}, x>0 \}\) ) to worry about.
\begin{aligned}
f_X(x) &= f_Y(g^{-1}(x)) \left|\frac{ \partial g^{-1}(x) }{ \partial x} \right| \\
            &= f_Y(\sqrt{x})  \left|\frac{ \partial \sqrt{x} }{ \partial x} \right|  \\
            &= (2x^{\frac{1}{2}}e^{-x}) \frac{1}{2} x^{-\frac{1}{2}} \\
            &= e^{-x}, \; x>0
\end{aligned}
Note:
Here we assume the probability spaces \((X,\mathcal{X},P_X)\), \((Y,\mathcal{Y},P_Y)\)and that a mapping T exists that maps \(A\in\mathcal{X}\) to \(B\in\mathcal{Y}\).
Start from the joint cdf in the X-space, define \(A\equiv\{\sqrt{X^2+Y^2}\leq |z|, \tan^{-1}(Y/X) \leq \theta_0\}\)
\[F_{|Z|,\Theta}(|z|,\theta_0) = P(A)  = \underset{(x,y)\in A}{\iint} f(x,y) dx \; dy \]
With a change of variable, define \(B\equiv\{|Z|\leq |z|, \Theta \leq \theta_0\}\)
\begin{aligned}
F_{|Z|,\Theta}(|z|,\theta_0) = P(B) &=  \underset{(r,\theta)\in B}{\iint} f(x(r,\theta), y(r,\theta)) r \; dr \; d\theta \\
&= \int_0^{|z|} \int_0^{\theta_0} f(x(r,\theta), y(r,\theta)) r \; dr \; d\theta
\end{aligned}
Differentiate wrt \(|z|\) and \(\theta\) to get the pdf.

Theorem.  Given any function \(g:\mathbb{R}^2 \rightarrow \mathbb{R}\) and T that maps the \(A\in\mathcal{X}\) to \(B\in\mathcal{Y}\) then
\[\iint_A g(x_1,x_2) dx_1 \; dx_2 = \iint_B g(x_1(y_1,y_2), x_2(y_1,y_2))  |J(y_1, y_2)| dy_1\; dy_2\] where \(J(y_1,y_2)\) is the Jacobian.

The inverse power of praise

New York Magazine article

Delay gratification

Newyorker article

The cult of Genius

Discover magazine blog

"... the brain is a muscle. Giving it a harder workout makes you smarter"

searching for files in Windows command prompt

• If you know the name of the file
• dir secret.* /s /p

Relationship between vec operator, Schur, Kronecker and Khatri-Rao product

\(\DeclareMathOperator{\diag}{diag}\)\(\DeclareMathOperator{\vec}{vec}\) Define \(\vec(A)\) as the operation of stacking the columns of matrix \(A\) into a vector, \(A\otimes B\) the Kronecker product, \(A\circ B\) the Schur (Hadamard) product and finally \(A\diamond B\) Bhatri-Rao product is defined as the column wise Kronecker product.

Here are some useful properties:

\[(A\otimes B)^T = A^T \otimes B^T\]

\[A \diag(x \circ y) B^T = A \diag(x) \diag(y) B^T\]

\[(C\otimes D) ( A \diamond B) = CA \diamond DB \]

\[\vec(AXB^T) = (B \otimes A) \vec(X)\]

\[\vec(A \diag(x) B^T) = (A \diamond B) x\]

\[(A\diamond B \diamond x^T) y = (A \diamond B) (x \circ y)\]

Where \(A,B,C,D,X\) are matrices and \(x,y\) are vectors of compatible dimensions.

Linear separability

(Cover, 1965)  Suppose we have \(N\) data points distributed at random in \(\mathbb{R}^d\) with an unspecified distribution.  Assume that there is no subset of \(d\) or fewer points which are linearly dependent.  We then assign each of the points to one of the two classes \(\mathcal{C}_1\) and \(\mathcal{C}_2\) with equal probability.

The fraction \(F(N,d)\) of realizations that is linearly separable is given by the expression
\[ F(N,d) = \left\{
    \begin{matrix}
    1 \quad &\mathrm{when}\; N \le d+1 \\
    \frac{1}{2^{N-1}}\sum\limits_{i=0}^d \left( \begin{matrix} N-1 \\ i \end{matrix} \right) \quad & \mathrm{when}\; N \ge d + 1
    \end{matrix}\right.
  \] Intuitively, the probability of separability increase with increasing dimension \(d\).

[TODO] include plot...

http://www-isl.stanford.edu/~cover/papers/paper76.pdf

Simply connectedness

Informally, a thick object in our space is simply-connected if it consists of one piece and does not have any "holes" that pass all the way through it.

A sphere (or, equivalently, a rubber ball with a hollow center) is simply connected, because any loop on the surface of a sphere can contract to a point, even though it has a "hole" in the hollow center.

The stronger condition, that the object has no holes of any dimension, is called contractibility.

Another characterization of simply-connectedness is the following:

\(X\) is simply-connected if and only if 

• it is path-connected, and 
• whenever \(p: [0,1] \rightarrow X\) and \(q: [0,1] \rightarrow X\) are two paths (i.e. continuous maps) with the same start and endpoint (\(p(0)=q(0)\) and \(p(1) == q(1)\)), then \(p\) and \(q\) are homotopic relative to {0,1}.

Intuitively, this means that \(p\) can be "continuously deformed" to get \(q\) while keeping the endpoints fixed. Hence the term simply connected: for any two given points in \(X\), there is one and "essentially" only one path connecting them.

Examples:

• All convex sets in \(\mathbb{R}^n\) are simply connected.
• A sphere is simply connected.

Interesting courses Spring 2015

• ECE 287 Spec Topics/Comm Theory & Syst
• TuTh 5:00p-6:20p CENTR223 Franceschetti, Massimo
• MATH 287D Statistical Learning
• TuTh 5:00p-6:20p APM 5402 Bradic, Jelena
• MATH 281C Mathematical Statistics
• TuTh 2:00p-3:20p APM 5402 Arias-Castro, Ery 
• MATH 280C Probability Theory
• MW 5:00p-6:20p APM 5402 Williams, Ruth J
• MATH 245C Convex Analysis and Optimization III
• MWF 4:00p-4:50p APM 5402 Nie, Jiawang 
• MATH 140C Foundations of Real Analysis III
• MWF 1:00p-1:50p HSS 1128A Saab, Rayan
• CSE 255 Data Mining and Predictive Analytics
• TuTh 3:30p-4:50p WLH 2207 Freund, Yoav 
• CSE 291 Neural Networks
• TuTh 2:00p-3:20p WLH 2113 Cottrell, Garrison W 
• CSE 272 Advanced Image Synthesis
• TuTh 11:00a-12:20p EBU3B 4140 Jensen, Henrik

Epigraph

$ \newcommand{\epi}{\mathop{\mathrm{epi}}} $

The epigraph of a function \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) is the set of points lying on or above its graph:

\[ \text{epi} f = \{ (x,\mu) : x\in \mathbb{R}^n, \mu \in \mathbb{R}, \mu \ge f(x) \} \subset \mathbb{R}^{n+1}\]. 

Properties:

A function is convex if and only if its epigraph is a convex set.

A function is lower semicontinuous if and only if its epigraph is closed.

Entropy maximization, part II

Let \(\mathcal{X} \in \{\alpha_1, \cdots, \alpha_n\}\) be a random variable with finite alphabet, what is the distribution that will achieve maximum entropy given the constraint that \(E[f(\mathcal{X})]=\beta\) ?

We define the expectation
\[\sum_i \alpha_i p_i = \beta \] The optimization problem is given as
\[\max_\mathbf{p} H(\mathbf{p}) \; s.t., \; \sum_i p_i = 1,\; \sum_i \alpha_i p_i = \beta\] Optimizing using Lagrange multipliers \(\lambda\) and \(\mu\), we have
\[ p_i = exp^{-(1-\lambda)}exp^{\mu \alpha_i}\] which turns out to be the familiar expression
\[p_i = \frac{1}{Z}exp^{\mu \alpha_i}\] with \(Z=\sum_i exp^{\mu \alpha_i}\) being the partition function.

The above form is called a Gibbs distribution.

Now consider the problem where with \(\mathcal{X} \in \mathbb{R}^p\) and we are given the moments \(E[f_j(\mathcal{X})]=\beta_j, j=1,\dots,p\).  The optimization problem becomes
\[\max_\mathbf{p} H(\mathbf{p}) \; s.t., \; \sum_i p_i = 1,\; \sum_i \alpha_{ij} p_i = \beta_j\] The expression have the form
\[p_i = \frac{1}{Z} exp^{\sum_{j=1}^p \mu_j \alpha_{ij}}
         =\frac{1}{Z} exp^{\mathbf{\mu}^T \mathbf{\alpha_{i}}}\] Since the distribution in general has infinite support the constraint on the moment will allow one to reach a unique solution.

Entropy maximization

One interesting and well known result is that out of all finite alphabet distributions, the uniform distribution achieves maximum entropy.

The Laplace's principle of insufficient reasoning, calls for assuming uniformity unless there is additional information.

Entropy maximization is the equivalent of minimizing the KL-Divergence between the distribution \(p\) and the uniform distribution.

More precisely, let \(\mathcal{X} \in \{\alpha_1, \cdots, \alpha_n\}\) be a random variable with finite alphabet, given a family of distribution \(\mathcal{P}\) and the uniform distribution \(u\),
\[ \underset{p\in\mathcal{P}}{\text{arg min}} \;D_{KL}(p\| u) = \underset{p\in\mathcal{P}}{\text{arg max}} \;H(p)\] where \(H(p)\) is the entropy.

Proof:
\[ D(p\|u) = \sum_i p_i \log p_i +  (\sum_i p_i) \log (n) = \log (n) - H(p) \]

Note: 

This is true in general for random variables with finite support.  For RVs with infinite support,  additional constraint is required.  See Gibbs measure...

A Side Path to Statistical Mechanics

Consider a physical system with many degrees of freedom, that can reside in any one of a large number of possible states.  Let \(p_i\) denote the probability of occurrence of state \(i\), for example, with the following properties:

\[p_i\ge 0 \quad \text{for all}\; i\]and 

\[\sum_i p_i = 1\] Let \(E_i\) denote the energy of the system when it is in state \(i\).  A fundamental results from statistical mechanics tells us that when the system is in thermal equilibrium with its surrounding environment, statie \(i\) occurs with a probability define by 

\[p_i = \frac{1}{Z}\exp(-\frac{E_i}{k_BT})\] where \(T\) is the absolute temperature in kelvins, \(k_B\) is the Boltzmann's constant, and \(Z\) is a constant that is independent of all states.  The partition function \(Z\) is the normalizing constant with 

\[Z= \sum_i \exp(-\frac{E_i}{k_BT}).\]  The probability distribution is called the Gibbs distribution.

Two interesting properties of the Gibbs distribution are:

1. States of low energy have a higher probability of occurrence than states of high energy.
2. As the temperature \(T\) is reduced, the probability is concentrated on a smaller subset of low-energy states.

In the context of neural networks, the parameter \(T\) may be viewed as a pseudo-temperature that controls thermal fluctualtions representing the effect of "synaptic noise" in a neuron.  Its precise scale is irrelevant.  We can redefine the probability \(p_i\) and partition function Z as

\[p_i = \frac{1}{Z}\exp(-\frac{E_i}{T}) \] and

\[Z = \sum_i \exp(-\frac{E_i}{T})\] where \(T\) is referred to simply as the temperature of the system. 

Note that \(-\log p_i\) may be viewed as a form of "energy" measured at unit temperature.

Free Energy and Entropy

The Helmholtz free energy of a physical system, denoted by \(F\), is defined in terms of the partition function \(Z\) as follows
\[F = -T \log Z.\]  The average energy of the system is defined by
\[\lt E\gt = \sum_i p_i E_i\] The difference between the average energy and free energy is
\[\lt E \gt - F = -T\sum_i p_i \log p_i\] which we can rewrite in terms of entropy \(H\)
\[\lt E \gt - F = T H\] or, equivalently,
\[F = \lt E \gt - TH\].  The entropy of any systems tend to increase until it reaches an equilibrium, and therefore the free energy of the system will reach a minimum.

This is an important principle called the principle of minimal free energy.

Cross Entropy

The cross entropy of distributions \(p\) and \(q\) is
\[H(p,q)=E_p[-\log q]\] It can be viewed as
\[H(p,q)=H(p)+D_{KL}(p\|q)\] where \(H(p)\) is the entropy of \(p\) and \(D_{KL}(p\|q)\) is the non-negative Kullback–Leibler divergence.

From an source coding perspective, it is the total bits required to encode information if the estimated distributed \(q\) diverged from the true distribution \(p\), where \(H(p)\) is the minimum.

This quantity is very useful in machine learning.  Viewed from a vector quantization point of view, logistic regression is a way of finding an optimal boundary to classifying samples in a (possibly high dimensional) space of interest.   This expression quantifies the loss of estimating distribution \(q\) instead of the true distribution \(p\).  Since \(H(p)\) is fixed because it is a property of the underlying true distribution, minimizing cross-entropy is equivalent to minimizing KL divergence in this setting.

Conditional Expectation

Definition.  \(\lambda\) is absolutely continuous (AC) with respect to \(\mu\), written \(\lambda \ll \mu\), if \(\mu(A)=0\) implies \(\lambda(A) = 0\).

Theorem 2 Radon-Nikodym Theorem  Let \((\Omega,\mathcal{B},P)\) be the probability space.  Suppose \(v\) is a positive bounded measure and \(v \ll P\).  Then there exists an integrable random variable \(X\in \mathcal{B}\), such that
\[v(E) = \int_E XdP, \quad \forall E \in \mathcal{B} \] \(X\) is a.s. unique (\(P\)) and is written
\[X=\frac{dv}{dP}.\] We also write \(dv=XdP\)

Definition of Conditional Expectation

Suppose \(X\in L_1(\Omega,\mathcal{B},P)\) and let \(\mathcal{G}\subset \mathcal{B}\) be a sub-\(\sigma\)-field.  Then there exists a random variable \(E(X|\mathcal{G})\), called the conditional expectation of \(X\) with respect to \(\mathcal{G}\), such that

1. \(E(X|\mathcal{G})\) is \(\mathcal{G}\)-measurable and integrable.
2. For all \(G\in\mathcal{G}\) we have \[ \int_G XdP = \int_G E(X|\mathcal{G})dP\]

Notes.

1. Definition of conditional probability: Given \((\Omega,\mathcal{B},P)\), a probability space, with \(\mathcal{G}\) a sub-\(\sigma\)-field of \(\mathcal{B}\), define \[P(A|\mathcal{G})=E(1_A|\mathcal{G}), \quad A\in \mathcal{B}.\]  Thus \(P(A|\mathcal{G}) \) is a random variable such that 
1. \(P(A|\mathcal{G}) \) is \(\mathcal{G}\)-measurable and integrable.
2. \(P(A|\mathcal{G}) \) satisfies \[\int_G P(A|\mathcal{G})dP = P(A\cap G), \quad \forall G \in \mathcal{G}. \]
2. Conditioning on random variables: Suppose \(\{X_t, t\in T \}\) is a family of random variables defined on \((\Omega,\mathcal{B})\) and indexed by some index set \(T\).   Define \[\mathcal{G}:=\sigma(X_t,t\in T)\] to be the \sigma-field generated by the process \(\{X_t, t\in T \}\).  Then define \[E(X|X_t, t\in T)= E(X|\mathcal{G}).\]

Note (1) continues the duality of probability and expectation but seems to place expectation in a somewhat more basic position, since conditional probability is defined in terms of conditional expectation.

Note (2) saves us from having to make separate definitions for \(E(X|X_1)\), \(E(X|X_1,X_2)\), etc.

Countable partitions Let \(\{\Lambda_n, n\ge 1 \}\) be a partition of \(\Omega\) so thyat \(\Lambda_i \cap \Lambda_j = \emptyset, i\neq j\), and \(\sum_n \Lambda_n=\Omega\).  Define
\[\mathcal{G}=\sigma(\Lambda_n, n\ge 1)\] so that
\[\mathcal{G}=\left\{ \sum_{i\in J}\Lambda_i: J\subset\{1,2,\dots \} \right\}.\] For \(X\in L_1(P)\), define
\[E_{\Lambda_n}(X)=\int XP(d\omega|\Lambda_n)=\int_{\Lambda_n}XdP/P\Lambda_n , \] if \(P(\Lambda_n)>0\) and \(E_{\Lambda_n}(X) = 18\) if \(P(\Lambda_n)=0\).  We claim

1. \[E(X|\mathcal{G})\overset{a.s.}{=} \sum_{n=1}^\infty E_{\Lambda_n}(X) 1_{\Lambda_n}  \] and for any \(A\in \mathcal{B}\)
2. \[P(A|\mathcal{G})\overset{a.s.}{=} \sum_{n=1}^\infty P(A|\Lambda_n)1_{\Lambda_n}\]

Product Spaces, Transition Kernel and Rubini's Theorem

Lemma 1. Sectioning sets Sections of measurable sets are measurable.  If \(A\in \mathcal{B}_1 \times \mathcal{B}_2\), then for all \(\omega_1 \in \Omega_1\),
\[A_{w_1}\in \mathcal{B_2}\]
Corollary 1. Sections of measurable functions are measurable.  That is if
\[ X: (\Omega_1\times \Omega_2, \mathcal{B}_1 \times \mathcal{B}_2) \mapsto (S,\mathcal{S})\] then \[ X_{\omega_1} \in \mathcal{B}_2. \]  We say \(X_{\omega_1}\) is \(\mathcal{B}/\mathcal{S}\) measurable.

Define the transition (probability) kernel

\[K(\omega_1,A_2):\Omega_1 \times \mathcal{B}_2 \mapsto [0,1]\]

if it satisfies the following

1. for each \(\omega_1, K(\omega_1,\cdot)\) is a probability measure on \(\mathcal{B}_2\), and
2. for each \(A_2\in \mathcal{B}_2, K(\cdot, A_2)\) is \(\mathcal{B}_1/\mathcal{B}([0,1])\) measurable.

Transition kernels are used to define discrete time Markov processes where \(K(\omega_1,A_2)\) represents the conditional probability that, starting from \(\omega_1\), the next movement of the system results in a state in \(A_2\).

Theorem 1.  Let \(P_1\) be a probability measure on \(\mathcal{B}_1\), and suppose

\[K:\Omega_1 \times \mathcal{B}_2 \mapsto [0,1]\] is a transition kernel.  Then \(K\) and \(P_1\) uniquely determine a probability on \(\mathcal{B}_1 \times \mathcal{B}_2\) via the formula

\[P(A_1\times A_2)= \int_{A_1}K(\omega_1,A_2)P_1(dw_1),\] for all \(A_1\times A_2\) in the class of measurable rectangles.

Theorem 2. Marginalization  Let \(P_1\) be a probability measure on \((\Omega_1,\mathcal{B}_1)\) and suppose \(K: \Omega_1\times \mathcal{B_2} \mapsto [0,1]\) is a transition kernel.  Define \(P\) on \((\Omega_1 \times \Omega_2, \mathcal{B_1}\times \mathcal{B_2})\) by
\[P(A_1\times A_2)= \int_{A_1} K(\omega_1,A_2)P_1(d\omega_1). \]  Assume
\[X:(\Omega_1\times \Omega_2, \mathcal{B}_1\times \mathcal{B}_2) \mapsto (\mathbb{R},\mathcal{B}(\mathbb{R})) \] and furthermore suppose \(X\) is integrable.  Then
\[Y(\omega_1)=\int_{\Omega_2} K(\omega_1,d\omega_2)X_{\omega_2}(\omega_2)\] has the properties

1. \(Y\) is well defined.
2. \(Y \in B_1\)
3. \(Y \in L_1(P_1)\) and furthermore

\[\int_{\Omega_1\times \Omega_2}XdP = \int_{\Omega_1} Y(\omega_1)P_1(d\omega_1) = \int_{\Omega_1} [ \int_{\Omega_2} K(\omega_1,d\omega_2) X_{\omega_1}(d\omega_2)]P_1(\omega_1). \]

Theorem 3.  Fubini Theorem  Let \(P=P_1\times P_2\) be a product measure.  If \(X\) is \(\mathcal{B}_1 \times \mathcal{B}_2\) measurable and is either non-negative or integrable with respect to \(P\) then

\[\begin{aligned}
\int_{\Omega_1\times \Omega_2}XdP &= \int_{\Omega_1}[ \int_{\Omega_2}X_{\omega_1}(\omega_2) P_2(d\omega_2) ] P_1(d\omega_1) \\
                                                                &= \int_{\Omega_2}[ \int_{\Omega_1}X_{\omega_2}(\omega_1) P_1(d\omega_1) ] P_2(d\omega_2)
\end{aligned} \]

Clarification of Expectation

Let \(X\) be a random variable on the probability space \((\Omega, \mathcal{B}, P)\).  Recall that the distribution of X is the measure
\[F := P \circ X^{-1}\] on \((\mathbb{R},\mathcal{B}(\mathbb{R}))\) defined by
\[F(A)=P\circ X^{-1}(A) = P[X\in A].\]
The distribution function of \(X\) is
\[F(x):= F((-\infty,x])=P[X\leq x].\]  Note that the letter "F" is overloaded in two ways.

An application of the Transformation Theorem allows us to compute the abstract integral
\[E(X) = \int_\Omega XdP\] as
\[E(X) = \int_\mathbb{R} xF(dx),\] which is an integral on \(\mathbb{R}\).

More precisely,
\[E(X) = \int_\Omega X(\omega)P(d\omega)=\int_\mathbb{R} x F(dx).\]
Also given a measurable function \(g(X)\), The expectation of \(g(X)\) is
\[E(g(X)) = \int_\Omega g(X(\omega))P(d\omega)=\int_\mathbb{R} g(x) F(dx).\]
Instead of computing expectations on the abstract space \(\Omega\), one can always compute them on \(\mathbb{R}\) using \(F\), the distribution of \(X\).

Random variables and Inverse maps

A random variable is a real valued function with domain \(\Omega\) which has an extra property called measurability that allows us to make probability statements about the random variable.

Suppose \(\Omega\) and \(\Omega'\) are two sets.  Often \(\Omega' = \mathbb{R}\).  Suppose
\[X:\Omega \mapsto \Omega',\]  Then \(X\) determines an inverse map (a set valued function)
\[X^{-1}: \mathcal{P}(\Omega')\mapsto \mathcal{P}(\Omega)\] defined by
\[X^{-1}(A') = \{\omega \in \Omega : X(\omega) \in A'\}\] for \(A' \subset \Omega'\).

\(X^{-1}\) preserves complementation, union and intersections.

Convergence Concepts

Implications of convergence

1. Almost Sure Convergence

Examples of statements that hold almost surely (a.s.)

• Let \(X,X'\) be two random variables.  Then \(X=X'\) a.s. means \[P[X=X']=1;\] that is, there exists an event \(N\in \mathcal{B}\), such that \(P(N)=0\) and if \(\omega\in N^c\), then \(X(\omega)=X'(\omega)\).
• If \(\{X_n\}\) is a sequence of random variables, then \(\lim_{n\rightarrow \infty}X_n\) exists a.s. means there exists an event \(N\in \mathcal{B}\), such that \(P(N)=0\) and if \(\omega\in N^c\) then \[\lim_{n\rightarrow \infty}X_n(w)\] exists. It also means that for a.a. \(\omega\), \[\underset{n\rightarrow \infty}{\text{lim sup}}X_n(\omega)=\underset{n\rightarrow \infty}{\text{lim inf}}X_n(\omega).\] We will write \(\lim_{n\rightarrow \infty}X_n = X\) or \(X_n \overset{a.s.}{\rightarrow}X\).
• If \(\{X_n\}\) is a sequence of random variables, then \(\sum_n X_n\) converges a.s. means there exists an event \(N\in \mathcal{B}\), such that \(P(N)=0\), and \(\omega \in N^c\) implies \(\sum_n X_n(w)\) converges.

2. Convergence in Probability

Suppose \(X_n, n\ge 1\) and \(X\) are random variables.  Then \({X_n}\) converges in probability (i.p.) to \(X\), written \(X_n \overset{P}{\rightarrow}X\), if for any \(\epsilon > 0\) \[ \lim_{n\rightarrow \infty} P[|X_n-X|>\epsilon]=0.\]
Almost sure convergence of \(\{X_n\}\) demands that for a.e. \(\omega\), \(X_n(w)-X(w)\) gets small and stay small.  Convergence i.p. is weaker and merely requires that the probability of the difference \(X_n(w)-X(w)\) being non-trivial become small.

It is possible for a sequence to converge in probability but not almost surely.

Theorem 1. Convergence a.s. implies convergence i.p. Suppose that \(X_n, n\ge 1\) and \(X\) are random variables on a probability space \((\Omega,\mathcal{B},P)\).  If \[ X_n \rightarrow X, \; a.s.\] then \[X_n \overset{P}{\rightarrow}X.\]
Proof.  If \(X_n \rightarrow X\) a.s. then for any \(\epsilon\),
\[\begin{aligned}
0\;&=P([|X_n-X|>\epsilon]i.o.) \\
  &=P(\underset{n\rightarrow \infty}{\text{lim sup}}[|X_n-X|>\epsilon]) \\
  &=\lim_{N\rightarrow \infty}P(\bigcup_{n\ge N}[|X_n-X|>\epsilon] ) \\
  &\ge \lim_{n\rightarrow \infty}P[|X_n-X|>\epsilon]
\end{aligned} \]

3. \(L_p\) Convergence

Recall the notation \(X\in L_p\) which means \(E(|X|^p)<\infty \). For random variables \(X,Y\in L_p\), we define the \(L_p\) metric for \(p\ge 1\) by
\[d(X,Y)=(E|X-Y|^p)^{1/p}.\]  This metric is norm induced because
\[\|X\|_p := (E|X|^p)^{1/p} \] is a norm on the space \(L_p\).

A sequence \(\{X_n\}\) of random variables converges in \(L_p\) to \(X\), written
\[X_n \overset{L_p}{\rightarrow}X , \] if
\[ E(|X_n-X|^p) \rightarrow 0 \] as \(n\rightarrow \infty\).

Facts about \(L_p\) convergence.

1. \(L_p\) convergence implies convergence in probability: For \(p>0\), if \(X_n\overset{L_p}{\rightarrow} X\) then \(X_n \overset{P}{\rightarrow}X \).  This follows readily from Chebychev's inequality, \[P[|X_n-X|\ge \epsilon] \leq  \frac{E(|X_n-X|^p|)}{\epsilon^p} \rightarrow 0.\]
2. Convergence in probability does not imply \(L_p\) convergence.  What can go wrong is that the \(n\)th function in the sequence can be huge on a very small set.
   Example.  Let the probability space be \( ([0,1],\mathcal{B}([0,1]),\lambda) \), where \(\lambda\) is Lebesgue measure and define
   \[X_n = 2^n 1_{(0,\frac{1}{n}) }\] then
   \[P[|X_n| > \epsilon ] = P \left( (0,\frac{1}{n}) \right)  = \frac{1}{n} \rightarrow 0 \] but
   \[ E(|X_n|^p) = 2^{np} \frac{1}{n} \rightarrow \infty \]
3. \(L_p\) convergence does not imply almost sure convergence.
   Example.  Consider the functions \(\{X_n\}\) defined on \( ([0,1],\mathcal{B}([0,1]),\lambda) \), where \(\lambda\) is Lebesgue measure.
   \begin{align*}
       X_1 &= 1_{[0,\frac{1}{2}]},  \quad  X_2 = 1_{[\frac{1}{2},1]} \\
       X_3 &= 1_{[0,\frac{1}{3}]},  \quad  X_4 = 1_{[\frac{1}{3},\frac{2}{3}]} \\
       X_5 &= 1_{[\frac{1}{3},1]},  \quad  X_6 = 1_{[0,\frac{1}{4}]}, \cdots \\
   \end{align*} and so on, Note that for any \(p>0\),
   \[ E(|X_1|^p)=E(|X_2|^p)=\frac{1}{2},\\
       E(|X_3|^p)=E(|X_4|^p)=E(|X_5|^p)=\frac{1}{3}, \\
       E(|X_6|^p)=\frac{1}{4}, \cdots \] so  \(E(|X_n|^p) \rightarrow 0\) and
   \[X_n \xrightarrow[]{L_p} 0.\]
   Observe that \(\{X_n\}\) does not converge almost surely to 0.

Limits and Integrals

Under certain circumstances we are allowed to interchange expectation with limits.

Theorem 1. Monotone Convergence Theorem (MCT). If
\[0\leq X_n \uparrow X\]then
\[0\leq E(X_n) \uparrow E(X)\]
Corollary 1.  Series Version of MCT.  If \(X_n \ge 0\) are non-negative random variables for \(n\ge1\), then
\[E(\sum_{n=1}^\infty X_n)= \sum_{n=1}^\infty E(X_n)\]
so that the expectation and infinite sum can be interchanged

Theorem 2. Fatou Lemma. If \(X_n \ge 0\), then
\[ E(\underset{n\rightarrow \infty}{\text{lim inf}} X_n ) \leq \underset{n\rightarrow \infty}{\text{lim inf}}E(X_n)\]
More generally, if there exists \(Z\in L_1\) and \(X_n\ge Z\), then
\[ E(\underset{n\rightarrow \infty}{\text{lim inf}} X_n ) \leq \underset{n\rightarrow \infty}{\text{lim inf}}E(X_n)\]
Corollary 2. More Fatou.  If \( 0 \leq X_n \leq Z\) where \(Z\in L_1\), then
\[ E(\underset{n\rightarrow \infty}{\text{lim sup}} X_n ) \ge \underset{n\rightarrow \infty}{\text{lim sup}}E(X_n)\]
Theorem 3. Dominated Convergence Theorem (DCT).  If
\[X_n \rightarrow X\] and there exists a dominating random variable \(Z\in L_1\) such that
\[ |X_n| \leq Z\]then
\[E(X_n)\rightarrow E(X) \; \text{and} \; E|X_n-X|\rightarrow 0.\]
\(
\newcommand{\scriptB}{\mathcal{B}}
\newcommand{\scriptP}{\mathcal{P}}
\newcommand{\vecX}{\mathbf{X}}
\newcommand{\vecx}{\mathbf{x}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\cplxs}{\mathbb{C}}
\newcommand{\rationals}{\mathbb{Q}}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\ntoinf}{n\rightarrow\infty}
\newcommand{\mtoinf}{m\rightarrow\infty}
\newcommand{\tendsto}{\rightarrow}
\)
Example of when interchanging limits and integrals without the dominating condition.  (When something very nasty happens on a small set and the degree of nastiness overpowers the degree of smallness).

Let
\[ (\Omega, \scriptB, P) = ([0,1], \scriptB([0,1]), \lambda)\] \(\lambda\) the Lebesgue measure. Define
\[ X_n = n^2 1_{(0,1/n)}. \] For any \(\omega \in [0,1]\),
\[  1_{(0,1/n)}(w) \tendsto 0,\] so
\[ X_n \tendsto 0. \] However
\[  E(X_n) = n^2 \cdot \frac{1}{n} = n \tendsto \infty, \] so
\[ E(\liminf_{\ntoinf} X_n) = 0 \le \liminf_{\ntoinf} (EX_n) = \infty \] and
\[ E(\limsup_{\ntoinf} X_n) = 0 \not\ge \limsup_{\ntoinf} (EX_n) = \infty.\]

Zero-One Laws

There are several common zero-one laws which identify the possible range of a random variable to be trivial. There are also several zero-one laws which provide the basis for all proofs of almost sure convergence.

Proposition 1. Borel-Cantelli Lemma Let \(\{A_n\}\) be any events (not necessarily independent).

If \(\sum_n{P(A_n)}<\infty\), then
\[P([A_n \; i.o.])=P(\underset{n\rightarrow \infty}{\text{lim sup}} A_n) = 0\].
Proposition 2. Borel Zero-One Law If \(\{A_n\}\) is a sequence of independent events, then

\[  \begin{equation*}
P([A_n \; i.o.])= \begin{cases}
0, \quad &  \text{iff} \sum_n P(A_n) < \infty \\
1, \quad &  \text{iff} \sum_n P(A_n) = \infty
\end{cases}
\end{equation*}
\]
Definition.  An almost trivial \(\sigma\)-field is a \(\sigma\)-field all of whose events has probability 0 or 1.

Theorem 3. Kolmogorov Zero-One Law If \(\{X_n\}\) are independent random variables with tail \(\sigma\)-field \(\mathcal{T}\), then \(\Lambda\in \mathcal{T}\) implies \(P(\Lambda)=0\) or 1 so that the tail \(\sigma\)-field is almost trivial.

Lemma 4. Almost trivial \(\sigma\)-fields  Let \(\mathcal{G}\) be an almost trivial \(\sigma\)-field and let \(X\) be a random variable measurable with respect to \(\mathcal{G}\).  Then there exists \(c\) such that \(P[X=c] = 1\).

Corollary 5.  Let \(\{X_n\}\) be independent random variables.  Then the following are true.

(a) The event
\[ [\sum_n X_n \;converges] \] has probability 0 or 1.

(b) The random variables \(\text{lim sup}_{n\rightarrow \infty}X_n\) and \(\text{lim inf}_{n\rightarrow \infty}X_n\) are constant with probability 1.

(c) The event
\[ \{\omega: S_n(\omega)/n \rightarrow 0 \} \] has probability 0 or 1.

Inequalities

Another valuable book for anyone in computer science who ever wants to bound any quantity (so, everyone!) is: The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities by Michael Steele.

An encyclopedic book on the topic is A Dictionary of Inequalities. While this is not a book for reading cover-to-cover, it is good to have it at your disposal. See also the supplement of the book.

Moreover, Wikipedia has an excellent list of inequalities.

For specific topics, you may consult:

• Probabilistic Inequalities
• Matrix Inequalities
• Geometric Inequalities
• The book "A=B" by Petkovsek, Wilf and Zeilberger
• Inequality cheatsheet

Dynkin's theorem

First we define a structure named \(\lambda\)-system.

A class of subsets \(\mathcal{L}\) of \(\Omega\) is called a \(\lambda\)-system if it satisfies the following postulates

1.  \(\Omega\in \mathcal{L}\)
2. \(A\in\mathcal{L} \Rightarrow A^c \in \mathcal{L}\)
3. \(n\neq m, A_nA_m = \emptyset, A_n \in \mathcal{L} \Rightarrow \cup_n A_n \in \mathcal{L}\)

It is clear that a \(\sigma\)-field is always a \(\lambda\)-system.

Next a \(\pi\)-system is a class of sets closed under finite intersections.

Dynkin's theorem

a) if \(\mathcal{P}\) is a \(\pi\)-system and \(\mathcal{L}\) is a \(\lambda\)-system such that \(\mathcal{P}\subset\mathcal{L}\), then \(\sigma(\mathcal{P})\subset \mathcal{L}\).

b) If \(\mathcal{P}\) is a \(\pi\)-system,

\(\sigma(\mathcal{P})=\mathcal{L}(\mathcal{P})\)

that is, the minimal \(\sigma\)-field over \(\mathcal{P}\) equals the minimal \(\lambda\)-system over \(\mathcal{P}\)

An example of Stein's paradox

Charles Stein showed in 1958, that a nonlinear, biased estimator of a multivariate mean has a lower MSE compared to the ML estimator.

Given a sample of \(N\) measurements of \(X\sim\mathcal{N}(\mu,\sigma I_p)\) with unknown parameter vector \(\mu\) of length \(p\).

The James-Stein estimator is given by

\begin{equation*}
\hat{\mu}_{JS}=\left (1-\frac{(p-2)\frac{\sigma^2}{N}}{\|\bar{x} \|^2}\right ) \bar{x}
\end{equation*}
where \(\bar{x}\) is the sample mean.

This estimator dominates the MLE everywhere in terms of MSE.  For all \(\mu\in\mathbb{R}^p\),

\begin{equation*}
\mathbb{E}_\mu \| \hat{\mu}_{JS}-\mu\|^2 < \mathbb{E}_\mu \| \hat{\mu}_{MLE}-\mu\|^2
\end{equation*}
This makes the MLE inadmissible for \(p\ge3\)!

The need for measure theory

The problem with measure arises when one needs to decompose a body into (possibly uncountable) number of components and reassemble it after some action on those components.  Even when you restrict attention to just finite partitions, one still runs into trouble here. The most striking example is the Banach-Tarski paradox, which shows that a unit ball \(B\) in three dimension can be disassembled into a finite number of pieces and reassembled to form two disjoint copies of the ball \(B\).

Such pathological sets almost never come up in practical applications of mathematics.  Because of this, the standard solution to the problem of measure has been to abandon the goal of measuring every subset \(E\) of \(\mathbb{R}^d\) and instead to settle for only measuring a certain subclass of
non-pathological subsets of \(\mathbb{R}^d\), referred to as the measurable sets.

The most fundamental concepts of measure is the properties of

1. finite or countable additivity
2. translation invariance
3. rotation invariance

The concept of Jordan measure (closely related to that of Riemann and Darboux integral) is sufficient for undergraduate level analysis.

However, the type of sets that arise in analysis, and in particular those sets that arise as limit of other sets, requires an extended concept of measurability (Lebesgue measurability)

Lebesgue theory is viewed as a completion of the Jordan-Darboux-Riemann theory.  It keeps almost all of the desirable properties of Jordan measure, but with the crucial additional property that many features of the Lebesgue theory are preserved under limits.

Probability space concepts

A field is a non-empty class of subsets of \(\Omega\) closed under finite union, finite intersection and complements.  A synonym for field is algebra.

From de Morgan's laws a field is also closed under finite intersection.

A \(\sigma\)-field \(\mathcal{B}\) is a non-empty class of subsets of \(\Omega\) closed under countable union, countable intersection and complements.  A synonym for \(\sigma\)-field is \(\sigma\)-algebra.

In probability theory, the event space is a \(\sigma\)-field.  This allows us enough flexibility constructing new-events from old ones (closure) but not so much flexibility that we have trouble assigning probabilities to the elements of the \(\sigma\)-field.

For the Reals, we start with sets that we know how to assign probabilities.

Supposes \(\Omega=\mathbb{R}\) and let

\(\mathcal{C}=\{(a,b],-\infty \leq a \leq b < \infty \}\)

The Borel sets is defined as

\(\mathcal{B}(\mathbb{R}) \equiv \sigma(\mathcal{C})\)

Also one can show that

\(\mathcal{B}(\mathbb{R}) = \sigma(\text{open sets in } \mathbb{R}) \)

Russell's Paradox

Shortly after the turn of the 19th century, Bertrand Russell demonstrated a hole in mathematical logic of set theory at the time.  A set can be member of itself. For sets \(R\) and \(S\)

\(R = \{S | R \notin S\}\)

The set \(R\) contains all sets that do not have themselves as members.

However, is \(R\) a member of itself?

Clearly not, since by definition \(R\) is the set of all sets that do not have themselves as member.

But then, if \(R\) does not have itself as a member then it must be a member of the set \(R\)

At that point in time, it created a huge stir among the mathematical community since most of what they do are based upon the foundation of sets.

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.

Properties of a positive definite matrix

Just found out some interesting properties about positive definite matrices.

Given an Hermitian matrix M

• The eigenvalues of M is strictly positive.
• It is the Gram matrix of linearly independent vectors.
• It has a Cholesky decomposition. M = M' = L' * L = H' * H.  Where L is a triangular matrix with strictly positive diagonal elements.

Kernel density estimation

Look into this on Monday.

Kernel density estimation

Ideal parent of a high reactive child

Quoted from Quiet: The power of introverts in a world that can't stop talking

Someone who can read your cues and respect your individuality; is warm and firm in placing demands on you without being harsh or hostile; promotes curiosity, academic achievement, delayed gratification, and self-control; and is not harsh, neglectful, or inconsistent.

Sequence alignment paper

Need to take a look at this for bitmatching.
Dynamic programming and sequence alignment

Paper from Todd Veldhuizen

This is a nice summary of techniques used in the development of Blitz++
Techniques for Scientific C++

Household hazardous waste disposal

Household hazardous waste disposal

More setbacks

It's all too often now that I experience another blow to my fragile self-esteem. I often feel confident about the amount of learning I have gather over the period. But to excel in what I do, I have to take extra steps beyond what is provided to really make an impact. Being severely drained as I am, I'm not how much more effort I can squeeze out of me...

HK Locations

Swindon book co. Ltd
13-15 Lock Road,
Tsimshatsui
MTR Tsimshatsui Exit C2
858-2366-8001

Heading to DB

I think this is a very special place and one that I'm particularly fond of.

• DB D-Deck dining

Workload

It's one of those moments when you felt your intuition is correct and you have put in significant effort to start the process, but all of a sudden you have been told your intuition will not lead you to the usefulness people see in you in the future.

Now I'm taking a step back and make sure I will not lead myself astray but trust the guidance of an expert more experienced than I am.

Anyway. It's complex.

How do you get gigabit per second over the air?

This question is still keeping my awake during the night.

• Multiple bits per symbol is a given; there is simply no technology out there that can digitize at gigasample per second.
• Multiple antenna - how do you pack up to four antenna to a device? I can picture that being possible on a decent sized laptop, at 5GHz or more, over short distance with a favourable channel.
• Getting gigabits to the home. This becomes a question of what type of infrastructure is required to do just that. Fiber to the home, and a wireless access point (femtocell). A cell tower managing hundreds of gigabits of data over the air will be challenging.
• A lot has to take place, similar to idea of fuel cell vehicles. Infrastructure is a significant issue.

Simulations

It appears most simulations are done in a Linux environment. Research tools are both open and actively worked on by the academic community as well as the industry.

However, a fair amount of practical implementation tools are developed on Window.

Survey of the disciplines in communications research

The study of communications encompasses the following theories

• Information theory
• Coding theory
• Dectection theory
• Control theory
• Network theory
• Computation theory
• Game theory

The underlying fundamentals consist of

• Linear systems and signals
• Statistics and random processes
• Antenna & wave propagation

Simulations

• Large Deviation Theory
• Importance sampling

Implementation level

• DSP and alogrithms
• RF/Microwave circuits
• Embedded systems

Illustrations in Latex documents

I've searched around for tools to help with creating diagrams. The closest contender seems to be something that is vector based and supports importing and exporting eps format.

One expensive choice is Adobe Illustrator + MathType. Even at student price, Illustrator is still prohibitively $$$.

A good contender is Inkscape but it's not mature enough for dealing with importing eps equations and editing them in place.

Library barcode system

Keeping track of the details for our library setup.

• My old Toshiba Portege A100 laptop
• Metrologic MS9540 (part of Honeywell) - $150
• Barcode labels (1000 labels) -$28
• Gaylord
• Brodart
• Demco

Barcode details

• Symbology: code 3 of 9, 5-6 Characters, no check code
• Heading: "Mira Mesa Chinese Baptist Church"
• Sequence: nnnnn (n = 0-9, e.g. 01234)

Testing formulas

This is a cool way of adding formulas to email/blogs. However it's not supported natively on the browser. Under the hood, it makes a request to a server for an embedded gif image.

The LaTex Equation Editor website is here

UCSD planning

• Take first quarter at $8,000, no-support.

Winning moves

A very good cheat sheet on Winning Eleven (PES)'s moves.

Thought record

Now is the time to blow the dust off my blog and start something substantial. I'll have to see what I want to place on here. I'll start off probably by writing what I've learned during the period.

Hair Stylist

Stylist: Maki
Muse Beauty Salon
7710 Balboa Ave. Suite 125
San Diego, CA
92111

LA Restaurants

Maxim Cafe

Hong Kong style western dishes

18904 East Gale Ave,

Rowland Heights, CA 91748

626-913-7777

A&J Restaurant
Taiwanese

14805 Jeffrey Rd. #D
Irvine, CA 92720
949-786-3585

July 19, 2008
The Kitchen
203 West Valley Blvd.
Alhambra, CA 91801
626-289-4828
Upscale chinese cuisine, relatively speaking. Great food.

Tasty Garden
288 West Valley Blvd.
Alhambra, CA 91801
626-300-8262

July 4, 2008
Din Tai Fung
1108 South Baldwin Avenue (First store)
1088 South Baldwin Avenue (New, larger, modern looking)
Arcadia, CA 91007
626-574-7068

Phoenix Food Boutique
1108 South Baldwin Avenue
Arcadia, CA 91007
626-284-2388
Beside the drinks, casual food, it has amazingly tasty curry fish balls, not to be missed.

SD Restaurants

This is where I will compile a list of restaurants and how their fare.

Chedi Thai Bistro
737 Pearl St. Suite 110

La Jolla, CA 92037

858-551-8424

Lanna Thai Cruisine
4501 Mission Bay Dr.
San Diego, CA 92109
858-274-8424

Extraordinary Desserts - Little Italy

1430 Union St.

San Diego, CA 92101

619-294-7001

Tajima Japanese Restaurant
4681 Convoy St
San Diego, CA 92111
(858) 576-7244

Curry House - Japanese style curry and spaghetti
3860 Convoy St. #102
San Diego, CA 92111
(858) 278-2454

Ichiro Japanese Restuarant
4344 Convoy St # Q
San Diego, CA 92111
(858) 565-8603

Lorna's Italian Kitchen
3945 Governer Drive
San Diego, CA 92122
858-452-0661

Dae Jang Keum (Korean fine Cuisine)
7905 Engineer Rd.
San Diego, CA 92111
858-573-2585

Sante Ristorante (Italian) - May 17, 2008
Located at an inside street in La Jolla, not that busy compared to the ones along the coast. But this is a Gem that cannot be missed. Excellent seafood pasta, and delicious tartufo. Highly recommend.

7811 Herschel Avenue
La Jolla, CA
858-454-1315

KI sushi - May 14, 2008
I like the atmosphere and lunch is not bad for the price you pay.

Costa Verde Shopping Center
8650 Genesee Ave
San Diego, CA 92122

Cafe Coyote - May 4, 2008
Great taste of Margaritas and Mexican food.

2461 San Diego Avenue
San Diego, CA 92110

Osetra - May 1, 2008
Gorgeous and modern ambiance with a spectacular 3 storey wine collection and suspension lift for getting the wine! Expensive place, but well worth a visit. Thanks Shirley for bringing me there!

904 5th Avenue, San Diego, CA 92101
Gaslamp Quarters

The art of moving...

Don't let anyone tell you moving is not stressful; when you have to cross the border that complicates the matter even more.

I understand now how much my dad had to go through when he moved our entire family over. That must have been a feat of enormous proportion. He moved into a completely new culture with a different governing system. But I had no idea at the time, since I was still trying to understand why we moved and coping with adjusting to yet another move in my young life - I was 14 and rebellious.

From HK to England, to Toronto, to Waterloo, to Ottawa, there was not once that I had company while I moved. From Ottawa to Waterloo, and now Waterloo to San Diego, I'm going solo. The lesson I learned from this is that a modern mercenary has to be mobile as ever. You simply cannot keep too many things.

Piotr Wozniak's prescription to becoming a genius

When someone spends his whole life mastering the technique of learning, you listen...

Clarify your goals, gain knowledge through spaced repetition, preserve health, work steadily, minimize stress, refuse interruption, and never resist sleep when tired. This should lead to radically improved intelligence and creativity.

Last glimpse of the Compaq Portable

Items for sale

This is a list of stuff I want to unload, I'm willing to give away some of them if I find a suitable owner.

• Black and Decker Toaster oven
• Car pedal lock
• Propane camping lamp
• Little Green portable wet vacuum
  
• Cricket stuff
• 2 Supersoaker water guns
• Hockey Gear
• Fishing rod
• PS2 steering wheel
• 2 Sleeping bags and mats
• camping chairs
• 6 foot folding table
• Inflatable sofa and mattress
• Camping tent for 4
• Bauer Roller blades size 8 1/2
• Michelin Pilot Alpin snow tires on steel rims 195/65/15 + hubcabs
  
• Broil-Mate 50K BTU Gas barbecue (Natural Gas) with stainless steel utensils
  
• Worx 13A 16" Mulching and bagging electric lawn mower, handle folds down
  
• 16 foot extension ladder
• Lawn rake, leaf scraper
  
• 2 Snow shovels
• 2 SnowZinger magic carpets
• Volley ball, basketball
  
• 2 Weight adjustable Dumbbells
  
• Stand-up vacuum
• Wine glasses
  
• Camera tripod