CS: The other long entry of the week. DT Phase transition, Finding pulars in a haystack.

Echoing these entries on Precise Undersampling Theorems and the Donoho-Tanner border crossing, Jared Tanner mentioned to me that he has made available forms for these phase transitions and the bounds on restricted isometry constants available on the Compressed Sensing group at University of Edinburgh. From the Restricted Isometry Constants page, the description starts with:

Many of the compressed sensing recovery algorithms (decoders) are guaranteed to recover the sparsest solution to an underdetermined system of equations y = Ax provided the matrix A (encoder) acts sufficiently close to an isometry on sparse vectors. Let
χN(k) := {x ∈ RN : ||x||l0 \le k} ,
where ||x||l0 counts the number of nonzeros in x.

Let A be of size n × N with n \lt N. The Lower and Upper Restricted Isometry Constants (RICs) of A are defined as:
L(k, n, N; A) := minc \ge 0 subject to (1 − c) ||x||22 \le ||Ax||22 for all x ∈ χN(k)
U(k, n, N; A) := minc \ge 0 subject to (1 + c) ||x||22 \ge ||Ax||22 for all x ∈ χN(k)
Gaussian matrices have the smallest known bound, with the tightest current bound provided in Compressed Sensing: How sharp is the RIP?, by Jeffrey D. Blanchard, Coralia Cartis, and Jared Tanner.

Update: Improved bounds for Gaussian matrices were recently published in Improved Restricted Isometry Constant Bounds for Gaussian Matrices by Bubacarr Bah and Jared Tanner. The below webforms will be updated to include these improved bounds soon.

Let ρn := k/n and δn := n/N be the compressed sensing over and under sampling ratios, respectively. Fix ε \gt 0, as n → ∞ with ρn → ρ ∈ (0,1) and δn → δ ∈ (0,1).

Prob(L(k, n, N; A) \lt L(δ, ρ) + ε) → 1 and Prob(U(k, n, N; A) \lt U(δ, ρ) + ε) → 1

Below are plots of these bounds, and functions which will calculate these bound for your choice of ρ and δ.

and Phase Transitions of the Regular Polytopes and Cone, the description starts with:

Some sparse approximation questions can be modelled exactly through convex polytopes. When this is possible, their analysis can provide Precise Undersampling Theorems (by Donoho and Tanner). These results are cast in terms of the:

Oversampling ratio: δ =n/N,

Undersampling ratio: ρ =k/n

where k is the sparsity of the vector, n is the number of measurements and N is the length of the vector measured.

This form interpolates the values of the strong and weak phase transitions of the orthant and three regular polytopes: the simplex, crosspolytope, and hypercube as well as the orthant. For ρ below a strong phase transition, the phenomenon is true for all k-sparse vectors, and below a weak phase transition, the phenomenon is true for most k-sparse vectors. The crosspolytope models l1-regularization, the simplex models l1-regularization with nonnegativity (or other sparsity constraints) and uniqueness of nonnegative vectors when the average of the signal is also measured, the orthant models uniqueness of nonnegative vectors from mean-zero measurement matrices, and the hypercube models bound constrainsts where k is the number of entries in the vector which are not at the bounds.

Once you click on these pages, you have the ability to input your parameters and estimate the bounds for the RIC or the phase transitions. Jared has also made available some mat file for the transition page. Thank you Jared .

In a different direction, Gonzalo Vazquez Vilar's SpectralHole, a blog focused on Cognitive Radio has a new entry on ICASSP Game Theory.

While reading Andrew's blog, I came across the following description on how to find a pulsar. It looks like there is a lot of multiplexing and de-multiplexing operations in this process. The amount of data generated by the survey is so large that it takes a long time to find interesting pulsars drowning in 134 TB of data. So the question becomes, could a series of random projections of these signals and a smashed filter approach speed up this quest tremendously ? or could a sparse FFT help in reducing the load of performing these giant FFTs in the first place ? Time will tell.

This week, I have been accumulating a series of papers related to Compressive sensing in some shape or another, here we go:

Universal Sparse Modeling by Ignacio Ramirez and Guillermo Sapiro. The abstract reads:

Sparse data models, where data is assumed to be well represented as a linear combination of a few elements from a dictionary, have gained considerable attention in recent years, and their use has led to state-of-the-art results in many signal and image processing tasks. It is now well understood that the choice of the sparsity regularization term is critical in the success of such models. In this work, we use tools from information theory, and in particular universal coding theory, to propose a framework for designing sparsity regularization terms which have several theoretical and practical advantages when compared to the more standard l0 or l1 ones, and which lead to improved coding performance and accuracy in reconstruction and classification tasks. We also report on further improvements obtained by imposing low mutual coherence and Gram matrix norm on the corresponding learned dictionaries. The presentation of the framework and theoretical foundations is complemented with examples in image denoising and classification.

Low Rate Sampling of Pulse Streams with Application to Ultrasound Imaging by Ronen Tur, Yonina C. Eldar, Zvi Friedman. The abstract reads:

Signals comprised of a stream of short pulses appear in many applications including bio-imaging, radar, and ultrawideband communication. Recently, a new framework, referred to as finite rate of innovation, has paved the way to low rate sampling of such pulses by exploiting the fact that only a small number of parameters per unit time are needed to fully describe these signals. Unfortunately, for high rates of innovation, existing approaches are numerically unstable. In this paper we propose a general sampling approach which leads to stable recovery even in the presence of many pulses. We begin by deriving a condition on the sampling kernel which allows perfect reconstruction of periodic streams of pulses from a minimal number of samples. This extends previous work which assumes that the sampling kernel is an ideal low-pass filter. A compactly supported class of filters, satisfying the mathematical condition, is then introduced, leading to a sampling framework based on compactly supported kernels. We then extend our periodic solution to finite and infinite streams, and show that our method is numerically stable even for a large number of pulses per unit time. High noise robustness is demonstrated as well when the time delays are sufficiently separated. Finally, we apply our results to ultrasound imaging data, and show that our techniques result in substantial rate reduction with respect to traditional ultrasound sampling schemes.

Fishing in Poisson streams: focusing on the whales, ignoring the minnows by Maxim Raginsky, Sina Jafarpour, Rebecca Willett, Robert Calderbank. The abstract reads:

This paper describes a low-complexity approach for reconstructing average packet arrival rates and instantaneous packet counts at a router in a communication network, where the arrivals of packets in each flow follow a Poisson process. Assuming that the rate vector of this Poisson process is sparse or approximately sparse, the goal is to maintain a compressed summary of the process sample paths using a small number of counters, such that at any time it is possible to reconstruct both the total number of packets in each flow and the underlying rate vector. We show that these tasks can be accomplished efficiently and accurately using compressed sensing with expander graphs. In particular, the compressive counts are a linear transformation of the underlying counting process by the adjacency matrix of an unbalanced expander. Such a matrix is binary and sparse, which allows for efficient incrementing when new packets arrive. We describe, analyze, and compare two methods that can be used to estimate both the current vector of total packet counts and the underlying vector of arrival rates.

Robust video denoising using low rank matrix completion by Hui Ji, Chaoqiang Liu, Zuowei Shen and Yuhong Xu. The abstract reads:

Most existing video denoising algorithms assume a single statistical model of image noise, e.g. additive Gaussian white noise, which often is violated in practice. In this paper, we present a new patch-based video denoising algorithm capable of removing serious mixed noise from the video data. By grouping similar patches in both spatial and temporal domain, we formulate the problem of removing mixed noise as a low-rank matrix completion problem, which leads to a denoising scheme without strong assumptions on the statistical properties of noise. The resulting nuclear norm related minimization problem can be efficiently solved by many recent developed methods. The robustness and effectiveness of our proposed denoising algorithm on removing mixed noise, e.g. heavy Gaussian noise mixed with impulsive noise, is validated in the experiments and our proposed approach compares favorably against a few state-of-art denoising algorithms.

An Efficient Numerical Method for General Lp Regularization in Fluorescence Molecular Tomography by Jean-Charles Baritaux, Kai Hassler, Michael Unser. The abstract reads:

Reconstruction algorithms for fluorescence tomography have to address two crucial issues : (i) the ill-posedness of the reconstruction problem, (ii) the large scale of numerical problems arising from imaging of three dimensional samples. Our contribution is the design and implementation of a reconstruction algorithm that incorporates general Lp regularization (p \ge 1). The originality of this work lies in the application of general Lp constraints to fluorescence tomography, combined with an efficient matrix-free strategy that enables the algorithm to deal with large reconstruction problems at reduced memory and computational costs.

In the experimental part, we specialize the application of the algorithm to the case of sparsity promoting constraints (L1). We validate the adequacy of L1 regularization for the investigation of phenomena that are well described by a sparse model, using data acquired during phantom experiments.

Energy Efficient Sampling for Event Detection in Wireless Sensor Networks by Zainul Charbiwala, Younghun Kim, Sadaf Zahedi, Jonathan Friedman, Mani B. Srivastava. The abstract reads:

Compressive Sensing (CS) is a recently developed mechanism that allows signal acquisition and compression to be performed in one inexpensive step so that the sampling process itself produces a compressed version of the signal. This significantly improves systemic energy efficiency because the average sampling rate can be considerably reduced and explicit compression eliminated. In this paper, we introduce a modifi cation to the canonical CS recovery technique that enables even higher gains for event detection applications. We show a practical implementation of this compressive detection with energy constrained wireless sensor nodes and quantify the gains accrued through simulation and experimentation.

Scalable Tensor Factorizations with Missing Data by Evrim Acar, Tamara G. Kolda, Daniel M. Dunlavy, and Morten Mørup. The abstract reads:

The problem of missing data is ubiquitous in domains such as biomedical signal processing, network traffic analysis, bibliometrics, social network analysis, chemometrics, computer vision, and communication networks|all domains in which data collection is subject to occasional errors. Moreover, these data sets can be quite large and have more than two axes of variation, e.g., sender, receiver, time. Many applications in those domains aim to capture the underlying latent structure of the data; in other words, they need to factorize data sets with missing entries. If we cannot address the problem of missing data, many important data sets will be discarded or improperly analyzed. Therefore, we need a robust and scalable approach for factorizing multi-way arrays (i.e., tensors) in the presence of missing data. We focus on one of the most well-known tensor factorizations, CANDECOMP/PARAFAC (CP), and formulate the CP model as a weighted least squares problem that models only the known entries. We develop an algorithm called CP-WOPT (CP Weighted OPTimization) using a rst-order optimization approach to solve the weighted least squares problem. Based on extensive numerical experiments, our algorithm is shown to successfully factor tensors with noise and up to 70% missing data. Moreover, our approach is signi cantly faster than the leading alternative and scales to larger problems. To show the real-world usefulness of CP-WOPT, we illustrate its applicability on a novel EEG (electroencephalogram) application where missing data is frequently encountered due to disconnections of electrodes.

A video of Tammy Kolda on Scalable Tensor Factorizations with Incomplete Data can be found here ( or downloaded here (197 MB) (the videos are also here)

Credit: ESA / DLR / FU Berlin (G. Neukum) / Emily Lakdawalla, the Far side of Phobos taken this week.