Math Notes

Decide to equip myself with more mathematics knowledges

2005-09-23T08:35:00.000-07:00

Recently, I found that without mathematics knowledge, it's impossible to create any good ideas in computer vision and multimedia processing. Whatever it is late or not, I decide to equip myself with those useful mathematics stuff step by step.

There are many branches within mathematics. I decide to focus on statstics (random process) and linear algebra as well as their combination (statictical analysis of matrix). I guess these two areas are very useful to design good algorithms to solve vision problem.

Some useful reference I will start
M.I.T Opencourse Website (related courses) http://ocw.mit.edu
Linear Algebra Journals:
Linear Algebra & Statistics books

Concept: Skew-Symmetric Hermitian Matrix and Skew-Symmetric Matrix

2005-08-04T08:53:00.000-07:00

I learn these two concepts tonight. Although I don't know what's the application of this kind of matries, it's very interesting to know these concepts.

skew-symmetric matrix is a special case of skew-symmetric hermitian matrix such that they share the same properties.

The trace of a skew-symmetric hermitian matrix is purely imaginary or zero;
The eigenvalues of a skew-symmetric hermitian matrix are purely imaginary or zero;

Tutorial_Spectral_Clustering: Principal Component Analysis

2005-07-24T20:46:00.000-07:00

I have thought that I have understand PCA quite well until I began to study this tutorial. PCA is an Dimension reduction/Embedding technique. Very fantastically, we can explain PCA from different points of view!

Energy preserving approximation: by removing the smallest eigenvalues/eigenvectors, the information loss of the approximation is minimized;
Local Structure Embedding: Given Y is the centered data matrix, A=Y'*Y (Gram/Kernel matrix) through normalization can be seen as the pairwise correlation matrix where each element Aij represents the correlation between i and j that is the cosine of the angle between these two vectors. Then because the energy preserving properties of PCA, the approximation preserves the local structure of nearby points due to their high cosine value (more energy); This property can also be explained as cluster discriminant within embedding system;
Feature dimension reduction, Clustering and Embedding is related with each other. The objective function can be derived to a common one. And solution of dimension reduction (PCA) is the k largest principal components Vk (Y'Y*Vk=aVk), Vk(s) are also the lower bounds of the indicator vectors of k clusters (the integer indicator (0...,1..1,0...) can be recovered from Vk) and Vk(s) can be used as the coordinate (Vk=A'X) to achieve low-dimension embedding;
Given a centered data matrix X, X*X' is the dimension covarance matrix (ignore the factor 1/n) according to its definition (m x m) that measures the variance of data to the mean. But because each dimension is not independent, we can not find the potential dominant direction with largest virance. Eigenvalue decomposition on the covariance matrix can simplify this matrix and make each dimension independent by rotating the coordinate system; normalized X'*X is the gram matrix or kernel matrix that is related to the cosine of the angle between each pair of data. So it is related to the pairwise similarity matrix (affinity matrix)

Tutorial1_Spectral Clustering: K-means Clustering vs PCA

2005-07-23T09:33:00.000-07:00

K-means clustering is a commonly used unsupervised learning method while PCA is a widely used unsupervised dimeansion reduction technique. Do you think about these two method correlate with each other? I first give you a simple intuitive: Given a data matrix X where each column is a data vector, there are two ways to reduce the rank of the data matrix. On one end, we can reduce the rank of matrix by column (reduce the number of feature) from the view of dimension reduction; On the other end, we can equivalently reduce the rank of the matrix by rows (cluster the data).
Mathematics analysis has proved that the principal components of the gram matrix of the centered data are the continuous solutions to the discrete cluster membership indicators for k-means clustering. Also by embedding the data into cluster subspace that is spanned by K cluster centroids, the cluster is becoming more compact (inter-cluster distance is remained and intra-cluster distance is reduced). Applying k-means clustering in this cluster subspace can achieve more effective result that is called PCA-guided k-means clustering.