aSymbol Soup

Karthik Thiagarajan

1. NOTE 2. Week-1

1. NOTEThis document is a collection of equations and expressions that are found throughout the course. All context and background information are absent and only the name of the object is presented. The reader is advised to proceed with extreme caution while engaging with this document. 2. Week-1 Data matrix X∈Rd×d Mean of the data-points ⏨x=1

nn∑i=1xiTo center data-points x′i=xi-⏨x Centered data matrix Xc∈Rd×d Xc=a

|		|
x′1	⋯	x′n
|		|

Xc is the centered data-matrix of shape d×n and we will call this X from now. Covariance Matrix We assume a centered dataset. C∈Rd×d Outer-product form C=1

nn∑i=1xixTi Matrix-form C=1

nXXT Scalar form Cpq=1

nn∑i=1xipxiq Cpp=1

nn∑i=1x2ip Projection of x onto unit vector w (xTw)w Scalar Projection of x onto unit vector w xTw Error vector for one data-point e=x-(xTw)w Reconstruction error for one data-point ||e||2=||x-(xTw)w||2 Reconstruction error for the entire dataset 1

nn∑i=1||xi-(xTiw)w||2 Error Minimization

min

w||w||=1 1

nn∑i=1||xi-(xTiw)w||2 is the same as

min

w||w||=1 1

nn∑i=1||xi||2-(xTiw)2 Variance of dataset along w 1

nn∑i=1(xTiw)2 is the same as wTCw Variance Maximization

max

w||w||=1 1

nn∑i=1(xTiw)2 is the same as

max

w||w||=1 wTCw First Principal Component a

max w||w||=1 wTCw	=𝜆1
argmax w||w||=1 wTCw	=w1

ith Principal Component a

max w||w||=1wTw1=0,⋯,wTwi-1=0 wTCw	=𝜆i
argmax w||w||=1wTw1=0,⋯,wTwi-1=0 wTCw	=wi

Projection of xi on subspace spanned by top-k PCs. (xTiw1)w1+⋯+(xTiwk)wk Principal component matrix W∈Rd×k W=a

|		|
w1	⋯	wk
|		|

Dimensionality reduced dataset X′∈Rk×n X′=WTX Compression ratio for dimensionality reduction Defined as new/old: nk

nd=k

d Reconstruction in Rd X′∈Rd×n X′=WWTX Reconstruction error 1

nn∑i=1aaxi-k∑j=1(xTiwj)wjaa2 Compression ratio for reconstruction in Rd Defined as new/old: k(n+d)

nd=k

d+k

n Total variance 𝜆1+⋯+𝜆d Choice of k, % variance captured 𝜆1+⋯+𝜆k

𝜆1+⋯+𝜆d⩾0.95