Private:progress-dameh

Summer 2011 (TA)

• Research: Gram Matrix approximation

May 5

• Recap
  • Problem: kernel methods' gram matrix is O(N^2), which is computationally and memory usage infeasible for large-scale datasets
  • Previous Work:
    • Low rank matrix approximation:
      • using EigenDecomposition: Optimal solution
        • Problem: requires O(N^3) computation to construct the low rank matrix
        • Solution: use Nytsrom theorem to approximate the EigenDecomposition of the matrix which requires O(m^2N) where m << N.
        • Problem: In this methods in despite of reducing the computation complexity still we need O(N^2) to store the matrix, so the next methods reduce both computation and memory.
    • Efficient implementation for computing the kernel matrix:
      • Using Spatial Indexing:
        • using Z-order, H-order, kd-tress and other spatial indexing techniques to order the points in the space and then using sliding window where the kernel function computed only between points in that window.
        • Problems: requires O(NlogN) as preprocessing to order the points, fails for very high dimensional Data and hard to parallel
        • Solution: We proposed a method that works fine for large-scale and highly dimensional data that overcomes all pervious works drawbacks, easy to parallel, requires linear time preprocessing and reduce both computation and memory usage down form quadratic to subquadratic:
      • Using Spatial Hashing or Locality sensitive hashing: where the kernel function and the cluster methods works on the buckets individually.
        • LSH families :
          • Random projection:
            • Hamming distance, Euclidean Distance, Cosine Distance
            • Problem for random projection, assume data uniformly distrubuted and it doesn’t take in account if data are in a kernel space, Solution:
          • Spectral Hashing: overcomes previous families problems
          • Kernelized LSH : Problem: more complex to compute
  • In progress: Comparing different LSH families

Spring 2011 (TA/RA)

• Courses:
  • CMPT 885: Special Topics in Computer Architecture
  • CMPT 886: Special Topics in Operating Systems

Fall 2010 (FAS-GF/RA)

• Courses:
  • CMPT 705: Design/Analysis Algorithms
  • CMPT 820: Multimedia Systems

• Worked on Gram matrix approximation, High Performance/large scale application case studies

Summer 2010 (TA)

• Worked on large Scale Kernel methods

Spring 2010 (RA)

• Courses:
  • CMPT 768: Sound Synthesis

• Worked on Locality sensitive hashing families and their applications and implementations