Home

Mark A. Davenport

  1. Compressive binary search.

    Tue, 02/07/2012 - 15:01 — SomNambul
    Authors: Mark A. Davenport, Ery Arias-Castro
    Subjects: Information Theory
    Abstract

    In this paper we consider the problem of locating a nonzero entry in a
    high-dimensional vector from possibly adaptive linear measurements. We consider
    a recursive bisection method which we dub the compressive binary search and
    show that it improves on what any nonadaptive method can achieve. We establish
    a non-asymptotic bound that applies to all methods, regardless of their
    computational complexity. Combined, these results show that the compressive
    binary search is within a double logarithmic factor of the optimal performance.

  2. How well can we estimate a sparse vector?.

    Fri, 04/29/2011 - 15:01 — SomNambul
    Authors: Emmanuel J. Candès, Mark A. Davenport
    Subjects: Information Theory
    Abstract

    The estimation of a sparse vector in the linear model is a fundamental
    problem in signal processing, statistics, and compressive sensing. This paper
    establishes a lower bound on the mean-squared error, which holds regardless of
    the sensing/design matrix being used and regardless of the estimation
    procedure. This lower bound very nearly matches the known upper bound one gets
    by taking a random projection of the sparse vector followed by an $\ell_1$
    estimation procedure such as the Dantzig selector. In this sense, compressive
    sensing techniques cannot essentially be improved.

  3. The Pros and Cons of Compressive Sensing for Wideband Signal Acquisition: Noise Folding vs. Dynamic Range.

    Wed, 04/27/2011 - 15:01 — SomNambul
    Authors: Mark A. Davenport, Jason N. Laska, Richard G. Baraniuk, John R. Treichler
    Subjects: Information Theory
    Abstract

    Compressive sensing (CS) exploits the sparsity present in many common signals
    to reduce the number of measurements needed for digital acquisition. With this
    reduction would come, in theory, commensurate reductions in the size, weight,
    power consumption, and/or monetary cost of both signal sensors and any
    associated communication links. This paper examines the use of CS in the design
    of a wideband radio receiver in a noisy environment. We formulate the problem
    statement for such a receiver and establish a reasonable set of requirements
    that a receiver should meet to be practically useful.

  4. A simple proof that random matrices are democratic.

    Thu, 11/05/2009 - 16:01 — SomNambul
    Authors: Mark A. Davenport, Jason N. Laska, Richard G. Baraniuk, Petros T. Boufounos
    Subjects: Numerical Analysis
    Abstract

    The recently introduced theory of compressive sensing (CS) enables the
    reconstruction of sparse or compressible signals from a small set of
    nonadaptive, linear measurements. If properly chosen, the number of
    measurements can be significantly smaller than the ambient dimension of the
    signal and yet preserve the significant signal information. Interestingly, it
    can be shown that random measurement schemes provide a near-optimal encoding in
    terms of the required number of measurements.

  5. Analysis of Orthogonal Matching Pursuit using the Restricted Isometry Property.

    Wed, 09/02/2009 - 12:02 — SomNambul
    Authors: Mark A. Davenport, Michael B. Wakin
    Subjects: Numerical Analysis
    Abstract

    Orthogonal Matching Pursuit (OMP) is the canonical greedy algorithm for
    sparse approximation. In this paper we demonstrate that the restricted isometry
    property (RIP) can be used for a very straightforward analysis of OMP. Our main
    conclusion is that the RIP of order $K+1$ (with isometry constant $\delta <
    \frac{1}{3\sqrt{K}}$) is sufficient for OMP to exactly recover any $K$-sparse
    signal. Our analysis relies on simple and intuitive observations about OMP and
    matrices which satisfy the RIP.

Math-arch

Syndicate content