Instructor: Barna Saha Office: CS 322. Office phone: (413) 5772510. Email: barna@cs.umass.edu.
Office Hours: By appointment.
Class Time: Currently Scheduled for Fri 2:303:30pm. CS 140.
Course Overview: Big Data brings us to interesting times and promises to revolutionize our society from business to government, from healthcare to academia. As we walk through this digitized age of exploded data, there is an increasing demand to develop unified toolkits for data processing and analysis. In this course our goal is two fold, (i) to study a subset of topics that build the mathematical foundation of big data processing, and (ii) to learn about applications of big data in important domains of interest. For the former, our plan is to concentrate on the following three topics.
Course Work:
This is a one credit seminar course covering several papers and course notes on the topics listed above. Each student will be assigned 1 paper/lecture note before the beginning of the semester which they will present in the class.
The presentation of theory paper needs to be indepth (preferably board presentation) covering the detailed proofs of main theorems and lemmas. Assignment of presentation topic to students will be
based on firstcomefirstserved basis.
Prerequisites: The students are expected to have strong mathematical foundations, must have basic knowledge of algorithms and probability, and should be able to read and understand papers appearing in top theoretical computer science conferences. Senior undergraduate students meeting these requirements are encouraged to take this course.
Class  Paper to be presented  References 

Jan 23rd  Introduction to Fourier Sampling, kSparse Fourier Sampling
Lecture 1 MIT 6.893 Lecture 2 MIT 6.893 
Survey on Sparse Fourier Transofrm
Paper1 Paper2 Paper3 
Jan 30th  Average case O(klog(n)) algorithm for Sparse Fourier Transform
Lecture 3 MIT 6.893 

Feb 6th  O(k log n) algorithm for worst case ksparse signals.
Lecture 4 MIT 6.893 Lecture 5 MIT 6.893 

Feb 13th  Applications: Network Evolution via Spectral Analysis
Reading 1a Reading 1b TimeFrequency Analysis of Biomedical Signal Reading 2a Presentation 2b 

Feb 20th  Recap: buffer class  
Feb 27th  Intro to Embedding, Metric Methods in Algorithms
Lecture 1 Lecture 2 
Lecture Notes from Algorithmic Applications of Metric Embeddings class at CMU

Mar 6th  Embeddings into l_{infinity}
Lecture 3 

Mar 13th  Embeddings into l_{p} spaces.
Lecture 4 

Mar 20th  No ClassSpring Recess  
Mar 27th  Embedding into tree distribution
Lecture 5 Lecture 6 

Apr 3rd  Applications
Reading1 Reading2 
Complex Networks and Hidden Metric Space 
Apr 10th  No Class due to travel, Substitute class date will be declared later.  
Substitute Class, Date TBD  Recap: buffer class  
Apr 17th  Intro to Convex Optimization, Gradient Descent
Reading1 Reading2 
Large Scale Optimization Course at UTexas
Nonlinear Programming Course at MIT, Lecture 1 to 4 
Apr 24th  Gradient Descent Continued
Reading3 