Nuit Blanche: This Week in Compressive Sensing

Tuesday, March 27, 2012

This Week in Compressive Sensing

Felix Krahmer gives a talk at MIT on Compressed sensing bounds via improved estimates for Rademacher chaos At Johns Hopkins, there is a project on a biomorphic Asynchronous Time-based Imaging Sensor (ATIS). But if you want to know more about compressive sensing, today we have also some pretty interesting papers. Enjoy!

First, when I met Yonina at MIA2012, she mentioned that this paper would be out. If you recall, this is a big controversy:, at least to the Science journalists who don't understand how Science really works: Designing and using prior data in Ankylography: Recovering a 3D object from a single diffraction intensity pattern by Eliyahu Osherovich, Oren Cohen, Yonina C. Eldar, Mordechai Segev The abstract reads:

We present a novel method for Ankylography: three-dimensional structure reconstruction from a single shot diffraction intensity pattern. Our approach allows reconstruction of objects containing many more details than was ever demonstrated, in a faster and more accurate fashion

On combinatorial approaches to compressed sensing by Abdolreza Abdolhosseini Moghadam and Hayder Radha. The abstract reads:

In this paper, we look at combinatorial algorithms for Compressed Sensing from a different perspective. We show that certain combinatorial solvers are in fact recursive implementations of convex relaxation methods for solving compressed sensing, under the assumption of sparsity for the projection matrix. We extend the notion of sparse binary projection matrices to sparse real-valued ones. We prove that, contrary to their binary counterparts, this class of sparse-real matrices has the Restricted Isometry Property. Finally, we generalize the voting mechanism (employed in combinatorial algorithms) to notions of isolation/alignment and present the required solver for real-valued sparse projection matrices based on such isolation/alignment mechanisms.

Combinatorial selection and debiasing ? I have also seen these here, even though the big idea here is gradient sketching: Sublinear Time, Approximate Model-based Sparse Recovery For All by Anastasios Kyrillidis, Volkan Cevher. The abstract reads:

We describe a probabilistic, {\it sublinear} runtime, measurement-optimal system for model-based sparse recovery problems through dimensionality reducing, {\em dense} random matrices. Specifically, we obtain a linear sketch $u\in \R^M$ of a vector $\bestsignal\in \R^N$ in high-dimensions through a matrix $\Phi \in \R^{M\times N}$ $(M less than N)$. We assume this vector can be well approximated by $K$ non-zero coefficients (i.e., it is $K$-sparse). In addition, the nonzero coefficients of $\bestsignal$ can obey additional structure constraints such as matroid, totally unimodular, or knapsack constraints, which dub as model-based sparsity. We construct the dense measurement matrix using a probabilistic method so that it satisfies the so-called restricted isometry property in the $\ell_2$-norm. While recovery using such matrices is measurement-optimal as they require the smallest sketch sizes $\numsam= O(\sparsity \log(\dimension/\sparsity))$, the existing algorithms require superlinear runtime $\Omega(N\log(N/K))$ with the exception of Porat and Strauss, which requires $O(\beta^5\epsilon^{-3}K(N/K)^{1/\beta}), ~\beta \in \mathbb{Z}_{+}, $ but provides an $\ell_1/\ell_1$ approximation guarantee. In contrast, our approach features $ O\big(\max \lbrace \sketch \sparsity \log^{O(1)} \dimension, ~\sketch \sparsity^2 \log^2 (\dimension/\sparsity) \rbrace\big) $ complexity where $ L \in \mathbb{Z}_{+}$ is a design parameter, independent of $\dimension$, requires a smaller sketch size, can accommodate model sparsity, and provides a stronger $\ell_2/\ell_1$ guarantee. Our system applies to "for all" sparse signals, is robust against bounded perturbations in $u$ as well as perturbations on $\bestsignal$ itself.

High Speed Compressed Sensing Reconstruction in Dynamic Parallel MRI Using Augmented Lagrangian and Parallel Processing by Cagdas Bilen, Yao Wang, Ivan Selesnick . The abstract reads:

Magnetic Resonance Imaging (MRI) is one of the fields that the compressed sensing theory is well utilized to reduce the scan time significantly leading to faster imaging or higher resolution images. It has been shown that a small fraction of the overall measurements are sufficient to reconstruct images with the combination of compressed sensing and parallel imaging. Various reconstruction algorithms has been proposed for compressed sensing, among which Augmented Lagrangian based methods have been shown to often perform better than others for many different applications. In this paper, we propose new Augmented Lagrangian based solutions to the compressed sensing reconstruction problem with analysis and synthesis prior formulations. We also propose a computational method which makes use of properties of the sampling pattern to significantly improve the speed of the reconstruction for the proposed algorithms in Cartesian sampled MRI. The proposed algorithms are shown to outperform earlier methods especially for the case of dynamic MRI for which the transfer function tends to be a very large matrix and significantly ill conditioned. It is also demonstrated that the proposed algorithm can be accelerated much further than other methods in case of a parallel implementation with graphics processing units (GPUs).

Combinatorial Selection and Least Absolute Shrinkage via the CLASH Algorithm by Anastasios Kyrillidis, Volkan Cevher. The abstract reads:

The least absolute shrinkage and selection operator (LASSO) for linear regression exploits the geometric interplay of the $\ell_2$-data error objective and the $\ell_1$-norm constraint to arbitrarily select sparse models. Guiding this uninformed selection process with sparsity models has been precisely the center of attention over the last decade in order to improve learning performance. To this end, we alter the selection process of LASSO to explicitly leverage combinatorial sparsity models (CSMs) via the combinatorial selection and least absolute shrinkage (CLASH) operator. We provide concrete guidelines how to leverage combinatorial constraints within CLASH, and characterize CLASH's guarantees as a function of the set restricted isometry constants of the sensing matrix. Finally, our experimental results show that CLASH can outperform both LASSO and model-based compressive sensing in sparse estimation.

Unified framework and algorithm for quantized compressed sensing by Zai Yang, Lihua Xie, and Cishen Zhang. The abstract reads:

Compressed sensing (CS) studies the recovery of high dimensional signals from their low dimensional linear measurements under a sparsity prior. This paper is focused on the CS problem with quantized measurements. There have been research results dealing with different scenarios including a single/multiple bits per measurement, noiseless/noisy environment, and an unsaturated/saturated quantizer. While the existing methods are only for one or more specific cases, this paper presents a framework to unify all the above mentioned scenarios of the quantized CS problem. Under the unified framework, a variational Bayesian inference based algorithm is proposed which is applicable to the signal recovery of different application cases. Numerical simulations are carried out to illustrate the improved signal recovery accuracy of the unified algorithm in comparison with state-of-the-art methods for both multiple and single bit CS problems.

Analysis of Sparse MIMO Radar by Thomas Strohmer, Benjamin Friedlander. The abstract reads:

We consider a multiple-input-multiple-output radar system and derive a theoretical framework for the recoverability of targets in the azimuth-range domain and the azimuth-range-Doppler domain via sparse approximation algorithms. Using tools developed in the area of compressive sensing, we prove bounds on the number of detectable targets and the achievable resolution in the presence of additive noise. Our theoretical findings are validated by numerical simulations.

Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms by Amir Beck, Yonina C. Eldar . The abstract reads:

This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinate-wise optimality. These conditions are then used to derive three numerical algorithms aimed at finding points satisfying the resulting optimality criteria: the iterative hard thresholding method and the greedy and partial sparse-simplex methods. The first algorithm is essentially a gradient projection method while the remaining two algorithms are of coordinate descent type. The theoretical convergence of these methods and their relations to the derived optimality conditions are studied. The algorithms and results are illustrated by several numerical examples.

Spread spectrum magnetic resonance imaging by Gilles Puy, Jose P. Marques, Rolf Gruetter, Jean-Philippe Thiran, Dimitri Van De Ville, Pierre Vandergheynst, Yves Wiaux. The abstract reads:

We propose a novel compressed sensing technique to accelerate the magnetic resonance imaging (MRI) acquisition process. The method, coined spread spectrum MRI or simply s2MRI, consists of pre-modulating the signal of interest by a linear chirp before random k-space under-sampling, and then reconstructing the signal with non-linear algorithms that promote sparsity. The effectiveness of the procedure is theoretically underpinned by the optimization of the coherence between the sparsity and sensing bases. The proposed technique is thoroughly studied by means of numerical simulations, as well as phantom and in vivo experiments on a 7T scanner. Our results suggest that s2MRI performs better than state-of-the-art variable density k-space under-sampling approaches

A differential equations approach to $l_1$-minimization with applications to array imaging by Miguel Moscoso, Alexei Novikov, George Papanicolaou, Lenya Ryzhik The abstract reads:

We present an ordinary differential equations approach to the analysis of algorithms for constructing $l_1$ minimizing solutions to underdetermined linear systems of full rank. It involves a relaxed minimization problem whose minimum is independent of the relaxation parameter. An advantage of using the ordinary differential equations is that energy methods can be used to prove convergence. The connection to the discrete algorithms is provided by the Crandall-Liggett theory of monotone nonlinear semigroups. We illustrate the effectiveness of the discrete optimization algorithm in some sparse array imaging problems.

Data Gathering with Compressive Sensing in Wireless Sensor Networks: An In-Network Computation Perspective by Haifeng Zheng, Xinbing Wang, Xiaohua Tian, Shilin Xiao.. The abstract reads:

In this paper, we investigate the fundamental performance limits of data gathering with compressive sensing (CS) in wireless sensor networks, in terms of both energy and latency. We consider two scenarios in which n nodes deliver data in centralized and distributed fashions, respectively. We take a new look at the problem of data gathering with compressive sensing from the perspective of in-network computation and formulate it as distributed function computation. We propose tree-based and gossip based computation protocols and characterize the scaling of energy and latency requirements for each protocol. The analytical results of computation complexity show that the proposed CS-based protocols are efﬁcient for the centralized fashion. In particular, we show the proposed CS-based protocol can save energy and reduce latency by a factor of (p n log n m ) when m = O(√n log n) in noiseless networks, respectively, where m is the number of random projections for signal recovery. We also show that our proposed protocol can save energy by a factor of (pnmplog n) compared with the traditional transmission approach when m = O(√nlog n) in noisy networks. For the distributed fashion, we show that the proposed gossip-based protocol can improve upon the scheme using randomized gossip, which needs fewer transmissions. Finally, simulations are also presented to demonstrate the effectiveness of our proposed protocols.

Energy and Latency Analysis for In-network Computation with Compressive Sensing in Wireless Sensor Networks by Haifeng Zheng, Shilin Xiao, Xinbing Wang, Xiaohua Tian The abstract reads:

In this paper, we study data gathering with compressive sensing from the perspective of in-network computation in random networks, in which n nodes are uniformly and independently deployed in a unit square area. We formulate the problem of data gathering to compute multiround random linear function. We study the performance of in-network computation with compressive sensing in terms of energy consumption and latency in centralized and distributed fashions. For the centralized approach, we propose a tree-based protocol for computing multiround random linear function. The complexity of computation shows that the proposed protocol can save energy and reduce latency by a factor of (√n= log n) for data gathering comparing with the traditional approach, respectively. For the distributed approach, we propose a gossip-based approach and study the performance of energy and latency through theoretical analysis. We show that our approach needs fewer transmissions than the scheme using randomized gossip.

Proof of Convergence and Performance Analysis for Sparse Recovery via Zero-point Attracting Projection by Xiaohan Wang, Yuantao Gu, Laming Chen. The abstract reads:

A recursive algorithm named Zero-point Attracting Projection (ZAP) is proposed recently for sparse signal reconstruction. Compared with the reference algorithms, ZAP demonstrates rather good performance in recovery precision and robustness. However, any theoretical analysis about the mentioned algorithm, even a proof on its convergence, is not available. In this work, a strict proof on the convergence of ZAP is provided and the condition of convergence is put forward. Based on the theoretical analysis, it is further proved that ZAP is non-biased and can approach the sparse solution to any extent, with the proper choice of step-size. Furthermore, the case of inaccurate measurements in noisy scenario is also discussed. It is proved that disturbance power linearly reduces the recovery precision, which is predictable but not preventable. The reconstruction deviation of $p$-compressible signal is also provided. Finally, numerical simulations are performed to verify the theoretical analysis.

Efficient Recovery of Block Sparse Signals via Zero-point Attracting Projection by Jingbo Liu, Jian Jin, Yuantao Gu. The abstract reads:

In this paper, we consider compressed sensing (CS) of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. An efficient algorithm, called zero-point attracting projection (ZAP) algorithm, is extended to the scenario of block CS. The block version of ZAP algorithm employs an approximate $l_{2,0}$ norm as the cost function, and finds its minimum in the solution space via iterations. For block sparse signals, an analysis of the stability of the local minimums of this cost function under the perturbation of noise reveals an advantage of the proposed algorithm over its original non-block version in terms of reconstruction error. Finally, numerical experiments show that the proposed algorithm outperforms other state of the art methods for the block sparse problem in various respects, especially the stability under noise.

Performance Analysis of $l_0$ Norm Constraint Least Mean Square Algorithm by Guolong Su, Jian Jin, Yuantao Gu, Jian Wang. The abstract reads:

As one of the recently proposed algorithms for sparse system identification, $l_0$ norm constraint Least Mean Square ($l_0$-LMS) algorithm modifies the cost function of the traditional method with a penalty of tap-weight sparsity. The performance of $l_0$-LMS is quite attractive compared with its various precursors. However, there has been no detailed study of its performance. This paper presents all-around and throughout theoretical performance analysis of $l_0$-LMS for white Gaussian input data based on some reasonable assumptions. Expressions for steady-state mean square deviation (MSD) are derived and discussed with respect to algorithm parameters and system sparsity. The parameter selection rule is established for achieving the best performance. Approximated with Taylor series, the instantaneous behavior is also derived. In addition, the relationship between $l_0$-LMS and some previous arts and the sufficient conditions for $l_0$-LMS to accelerate convergence are set up. Finally, all of the theoretical results are compared with simulations and are shown to agree well in a large range of parameter setting.

Retrieve Sparse Solution of Multiple-Measurement Vectors via Zero-point Attracting Projection by Yang You, Laming Chen, Yuantao Gu, Wei Feng, Hui Dai. The abstract reads:

A new sparse signal recovery algorithm for multiple-measurement vectors (MMV) problem is proposed in this paper. The sparse representation is iteratively drawn based on the idea of zero-point attracting projection (ZAP). In each iteration, the solution is first updated along the negative gradient direction of sparse constraint, and then projected to the solution space to satisfy the under-determined equation. A variable step size scheme is adopted further to accelerate the convergence as well as to improve the recovery accuracy. Numerical simulations demonstrate that the performance of the proposed algorithm exceeds the references in various aspects, as well as when applied to the Modulated Wideband Converter, where recovering MMV problem is crucial to its performance.

And finally, a PhD thesis: Numerical methods for phase retrieval by Eliyahu Osherovich. The abstract reads:

In this work we consider the problem of reconstruction of a signal from the magnitude of its Fourier transform, also known as phase retrieval. The problem arises in many areas of astronomy, crystallography, optics, and coherent diffraction imaging (CDI). Our main goal is to develop an efficient reconstruction method based on continuous optimization techniques. Unlike current reconstruction methods, which are based on alternating projections, our approach leads to a much faster and more robust method. However, all previous attempts to employ continuous optimization methods, such as Newton-type algorithms, to the phase retrieval problem failed. In this work we provide an explanation for this failure, and based on this explanation we devise a sufficient condition that allows development of new reconstruction methods---approximately known Fourier phase. We demonstrate that a rough (up to $\pi/2$ radians) Fourier phase estimate practically guarantees successful reconstruction by any reasonable method. We also present a new reconstruction method whose reconstruction time is orders of magnitude faster than that of the current method-of-choice in phase retrieval---Hybrid Input-Output (HIO). Moreover, our method is capable of successful reconstruction even in the situations where HIO is known to fail. We also extended our method to other applications: Fourier domain holography, and interferometry. Additionally we developed a new sparsity-based method for sub-wavelength CDI. Using this method we demonstrated experimental resolution exceeding several times the physical limit imposed by the diffraction light properties (so called diffraction limit).