Lecture 3: Mathematical Preliminaries

Lecture 3: Mathematical Preliminaries

Projects (한동수 교수님과 컨텍할 주제. )

  1. Network tomography
  2. Cloud service에서 private data를 어떻게 보호할 것인가.
    SMPC
    big data analysis의 결과에 영향을 주지 않을 만큼 작지만 private data를 노출시키지 않을 만큼 큰 noise로 private data를 distort하여 private data를 보호할 수 있는 상화은 없을까?

Algorithm (30%) + Machine learning or data mining (40%) + Data Parallelism (30%)

Matrix rank: column rank == row rank

Eigen values and Eigenvectors

  • Av = λv
  • det(A-λI) = 0
  • Hence, there are n λs

Matrix Decomposition

  • Rank Factorization
  • Singular value decomposition
  • Algorithms: 언제든 O(max{m,n}^3)의 decomposition algorithm을 찾을 수 있다.
  • Most matrix decomposition are in P

Machine learning: Build a system trainable from data (왜냐면 machine이 빠르니까)

P vs. NP

  • P: A computer can find the solution in polynomial running time with respect to the size of input data
  • NP: A computer can verify the solution in polynomial running time with respect to the size of input data
  • P = NP ?

Convex optimization: Example of P

  • Minimize F(x) subject to x ∈ D ⊆ Dn (n차원 space에서 Convex function의 minimum value를 찾는 것.
  • Function F is convex if (F(x) + F(y))/2 >= F((x+y)/2)
  • Set D is convex if (x+y)/2 ∈ D when x, y ∈ D
  • Linear Programming
  • Semidefinite Programming
  • Gradient Descent Algorithm: xt+1 = x_t – _t∇F(x_t)
  • Lagrange functions

 

Leave a Reply