February 25 & 26, 2009

Location: Duke University

Sponsored by the AFRL ATR Center

Co-sponsored by AFOSR, ARO, DARPA, NGA and ONR

This workshop brought together leading experts in the new field of compressive sensing (CS). The meeting focused on new theory, algorithms and applications of CS. In addition to having talks from many of the leading CS researchers from academia, there were talks from the members of the US government and industry, on directions for this new technology, including future research directions and programs.

The meeting was jointly organized by Lawrence Carin (Duke) and Gregory Arnold (AFRL), who are affiliated with the AFRL ATR Center in Dayton, Ohio.

The local Duke hosts for the workshop were Lawrence Carin, David Brady, Mauro Maggioni, Xiaobai Sun, and Rebecca Willet.

- [0900 - 0920] Ronald Coifman - Compressed Sensing, Intrinsic Variables and Diffusion Geometries (video)
- [0920 - 0940] Stanley Osher - Bregmanized Methods for Sparse Reconstruction and Restoration (video)
- [0940 - 1000] Rama Chellappa and Volkan Cevher - Applications of Compressed Sensing Concepts to Some Computer Vision Problems (video)
- [1000 - 1020] Guillermo Sapiro - Learning Sparse Representations to Restore, Classify and Sense Images & Video (video)

- [1100 - 1120] Martin Wainwright - Graphical Model Selection in High-dimensions: Trade-offs Between Computational and Statistical Efficiency (video)
- [1120 - 1140] Mario Figueiredo - Iterative Shrinkage/Thresholding Algorithms: Some History and Recent Development (video)
- [1140 - 1200] Lee Potter - Bayes to the Bone: Sparse Linear Regression with Limited Data (video)
- [1200 - 1220] Kevin Murphy - Learning Graph Structures with Unknown Blocks (video)

- [1400 - 1420] Robert Calderbank - Deterministic Compressive Sensing Matrices (video)
- [1420 - 1440] Rob Nowak - Distilled Sensing: The Power of Adaptivity (video)
- [1440 - 1500] Rick Chartrand - Fast Algorithms for Nonconvex Compressive Sensing (video)
- [1500 - 1520] Joel Tropp - Beyond Nyquist: Efficient Sampling of Sparse, Bandlimited Signals (video)

- [1600 - 1620] Michael Lustig - Frontiers in Rapid MRI: Parallel Imaging and Compressed Sensing (video)
- [1620 - 1640] Mark Neifeld - Adaptation for Task-Specific Compressive Sensing (video)
- [1640 - 1700] Kevin Kelly - Micromirror-based Compressive Imaging and Spectroscopy (video)
- [1700 - 1720] David Brady - Coding and Regularization in Optical Sensor Forward and Inverse Models (video)

- [0830 - 0850] Venkatesh Saligrama - Noisy Group Testing and Boolean Compressed Sensing (video)
- [0850 - 0910] Yonina Eldar - Beyond Nyquist: Compressed Sensing of Analog Signals (video)
- [0910 - 0930] Justin Romberg - Multiple Channel Estimation and Compressive Sensing (video)
- [0930 - 0950] Donald Goldfarb - Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization (video)

- [1030 - 1050] Wotao Yin - Enhanced Compressed Sensing Based on Iterative Support Detection (video)
- [1050 - 1110] Thomas Blumensath - Iterative Hard Thresholding: Theory and Practice (video)
- [1110 - 1130] Richard Baraniuk - Model-based Compressive Sensing (video)
- [1130 - 1150] Rebecca Willet - Compressed Sensing in Low-Light Imaging (video)

- [1330 - 1350] George Papanicolaou - Resolution and Robustness of Array Imaging Algorithms Viewed with Compressive Sensing in Mind (video)
- [1350 - 1410] Edward Bosch - Hyperspectral Imagery and Compressive Sensing
- [1410 - 1430] Myron Brown - LIDAR and Compressive Sensing
- [1430 - 1450] James McClellan - Compressive Sensing Data Acquisition and Imaging for GPR (video)

- [1530 - 1550] Mathias Seeger - Compressed Sensing for Medical Imaging (video)
- [1550 - 1610] Jian Li - On Sparse Bayesian Learning and Iterative Adaptive Approach (video)
- [1610 - 1630] David Wipf - Latent Variable Bayesian Models for Promoting Sparsity (video)
- [1630 - 1650] Lawrence Carin - Putting Compression into Compressive Sensing (video)

- Lam Nguyen - SAR Imaging Technique for Reduction of Sidelobes and Noise
- Ivana Stojanovic and W. Clem Karl - An Overcomplete Dictionary Approach to Imaging of Moving Targets with Multistatic SAR
- Lawrence Carin, Bin Guo, Dehong Liu, and Wenbin Lin - On Compressive Sensing for the Random Sensor Array Design
- Robert Muise - A Compressive Imaging Approach for Tracking Targets in Multiplexed Data
- Xuejun Liao, Hui Li, and Lawrence Carin - Fast Projections onto the Set of Sparse Signals
- Maxim Raginsky and Rebecca M. Willett - Minimax Risk Bounds for Poisson Compressed Sensing
- Kerkil Choi - Coded Aperture Compressive Computed Tomography
- Manqi Zhao, Venkatesh Saligrama - Thresholded Basis Pursuit: A Linear Programming Approach for Support Recovery
- Wotao Yin - Enhanced Compressed Sensing Based on Iterative Support Detection

- Aswin Sankaranarayanan - Fast Compressive Acquisition of Reflectance Fields
- Bin Dong, Eric Savitsky and Stanley Osher - A Novel Method for Enhanced Needle Localization Using Ultrasound-Guidance
- Christy Fernandez - Cull Image Segmentation with a Compressive Snapshot Spectral Imager
- David Mao - Equally-Sloped Tomographic Reconstruction and Its Application to Radiation Dose Reduction.
- Igal Bilik - Spatial Compressive Sensing Approach for Field Directionality Estimation Via Spatial Diversity.
- Jort F. Gemmeke - Missing Data Imputation for Noise Robust Speech Recognition Using Compressive Sensing
- Lorne Applebaum - Chirp Sensing and A/D Conversion
- Sina Jafarpour - Compressed Sensing Using High-quality Expander Graphs: Optimal Measurements, Efficient Recovery, Explicit Construction, and Noise Tolerance
- Tom Goldstein - Split Bregman Schemes for L1 Regularized Problems
- Vishal Patel - Compressive Synthetic Aperture Radar Imaging
- Weiyu Xu - The Balancedness Properties of Linear Subspaces and their Applications in Compressive Sensing
- Xing Tan - Computationally Efficient Sparse Bayesian Learning via Belief Propagation.
- Thong T. Do, Yi Chen, Dzung T. Nguyen, Nam Nguyen, Lu Gan and Trac D. Tran - Robust Video Transmission Using Layered Compressed Sensing
- Thong T. Do, Yi Chen , Dzung T. Nguyen , Nam Nguyen, Lu Gan and Trac D. Tran - Distributed Compressed Video Sensing
- Thong T. Do, Yi Chen , Dzung T. Nguyen , Nam Nguyen , Lu Gan and Trac D. Tran - Fast and Efficient Compressive Imaging Using Separable Measurement Ensembles
- Haichao Wang - Sequential Compressed Sensing
- Yingying Li - Heat Source Identification Based on Compressed Sensing
- Anwei Chai - Compressed Sensing and Imaging: a Comparative Study
- Haojun Chen - Bayesian Group LASSO for Compressive Sensing
- Zachary Harmany, Roummel Marcia, and Rebecca Willett - Compressive Coded Aperture Imaging
- Christian Austin - On the Relation Between Sparse Sampling and Parametric Estimation
- Zaiwen Wen - A Fast Algorighm For Sparse Reconstruction Based On Shrinkage, Subspace Optimization and Continuation
- Shiqian Ma - An Efficient Algorithm for Compressed MR Imaging using Total Variation and Wavelets
- Hao Gao and Hongkai Zhao - Compressive Sensing in Bioluminescence Tomography Based on Radiative Transfer Equation

University of Maryland

Acquiring the reflectance field of real objects is an important problem that is often encountered for solving several imaging, vision and graphics tasks such as relighting. Typical methods for capturing such reflectance fields are based on acquiring images with a single light source 'ON' in each image. Recently, it has been shown that using multiple light sources per each acquired image and performing a linear inversion in order to recover the reflectance field results in higher signal to noise ratios of the captured reflectance fields. Nevertheless, the number of images to be acquired to infer the reflectance field remains identical to the number of illumination sources. Here, we describe a method for acquiring accurate reflectance fields of objects with significantly lower number of captured images than the number of illumination sources. This reduction in the number of required images is achieved by exploiting recent developments in compressive sensing, which essentially show that if the signal to be acquired is sparse in some basis, then the signal can be accurately reconstructed using sub-Nyquist linear samples of the signal. We empirically show that the reflectance fields are sparse in the Haar basis. We then develop a scheme for capturing reflectance fields using multiplexed illumination, thereby achieving the signal-to-noise ratio advantages of multiplexed illumination and use a compressive sensing based recovery algorithm to infer reflectance fields. This is joint work with Dr. Veeraraghavan (MERL), Prof. Chellappa (UMD) and Prof. Raskar (MIT).

UCLA

Image guided interventions via ultrasound imaging have become the standard of care for many surgical procedures. A majority of medical care-providers utilize low resolution ultrasound units. In addition, many office-based or emergency department procedures are performed using generic (non-specialized) needles. Therefore, the quality of the imagery obtained by most ultrasound units does not allow for clear and concise visualization of a regular needle during many needle-based procedures. The inability to clearly see the tip of a needle in relation to the object of interest (e.g., a vein, artery, or mass) makes such image guided interventions less accurate. In this paper, we propose a new and improved framework for tracking needles in ultrasound image frames. The problem can be easily transformed to a segmentation problem, which needs to be solved in real time. The core of our method is to employ the split Bregman iterations [T. Goldstein and S. J. Osher, 2008] on solving the weighted geometric active contour (WGAC) model [X. Bresson et al, 2007]. After a simple change of variables, the WGAC model can be converted to a standard L1-minimization problem, which can then be solved rather efficiently by Bregman iterations [W. Yin et al, 2008].

Duke University

This poster describes spectrally adaptive signal segmentation with a compressive sensing architecture. Total variation minimization is used to reconstruct a three-dimensional (3D) data cube from a two-dimensional (2D) snapshot. A priori knowledge of spectral signatures found in a sample is used for image segmentation. We apply this algorithm to fluorescence microscopy data acquired from a snapshot spectral imager. The instrument records 32 spectral channels that span the spectral range between 450nm and 750nm with 10nm spectral resolution. We report on reconstructions for both static and dynamic samples used in fluorescence microscopy.

UCLA

The central problem for tomographic reconstruction is to reconstruct a clean and faithful image from very limited projections and therefore reduce the radiation dose. Since the Fourier slice theorem gives us a linear relationship between the projection data and the medical image, the reconstruction of image becomes a standard compressive sensing type of problem, that is to say, we want to reconstruct the best result (defined by certain criteria) from limited number of linear measurements of the image.

This leads to a constrained optimization problem and we will address a fast and efficient scheme to solve it. The numerical results demonstrate that this method strongly outperforms the conventional tomographic reconstruction in terms of the reduced radiation dose and the quality of the reconstruction.

University of Massachusetts, Dartmouth

This work addresses the problem of 2-D field directionality estimation using short uniform linear array. The field directionality in the proposed model is represented as a compressible signal in the frequency-wavenumber domain, motivating the application of the compressive sensing (CS) theory to the addressed problem. The spatial interpretation of the CS approach, denoted as spatial CS (SCS), provides a high azimuth resolution for a fixed linear array. Moreover, the SCS provides an efficient way to exploit the spatial diversity achieved by the changing array orientation or distributed networks to resolves the left-right ambiguity of linear array and to improve the estimation performance in the endfire regions. Simplicity of implementation comparing to other methods, is an additional advantage of the proposed approach. The performance of the SCS approach for the field directionality estimation was evaluated via simulation and it is shown that it outperforms other tested methods.

Radboud University (The Netherlands)

An effective way to increase the noise robustness of automatic speech recognition is to label noisy speech features as either reliable or unreliable (missing) prior to decoding, and to replace (impute) the missing ones by clean speech estimates. Work in Compressive Sensing has shown signals can be reconstructed using relatively few measurements provided the signal is known to be sparse in an appropriate basis. We sparsely represent spectrographic representations of speech in an overcomplete basis of exemplar (clean) speech signals using only the reliable speech features. The missing elements of the speech signals are then obtained by projecting the sparse representation in the basis. Experiments on spoken digit recognition show that this imputation technique greatly outperforms other imputation techniques for noise robust speech recognition.

Princeton University

We consider deterministic compressive sensing matrices where the columns are discrete chirp waveforms from an overcomplete dictionary, and we show that these matrices satisfy a statistical variant of the Restricted Isometry Property. We will then describe an algorithm for recovery of k-sparse signals that is resilient to noise, and has complexity kN logN where N is the number of measurements. The original motivation for our work was the application to active sensing, specifically radar applications. However we have recently developed and interesting connection to A/D conversion through analysis of the NYFR receiver developed by L3 Communications as part of the A-to-I program at DARPA. When the NYFR receiver samples a wideband signal at the level crossings of a chirp waveform, the samples of continuous time sinusoids are discrete chirp sequences, and so the sparse narrowband recovery problem amounts to determining a small number of chirps that agree with the sampled data. This reduces to essentially the same problem that we explored in the original radar application.

Boston University

This paper presents a method for imaging of moving targets with a SAR sensor by treating the problem as one of spatial reflectivity signal inversion over an overcomplete dictionary of target velocities. Since SAR sensors returns can be related to the spatial frequency domain projections of the scattering field, we exploit insights from compressed sensing theory to show that moving targets can be effectively imaged with a small number of transmitters and receivers randomly dispersed within a narrow forward cone around the scene of interest. Existing approaches to dealing with moving targets in SAR solve a coupled non-linear problem of target scattering and motion estimation typically through matched filtering. In contrast, by using an overcomplete dictionary approach we effectively linearize the forward model and solve the moving target problem as a larger, regularized inversion problem subject to sparsity constraints.

Army Research Laboratory

The U.S. Army Research Laboratory (ARL), as part of a mission and customer funded exploratory program, has developed a new low-frequency, ultra-wideband (UWB) synchronous impulse reconstruction (SIRE) synthetic aperture radar (SAR). The radar has been used as a testbed to support proof-of-concept demonstration for several programs for detection of concealed targets.

We will present the recursive sidelobe minimization (RSM) technique - which is based on compressive sensing principle - when combined with the standard SAR image formation would result in significant reduction in sidelobes and noise in resulting SAR imagery. Although the technique is developed using the ARL UWB SIRE radar in forward-looking mode, it is also applicable for other radar configuration such as side-looking SAR.

Princeton University

We develop efficient compressive sensing algorithms based on expander graphs for which the number of measurements is optimal. The recovery algorithm is based on key properties of expander graphs: first, the restricted isometry property with respect to the l1 norm (RIP1) which is a geometric view of expander graphs; and second, the excessive unique neighborhood property which is a combinatorial view of expander graphs. We show that these two properties imply that not only basis pursuit algorithm works with the expander graph, but also that there exists a very simple combinatorial algorithm which recovers any k-sparse signal in about k (sparsity level) very simple iterations. We also show that by tolerating a small penalty on the number of measurements (and not on the number of recovery iterations) we can use known constructions of expander graphs to come up with explicit measurement matrices for this method. Finally we show how the algorithm can be generalized to approximate compressible signals and noisy measurements, with very high precision with respect to the l1 metric.

UCLA

The previously introduced Split Bregman method is an iterative scheme for solving L1 regularized problems, and is particularly well suited for problems involving total variation and Besov regularizers. This presentation will explore applications of this type of scheme, including compressed sensing MRI. We shall also discuss several novel applications of the Split Bregman method, including image segmentation and surface reconstruction from unorganized data points,

University of Maryland

Synthetic Aperture Radar (SAR) is an imaging modality that provides a high resolution map of the spatial distribution of targets and terrain based on their response to transmitted electromagnetic waveforms. In this presentation, we will introduce a new SAR imaging scheme based on compressing the number of transmitted waveforms. We will show that if the target reflectivity function is assumed to be sparse in some domain, one can reconstruct a good estimate of the reflectivity profile using a new image formation algorithm that relies on using far fewer number of waveforms than conventional systems do. Some applications of this compressed aperture Radar will be discussed in the talk. This is joint work with Glenn Easley, Dennis Healy, and Rama Chellappa.

Caltech

In this talk, we will investigate the fundamental "balancedness" properties of linear subspaces and discuss the applications of these properties in the emerging field of compressive sensing. First, we will give the definitions of several "balancedness" properties for linear subspaces and show the respective connections between them and compressive sensing. Then using tools from high-dimensional integral geometry and geometric probability, we establish a unified framework for analyzing these "balancedness" properties, and give sharp performance bounds for the "balancedness" a linear subspace can achieve under these different notions of "balancedness". We will further discuss the applications of this analytical framework in the analysis and design of (new) sparse signal recovery algorithms for compressive sensing. This work concerns fundamental properties of linear subspaces and may be of independent mathematical interest.

University of Florida

We present two belief propagation (BP) based sparse Bayesian learning (SBL) algorithms, referred to as the SBL-BP and the modified SBL-BP algorithm, to recover sparse transform coefficients in large scale compressed sensing problems. Both algorithms are based on a widely-used hierarchical Bayesian model, which is turned into a factor graph so that BP can be applied to achieve computational efficiency. We prove that the messages in BP are Gaussian probability density functions and therefore, we only need to update their means and variances when we update the messages. The computational complexity of both algorithms is proportional to the number of transform coefficients, allowing the algorithms to deal with large scale compressed sensing problems efficiently. Numerical examples are provided to demonstrate the effectiveness of the algorithms and to show that the modified SBL-BP algorithm performs similarly to the SBL-BP algorithm but the former is computationally faster than the latter.

* John Hopkins University

** Brunel University (UK)

In this work, we propose a novel scheme of layered compressed sensing (LaCoS) for robust transmission of video signals over packet loss channels. In the proposed transmission system, the encoder consists of a base layer and an enhancement layer. The base layer is a conventionally encoded bitstream and transmitted without any error protection. The additional enhancement layer is a stream of compressed measurements taken across slices of video signals for error-resilience. The decoder generates side information that is a measurement vector of the corrupted base layer and then employs a sparse recovery with this side information to recover lost packets. By exploiting the side information at the decoder, the enhancement layer is required to transmit a minimal amount of compressed measurements that is only proportional to the amount of lost packets. Simulation results show that both compression efficiency and error-resilience capacity of the proposed scheme are competitive with those of other state-of-the-art robust transmission methods, in which Wyner-Ziv coders often generate an enhancement layer.

* This work has been supported in part by the National Science Foundation under Grant CCF-0728893.

* John Hopkins University

** Brunel University (UK)

In this work, we propose a novel framework called Distributed Compressed Video Sensing (DisCoS). Like other Distributed Video Coding (DVC) schemes, in which video frames are often intraframe-coded and interframe-decoded to exploit temporal correlation among them, the proposed scheme also samples each frame independently and recovers them by exploiting the interframe sparsity with side information. In particular, the encoder acquires two types of compressed measurements: block-based measurements (or local measurements) and frame-based measurements (or global measurements). The decoder first generates a prediction of the current frame from previously reconstructed frame(s) and the local measurements. The key observation is that a block in the current frame can be sparsely represented by a linear combination of few neighboring blocks in previously reconstructed frame(s), enabling it to be predicted from its local measurements by soling the l-1 minimization. The process of block prediction follows a similar idea of motion estimation at the decoder side in other state-of-the-art DVC schemes. Then, the decoder generates global measurements of the prediction error from those of the current frame and the predicted one. As the prediction error is often very sparse, it can be recovered from these measurements by solving the l-1 minimization. Simulation results show that DisCoS significantly outperforms the intraframe-sensing and intraframe-sparse recovery scheme. It is even comparable to a scheme of intraframe-sensing and interframe-sparse recovery with oracle motion vectors available at the decoder. In addition, unlike all other previous DVC schemes, the DisCoS can perform encoding operation in the analog domain with very low-complexity, making it a promising candidate for applications where the sampling process is very expensive, e.g., in Terahertz imaging.

* This work has been supported in part by the National Science Foundation under Grant CCF-0728893.

* John Hopkins University

** Brunel University (UK)

We extend our previous work of Structurally Random Matrices to propose a fast and efficient compressive sampling for two dimensional signals such as natural images. Unlike other previous compressive sampling algorithms that often regard sensing signals as 1-d signals, the proposed approach uses separable operators to sample rows and columns of an image independently. Let X be the sensing image. Then, the separable measurement process can be mathematically represented as D1 F1 R1 XR2 F2 D2 , where:

- R1 and R2 are row-randomizer and column -randomizer, respectively. They are diagonal matrices with i.i.d Bernoulli random variables on their main diagonals
- F1 and F2 are fast orthonormal transforms such as the DCT, the WHT or the FFT, etc.
- D1 and D2 are row-downsampler and column-downsampler that are randomly selected rows and columns of an identity matrix, respectively

* This work has been supported in part by the National Science Foundation under Grant CCF-0728893.

Vanderbilt University

There are two main approaches in compressed sensing: the geometric approach and the combinatorial approach. In this talk, we will introduce an information theoretic approach and construct a sequence of binary sampling vectors to determine a sparse signal. Unlike other approaches, ours is adaptive in the sense that each sampling vector depends on the previous sample. The number of measurements we need is no more than O(k log n) and the reconstruction is O(k).

Duke University

As an old problem, random sensor array has been considered for decades. The main motivation for the use of random or non-uniform arrays has typically been the goal of achieving high-resolution sensing while reducing sensing costs. The recently developed compressive sensing (CS) is a framework in which one attempts to measure a signal in a compressive mode, implying that fewer total measurements are required. In this poster, the random sensor arrays are examined from a CS perspective. It is demonstrated that the natural random-array projections manifested by the media Green's function are consistent with the projection type measurements associated with CS. This linkage allows the use of existing CS theory to quantify the performance of random arrays, of interest for array design. The analysis as well as the numerical simulation examples demonstrate that the CS theory is applicable to arrays in vacuum as well as in the presence of a surrounding media; further, the presence of a surrounding media with known properties may be used to improve array performance.

UCLA

We consider the problem of inverting the heat equation, where known point-value samples at time T are used to estimate the initial condition. The initial condition is assumed to be sparse. We solve the problem using compressed sensing techniques, formulating the problem as an L1 optimization and solving it with the linearized Bregman method. Examples in both one and two spatial dimensions are shown. Finally, we show how our approach may be adapted to solve some similar problems.

Lockheed-Martin

We consider the application of compressive imaging theory to increase the performance of current imaging sensors. Spatial multiplexing sensors can increase the effective field-of-view (FOV) of the sensor without loss of resolution. We present an optical architecture which is compressive in nature and results in 2-orders of magnitude increased FOV when compressive sensing theory is applied to detect moving targets. Building on this compressive imaging model, we then turn to the time multiplexing case. Smart Focal-Plane-Array (FPA) technology is assumed, to integrate light at varying time-constants throughout the scene. The result is the ability to track a moving object during the integration time of the sensor. These simulated examples highlight the ability to increase current sensor performance significantly by designing sensors and exploitation tasks simultaneously with Compressive Imaging as the underlying theory.

Duke University

We propose a method for projecting N-dimensional vectors in Euclidean space onto the set of K-sparse vectors. The method is based on simple operations requiring time on the order of O(N*log(N)). We also consider the case of projecting onto the set of K-block-sparse vectors and extend the method to perform the projection in time O(B*log(B),N), where B is the number of blocks. Together with projections from linear algebra, the proposed methods yield efficient algorithms for CS reconstructions. We present experimental results on large images and compare to state-of-the-art algorithms.

Stanford University

Compressed sensing is a robust method for recovering sparse signals that can also be used in array imaging. In this work we present a framework to assess the results of imaging using compressed sensing and other previously developed approaches. We will show various numerical simulations and interpret those results with analytical ones.

Duke University

We introduce a probabilistic formulation of group LASSO and employ it as a block-sparse prior for Bayesian compressive sensing (CS). The resulting Bayesian group LASSO algorithm retains the robustness of Bayesian CS and, in addition, exploits the inter-dependency between the sparse coefficients to achieve accurate signal reconstruction based on a smaller number of measurements. The algorithm effectively reduces the signal dimensionality by squeezing strongly dependent coefficients into a group, and achieves computational efficiency by performing calculation at the level of groups versus individual coefficients. We compare the proposed algorithm, in terms of reconstruction performance as well as time complexity, to state-of-the-art CS algorithms.

Duke University

We present performance bounds for compressed sensing in the presence of Poisson noise and shows that, for sparse or compressible signals, they are within a log factor of known lower bounds on the risk. The signal-independent and bounded noise models used in the literature to analyze the performance of compressed sensing do not accurately model the effects of Poisson noise. However, Poisson noise is an appropriate noise model for a variety of applications, including low-light imaging, in which sensing hardware is large or expensive and limiting the number of measurements collected is important. We will show how a feasible, positivity-preserving sensing matrix can be constructed and prove a concentration-of-measure inequality for these matrices. We then show that minimizing an objective function consisting of a negative Poisson log likelihood term and a penalty term which could be used as a measure of signal sparsity results in near-minimax rates of error decay.

Duke University

A fundamental challenge in applying compressed sensing theory to practical imaging systems is that physical constraints typically make it infeasible to actually measure many of the random projections described in the literature, and therefore, innovative and sophisticated imaging systems must be carefully designed to effectively exploit CS theory. In this work, we propose compressive imaging techniques for improving the performance of video imaging systems in the presence of constraints on the focal plane array size. In particular, we describe a novel yet practical approach that combines coded aperture imaging to enhance pixel resolution with superimposing subframes of a scene onto a single focal plane array to increase field of view. Specifically, the proposed method superimposes coded observations and uses wavelet-based sparsity recovery algorithms to reconstruct the original subframes. We demonstrate the effectiveness of this approach by reconstructing with high resolution the constituent images of a video sequence.

Ohio State University

We consider the relationship between parameter estimation of an additive model and sparse inversion of an under-determined matrix (dictionary) in a linear system. The dictionary is constructed by sampling parameters of the additive model and does not satisfy the Restricted Isometry Property (RIP) of Compressive Sensing. Parameters and model order are estimated using regularized least-squares inversion with lp norm penalty, where p≤1. We investigate equi-spaced and Fisher information inspired parameter sampling methods for dictionary construction. Examples are presented quantifying parameter estimation performance for the different sampling methods and for different sampling densities.

Duke University

This paper analyzes the role of coded apertures and compressive-sensing based inference with x-ray transform measurements to improve data efficiency and reconstruction fidelity. While x-ray tomography is the canonical example, diverse physical measurements can be modeled by x-ray transform measurements. Our group has previously demonstrated the use of coding in reference structure tomography (RST) and coded aperture snapshot spectral imaging (CASSI). This paper investigates coding strategies in these applications and extends this approach in proposing compressive x-ray tomography based on the use of coding concepts.

Boston Univeristy

We will describe a novel algorithm based on thresholding the solution to basis pursuit for support recovery and approximation. Our result offers a sharp characterization in that neither the SNR nor the sparsity ratio can be significantly improved in comparison to the information theoretic/Max-Likelihood bounds. Our idea is to adopt a perturbation approach to the noiseless problem. Keeping the number of measurements fixed (at the level achievable for noiseless recovery) we increase the noise and characterize the maximum noise level for which support recovery fails.

Rice University

We demonstrate that the recovery rate of l1-minimization on signals with fast decaying distribution of nonzero values can be enhanced by applying a simple, novel iterative support detection strategy. Preliminary theoretical and experimental results, as well as the limitation of the strategy, are presented.

Columbia University

We describe a fast algorithm for sparse reconstruction. The algorithm is divided into two stages that are performed repeatedly. In the first stage, "shrinkage" yields an estimate of the subset of variables likely to be nonzero in an optimal solution. Restricting the decision variables to this subset and fixing their signs at their current values results in a smooth quadratic problem that is solved in the second phase. Our method also embeds this basic two-stage algorithm in a continuation (homotopy) approach. Our implementation of this method exhibits state-of-the-art performance both in terms of its speed and its ability to recover sparse signals. It can even recover signals that are not as sparse as required by current compressive sensing theory.

Columbia University

Because information such as boundaries of organs is very sparse in most MR images, compressed sensing makes it possible to reconstruct the same MR image from a very limited set of measurements significantly reducing the MRI scan duration. In order to do that however, one has to solve the difficult problem of minimizing nonsmooth functions on large data sets. To handle this, we propose an efficient algorithm that jointly minimizes the L1 norm, total variation, and a least squares measure, one of the most powerful models for compressive MR imaging. Our algorithm is based upon an iterative operator-splitting framework. The calculations are accelerated by continuation and takes advantage of fast wavelet and Fourier transforms enabling our code to process MR images from actual real life applications. We show that faithful MR images can be reconstructed from a subset that represents a mere 20 percent of the complete set of measurements.

UC Irvine

In this work, we study compressive sensing (CS) in bioluminescence tomography (BLT), in particularly based on radiative transfer equation (RTE). BLT is an emerging and promising technique for molecular imaging in which one tries to reconstruct the distribution of bioluminescent sources through boundary measurements. Although the source localization problem can be casted as a linear problem, the reconstruction is still very challenging due to the severe ill-posedness. Since sources in BLT are usually sparse in space, compressive sensing method would be a natural solution. However, directly using Green's function of RTE as the basis and standard measurement data for reconstruction will not satisfy the restricted isometry property (RIP) which is crucial for the success of CS. We propose an algorithm to transform the standard setup into a new system that satisfies the RIP. Hence, with compressive sensing method, we produce much improved results over standard reconstruction method.