Nuit Blanche: Compressive Sensing This Week

Thursday, February 09, 2012

Compressive Sensing This Week

Here are some of the finds for this week in compressive sensing:

a course on CS at KTH
a connection between memristor and compressed sensing.
Sensor Networks ar CSIRO that seem to use compressive sensing even though I cannot see an actual reference to it.
a presentation on Concentration of Measure Inequalities for Compressive Toeplitz Matrices with Applications to Detection and System Identification by Borhan M. Sanandaji

First here is a paper of interest for someone interested in calibratiing a coded aperture imager:

LEARNING A CIRCULANT SENSING MATRIX by YANGYANG XU, WOTAO YIN, SUSAN CHEN, AND STANLEY OSHER. The abstract reads:

In signal acquisition, Toeplitz and circulant matrices are widely used as sensing operators since they can be easily or even naturally realized in various applications. For compressive sensing, recent work has used random Toeplitz and circulant sensing matrices and proved their e ciency in theory, by computer simulations, as well as through physical optical experiments. Motivated by recent work [7], we propose models to optimize a circulant sensint matrix. Given the dictionary of the signal(s) to be sensed, the optimized circulant sensing matrix is more e ective than a randomly generated circulant sensing matrix, and even a Gaussian random sensing matrix. In addition, we test learning the circulant sensing matrix and the nonparametric dictionary altogether and obtain even better performance on encoding and decoding test signals. We demonstrate these results using both synthetic sparse signals and real images.

ROBUST 1-BIT COMPRESSED SENSING AND SPARSE LOGISTIC REGRESSION: A CONVEX PROGRAMMING APPROACH by YANIV PLAN AND ROMAN VERSHYNIN. The abstract reads:

Abstract. This paper develops theoretical results regarding noisy 1-bit compressed sensing and

sparse binomial regression. We demonstrate that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We show that an s-sparse signal in Rn can be accurately estimated from m = O(s log(n=s)) single-bit measurements using a simple convex program. This remains true even if almost half of the measurements are randomly flipped. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(s log(n=s)) Bernoulli trials are sufficient to estimate a coe cient vector in Rn which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.

LOW-COMPLEXITY VIDEO COMPRESSION AND COMPRESSIVE SENSING by Salman Asif , Felix Fernandes, Justin Romberg. The abstract reads:

Compressive sensing (CS) provides a general signal acquisition framework that enables the reconstruction of sparse signals from a small number of linear measurements. To reduce video-encoder complexity, we present a CS-based video compression scheme. Modern video-encoder complexity arises mainly from the transformcoding and motion-estimation blocks. In our proposed scheme, we eliminate these blocks from the encoder, which achieves compression by merely taking a few linear measurements of each image in a video sequence. To guarantee stable reconstruction of the video sequence from only a few measurements, the decoder must effectively exploit the inherent spatial and temporal redundancies in a video sequence. To leverage these redundancies, we consider a motion-adaptive linear dynamical model for videos. Recovery process involves solving an `1-regularized optimization problem, which iteratively updates estimates for the video frames and motion within adjacent frames.

The poster is here.

FPGA-Accelerated 3D Reconstruction Using Compressive Sensing by Jianwen Chen, Jason Cong, Ming Yan and Yi Zou. The abstract reads:

The radiation dose associated with computerized tomography (CT) is signiﬁcant. Optimization-based iterative reconstruction approaches, e.g., compressive sensing provide ways to reduce the radiation exposure, without sacriﬁcing image quality. However, the computational requirement such algorithms is much higher than that of the conventional Filtered Back Projection (FBP) reconstruction algorithm. This paper describes an FPGA implementation of one important iterative kernel called EM, which is the major computation kernel of a recent EM+TV reconstruction algorithm. We show that a hybrid approach (CPU+GPU+FPGA) can deliver a better performance and energy efﬁciency than GPU-only solutions, providing 13X boost of throughput than a dual-core CPU implementation.

Implementation of Sub-Nyquist Sampling System Based on Compressed Sensing by Xiaoyan Zhuang, Yijiu Zhao, Li Wang, Houjun Wang. The abstract reads:

This paper describes the development of a sub-Nyquist sampling system that can digitize high-speed signals using a low-speed analog to digital converter (ADC). The system is implemented by a field programmable gate array (FPGA), and it is possible to make change to the equivalent sampling frequency according to the practical applications. As an application of the compressed sensing (CS) theory, for the spectrally sparse analog signal sampling, the proposed system has the potential to break though the constraint of Shannon theorem and the bandwidth barrier of state-of-the-art ADCs. Potential limitations of the applicability of CS-based sampling system are also discussed. Experimental results show that this sampling system is able to capture spectrally sparse analog signal at an equivalent sampling rate of 500 MHz while sampled at a rate of no more than 100 MHz physically.

DESIGN OF A COMPRESSIVE REMOTE IMAGING SYSTEM COMPENSATING A HIGHLY LIGHTWEIGHT ENCODING WITH A REFINED DECODING SCHEME by George Tzagkarakis, Arnaud Woiselle, Panagiotis Tsakalides and Jean-Luc Starck. The abstract reads:

Lightweight remote imaging systems have been increasingly used in surveillance and reconnaissance. Nevertheless, the limited power, processing and bandwidth resources is a major issue for the existing solutions, not well addressed by the standard video compression techniques. On the one hand, the MPEGx family achieves a balance between the reconstruction quality and the required bit-rate by exploiting potential intra- and interframe redundancies at the encoder, but at the cost of increased memory and processing demands. On the other hand, the M-JPEG approach consists of a computationally efﬁcient encoding process, with the drawback of resulting in much higher bit-rates. In this paper, we cope with the growing compression ratios, required for all remote imaging applications, by exploiting the inherent property of compressive sensing (CS), acting simultaneously as a sensing and compression framework. The proposed compressive video sensing (CVS) system incorporates the advantages of a very simple CS-based encoding process, while putting the main computational burden at the decoder combining the efﬁciency of a motion compensation procedure for the extraction of inter-frame correlations, along with an additional super-resolution step to enhance the quality of reconstructed frames. The experimental results reveal a signiﬁcant improvement of the reconstruction quality when compared with M-JPEG, at equal or even lower bit-rates.

Augmented ℓ1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm by Ming-Jun Lai, Wotao Yin. The abstract reads:

This paper studies the models of minimizing kxk1 +12αkxk22 where x is a vector, as well as those of minimizing kXk∗ +12αkXk2F where X is a matrix and kXk∗ and kXkF are the nuclear and Frobenius norms of X, respectively. We show that they can eﬃciently recover sparse vectors and low-rank matrices. In particular, they enjoy exact and stable recovery guarantees similar to those known for minimizing kxk1 and kXk∗ under the conditions on the sensing operator such as its null-space property, restricted isometry property, spherical section property, or “RIPless” property. To recover a (nearly) sparse vector x0, minimizing kxk1 +12αkxk2 returns (nearly) the same solution as minimizing kxk1 almost wheneverα ≥ 10kx0k∞. The same relation also holds between minimizing kXk∗ +12αkXk2F and minimizing kXk∗ for recovering a (nearly) low-rank matrix X0, if α ≥ 10kX0k2. Furthermore, we show that the linearized Bregman algorithm for minimizing kxk1 +12αkxk22 subject to Ax = b enjoys global linear convergence as long as a nonzero solution exists, and we give an explicit rate of convergence. The convergence property does not require a solution solution or any properties on A. To our knowledge, this is the best known global convergence result for ﬁrst-order sparse optimization algorithms.

Achievable Angles Between two Compressed Sparse Vectors Under Norm/Distance Constraints Imposed by the Restricted Isometry Property: A Plane Geometry Approach by Ling-Hua Chang, Jwo-Yuh Wu. The abstract reads:

The angle between two compressed sparse vectors subject to the norm/distance constraints imposed by the restricted isometry property (RIP) of the sensing matrix plays a crucial role in the studies of many compressive sensing (CS) problems. Assuming that (i) u and v are two sparse vectors separated by an angle thetha, and (ii) the sensing matrix Phi satisfies RIP, this paper is aimed at analytically characterizing the achievable angles between Phi*u and Phi*v. Motivated by geometric interpretations of RIP and with the aid of the well-known law of cosines, we propose a plane geometry based formulation for the study of the considered problem. It is shown that all the RIP-induced norm/distance constraints on Phi*u and Phi*v can be jointly depicted via a simple geometric diagram in the two-dimensional plane. This allows for a joint analysis of all the considered algebraic constraints from a geometric perspective. By conducting plane geometry analyses based on the constructed diagram, closed-form formulae for the maximal and minimal achievable angles are derived. Computer simulations confirm that the proposed solution is tighter than an existing algebraic-based estimate derived using the polarization identity. The obtained results are used to derive a tighter restricted isometry constant of structured sensing matrices of a certain kind, to wit, those in the form of a product of an orthogonal projection matrix and a random sensing matrix. Follow-up applications to three CS problems, namely, compressed-domain interference cancellation, RIP-based analysis of the orthogonal matching pursuit algorithm, and the study of democratic nature of random sensing matrices are investigated.

The road to deterministic matrices with the restricted isometry property by Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon, Percy Wong. The abstract reads:

The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.

Finite Frames for Sparse Signal Processing by Waheed U. Bajwa and Ali Pezeshki. The abstract reads:

Abstract Over the last decade, considerable progress has been made towards developing new signal processing methods to manage the deluge of data caused by advances in sensing, imaging, storage, and computing technologies. Most of these methods are based on a simple but fundamental observation. That is, highdimensional data sets are typically highly redundant and live on low-dimensional manifolds or subspaces. This means that the collected data can often be represented in a sparse or parsimonious way in a suitably selected ﬁnite frame. This observation has also led to the development of a new sensing paradigm, called compressed sensing, which shows that high-dimensional data sets can often be reconstructed, with high ﬁdelity, from only a small number of measurements. Finite frames play a central role in the design and analysis of both sparse representations and compressed sensing methods. In this chapter, we highlight this role primarily in the context of compressed sensing for estimation, recovery, support detection, regression, and detection of sparse signals. The recurring theme is that frames with small spectral norm and/or small worst-case coherence, average coherence, or sum coherence are well-suited for making measurements of sparse signals.

DICTIONARY LEARNING OF CONVOLVED SIGNALS by Daniele Barchiesi and Mark D. Plumbley. The abstract reads:

Assuming that a set of source signals is sparsely representable in a given dictionary, we show how their sparse recovery fails whenever we can only measure a convolved observation of them. Starting from this motivation, we develop a block coordinate descent method which aims to learn a convolved dictionary and provide a sparse representation of the observed signals with small residual norm. We compare the proposed approach to the K-SVD dictionary learning algorithm and show through numerical experiment on synthetic signals that, provided some conditions on the problem data, our technique converges in a ﬁxed number of iterations to a sparse representation with smaller residual norm

The implementation of the k-t FOCUSS web address is now here at: Dynamic MRI

New Update

The matlab source codes for cartesian k-t FOCUSS with ME/MC (motion estimation and compensation) and radial k-t FOCUSS are now downloadable. Please see "Download and File Description" below.

k-t FOCUSS

We developed k-t FOCUSS algorithm which is optimal from compressed sensing point of view. The basic concept of k-t FOCUSS starts from compressed sensing theory. According to compressed sensing theory, it is possible to reconstruct original signal from severely reduced sampling ratio which break Nyquist sampling limit. Therefore, this theory is getting huge interests in MRI area, because it is greatly required to reconstruct artifact free images from very sparse measurements to improve temporal resolution. There are some constraints to exploit this concept. From compressed sensing perspective, the aliasing pattern due to down sampling should incoherently appear. Therefore, the random sampling pattern is preferred. Furthermore, the original signal should be able to be sparsely transformed or compressed. And then, L1 minimization of the sparse signal is required. From these basic assumptions, we found that FOCUSS is a very suitable reconstruction algorithm. FOCUSS is originally designed to reconstruct sparse signal. Furthermore, L1 optimization is achieved by successively solving weighted L2 optimization problem, which can be easily implemented. From these advantages, we successfully developed k-t FOCUSS which reconstructs high spatio-temporal resolution of dynamic images such as a heart beating.

Finally, we have a workshop in Germany:

1st International Workshop on Compressed Sensing applied to Radar
Radar/SAR awaits Compressed SensingCompressed sensing (CS) techniques offer a framework for the detection and allocation of sparse signals with a reduced number of samples. Today, modern radar systems operate with high bandwidths - demanding high sample rates according to the Shannon-Nyquist theorem - and a huge number of single elements for phased array antennas. Often only a small amount of target parameters is the final output, raising the question, whether CS could be a good means to reduce data size, complexity, weight, power consumption and costs of radar systems. The amount of publications addressing the application of CS to radar is still limited, leaving open a number of questions.
ScopeThe scope of the proposed International Workshop is to bring experts of Compressed Sensing together to explore the state-of-the-art in development of such techniques in the different nations and for the different applications and to turn out its advantages or possible drawbacks compared to classical solutions. The workshop program will include invited speeches from distinguished experts as well as contributed talks.
Key aspectsContributions are expected on, but not limited to:

CS for pulse compression

CS for synthetic aperture radar (SAR)

CS for SAR tomography

CS for active and passive airspace surveillance

CS for moving target detection

CS for radar clutter suppression

CS for MIMO architectures

Hardware aspects of CS

CS for radiometry and sonar

Mathematical aspects of CS in radar

CS in statistical signal processing

ParticipantsThe workshop will provide a forum for experts, research engineers, and scientists working in the area of Compressive Sensing and Radar/SAR.
They get insight into the current research trends, innovative sensor technology, associated signal processing, and the subsequent data processing and transmission steps.
Veranstaltungsort
Bonn, Germany
Datum
14.5.2012 - 16.5.2012
Organisation
Fraunhofer-Institut für Hochfrequenzphysik und Radartechnik FHR
Sprache
Englisch
1st International Workshop on Compressed Sensing applied to Radar 1st International Workshop on Compressed Sensing applied to Radar(elserv.fhr.fraunhofer.de)

Image Credit: NASA/JPL/Space Science Institute
Full-Res: N00181212.jpg
N00181212.jpg was taken on February 06, 2012 and received on Earth February 07, 2012. The camera was pointing toward JANUS, and the image was taken using the CL1 and CL2 filters.