Research Interests

The discrete Fourier transform is a mathematical algorithm which has numerous applications in computational mathematics and engineering. For example, it can be used to quickly multiply two polynomials, to help solve partial differential equations numerically, and to compress digital images. In signal processing and engineering its use is even more widespread. One would be hard-pressed to make a cellphone call or log on to a wireless network without it. Over the past several years I have been investigating generalized discrete Fourier transform algorithms which improve the speed of standard discrete Fourier transform algorithms (e.g., the Fast Fourier Transform, or FFT) for an important class of functions which appears in many of the applications mentioned above.

In classical Fourier analysis and related signal processing applications the emphasis has generally been on analyzing relatively smooth "band-limited" functions that are primarily composed of a small number of the lowest-possible frequency components. For periodic signals this generally means that the functions are well approximated by a small weighted sum of the lowest-possible integer-frequency sine and cosine functions (e.g., cos(x), cos(-x), cos(2x), etc.). Over the past few years I have been studying a generalization of this situation. Mainly, the approximation of functions which are well approximated by a weighted sum of a small number of sine and cosine functions with unknown, arbitrary integer frequencies. These functions are referred to as "frequency-sparse functions" because they have a relatively small number of large Fourier coefficients scattered over a very large range of frequencies. Fourier transform algorithms that are faster than the FFT for such frequency-sparse functions are known as "sparse Fourier transforms".

Some selected publications in this area include:

1. M. A. Iwen,
   Combinatorial Sublinear-Time Fourier Algorithms (.pdf),
   Foundations of Computational Mathematics, Vol. 10, Issue 3, pages 303 -- 338, 2010.
   
   Summary: This paper develops both randomized and deterministic Sparse Fourier Transform algorithms (SFTs) that are faster than standard FFT algorithms at approximating frequency-sparse functions. Several tradeoffs are also noted between the randomized and deterministic SFTs developed herein. Mainly, the randomized SFTs can approximate a given periodic function more quickly than their deterministic counterparts can, while simultaneously observing fewer samples from the function. However, the randomized methods fail to output an accurate approximation with some nonzero probability. The deterministic SFTs, on the other hand, always produce accurate results.
   
   
2. M. A. Iwen,
   Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms (.pdf),
   Applied and Computational Harmonic Analysis, to appear.
   
   Summary: This paper develops stronger error guarantees for variants of the sparse Fourier transforms developed above. Furthermore, it extends these Fourier algorithms to address the problem of quickly approximating a function of many variables using only a few function evaluations. The end result is a set of robust algorithms for estimating frequency-sparse functions of many variables without suffering from the curse of dimensionality.
   
   
3. I.B. Segal^* & M.A. Iwen,
   Improved Sparse Fourier Approximation Results: Faster Implementations and Stronger Guarantees (.pdf),
   Numerical Algorithms, to appear. ^*Undergraduate Student
   
   Summary: This paper introduces new implementations of the sparse Fourier transform algorithms considered above which are then empirically demonstrated to be faster than previous SFT implementations, as well as a highly optimized FFT implementation (FFTW), for frequency-sparse functions. In addition, a hybrid SFT algorithm is developed which combines the superior sampling complexity of the randomized SFTs considered in the first paper above with the guaranteed accuracy of deterministic SFTs.



---



Run time of several SFTs compared with a standard FFT (FFTW) for frequency-sparse functions. The vertical axis is run time. The horizontal axis is the number of sine and cosine functions needed in order to accurately approximate the tested frequency-sparse functions. The absolute value of all frequencies is bounded above by 2²². The run time of FFTW is graphed as the horizontal dotted cyan line. The fastest SFT implementation was introduced in the paper immediately above (i.e., see the yellow dashed line).

---

Compressed sensing methods deal with the approximation of vectors that can be sparsely represented as a sum of a small number of columns from a given dictionary matrix. Such "dictionary-sparse" vectors can be compactly stored in a compressed form that is easy to transmit and store. Moreover, they can be recovered from their compressed representations when necessary. This compression/recovery problem has been well studied when the vector, x, is available in its entirety before compression. However, in situations where the vector is costly to observe, one may only have the ability to collect a very small set of linear measurements of x to begin with, thus rendering standard compression techniques impractical. This is the compressed sensing regime, where lossless compression must occur before one determines which dictionary components (or transform coefficients) are actually important. Hence, the goal of compressed sensing becomes to design a rectangular measurement matrix, M, with as few rows as possible, together with an accompanying algorithm capable of uniquely inverting Mx for all sufficiently dictionary-sparse x.

Compressed sensing methods are related to many other signal processing and computer science applications involving error correction and approximation. One such application involves the observation of a high-volume data stream which is too massive to store (e.g., all IP addresses processed by an internet service provider). In such cases it is important to utilize as little computer memory and runtime as possible while still maintaining the ability to accurately monitor important characteristics of the data stream (e.g., the most popular websites from minute to minute). Over the past couple years I have been working on developing compressed sensing algorithms which are as fast and memory efficient as possible. Such compressed sensing methods naturally provide a means of compactly sketching massive data streams while simultaneously maintaining one's ability to quickly recover important data elements as desired.

Some selected publications in this area include:

1. M. A. Iwen & A. H. Tewfik,
   Adaptive Strategies for Target Detection and Localization in Noisy Environments (.pdf),
   IEEE Transactions on Signal Processing, Vol. 60, Issue 5, pages 2344 -- 2353, 2012.
   
   Summary: This paper explores the recovery of sparse vectors whose entries are each contaminated with additive noise that varies from observation to observation. Given this model, the paper develops lower bounds for the number of nonadaptive linear measurements required by any algorithm in order to recover an arbitrary sparse vector with high probability. An adaptive compressed sensing strategy is then developed which uses fewer linear measurements than the number required by any nonadaptive scheme. As a result, adaptive methods are shown to be superior, in general, to nonadaptive compressed sensing methods for the given model.
   
   
2. J. Bailey^*, M. A. Iwen, and C. V. Spencer,
   On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions (.pdf),
   SIAM J. Matrix Anal. Appl., Vol. 33, No. 1, pages 263 -- 289, 2012. ^*Undergraduate Student
   
   Summary: This paper relates the design of sampling sets for sparse Fourier transforms to the design of compressed sensing matrices, nonadaptive group testing procedures, codebooks in signal processing, unbalanced expander graphs, and discrete uncertainty principles. These relationships are then exploited in order to help generalize existing deterministic SFT methods into a related class of fast and deterministic compressed sensing methods. The optimality of these deterministic compressed sensing methods is also explored.
   
   
3. M. A. Iwen,
   Nonadaptive Compressed Sensing with Binary Matrices: Instance Optimal Error Guarantees in Near-Optimal Time (.pdf),
   Submitted, 2012.
   
   Summary: This paper presents a general method for developing randomized compressed sensing/sketching algorithms that have near-optimal space and run time complexities. The fastest such algorithm is a single log-factor above a lower-bound on the necessary runtime complexity.

Many high-dimensional data sets encountered in practice exhibit much lower intrinsic dimensionality (i.e., they are ``simpler than they appear''). Examples of such data sets include certain image data sets, collections of handwritten text/digits, and some types text documents. Over the past couple years I have begun to work on computational methods for the analysis of high-dimensional data sets which exploit existing low dimensional structure. The low dimensional structure is often represented by assuming that the data can be approximated well by a low-dimensional manifold (e.g., that every element of data set corresponds to a point on a low dimensional surface in higher n-dimensional space). Taking advantage of such intrinsic low dimensionality allows one to study massive high-dimensional data sets which are otherwise difficult to analyze.

Some selected publications in this area include:

1. Guangliang Chen, Mark Iwen, Sang Chin, and Mauro Maggioni,
   A Fast Multiscale Framework for Data in High-Dimensions: Measure Estimation, Anomaly Detection, and Compressive Measurements (.pdf),
   Visual Comm. and Image Proc. (VCIP), 2012.
   
   Summary: This paper presents an algorithm for approximating the geometric structure of a given high-dimensional probability density using as few observed samples as possible. Approximation theoretic bounds are given which characterize the quality of the resulting estimate for certain types of intrinsically low-dimensional densities. Several applications are also considered, including the detection of anomalous data that is unlikely to have been sampled from the same density that is responsible for generating most of the high-dimensional data set.
   
   

---



An example two-dimensional manifold which is evolving in time (i.e., by "growing a bump"). The anomalous bump points (in blue) can be identified quickly by paying attention to their distances from well chosen tangent planes of the manifold.

---

2. M. A. Iwen & Mauro Maggioni,
   Approximation of Points on Low-Dimensional Manifolds via Random Linear Projections (.pdf),
   Information and Inference: A Journal of the IMA, to appear.
   
   Summary: This paper proves that compact d-dimensional submanifolds of D-dimensional Euclidean space can be embedded into O(d log(d))-dimensional Euclidean space almost isometrically (i.e., in a way which preserves their local geometry). Hence, it is shown that one can "compress" such manifolds down into a "smaller space", whose dimension is independent of their extrinsic dimensionality D, without loosing much information. This fact is then utilized in order to construct a compressed sensing recovery algorithm for data sets that are well approximated by a low-dimensional manifold.

Many signal processing applications involve inverse problems where the unknowns are "words" (e.g., codes). Inverse problems of this type generally occur when one must correctly infer a given code word despite only having access to a noisy and distorted version of it. One example of such a problem involves decoding a product bar code using only a blurred and noisy laser scan of the original (e.g., the way your purchases are priced when you check out at the grocery store). I have recently begun considering applications consisting of such decoding problems.

Some selected publications in this area include:

1. M. A. Iwen, Fadil Santosa, and Rachel Ward,
   A Symbol-based Bar Code Decoding Algorithm (.pdf),
   SIAM Journal on Imaging Sciences, to appear.
   
   Summary: This paper develops a bar coding decoding algorithm for UPC (and other related) bar codes. Both theoretical and empirical results demonstrate that the method is tolerant to high levels of noise and blur. This new method is of potential value for industrial applications where bar code scans are highly noisy/distorted.



---



An example bar code decoding problem. The laser scanner returns a blurred and noisy data version of the underlying bar code (top graph). Given this measured data, one must correctly decode the underlying bar code (bottom graph).

---