Saturday, February 16, 2008

Compressed Sensing: Recovery Algorithms for Vector Valued Data, Wavelet-tailored Algorithm and a Network API for Sensor Networks

Here is a new preprint from Massimo Fornasier and Holger Rauhut on Recovery Algorithms for Vector Valued Data with Joint Sparsity Constraints. The abstract reads:

Vector valued data appearing in concrete applications often possess sparse expansions with respect to a preassigned frame for each vector component individually. Additionally, different components may also exhibit common sparsity patterns. Recently, there were introduced sparsity measures that take into account such joint sparsity patterns, promoting coupling of non-vanishing components. These measures are typically constructed as weighted l1 norms of componentwise lq norms of frame coefficients. We show how to compute solutions of linear inverse problems with such joint sparsity regularization constraints by fast thresholded Landweber algorithms. Next we discuss the adaptive choice of suitable weights appearing in the definition of sparsity measures. The weights are interpreted as indicators of the sparsity pattern and are iteratively up-dated after each new application of the thresholded Landweber algorithm. The resulting two-step algorithm is interpreted as a double-minimization scheme for a suitable target functional. We show its l2-norm convergence. An implementable version of the algorithm is also formulated, and its norm convergence is proven. Numerical experiments in color image restoration are presented.
They point out to the areas which can use the algorithm developed in the paper:

"...Neuroimaging (functional Magnetic Resonance Imaging, Magnetoencephalography), distributed compressed sensing [3] and several other problems with coupled vector valued solutions are fields where we expect that our scheme can be fruitfully used. The numerical solution of differential and integral operator equations can also be addressed within this framework.."

There are also a new batch of preprints and presentation slides from Rice:

The poster for Sparse Signal Reconstruction from Noisy Compressive Measurements Using Cross Validation by Petros Boufounos , Marco F. Duarte and Richard Baraniuk is here. While the slides for Multiscale Random Projections for Compressive Classification are here ( Marco F. Duarte, Mark Davenport, Michael Wakin, Jason Laska , Dharmpal Takhar, Kevin Kelly and Richard Baraniuk).

Marco F. Duarte
, Michael Wakin and Richard Baraniuk, Wavelet-Domain Compressive Signal Reconstruction Using a Hidden Markov Tree Model. The abstract reads:

Compressive sensing aims to recover a sparse or compressible signal from a small set of projections onto random vectors; conventional solutions involve linear programming or greedy algorithms that can be computationally expensive. Moreover, these recovery techniques are generic and assume no particular structure in the signal aside from sparsity. In this paper, we propose a new algorithm that enables fast recovery of piecewise smooth signals, a large and useful class of signals whose sparse wavelet expansions feature a distinct “connected tree” structure. Our algorithm fuses recent results on iterative reweighted ℓ1-norm minimization with the wavelet Hidden Markov Tree model. The resulting optimization-based solver outperforms the standard compressive recovery algorithms as well as previously proposed wavelet-based recovery algorithms. As a bonus, the algorithm reduces the number of measurements necessary to achieve low-distortion reconstruction.
As pointed out in the conclusion: "This paper introduced a wavelet-tailored weighting scheme for the iterative reweighted ℓ1-norm minimization algorithm for compressive sensing recovery." I am sure their scheme can also be used for the reweighted l-p minimization. This is the second algorithm (it seems) that is tailored to wavelets (the first one is Sublinear recovery of sparse wavelet signals by Ray Maleh and Anna Gilbert )

and the final intriguing paper is A Network Application Programming Interface for Data Processing in Sensor Networks by Raymond Wagner, J. Ryan Stinnett, Marco F. Duarte, Richard Baraniuk, David B. Johnson and T. S. Eugene Ng. The abstract reads:
Since the inception of sensor networks, a wide variety of algorithms for in-network data processing have emerged. To enable practical implementation of a broad class of these proposed algorithms, sufficient application programming support for network communications is critical. While standard (but relatively low-level) network application programming interfaces (APIs) such as those implemented in TinyOS can provide a basis for flexible application-specific customization, experience in the past several years has shown that data processing algorithms in fact share similar higher level communication needs that can be better supported. In this paper, we first identify common communication patterns through an extensive survey of data processing algorithms proposed over the past four years in the proceedings of the Information Processing in Sensor Networks (IPSN) conference. We then present the design of a higher level network API for sensor networks that is powerful, convenient to use, and compact. Many familiar issues in traditional networking such as addressing and reliability have vastly different solutions in the sensor network environment, and we carefully develop the rationales behind the design of the resulting network API, providing an in-depth discussion on the fundamental design decisions. We believe that the proposed network API serves as a starting point for the implementation of a more comprehensive sensor network communication middleware than what is found in currently available systems, enabling algorithm developers to quickly and easily implement their designs without having to handle low-level networking details themselves.
Image credit: NASA/JPL-Caltech/Cornell University, Opportunity used its panoramic camera (Pancam) to capture this image with low-sun angle at a local solar time of 3:21 p.m. during the rover's 1,433rd Martian day, of sol (Feb. 4, 2008).

No comments: