Wednesday, December 08, 2010

CS: Bob and Alejandro's conversation, Can GREAT10 be solved with the help of CS, Compressed Neighbor Discovery for Wireless Networks, Compressive Sensing Over Networks

Bob continues his investigation with some feedback from Alejandro Weinstein in Greedy recovery depends on the sparse vector distribution, become part of that conversation!

In other news, you recall this entry on gravitational lenses and M&Ms, well this recently released wired article features the GREAT10 challenge. I made the point a little later that each of these photos from the Hubble were instance of a randomly modulated of a galaxy behind the "random" lens in CS / Imaging With Nature: A Galaxy Wide Single Pixel Camera. The goal of GREAT10 is divided in two challenges:

The Star Challenge : Is to the reconstruct the Point Spread Function, or convolution kernel, in astronomical images, which occurs because of the slight blurring effects of the telescope and atmosphere. The PSF varies across each image and is only sparsely sampled by stars, which are pixelated and noisy. The challenge is to reconstruct the PSF at non-star positions.

The Galaxy Challenge : Is to measure the shapes of galaxies to reconstruct the gravitational lensing signal in the presence of noise and a known Point Spread Function. The signal is a very small change in the galaxies’ ellipticity, an exactly circular galaxy image would be changed into an ellipse; however real galaxies are not circular. The challenge is to measure this effect over 52 million galaxies.

Hmm finding the PSF and gravitional lensing, looks to me like a blind deconvolution problem. Can compressive sensing help speed up that process ? The arxiv document on GREAT10 is here.

This paper studies neighbor discovery problem in wireless networks. A novel scheme, called compressed neighbor discovery is proposed, which assigns each node a unique signature and let nodes simultaneously transmit their signatures during the discovery period. The query node then determines, based on the superposition of the signatures, a small number of nodes as its neighbors, out of a large number of nodes in the network. This is fundamentally a sparse recovery problem. Using the proposed scheme, a single frame time suffices to achieve reliable discovery for large networks. This is in contrast to conventional schemes, where each node repeatedly transmits its identity with random delay, so that a receiver can identify each neighbor at least once without collision. Two practical, low-complexity discovery schemes are studied. The first scheme assigns sparse pseudo-random on-off signatures to the nodes, so that each node can listen to the channel during its own off-slots. Despite of half-duplex constraint, all nodes can simultaneously discover their respective neighborhoods, using a simple noncoherent detection algorithm based on group testing. A network of 10000 nodes is simulated, where each node has 50 neighbors on average. At moderate signal-to-noise ratios, all nodes can identify their neighbors with on average 99% accuracy using 2500-bit signatures, which is much more efficient than random-access discovery. The second scheme uses deterministic signatures from a second order Reed-Muller code. Decoding using the chirp algorithm entails only sub-linear complexity, so the scheme is feasible for networks with 2^32 nodes or more. This scheme significantly outperforms the first one, although, unlike the first scheme, full-duplex decoding is not supported. Both schemes are applicable to mobile ad hoc networks (MANETs) as well as heterogeneous cellular networks with femtocells and picocells
In this paper, we demonstrate some applications of compressive sensing over networks. We make a connection between compressive sensing and traditional information theoretic techniques in source coding and channel coding. Our results provide an explicit trade-off between the rate and the decoding complexity. The key difference of compressive sensing and traditional information theoretic approaches is at their decoding side. Although optimal decoders to recover the original signal, compressed by source coding have high complexity, the compressive sensing decoder is a linear or convex optimization. First, we investigate applications of compressive sensing on distributed compression of correlated sources. Here, by using compressive sensing, we propose a compression scheme for a family of correlated sources with a modularized decoder, providing a trade-off between the compression rate and the decoding complexity. We call this scheme Sparse Distributed Compression. We use this compression scheme for a general multicast network with correlated sources. Here, we first decode some of the sources by a network decoding technique and then, we use a compressive sensing decoder to obtain the whole sources. Then, we investigate applications of compressive sensing on channel coding. We propose a coding scheme that combines compressive sensing and random channel coding for a high-SNR point-to-point Gaussian channel. We call this scheme Sparse Channel Coding. We propose a modularized decoder providing a trade-off between the capacity loss and the decoding complexity. At the receiver side, first, we use a compressive sensing decoder on a noisy signal to obtain a noisy estimate of the original signal and then, we apply a traditional channel coding decoder to find the original signal.

Credit: Andrew Fruchter (STScI) et al., WFPC2, HST, NASA, Image: Light bends around the massive galaxy cluster Abell 2218 in this image from the Hubble Space Telescope.

No comments: