Fast and sample efficient algorithms for the sparse Fourier transform
Event details
| Date | 22.07.2016 |
| Hour | 14:00 › 16:00 |
| Speaker | Amir Zandieh |
| Location | |
| Category | Conferences - Seminars |
EDIC Candidacy Exam
Exam President: Prof. Ola Svensson
Thesis Director: Prof. Mikhail Kapralov
Co-examiner: Prof. Volkan Cevher
Background papers:
Nearly Optimal Sparse Fourier Transform, by H. Hassanieh, P. Indyk, D. Katabi, E. Price.
The Restricted Isometry Property of Subsampled Fourier Matrices, by I. Haviv, O. Regev.
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices, by A. Moitra.
Abstract
The Fourier transform appears in many theoretical,
algorithmic, and practical problems. It has a wide range of
applications in digital and analog signal processing. Although
most of the signals in real world are continuous, because
processing tools are all digital, they have to be converted to
digital eventually. Once a signal is digitized, we need fast
algorithms for computing its Fourier transform. Fortunately, in
many applications signals are also sparse and this enables us to
compute sparse Fourier transform in sub-linear time. We review
the techniques and algorithms for doing so. The sparsity leverage,
also enables accurate reconstruction of the signals from a very
limited number of measurements. It reduces the cost of analog to
digital conversion considerably. The techniques for such sample
efficient signal acquisition, which are known as “compressed
sensing”, rely on the restricted isometry property (RIP) of the
sensing matrix. We explain this property and represent one of
the best known result on the RIP of Fourier sensing matrices.
The procedure of sampling analog signals works very nicely
when the hardware is able to sample at a sufficient rate, i.e., the
gap between two consecutive samples are small enough. But there
are some cases where we want to extract structure of a sparse
continuous signal from coarse grained measurements (because
of some physical limitations). This problem is known as ”Super
resolution”. In these cases the digitized signal is not sparse even
though the analog signal is such and we need to develop different
techniques.
Exam President: Prof. Ola Svensson
Thesis Director: Prof. Mikhail Kapralov
Co-examiner: Prof. Volkan Cevher
Background papers:
Nearly Optimal Sparse Fourier Transform, by H. Hassanieh, P. Indyk, D. Katabi, E. Price.
The Restricted Isometry Property of Subsampled Fourier Matrices, by I. Haviv, O. Regev.
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices, by A. Moitra.
Abstract
The Fourier transform appears in many theoretical,
algorithmic, and practical problems. It has a wide range of
applications in digital and analog signal processing. Although
most of the signals in real world are continuous, because
processing tools are all digital, they have to be converted to
digital eventually. Once a signal is digitized, we need fast
algorithms for computing its Fourier transform. Fortunately, in
many applications signals are also sparse and this enables us to
compute sparse Fourier transform in sub-linear time. We review
the techniques and algorithms for doing so. The sparsity leverage,
also enables accurate reconstruction of the signals from a very
limited number of measurements. It reduces the cost of analog to
digital conversion considerably. The techniques for such sample
efficient signal acquisition, which are known as “compressed
sensing”, rely on the restricted isometry property (RIP) of the
sensing matrix. We explain this property and represent one of
the best known result on the RIP of Fourier sensing matrices.
The procedure of sampling analog signals works very nicely
when the hardware is able to sample at a sufficient rate, i.e., the
gap between two consecutive samples are small enough. But there
are some cases where we want to extract structure of a sparse
continuous signal from coarse grained measurements (because
of some physical limitations). This problem is known as ”Super
resolution”. In these cases the digitized signal is not sparse even
though the analog signal is such and we need to develop different
techniques.
Practical information
- General public
- Free
Contact
- Cecilia Chapuis EDIC