CS: The long post of the week (Q&A, Blog Entries, Book, Preprints)

On LinkedIn we have the following questions:

• Tanish asks a question on the Complexity of SL0 algorithm
• Ma asks a question on How to simulate the image acquisition process

Maybe Tanish's question can be answered in the Theory CS Q&A,

On MetaOptimize Q&A, there is a long question on Compressed Sensing of Communities in a Network

Some blog entries got my attention recently:

Djalil

• Gaussians and matrix completion
• Souvenirs d’un évalué médiocre  (where we read the remarks of Bernard Beauzamy who I have mentioned in the EPH entries)

Alex

• The gist of the Laplace transform method for bounding eigenvalues of random matrices
• Positivity of a certain integral
• Comparing products of gaussian moments with one gaussian moment
• A Matrix Cauchy-Schwarz Inequality via Schur Complements
• Nasty matrix moment!
• Convergence of eigenvalues of sample covariance matrices
• Eigenvalues of sums of random matrices

Andrew

• A new efficient lossless compression algorithm

Bob

• A Briefly Annotated Timeline of Similarity Search in Time Series
• Paper of the Day (Po'D): Minimum Distances in High-Dimensional Musical Feature Spaces Edition
• Paper of the Day (Po'D): Audio Signal Representations for Indexing in the Transform Domain Edition
• Paper of the Day (Po'D): Sound Retrieval and Ranking Using Sparse Auditory Representations Edition
• EUSIPCO 2010 update

in the last entry one can read:

Martin Vetterli gave the most humorous talk, and at the same time trumpeted a very important message: Reproducible Research. If we as scientists put in a little extra effort to make the results and algorithms described in our publications clearly available, either by sufficient description, or by downloadable software, and if we make meaningful and sufficient comparisons with other algorithms where appropriate, then we will simultaneously improve the quality of our work, and increase our achievements. As an added bonus, the evidence suggests that research made reproducible is cited more, and more quickly than research that is not; and that once you have started making your research reproducible, the time it takes you the next time decreases. The idea isn't all roses though, as the vast majority of reproducible research is in the form of MATLAB code. I am lucky to have an institution license, but many others are not. There is also the fact that one day the various websites with code that we point to in our papers will not exist any longer.

Highlights are mine. With this state of the affairs and issues like the ones mentioned  in Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction?. by Xiaochuan Pan, Emil Sidky and Michael Vannier or the inability to run the wonderful  numerical tours of Gabriel Peyre if you don't have a matlab licence or cannot install Scilab (on the iPad for instance). I am wondering and probably starting to implement a solution that might be answering some of these issues...Stay tuned....

In a different direction, a book entitled:GPU Computing Gems Edited by Wen-mei W Hwu is coming out in December and will feature a chapter on compressed sensing reconstruction:

Chapter 45: ℓ1 Minimization in ℓ1-SPIRiT Compressed Sensing MRI Reconstruction

I have added it to the Nuit Blanche - Amazon Store in case you want to order it.

Here is a list of papers that showed up on my radar screen for your enjoyment:

Hard thresholding pursuit: an algorithm for Compressive Sensing by Simon Foucart. The abstract reads:

We introduce a new iterative algorithm to find sparse solutions of underdetermined linear systems. The algorithm, a simple combination of the Iterative Hard Thresholding algorithm and of the Compressive Sampling Matching Pursuit or Subspace Pursuit algorithms, is called Hard Thresholding Pursuit. We study its general convergence, and notice in particular that only a finite number of iterations are required. We then show that, under a certain condition on the restricted isometry constant of the matrix of the system, the Hard Thresholding Pursuit algorithm indeed finds all s-sparse solutions. This condition, which reads \delta_3s < 1=p3, is heuristically better than the sufficient conditions currently available for other Compressive Sensing algorithms. It applies to fast versions of the algorithm, too, including the Iterative Hard Thresholding algorithm. Stability with respect to sparsity defect and robustness with respect to measurement error are also guaranteed under the condition \delta_3s < 1=p3. We conclude with some numerical experiments to demonstrate the good empirical performance and the low complexity of the Hard Thresholding Pursuit algorithm.

Explicit constructions of RIP matrices and related problems by Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin and Denka Kutzarova.. The abstract reads:

We give a new explicit construction of $n imes N$ matrices satisfying the Restricted Isometry Property (RIP). Namely, for some c \gt 0, large N and any n satisfying N^{1-c} \lt n \lt N, we construct RIP matrices of order k^{1/2+c}. This overcomes the natural barrier k=O(n^{1/2}) for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure. We also give a construction of sets of n complex numbers whose k-th moments are uniformly small for 1le kle N (Turan's power sum problem), which improves upon known explicit constructions when (log N)^{1+o(1)} le nle (log N)^{4+o(1)}. This latter construction produces elementary explicit examples of n by N matrices that satisfy RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (log N)^{1+o(1)} le nle (log N)^{5/2+o(1)}.

Collaborative Spectrum Sensing from Sparse Observations in Cognitive Radio Networks by Jia Meng, Wotao Yin, Husheng Li, Ekram Hossain, Zhu Han. The abstract reads:

Spectrum sensing, which aims at detecting spectrum holes, is the precondition for the implementation of cognitive radio (CR). Collaborative spectrum sensing among the cognitive radio nodes is expected to improve the ability of checking complete spectrum usage. Due to hardware limitations, each cognitive radio node can only sense a relatively narrow band of radio spectrum. Consequently, the available channel sensing information is far from being sufficient for precisely recognizing the wide range of unoccupied channels. Aiming at breaking this bottleneck, we propose to apply matrix completion and joint sparsity recovery to reduce sensing and transmitting requirements and improve sensing results. Specifically, equipped with a frequency selective filter, each cognitive radio node senses linear combinations of multiple channel information and reports them to the fusion center, where occupied channels are then decoded from the reports by using novel matrix completion and joint sparsity recovery algorithms. As a result, the number of reports sent from the CRs to the fusion center is significantly reduced. We propose two decoding approaches, one based on matrix completion and the other based on joint sparsity recovery, both of which allow exact recovery from incomplete reports. The numerical results validate the effectiveness and robustness of our approaches. In particular, in small-scale networks, the matrix completion approach achieves exact channel detection with a number of samples no more than 50% of the number of channels in the network, while joint sparsity recovery achieves similar performance in large-scale networks.

Wireless Tomography, Part III: Compressed Sensing for Ultra-wideband Signals by Peng Zhang, Robert C. Qiu. The abstract reads:

This is Part III of the wireless tomography three paper series.Wireless tomography is related to wireless communications in that it requires the channel recovery between different waveforms at transmit and receive, as well as multiple-input multiple-output (MIMO) communication system. According to the pulse propagation mechanisms of reflection and diffraction, ultra-wideband (UWB) waveforms suffer pulse distortion. Distorted pulses will overlap and therefore increases the sampling rate for accurate UWB channel recovery. Thanks to the recent progresses in sampling theory and radio propagation theory, we are able to propose a compressed sensing (CS) based UWB channel recovery method considering pulse distortion. The concept has been demonstrated through simulations. The sampling rate is as low as 2 Gsps, compared with the Nyquist rate of 50 Gsps. A CS based 2 × 2 MIMO communication system is also proposed and simulated. The communication problem is modeled as CS problem, and further reduce sampling rate required at the receiver.

Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma by Yonina Eldar, and Deanna Needell. The abstract reads: 

The Kaczmarz method is an algorithm for finding the solution to an overdetermined system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson-Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.

Demonstration of real-time spectrum sensing for cognitive radio by Zhe Chen, Nan Guo, and Robert C. Qiu. The abstract reads:

The requirement for real-time processing indeed poses challenges on implementing spectrum sensing algorithms. Trade-off between the complexity and the effectiveness of spectrum sensing algorithms should be taken into consideration. In this paper, a fast Fourier transform based spectrum sensing algorithm, whose decision variable is independent of noise level, is introduced. A small form factor software defined radio development platform is employed to implement a spectrum sensing receiver with the proposed algorithm. To our best knowledge, it is the first time that real-time spectrum sensing on hardware platform with controllable primary user devices is demonstrated.

Airborne Radar STAP using Sparse Recovery of Clutter Spectrum by Ke Sun, Hao Zhang, Gang Li, Huadong Meng, Xiqin Wang. The abstract reads:

Space-time adaptive processing (STAP) is an effective tool for detecting a moving target in spaceborne or airborne radar systems. Statistical-based STAP methods generally need sufficient statistically independent and identically distributed (IID) training data to estimate the clutter characteristics. However, most actual clutter scenarios appear only locally stationary and lack sufficient IID training data. In this paper, by exploiting the intrinsic sparsity of the clutter distribution in the angle-Doppler domain, a new STAP algorithm called SR-STAP is proposed, which uses the technique of sparse recovery to estimate the clutter space-time spectrum. Joint sparse recovery with several training samples is also used to improve the estimation performance. Finally, an effective clutter covariance matrix (CCM) estimate and the corresponding STAP filter are designed based on the estimated clutter spectrum. Both the Mountaintop data and simulated experiments have illustrated the fast convergence rate of this approach. Moreover, SR-STAP is less dependent on prior knowledge, so it is more robust to the mismatch in the prior knowledge than knowledge-based STAP methods. Due to these advantages, SR-STAP has great potential for application in actual clutter scenarios.