Monday, April 27, 2009

CS: Minimum Sum of Distances Estimator, Iterative reweighted L1, CS with quantized measurements, GPU, Missing Data Imputation, Duke Workshop Posters

Here is a very nice approach to navigation in autonomous robots:
Minimum Sum of Distances Estimator: Robustness and Stability by Yariv Sharon, John Wright and Yi Ma. The abstract reads:

We consider the problem of estimating a state x from noisy and corrupted linear measurements y = Ax + z + e, where z is a dense vector of small-magnitude noise and e is a relatively sparse vector whose entries can be arbitrarily large. We study the behavior of the l1 estimator x^ = argmin_x ||y - Ax||_1, and analyze its breakdown point with respect to the number of corrupted measurements ||e||_0. We show that the breakdown point is independent of the noise. We introduce a novel algorithm for computing the breakdown point for any given A, and provide a simple bound on the estimation error when the number of corrupted measurements is less than the breakdown point. As a motivational example we apply our algorithm to design a robust state estimator for an autonomous vehicles, and show how it can significantly improve performance over the Kalman filter.
They actually show an improvement over a non-linear Kalman filter. We observed this issue of the GPS error during our entry in DARPA's grand challenge.

Compressed sensing has shown that it is possible to reconstruct sparse high dimensional signals from few linear measurements. In many cases, the solution can be obtained by solving an ℓ1-minimization problem, and this method is accurate even in the presence of noise. Recent a modified version of this method, reweighted ℓ1-minimization, has been suggested. Although no provable results have yet been attained, empirical studies have suggested the reweighted version outperforms the standard method. Here we analyze the reweighted ℓ1-minimization method in the noisy case, and provide provable results showing an improvement in the error bound over the standard bounds.
Still in the robotics area here a new use for GPU: learning dictionariesin Large-scale Deep Unsupervised Learning using Graphics Processors by Rajat Raina, Anand Madhavan, Andrew Y. Ng. The abstract reads:
The promise of unsupervised learning methods lies in their potential to use vast amounts of unlabeled data to learn complex, highly nonlinear models with millions of free parameters. We consider two well-known unsupervised learning models, deep belief networks (DBNs) and sparse coding, that have recently been applied to a flurry of machine learning applications (Hinton & Salakhutdinov, 2006; Raina et al., 2007). Unfortunately, current learning algorithms for both models are too slow for large-scale applications, forcing researchers to focus on smaller-scale models, or to use fewer training examples. In this paper, we suggest massively parallel methods to help resolve these problems. We argue that modern graphics processors far surpass the computational capabilities of multicore CPUs, and have the potential to revolutionize the applicability of deep unsupervised learning methods. We develop general principles for massively parallelizing unsupervised learning tasks using graphics processors. We show that these principles can be applied to successfully scaling up learning algorithms for both DBNs and sparse coding. Our implementation of DBN learning is up to 70 times faster than a dual-core CPU implementation for large models. For example, we are able to reduce the time required to learn a four-layer DBN with 100 million free parameters from several weeks to around a single day. For sparse coding, we develop a simple, inherently parallel algorithm, that leads to a 5 to 15-fold speedup over previous methods.
We have had different papers on 1-bit or several-bit Compressive Sensing, here is a new one: Compressed sensing with quantized measurements by Argyrios Zymnis, Stephen Boyd, and Emmanuel Candes. The abstract reads:
We consider the problem of estimating a sparse signal from a set of quantized, Gaussian noise corrupted measurements, where each measurement corresponds to an interval of values. We give two methods for (approximately) solving this problem, each based on minimizing a differentiable convex function plus an regularization term. Using a first order method developed by Yin et al, we demonstrate the performance of the methods through numerical simulation. We find that, using these methods, compressed sensing can be carried out even when the quantization is very coarse, e.g., 1 or 2 bits per measurement.
and finally, we have: Missing Data Imputation using Compressive Sensing techniques for connected digit recognition by Jort Gemmeke and Bert Cranen. The abstract reads:
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 the missing ones by clean speech estimates. We present a novel method based on techniques from the field of Compressive Sensing to obtain these clean speech estimates. Unlike previous imputation frameworks which work on a frame-by-frame basis, our method focuses on exploiting information from a large time-context. Using a sliding window approach, denoised speech representations are constructed using a sparse representation of the reliable features in an overcomplete dictionary of clean, fixed-length speech exemplars. We demonstrate the potential of our approach with experiments on the AURORA-2 connected digit database.


Larry Carin has updated the Duke Workshop page and included the abstract of the posters shown there, here is the list, lots of goodies, whished I had been there:

Poster Abstracts

Aswin Sankaranarayanan - Fast Compressive Acquisition of Reflectance Fields

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).

Bin Dong, Eric Savitsky and Stanley Osher - A Novel Method for Enhanced Needle Localization Using Ultrasound-Guidance

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].

Christy Fernandez - Cull Image Segmentation with a Compressive Snapshot Spectral Imager

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.

David Mao - Equally-Sloped Tomographic Reconstruction and Its Application to Radiation Dose Reduction.

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.

Igal Bilik - Spatial Compressive Sensing Approach for Field Directionality Estimation Via Spatial Diversity.

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.

Jort F. Gemmeke - Missing Data Imputation for Noise Robust Speech Recognition Using Compressive Sensing

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.

Lorne Applebaum - Chirp Sensing and A/D Conversion

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.

Ivana Stojanovic and W. Clem Karl - An Overcomplete Dictionary Approach to Imaging of Moving Targets with Multistatic SAR

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.

Lam Nguyen - SAR Imaging Technique for Reduction of Sidelobes and Noise

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.

Sina Jafarpour - Compressed Sensing Using High-quality Expander Graphs: Optimal Measurements, Efficient Recovery, Explicit Construction, and Noise Tolerance.

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.

Tom Goldstein - Split Bregman Schemes for L1 Regularized Problems

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,

Vishal Patel - Compressive Synthetic Aperture Radar Imaging

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.

Weiyu Xu - The Balancedness Properties of Linear Subspaces and their Applications in Compressive Sensing

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.

Xing Tan - Computationally Efficient Sparse Bayesian Learning via Belief Propagation.

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.

Thong T. Do*, Yi Chen* , Dzung T. Nguyen* , Nam Nguyen* , Lu Gan** and Trac D. Tran** - Robust Video Transmission Using Layered Compressed Sensing

* 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.

Thong T. Do*, Yi Chen* , Dzung T. Nguyen* , Nam Nguyen* , Lu Gan** and Trac D. Tran** - Distributed Compressed Video Sensing

* 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.

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

* 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:

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

Haichao Wang - Sequential Compressed Sensing

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).

Lawrence Carin, Bin Guo, Dehong Liu, and Wenbin Lin - On Compressive Sensing for the Random Sensor Array Design

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.

Yingying Li - Heat Source Identification Based on Compressed Sensing

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.

Robert Muise - A Compressive Imaging Approach for Tracking Targets in Multiplexed Data

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.

Xuejun Liao, Hui Li, and Lawrence Carin - Fast Projections onto the Set of Sparse Signals

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.

Anwei Chai - Compressed Sensing and Imaging: a Comparative Study

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.

Haojun Chen - Bayesian Group LASSO for Compressive Sensing

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.

Maxim Raginsky and Rebecca M. Willett - Minimax Risk Bounds for Poisson Compressed Sensing

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.

Zachary Harmany, Roummel Marcia, and Rebecca Willett - Compressive Coded Aperture Imaging

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.

Christian Austin - On the Relation Between Sparse Sampling and Parametric Estimation

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.

Kerkil Choi - Coded Aperture Compressive Computed Tomography

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.

Manqi Zhao, Venkatesh Saligrama - Thresholded Basis Pursuit: A Linear Programming Approach for Support Recovery

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.

Wotao Yin - Enhanced Compressed Sensing Based on Iterative Support Detection

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.

Zaiwen Wen - A Fast Algorighm For Sparse Reconstruction Based On Shrinkage, Subspace Optimization and Continuation

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.

Shiqian Ma - An Efficient Algorithm for Compressed MR Imaging using Total Variation and Wavelets

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.

Hao Gao and Hongkai Zhao - Compressive Sensing in Bioluminescence Tomography Based on Radiative Transfer Equation

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.

1 comment:

Unknown said...

For the first paper, ie. Minimum ..
The author proposed an algorithm which can estimate the breakdown points, just using matrix A? That's unbelievable. Can we determine the signal whether or not corrupted by noises just according to the Matrix A? Without the measurements, i.e. y? Unbelievalbe...

Printfriendly