PCA

PCA is to find the dominant directions of the point cloud

Applications:

• Dimensionality reduction
• Surface normal estimation
• Canonical orientation
• Keypoint detection
• Feature description

Physical intuitions:

• Vector Dot Product
  
• Matrix-Vector Multiplication
  
• Singular Value Decomposition (SVD)
  

Spectral Theorem:

$A = U{\Lambda}U^T=\sum_{i=1}^n\lambda_iu_iu^T_i,\Lambda=diag(\lambda_1,\cdots,\lambda_n)$A=UΛUT=i=1∑n​λi​ui​uiT​,Λ=diag(λ1​,⋯,λn​)

Rayleigh Quotients:

$\lambda_{min}(A)\le\frac{x^TAx}{x^Tx}\le\lambda_{max}(A),\forall{x}\ne0$λmin​(A)≤xTxxTAx​≤λmax​(A),∀x​=0

Summary:

1. Normalized by the center:
   $\tilde{X}=[\tilde{x}_1,\cdots,\tilde{x}_m],\tilde{x}_i=x_i-\overline{x}$X~=[x~1​,⋯,x~m​],x~i​=xi​−x
2. Compute SVD:
   $H=\tilde{X}\tilde{X}^T=U_r{\Sigma^2}U_r^T$H=X~X~T=Ur​Σ2UrT​
3. The principle vectors are the columns of U_r (Eigenvector of $X$X= Eigenvector of $H$H)

KPCA

$\tilde{H}\tilde{z}=\tilde{\lambda}\tilde{z} \rightarrow \tilde{z}=\sum^N_{j=1}\alpha_j\phi(x_j) \rightarrow K\alpha=\lambda\alpha$H~z~=λ~z~→z~=j=1∑N​αj​ϕ(xj​)→Kα=λα
The normalization of $\tilde{z}$z~:
$\alpha_r^T\lambda_r\alpha_r=1 \rightarrow \alpha_r=1/\lambda_r$αrT​λr​αr​=1→αr​=1/λr​

Kernel:

• Linear $k(x_i,x_j)=x_i^Tx_j$k(xi​,xj​)=xiT​xj​
• Polynomial $k(x_i,x_j)=(1+x_i^Tx_j)^p$k(xi​,xj​)=(1+xiT​xj​)p
• Gaussian $k(x_i,x_j)=e^{-\beta{||x_i-x_j||_2}}$k(xi​,xj​)=e−β∣∣xi​−xj​∣∣2​
• Laplacian $k(x_i,x_j)=e^{-\beta{||x_i-x_j||_1}}$k(xi​,xj​)=e−β∣∣xi​−xj​∣∣1​

Summary

1. Select a kernel $k(x_i,x_j)$k(xi​,xj​),compute the Gram matrix $K(i,j)=k(x_i,x_j)$K(i,j)=k(xi​,xj​)
2. Normalize $K$K:
   $\tilde{K}=K-2\textbf{II}_{\frac{1}{N}}K+\textbf{II}_{\frac{1}{N}}K\textbf{II}_{\frac{1}{N}}$K~=K−2IIN1​​K+IIN1​​KIIN1​​
3. Solve the eigenvector/eigenvalues of $\tilde{K}$K~:
   $\tilde{K}\alpha_r=\lambda_r\alpha_r$K~αr​=λr​αr​
4. Normalize $\alpha_r$αr​ to be $\alpha_r^T\alpha_r=\frac{1}{\lambda_r}$αrT​αr​=λr​1​
5. For any data point $x\in{R^n}$x∈Rn, compute its projection onto $r^{th}$rth principle component $y_r\in{R}$yr​∈R:
   $y_r=\phi^T(x)\tilde{z}_r=\sum^N_{j=1}\alpha_{rj}k(x,x_j)$yr​=ϕT(x)z~r​=j=1∑N​αrj​k(x,xj​)