Compressed Sensing: 1-Bit Compressive Sensing, Causal Compensation for Erasures in Frame Representations, Curvelet-based seismic data processing

Found on the internets, the mind altering 1-Bit Compressive Sensing by Petros Boufounos and Richard Baraniuk.The abstract reads:

Compressive sensing is a new signal acquisition technology with the potential to reduce the number of measurements required to acquire signals that are sparse or compressible in some basis. Rather than uniformly sampling the signal, compressive sensing computes inner products with a randomized dictionary of test functions. The signal is then recovered by a convex optimization that ensures the recovered signal is both consistent with the measurements and sparse. Compressive sensing reconstruction has been shown to be robust to multi-level quantization of the measurements, in which the reconstruction algorithm is modified to recover a sparse signal consistent to the quantization measurements. In this paper we consider the limiting case of 1-bit measurements, which preserve only the sign information of the random measurements. Although it is possible to reconstruct using the classical compressive sensing approach by treating the 1-bit measurements as ±1 measurement values, in this paper we reformulate the problem by treating the 1-bit measurements as sign constraints and further constraining the optimization to recover a signal on the unit sphere. Thus the sparse signal is recovered within a scaling factor. We demonstrate that this approach performs significantly better compared to the classical compressive sensing reconstruction methods, even as the signal becomes less sparse and as the number of measurements increases.

Notwithstanding the obvious simple hardware implementation, I am stunned by the potential of this result. I am impatient to see an actual implementation of this modified FPC solver originally developed by Elaine Hale, Wotao Yin and Yin Zhang.

While the link exists for Reconstructing Sparse Signals From their Zero Crossings by Petros Boufounos, Richard Baraniuk. Permissions have not been set on the server for people of the outside to see it yet.


Petros Boufounos, Alan Oppenheim and Vivek Goyal introduces us to the subject of Causal Compensation for Erasures in Frame Representations. The abstract reads:

In a variety of signal processing and communications contexts, erasures occur inadvertently or can be intentionally introduced as part of a data reduction strategy. This paper discusses causal compensation for erasures in frame representations of signals. The approach described assumes linear synthesis of the signal using a pre-specified frame but no specific generation mechanism for the coefficients. Under this assumption it is demonstrated that erasures can be compensated for using low-complexity causal systems. If the transmitter is aware of the occurrence of the erasure, an optimal compensation is to project the erasure error to the remaining coefficients. It is demonstrated that the same compensation can be executed using a transmitter/receiver combination in which the transmitter is not aware of the erasure occurrence. The transmitter precompensates using projections, as if assuming erasures will occur. The receiver undoes the compensation for the coefficients that have not been erased, thus maintaining the compensation only of the erased coefficients. The stability of the resulting systems is explored, and stability conditions are derived. It is shown that stability for any erasure pattern can be enforced by optimizing a constrained quadratic program at the system design stage. The paper concludes with examples and simulations that verify the theoretical results and illustrate key issues in the algorithms.

This somehow resembles a little bit what Jort is doing.


Gilles Hennenfent, Ewout van den Berg, Michael Friedlander and Felix Herrmann produced New insights into one-norm solvers from the pareto curve. The paper is for SINBAD sponsors only for the moment, we at least get to see the abstract:

Geophysical inverse problems typically involve a trade off between data misfit and some prior. Pareto curves trace the optimal trade off between these two competing aims. These curves are commonly used in problems with two-norm priors where they are plotted on a log-log scale and are known as L-curves. For other priors, such as the sparsity-promoting one norm, Pareto curves remain relatively unexplored. We show how these curves lead to new insights in one-norm regularization. First, we confirm the theoretical properties of smoothness and convexity of these curves from a stylized and a geophysical example. Second, we exploit these crucial properties to approximate the Pareto curve for a large-scale problem. Third, we show how Pareto curves provide an objective criterion to gauge how different one-norm solvers advance towards the solution.

In the world of seismic signal processing, people have access to interesting sets of basis functions such as curvelets. Felix Herrmann, D. Wang, Gilles Hennenfent, and Peyman Moghaddam wrote a summary of the current field in Curvelet-based seismic data processing: a multiscale and nonlinear approach.

In this letter, the solutions to three seismic processing problems are presented that exploit the multiscale and multi-angular properties of the curvelet transform. Data regularization, multiple removal, and restoration of migration amplitudes are all formulated in terms of a sparsity promoting program that employs the high degree of sparsity attained by curvelets on seismic data and images. For each problem the same nonlinear program is solved, simultaneously minimizing the data misfit and the one norm (l1) on the desired curvelet domain solution. Parsimony of curvelets on seismic wavefields and images of the sedimentary crust with wavefront-like features underlies the successful solution of these problems and is a clear indication of the broad applicability of this transform in exploration seismology.

The next step would be to devise sensors that can directly acquire data in a compressed sensing fashion. As far I recall the oil drilling industry did not care much about getting less data as they have plenty of infrastructure to take care of that for the time being. However in some instances, getting few data is the only thing people can get (recall the 30 bit/s pulse mud business).