Private:progress-dameh

Summer 2011 (TA)

• Research: Gram Matrix approximation
  • Recap:
    • Problem: kerenl methods gram matrix is $O(N^2)$, which is computational and memory usage infiseable for large-scale datasets
    • Prevoius Work:
      • Low rank matrix approximation:
        • using EginDecomposition: Optimal solution but reqiures <math>O(N^3)</math> computation to constuct the low rank matix
        • Solution: use Nysrom therorem to approximate the eigen decomposition of the matrix which reqiures <math>O(m^2N)</math> where m << N.

• • • • • Problem: In this methods in despite of reduce the computation complexity still we need <math>O(N^2)</math> to store the matrix, so the next method reduce both computation and memory.

• • • • Efficient implementation for computing the kernel matrix:
        • Using Spatial Indexing:

using Z-order, H-order, Td-tress and other spatial indexing techniques to order the points in the space and then use sliding window where the kernel function computed only between points in that wiondow.

• • • • • • Problems: reqiures <math>O(NlogN)</math> as preprocessing to order the points, fails for very hight dimentional Data and hard to parallel

So we proposed a method that works fine foy large-scale and highly dimentinla data, overcome or pervoius work drwobbacks, easy to parallel, reqiures linear time preprocessing and reduce the computation and memory usae down form quadratic to subquadratic:

• • • • • Using Spatial Hashing or Locality sensitive hashing:

where the kerenl function and the cluster methods works on the buckets indicusally.

• • • • • • LSH families :
            • Random projection
              • Hamming distance
              • Eclidean Distance
              • Cosine Distance
                • Problem: assumes data uniforly distubuted solution:
              • Spectral Hasing

General Problem for random projection, it' doesnt take care of data comes in a kerenel space, Solution

• • • • • • • Kerenalized LSH

• • Recap: Comparing differnt 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