Source author record

M. A. Iwen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

3works
5topics
2close collaborators

Published work

3 publications

preprint2013arXiv

Compressed Sensing with Sparse Binary Matrices: Instance Optimal Error Guarantees in Near-Optimal Time

A compressed sensing method consists of a rectangular measurement matrix, $M \in \mathbbm{R}^{m \times N}$ with m≪Nm \ll N, together with an associated recovery algorithm, $\mathcal{A}: \mathbbm{R}^m \rightarrow \mathbbm{R}^N$. Compressed sensing methods aim to construct a high quality approximation to any given input vector ${\bf x} \in \mathbbm{R}^N$ using only $M {\bf x} \in \mathbbm{R}^m$ as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for MM and A\mathcal{A} of the form ∥x−A(Mx)∥p≤∥x−xkopt∥p+Ck1/p−1/q∥x−xkopt∥q \| {\bf x} - \mathcal{A} (M {\bf x}) \|_p \leq \| {\bf x} - {\bf x}^{\rm opt}_k \|_p + C k^{1/p - 1/q} \| {\bf x} - {\bf x}^{\rm opt}_k \|_q for ${\bf x} \in \mathbbm{R}^N$, where xkopt{\bf x}^{\rm opt}_k is the best possible kk-term approximation to x{\bf x}. In this paper we develop a compressed sensing method whose associated recovery algorithm, A\mathcal{A}, runs in O((klog⁡k)log⁡N)O((k \log k) \log N)-time, matching a lower bound up to a O(log⁡k)O(\log k) factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for high-volume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein.

preprint2011arXiv

On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions

We present a general class of compressed sensing matrices which are then demonstrated to have associated sublinear-time sparse approximation algorithms. We then develop methods for constructing specialized matrices from this class which are sparse when multiplied with a discrete Fourier transform matrix. Ultimately, these considerations improve previous sampling requirements for deterministic sparse Fourier transform methods.

preprint2010arXiv

Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms

In this paper modified variants of the sparse Fourier transform algorithms from [14] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, f:[0,2pi]−>C,inO(k2⋅D4)f : [0, 2 pi] -> C, in O(k^2 \cdot D^4) time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.