CS: This week's long entry

Today's long post is mix of hardware and theoretical papers. Woohoo, enjoy.

A (256x256) Pixel 76.7mW CMOS Imager/ Compressor Based on Real-Time In-Pixel Compressive Sensing by Vahid Majidzadeh, Laurent Jacques, Alexandre Schmid, Pierre Vandergheynst, Yusuf Leblebici. The abstract reads:

A CMOS imager is presented which has the ability to perform localized compressive sensing on-chip. In-pixel convolutions of the sensed image with measurement matrices are computed in real time, and a proposed programmable two- dimensional scrambling technique guarantees the randomness of the coefficients used in successive observation. A power and area- efficient implementation architecture is presented making use of a single ADC. A 256×256 imager has been developed as a test vehicle in a 0.18μm CIS technology. Using an 11-bit ADC, a SNR of 18.6dB with a compression factor of 3.3 is achieved after reconstruction. The total power consumption of the imager is simulated at 76.7mW from a 1.8V supply voltage.

I'll add the reference to the compressive sensing hardware page later this week.

Improved Constructions for Non-adaptive Threshold Group Testing by Mahdi Cheraghchi. The abstract reads:

The basic goal in combinatorial group testing is to identify a set of up to $d$ defective items within a large population of size $n \gt\gt d$ using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool passes a fixed threshold $u$, negative if this number is below a fixed lower threshold $\ell \leq u$, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, $O(d^{g+2} (\log d) \log(n/d))$ measurements (where $g := u-\ell$) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound $O(d^{u+1} \log(n/d))$. Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by $O(d^{g+3} (\log d) \log n)$. Using state-of-the-art constructions of lossless condensers, however, we come up with explicit testing schemes with $O(d^{g+3} (\log d) quasipoly(\log n))$ and $O(d^{g+3+\beta} \poly(\log n))$ measurements, for arbitrary constant $\beta \gt 0$.

Compressed Channel Sensing: A New Approach to Estimating Sparse Multipath Channels, by Waheed U. Bajwa, Jarvis Haupt, Akbar M. Sayeed, and Robert Nowak. The abstract reads:

High-rate data communication over a multipath wireless channel often requires that the channel response be known at the receiver. Training-based methods, which probe the channel in time, frequency, and space with known signals and reconstruct the channel response from the output signals, are most commonly used to accomplish this task. Traditional training-based channel estimation methods, typically comprising of linear reconstruction techniques, are known to be optimal for rich multipath channels. However, physical arguments and growing experimental evidence suggest that many wireless channels encountered in practice tend to exhibit a sparse multipath structure that gets pronounced as the signal space dimension gets large (e.g., due to large bandwidth or large number of antennas). In this paper, we formalize the notion of multipath sparsity and present a new approach to estimating sparse (or effectively sparse) multipath channels that is based on some of the recent advances in the theory of compressed sensing. In particular, it is shown in the paper that the proposed approach, which is termed as compressed channel sensing, can potentially achieve a target reconstruction error using far less energy and, in many instances, latency and bandwidth than that dictated by the traditional leastsquares-based training methods.

Sampling Piecewise Sinusoidal Signals with Finite Rate of Innovation Methods by Jesse Berent, Pier Luigi Dragotti, and Thierry Blu. The abstract reads:

We consider the problem of sampling piecewise sinusoidal signals. Classical sampling theory does not enable perfect reconstruction of such signals since they are not band-limited. However, they can be characterized by a finite number of parameters, namely, the frequency, amplitude, and phase of the sinusoids and the location of the discontinuities. In this paper, we show that under certain hypotheses on the sampling kernel, it is possible to perfectly recover the parameters that define the piecewise sinusoidal signal from its sampled version. In particular, we show that, at least theoretically, it is possible to recover piecewise sine waves with arbitrarily high frequencies and arbitrarily close switching points. Extensions of the method are also presented such as the recovery of combinations of piecewise sine waves and polynomials. Finally, we study the effect of noise and present a robust reconstruction algorithm that is stable down to SNR levels of 7 [dB].

A Split Bregman Methodfor Non-Negative Sparsity Penalized Least Squares with Applications to Hyperspectral Demixing, by Arthur Szlam, Zhaohui Guo and Stanley Osher. The abstract reads:

We will describe an alternating direction (aka split Bregman) method for solving problems of the form minu ||Au −f||2 + \eta||u||1 such that u \ge 0, where A is anm×n matrix, and \eta is a nonnegative parameter. The algorithm works especially well for solving large numbers of small to medium overdetermined problems (i.e. m \gt n) with a fixed A. We will demonstrate applications in the analysis of hyperspectral images.

I note the use of the term alternating direction for split Bregman :-)

Condition number of a square matrix with i.i.d. columns drawn from a convex body by Alain Pajor, Radoslaw Adamczak, Alexander Litvak, Olivier Guédon, Nicole Tomczak-Jaegermann. The abstract reads:

We study the smallest singular value of a square random matrix with i.i.d. columns drawn from an isotropic log-concave distribution. An important example is obtained by sampling vectors uniformly distributed in an isotropic convex body. We deduce that the condition number of such matrices is of the order of the size of the matrix and give an estimate on its tail behavior.

From the Rice Repository, we have:

On performance of greedy algorithms by Vladimir N. Temlyakov , Pavel Zheltov. The abstract reads:

In this paper we show that for dictionaries with small coherence in a Hilbert space the Orthogonal Greedy Algorithm (OGA) performs almost as well as the best m-term approximation for all signals with sparsity almost as high as the best theoretically possible threshold s = 1 2 (M^-1 + 1) by proving a Lebesgue-type inequality for arbitrary signals. On the other hand, we present an example of a dictionary with coherence M and an s-sparse signal for which OGA fails to pick up any atoms from the support, thus showing that the above threshold is sharp. Also, by proving a Lebesgue-type inequality for Pure Greedy Algorithm (PGA), we show that PGA matches the rate of convergence of the best m-term approximation, even beyond the saturation limit of m^(-1/2) .

Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing by Entao Liu, Vladimir N. Temlyakov. The abstract reads:

The general theory of greedy approximation is well developed. Much less is known about how speci c features of a dictionary can be used for our advantage. In this paper we discuss incoherent dictionaries. We build a new greedy algorithm which is called the Orthogonal Super Greedy Algorithm (OSGA). OSGA is more efficient than a standard Orthogonal Greedy Algorithm (OGA). We show that the rates of convergence of OSGA and OGA with respect to incoherent dictionaries are the same. Greedy approximation is also a fundamental tool for sparse signal recovery. The performance of Orthogonal Multi Matching Pursuit (OMMP), a counterpart of OSGA in the compressed sensing setting, is also analyzed under RIP conditions.

Finally, Massimo Fornasier and Holger Rauhut seem to be coming up with an introduction to compressive sensing aptly named: Compressive Sensing - An Introduction (feb11, 2010 version). Holger Rauhut is also writing some lecture notes entitled Compressive sensing and structured random matrices. Version of February 9, 2010. These Lecture Notes are still under construction. If you have comments of any sort, Holger would be happy to receive them.

On the interwebs, I just noticed a blog entitled Error Correcting Codes: Combinatorics, Algorithms and Applications for CSE 545 @ CSE SUNY Buffalo and a student project at Stanford in EE 360 entitled Primary User Detection in Cognitive Radios with Multi-Resolutional Bayesian Compressive Sensing by Steven Hong .

Image Credit: NASA, In a very unique setting over Earth's colorful horizon, the silhouette of the space shuttle Endeavour is featured in this photo by an Expedition 22 crew member on board the International Space Station, as the shuttle approached for its docking on Feb. 9 during the STS-130 mission. Via the Bad Astronomy blog.