
Date: 1718 February, 2013
Location: MIT
Program:
Sunday, Feb 17 : Tutorials
Location: Media Lab, 6th floor (Map)
• 2:00  3:15 pm  Basic Fourier Analysis [Notes]  Anna Gilbert (U Michigan) 
• 3:15  3:30 pm  Break  
• 3:30  4:45 pm  Algorithms for Sparse Fourier Transform [Slides]  Mark Iwen (Duke) 
• 4:45  5:00 pm  Break  
• 5:00  6:15 pm  Sparsity and Computational Photography [Slides] [Slides2]  Ramesh Raskar (MIT) 
• 6:15  7:15 pm  Reception + Posters  
Monday, Feb 18 : Talks
Location: Stata Center, D463 Star (Map)
• 9:30  11:10 am 
+ Average Case Sparse Fourier Transform Algorithms [Slides]
Abstract:
We present the first sampleoptimal sublinear time
algorithms for the sparse Discrete Fourier Transform
over a twodimensional \sqrt{n} \times \sqrt{n} grid.
Our algorithms are analyzed for the average case
signals. For signals whose spectrum is exactly sparse,
our algorithms use O(k) samples and run in O(k \log k) time,
where k is the expected sparsity of the signal.
For signals whose spectrum is approximately sparse,
our algorithm uses O(k \log n) samples and runs in O(k \log^2 n) time; the
latter algorithm works for k=\Theta(\sqrt{n}). The number of samples used by
our algorithms matches the known lower bounds for the respective signal models.
 Piotr Indyk (MIT)
 
+ Sparse Fourier Transform Algorithms [Slides]
Abstract:
I will give a brief overview of an algorithm achieving approximate
ksparse Fourier transforms with O(k log (n/k) log n) time and
measurements. The talk will emphasize the design and use of an error
correcting code that allows both noise tolerance and efficient
recovery.
 Eric Price (MIT)
 
+ The Sparse FFT: from Theory to Practice [Slides]
Abstract:
sFFT application to spectrum sensing, medical imaging, and computational photography
 Dina Katabi (MIT)
 
+ Faster GPS via the Sparse Fourier Transform [Slides]
Abstract: GPS is one of the most widely used wireless systems. A GPS receiver
has to lock on the satellite signals to calculate its position.
The process of locking on the satellites is quite costly and requires
hundreds of millions of hardware multiplications, leading to high
power consumption. The fastest known algorithm for this problem
is based on the Fourier transform and has a complexity of
O(n log n), where n is the number of signal samples.
This talk presents the fastest GPS locking algorithm to date.
The algorithm reduces the locking complexity to O(n \sqrt(log n)). Further,
if the SNR is above a threshold, the algorithm becomes linear,
i.e., O(n). Our algorithm builds on recent developments in the
growing area of sparse recovery. It exploits the sparse nature of
the synchronization problem, where only the correct alignment between
the received GPS signal and the satellite code causes their
crosscorrelation to spike.
 Haitham Hassanieh (MIT)

• 11:10  11:40 am  Break 
• 11:40  12:55 pm 
+ Matrix Pencil Methods for Sparse Fourier Transform [Slides]
Abstract: I will present a modification of the binbased sparse FFT
algorithm of Hassanieh et al. that involves the matrix pencil  a
robust version of Prony's method  for the frequency identification
step. This refinement offers a way to keep the complexity a O(k) up to
logN factors, while making the algorithm stable to noise. The
resulting algorithm is competitive in practice.
 Laurent Demanet (MIT)
 
+ What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid [Slides]
 Yi Li (U Michigan)
 
+ Sparse Methods in Array Processing [Slides]
Abstract: We examine the application of sparse methods in array processing. Array
processing systems typically observe scenes with very few targets of interest
relatively to the size of the scene. Thus spatial sparsity can be exploited in
the design and processing for such systems. After introducing and setting up
the general array acquisition problem, we formulate the special case of linear
arrays. We demonstrate that this formulation results in a sparse Fourier
sampling problem, amenable to all the techniques available for such problems.
While passive arrays can only resolve the direction of signal sources in the
scene, we also examine active arrays, which further enable depth resolution.
For such systems we demonstrate that modelbased compressive sensing can
further improve the performance of the system.
 Petros Boufounos (MERL)

• 12:55  2:00 pm  Lunch 
• 2:00  2:50 pm 
+ Convex Approach for Learning NearIsometric Linear Embeddings [Slides]
 Chinmay Hegde (MIT)
 
+ FPGABased Design of a Million Point Sparse FFT [Slides]
Abstract: In this talk, we describe our efforts to build a highthroughput and
lowpower hardware implementation of the Sparse FFT algorithm targeted for FPGAs.
This implementation targets processing a new million point input every
millisecond, generating the location and values of the top 500 frequencies
in the sparse input, while having a power constraint of 12 W. The chosen
FPGA platform is the Xilinx ML605 with a Virtex6 FPGA. Design of major
computational blocks used in SFFT will be discussed in detail, exploring
performance and resource consumption implications.
 Abhinav Agarwal (MIT)

• 2:50  3:00 pm  Break  
• 3:00  4:15 pm 
+ New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows [Slides]
Abstract:
Many offtheshelf algorithms for compressed sensing,
like linear programming, rely on the compressed sensing
matrix satisfying a sufficient condition called the "Restricted
Isometry Property" (RIP). These algorithms also run faster if
the compressed sensing matrix supports fast matrixvector
multiplicationfor example, if it consists of random rows of
a DFT. However, showing that the Fourier ensemble has the RIP
with an optimal number of measurements appears to be a very difficult
problem. In this talk, I will present some progress: we show that a
matrix whose rows are sparse linear combinations of Fourier measurements
has the RIP with fewer rows than previous constructions. Our results
give RIP matrices supporting fast multiplication with fewer rows
than previously known, and also imply improved fast JohnsonLindenstrauss
transforms. (This is joint work with Jelani Nelson and Eric Price.)
 Mary Wooters (UMichigan)
 
+ Modal Analysis with Compressive Measurements
 Jae Young Park (UMichigan)
 
+ Spectral Compressive Sensing [Slides]
 Marco Duarte (UMASS)

• 4:15  4:25 pm  Break  
• 4:25  5:00 pm  Discussion / Open Problems Session  
Organizers: Anna Gilbert (U Michigan), Piotr Indyk (MIT), Dina Katabi (MIT), Ramesh Raskar (MIT).

