Monday, January 11, 2010

CS: Today's long entry.

The results of the iPhone/iPod Touch poll so far (see below). For the person who hit the $500 mark, please get in touch with me, I need toknow if you are serious.


I do not own an iPhone / iPod Touch 43 48%

Free 32 36%

0.99 $ 7 8%

9.99 $ 2 2%

500 $ (cost of the actual app) 1 1%

49.99 $ (as information rich as Wolfram's app) 1 1%

19.99 $ 1 1%

4.99 $ 1 1%

1.99 $ 1 1%

2.99 $ 0 0%

1000 $ (if there are takers, I'll make a similar one for free) 0 0%




The recent theory of Compressed Sensing (Candes, Tao & Romberg, 2006, and Donoho, 2006) states that a signal, e.g. a sound record or an astronomical image, can be sampled at a rate much smaller than what is commonly prescribed by Shannon-Nyquist. The sampling of a signal can indeed be performed as a function of its "intrinsic dimension" rather than according to its cut off frequency. This chapter sketches the main theoretical concepts surrounding this revolution in sampling theory. We emphasize also its deep affiliation with the concept of "sparsity", now ubiquitous in modern signal processing. The end of this chapter explains what interesting e ffects this theory may have on some Compressive Imaging applications.

I like the 8th paragraph entitled Conclusion and the "Science 2.0" Effect which lists other blogs than NB as sources of info on CS. Thanks guys! More precisely, I noted the following at the end:
...Let us conclude this chapter by one important, and somehow sociologic", observation. The Compressed Sensing paradigm is born in what is often called the Science 2.0." evolution. This term represents a real boom in the exchange of information in the scienti fic community, a byproduct of the steady Internet development. This recent trend take several forms. It consists for instance in the online publication of preprint before their acceptance in scienti fic journals (through ArXiv [68] or directly on personal homepages), or, more remarkably, in the writing of scienti c blogs regularly fed by researchers and often the source of fruitful online discussions with other scientists. Another aspect of this trend is the free exchange of numerical codes guaranteeing the reproducibility of the results....
Kronecker products used for compressive measurement systems promise to reduce substantially the size of measurement systems, hence I am always anxious to see some development in that area. Here is today's: Kronecker Compressive Sensing by Marco Duarte, and Richard Baraniuk. The abstract reads:
Compressive sensing (CS) is an emerging approach for acquisition of signals having a sparse or compressible representation in some basis. While the CS literature has mostly focused on problems involving 1-D signals and 2-D images, many important applications involve signals that are multidimensional; in this case, CS works best with representations that encapsulate the structure of such signals in every dimension. We propose the use of Kronecker product matrices in CS for two purposes. First, we can use such matrices as sparsifying bases that jointly model the different types of structure present in the signal. Second, the measurement matrices used in distributed settings can be easily expressed as Kronecker product matrices. The Kronecker product formulation in these two settings enables the derivation of analytical bounds for sparse approximation of multidimensional signals and CS recovery performance as well as a means to evaluate novel distributed measurement schemes.
from that paper, I noted the reference to this earlier paper: A MULTISCALE FRAMEWORK FOR COMPRESSIVE SENSING OF VIDEO by Jae Young Park and Michael B. Wakin. The abstract reads:
Compressive Sensing (CS) allows the highly efficient acquisition of many signals that could be difficult to capture or encode using conventional methods. From a relatively small number of random measurements, a high-dimensional signal can be recovered if it has a sparse or near-sparse representation in a basis known to the decoder. In this paper, we consider the application of CS to video signals in order to lessen the sensing and compression burdens in single- and multi-camera imaging systems. In standard video compression, motion compensation and estimation techniques have led to improved sparse representations that are more easily compressible; we adapt these techniques for the problem of CS recovery. Using a coarse-to-fine reconstruction algorithm, we alternate between the tasks of motion estimation and motion-compensated wavelet-domain signal recovery. We demonstrate that our algorithm allows the recovery of video sequences from fewer measurements than either frame-by frame or inter-frame difference recovery methods.
In a different direction, since reconstruction is expensive, one is always trying to find out if some evaluation of features can be made while the measurements are still compressed. Here is some work in that direction Motion Estimation from Compressed Linear Measurements by Thirumalai, Vijayaraghavan and Pascal Frossard. the abstract reads:
This paper presents a novel algorithm for computing the relative motion between images from compressed linear measurements. We propose a geometry based correlation model that describes the relative motion between images by translational motion of visual features. We focus on the problem of estimating the motion field from a reference image and a highly compressed image given by means of random projections, which are further quantized and entropy coded. We capture the most prominent visual features in the reference image using geometric basis functions. Then, we propose a regularized optimization problem for estimating the corresponding features in the compressed image, and eventually the dense motion field is generated from the local transform of the geometric features. Experimental results show that the proposed scheme defines an accurate motion field. In addition, when the motion field is used for image prediction, the resulting rate-distortion (RD) performance becomes better than the independent coding solution based on JPEG-2000, which demonstrates the potential of the proposed scheme for distributed coding algorithms.

The ease of image storage and transmission in modern applications would be unfeasible without compression, which converts high resolution images into a relatively small set of significant transform coefficients. Due to the specific content of many real-world images they are highly sparse in an appropriate orthonormal basis. The inherent property of compressed sensing (CS) theory working simultaneously as a sensing and compression protocol, using a small subset of random incoherent projection coefficients, enables a potentially significant reduction in the sampling and computation costs of images favoring its use in real-time applications which do not require an excellent reconstruction performance. In this paper, we develop a Bayesian CS (BCS) approach for obtaining highly sparse representations of images based on a set of noisy CS measurements, where the prior belief that the vector of projection coefficients should be sparse is enforced by fitting directly its prior probability distribution by means of a Gaussian Scale Mixture (GSM). The experimental results show that our proposed method, when compared with norm-based constrained optimization algorithms, maintains the reconstruction performance, in terms of the reconstruction error and the PSNR, while achieving an increased sparsity using much less basis functions.


Traditional bearing estimation techniques perform Nyquist-rate sampling of the received sensor array signals and as a result they require high storage and transmission bandwidth resources. Compressed sensing (CS) theory provides a new paradigm for simultaneously sensing and compressing a signal using a small subset of random incoherent projection coefficients, enabling a potentially significant reduction in the sampling and computation costs. In this paper, we develop a Bayesian CS (BCS) approach for estimating target bearings based on multiple noisy CS measurement vectors, where each vector results by projecting the received source signal on distinct over-complete dictionaries. In addition, the prior belief that the vector of projection coefficients should be sparse is enforced by fitting directly the prior probability distribution with a Gaussian Scale Mixture (GSM) model. The experimental results show that our proposed method, when compared with norm-based constrained optimization CS algorithms, as well as with single-measurement BCS methods, improves the reconstruction performance in terms of the detection error, while resulting in an increased sparsity.


MODIFIED COMPRESSIVE SENSING FOR REAL-TIME DYNAMIC MR IMAGING by Wei Lu and Namrata Vaswani. The abstract reads:
In this work, we propose algorithms to recursively and causally reconstruct a sequence of natural images from a reduced number of linear projection measurements taken in a domain that is “incoherent” with respect to the image’s sparsity basis (typically wavelet) and demonstrate their application in real-timeMR image reconstruction. For a static version of the above problem, Compressed Sensing (CS) provides a provably exact and computationally efficient solution. But most existing solutions for the actual problem are either offline and non-causal or cannot compute an exact reconstruction (for truly sparse signal sequences), except using as many measurements as those needed for CS. The key idea of our proposed solution (modified-CS) is to design a modification of CS when a part of the support set is known (available from reconstructing the previous image). We demonstrate the exact reconstruction property of modified-CS on full-size image sequences using much fewer measurements than those required for CS. Greatly improved performance over existing work is demonstrated for approximately sparse signals or noisy measurements.
In this paper we investigate the efficiency of the Orthogonal Matching Pursuit (OMP) for random dictionaries. We concentrate on dictionaries satisfying the Restricted Isometry Property. We also introduce a stronger Homogenous Restricted Isometry Property which we show is satisfied with overwhelming probability for random dictionaries used in compressed sensing. For these dictionaries we obtain upper estimates for the error of approximation by OMP in terms of the error of the best n-term approximation (Lebesgue-type inequalities). We also present and discuss some open problems about OMP. This is a development of recent results obtained by D.L. Donoho, M. Elad and V.N. Temlyakov.

We propose an ℓ1 criterion for dictionary learning for sparse signal representation. Instead of directly searching for the dictionary vectors, our dictionary learning approach identifies vectors that are orthogonal to the subspaces in which the training data concentrate. We study conditions on the coefficients of training data that guarantee that ideal normal vectors deduced from the dictionary are local optima of the criterion. We illustrate the behavior of the criterion on a 2D example, showing that the local minima correspond to ideal normal vectors when the number of training data is sufficient. We conclude by describing an algorithm that can be used to optimize the criterion in higher dimension.

This paper develops a new class of algorithms for signal recovery in the distributed compressive sensing (DCS) framework. DCS exploits both intra-signal and inter-signal correlations through the concept of joint sparsity to further reduce the number of measurements required for recovery. DCS is well suited for sensor network applications due to its universality, computational asymmetry, tolerance to quantization and noise, and robustness to measurement loss. In this paper we propose recovery algorithms for the sparse common and innovation joint sparsity model. Our approach leads to a class of efficient algorithms, the Texas Hold ’Em algorithms, which are scalable both in terms of communication bandwidth and computational complexity.
This is the latest version of Best Basis Compressed Sensing by Gabriel Peyré. The abstract reads:
This paper proposes a best basis extension of compressed sensing recovery. Instead of regularizing the compressed sensing inverse problem with a sparsity prior in a fixed basis, our framework makes use of sparsity in a tree-structured dictionary of orthogonal bases. A new iterative thresholding algorithm performs both the recovery of the signal and the estimation of the best basis. The resulting reconstruction from compressive measurements optimizes the basis to the structure of the sensed signal. Adaptivity is crucial to capture the regularity of complex natural signals. Numerical experiments on sounds and geometrical images indeed show that this best basis search improves the recovery with respect to fixed sparsity priors.

while most recent version of Compressed Genotyping is out.

In the area of sparsity, here are the following papers:

An image representation framework based on structured sparsemodel selection is introduced in this work. The corresponding modeling dictionary is comprised of a family of learned orthogonal bases. For an image patch, a model is first selected fromthis dictionary through linear approximation in a best basis, and the signal estimation is then calculated with the selected model. The model selection leads to a guaranteed near optimal denoising estimator. The degree of freedom in the model selection is equal to the number of the bases, typically about 10 for natural images, and is significantly lower than with traditional overcomplete dictionary approaches, stabilizing the representation. For an image patch of size √N ×√N, the computational complexity of the proposed framework is O(N2), typically 2 to 3 orders of magnitude faster than estimation in an overcomplete dictionary. The orthogonal bases are adapted to the image of interest and are computed with a simple and fast procedure. State-of-the-art results are shown in image denoising, deblurring, and inpainting.

We propose to evaluate our sparsity driven people localization framework on crowded complex scenes. The problem is recast as a linear inverse problem. It relies on deducing an occupancy vector, i.e. the discretized occupancy of people on the ground, from the noisy binary silhouettes observed as foreground pixels in each camera. This inverse problem is regularized by imposing a sparse occupancy vector, i.e. made of few non- zero elements, while a particular dictionary of silhouettes linearly maps these non-empty grid locations to the multiple silhouettes viewed by the cameras network. The proposed approach is (i) generic to any scene of people, i.e. people are located in low and high density crowds, (ii) scalable to any number of cameras and already working with a single camera, (iii) unconstraint on the scene surface to be monitored. Qualitative and quantitative results are presented given the PETS 2009 dataset. The proposed algorithm detects people in high density crowd, count and track them given severely degraded foreground silhouettes.

Saturday, January 09, 2010

CS: LSH, Photon Sieves, Fieldstream

Sergey Ten asks the following question on Twitter:

Are there connection between locality sensitive hashing and compressed sensing ? (RIP)

My take is that one could use random projections to reduce a very high dimensional dataset onto some lower dimensional manifold and then probably use LSH to evaluate how these reduced data are connected to each other. Piotr Indyk on his LSH page makes a different case in the presentation entitled: Near-Optimal Hashing Algorithms for Approximate Near(est) Neighbor Problem, where the following slide appear:


On a related item, Piotr also taught some course at Rice last year, the list of presentation can be found below:

These are the lecture notes for a short course "Streaming etc.", given at Rice University in Spring'09.


Laurent Jacques mentioned to me the use of coded aperture to perform X-ray focusing. As you recall Gerry Skinner, a specialist in coded aperture, does not like coded aperture for imaging x-rays and this is the reason he is looking into Fresnel lenses for x-rays. As it turns out a way of providing additional focus for x-rays is by drilling holes in Fresnel lenses.


Instead of just using Fresnel Zone plates, they drill a (random ?) distribution of points on them:
Light passing a circular pinhole produces a diffraction pattern of concentric rings of decreasing width with increasing radius. If light is passed through a mask made up of the same pattern of rings a focus is formed. These Fresnel zone plates are used to focus soft X-rays where conventional optics fail because of strong absorption of all materials in this spectral region.

The ultimate resolution of a Fresnel zone plate is determined by the width of the outermost zone. The focal spot is surrounded by rings of intensity (secondary maxima) that blur the images obtained in X-ray microscopy and scanning spectroscopy.

These limitations can be overcome by using a large number of appropriately distributed pinholes instead of rings as the diffracting elements. To obtain a distinct first-order focus, the pinholes have to be positioned such that the optical path length from the source via the center of the pinholes to the focal point is an integral number of wavelengths.




Furthermore, with photon sieves, the unwanted ring-like secondary maxima generated by zone plates can be suppressed. For a zone plate each ring contributes equally to the amplitude in the focus. This contribution drops abruptly to zero beyond the outermost ring which leads to strong intensity oscillations in the diffraction pattern. With a photon sieve the number of pinholes per ring can be readily adjusted to yield a smooth transition which minimizes the secondary maxima.

Thanks Laurent.

Finally, the Google webcrawler just found the following recently funded project: Fieldstream. The compressive sensing part is currently empty. They seem to be connected to the Urban sensing project at UCLA.

Thursday, January 07, 2010

CS: ART and CS in CT, Regularization for Matrix Completion, Estimation of High-Dimensional Low-Rank Matrices


With regards to nonlinear solvers in CT, I got the following e-mail (reproduced here with permission as always) from Emil Sidky:
Hi Igor,

I saw your entry last week on the use of ART in CT. There's no contradiction there with what we wrote in our IP review [1]. While it may be true that there are specific protocols that use something other than FBP in CT. These are but a drop in the bucket. No one can really argue with the fact that FBP is the workhorse algorithm of medical CT, and considering the numbers of people that get scanned there is certainly room for substantial exposure reduction to the general population by engineering a general-purpose CT scanner with advanced image-reconstruction algorithms.

Cheers,
Emil

Emil Sidky is right, we ought to be looking at what constitutes the largest market share and it looks like there is room for improvement. However, if radiation dose is the only issue, I fear that Richard Gordon articulation of the inability of ART to topple FBP is the same problem that a CS implementation would face. Therefore a CS system would have to provide something else.

In the previous post, Larry Wasserman made the comment that I had missed a paper related to the themes of this blog. And indeed, my arxiv search did not include the term "matrix completion" and therefore missed the following two items (see below). This has been fixed and if you come to the blog, you can click on the Arxiv link on the right hand side of the menu to see all the papers related to compressive sensing and attendant problems. One thing that is clear from this request is the large variety of fields involved. The first 25 entries of this search include the following arxiv field labels:

physics.optics
cs.IT
cs.NA
quant-ph
cs.DS
math.OC
nlin.CG
math.MG
physics.med-ph
stat.ML
math.ST
Wow, talk about a diverse crowd! And this is just those fields that regularly post on Arxiv.

Here are the two preprints I missed earlier:
Regularization for Matrix Completion by Raghunandan H. Keshavan, Andrea Montanari. The abstract reads:
We consider the problem of reconstructing a low rank matrix from noisy observations of a subset of its entries. This task has applications in statistical learning, computer vision, and signal processing. In these contexts, "noise" generically refers to any contribution to the data that is not captured by the low-rank model. In most applications, the noise level is large compared to the underlying signal and it is important to avoid overfitting. In order to tackle this problem, we define a regularized cost function well suited for spectral reconstruction methods. Within a random noise model, and in the large system limit, we prove that the resulting accuracy undergoes a phase transition depending on the noise level and on the fraction of observed entries. The cost function can be minimized using OPTSPACE (a manifold gradient descent algorithm). Numerical simulations show that this approach is competitive with state-of-the-art alternatives.

Estimation of High-Dimensional Low-Rank Matrices by Angelika Rohde, Alexandre Tsybakov. The abstract reads:
Suppose that we observe entries or, more generally, linear combinations of entries of an unknown mxT-matrix A corrupted by noise. We are particularly interested in the high-dimensional setting where the number mT of unknown entries can be much larger than the sample size N. Motivated by several applications, we consider estimation of matrix A under the assumption that it has small rank. This can be viewed as dimension reduction or sparsity assumption. In order to shrink towards a low-rank representation, we investigate penalized least squares estimators with a Schatten-p quasi-norm penalty term, $p\leq 1$. We study these estimators under two possible assumptions -- a modified version of the restricted isometry condition and a uniform bound on the ratio "empirical norm induced by the sampling operator/Frobenius norm". The main results are stated as non-asymptotic upper bounds on the prediction risk and on the Schatten-$q$ risk of the estimators, where $q\in[p,2]$. The rates that we obtain for the prediction risk are of the form rm/N (for m=T), up to logarithmic factors, where r is the rank of A. The particular examples of multi-task learning and matrix completion are worked out in detail. The proofs are based on tools from the theory of empirical processes. As a by-product we derive bounds for the $k$th entropy numbers of the quasi-convex Schatten class embeddings $S_p^M\hookrightarrow S_2^M$, p \lt1, which are of independent interest.

Thanks Larry and Emil !

Wednesday, January 06, 2010

CS: The reports of Compressive Sensing's demise have been greatly exaggerated, GPU-TV-CT, Tensor product of sparse matrices.


If you haven't done so yet, please go out and fill in yesterday's poll (please note the possibility of saying that you do not own an iPod/iPhone).

Today, we have two preprints from arxiv but before that (given some exchange with some of you) I would like to remind all of you of the following short discussion I had with Gerry Skinner, a specialist in Coded Aperture Imaging back in August'08. Once you are done reading this insightful interview from a veteran in coded aperture, who, for all intent and purpose tells people to stay away from coded aperture after having worked on it for the past thirty years, you may want to reflect on the three other recent entries:
All these interrogations could provide some doubts in the minds of the weak :-), however, one should really look at Compressive Sensing, not just as an incremental technology, but rather as a way to do something that would be infinitely more complex and resource intensive to do with current technology. Some won't work because current technology will catch up faster thanks to Moore's law (the one pixel example of Gerry), some will work because even if Moore's law is helping them, they will still be more expensive to do than a low tech CS approach. In the CT business, CS brings the ability to reduce the dose to the patient. In MRI, it brings the potential of studying the internal dynamics of our body. In bio, group testing procedures allow testing reduction by one order of magnitude (for the moment). In coded aperture, CS brings the ability to get superresolution, 3D or some multi-spectral capability. As one can see, CS is not reaching an end-game, rather it opens new futures and it is really up to us to make them happen. For those of us concerned about noise, maybe we should be in the business of redefining noise and use compressive sensing as a way to do this, surely we cannot always rely on electrical engineers to do that. If you have one sentence feel good story about how CS changed your area of expertise, I could group it with others. Coming back to the app phone poll, how much do you think that insight is worth :-) ? I bet more than $0.99 and surely more than free.

Today, the first paper is about providing speed in the reconstruction in the CT case, please note the number of x-ray projections for a "good" image:

GPU-based Cone Beam CT Reconstruction via Total Variation Regularization by Xun Jia, Yifei Lou, John Lewis, Ruijiang Li, Xuejun Gu, Chunhua Men, Steve B. Jiang. The abstract reads:
Cone-beam CT (CBCT) reconstruction is of central importance in image guided radiation therapy due to its broad applications in many clinical contexts. However, the high image dose in CBCT scans is a clinical concern, especially when it is used repeatedly for patient setup purposes before each radiotherapy treatment fraction. A desire for lower imaging does has motivated a vast amount of interest in the CBCT reconstruction based on a small number of X-ray projections. Recently, advances in image processing and compressed sensing have led to tremendous success in recovering signals based on extremely low sampling rates, laying the mathematical foundation for reconstructing CBCT from few projections. In this paper, we present our recent development on a GPU-based iterative algorithm for the highly under-sampled CBCT reconstruction problem. We considered an energy functional consisting of a data fidelity term and a regularization term of a total variation norm. In order to solve our model, we developed a modified fixed-point continuation algorithm. Our numerical computations demonstrated satisfactory reconstruction accuracy and promising efficiency. We evaluated the reconstruction results under different number of projections. It is found that about 15-40 X-ray projections are enough to provide satisfactory image quality for clinical purpose in cancer radiotherapy. Potential applications of our algorithm in 4D-CBCT and possible approaches to improve our algorithm will also be discussed.

the second paper is about providing some theoretical justification for the use of sparse measurement matrices in tensor products for high dimensional cases:

It has been known since 1970's that the N-dimensional $\ell_1$-space contains nearly Euclidean subspaces whose dimension is $\Omega(N)$. However, proofs of existence of such subspaces were probabilistic, hence non-constructive, which made the results not-quite-suitable for subsequently discovered applications to high-dimensional nearest neighbor search, error-correcting codes over the reals, compressive sensing and other computational problems. In this paper we present a "low-tech" scheme which, for any $a > 0$, allows to exhibit nearly Euclidean $\Omega(N)$-dimensional subspaces of $\ell_1^N$ while using only $N^a$ random bits. Our results extend and complement (particularly) recent work by Guruswami-Lee-Wigderson. Characteristic features of our approach include (1) simplicity (we use only tensor products) and (2) yielding arbitrarily small distortions, or "almost Euclidean" subspaces.


Credit Photo: NASA/ESA, SOHO spacecraft imaging the demise of a comet crashing on the Sun on January 3, 2010

Tuesday, January 05, 2010

A Nuit Blanche iPhone/iPod Touch App. How much would you be willing to pay for it ?


With the acquisition of an iPod Touch, I and many others have found the new convenience of being able to think things through while away from a desk. One of the issues I have is that I do not have an app dedicated to a subject that I specifically care about. In particular, an RSS feed from this blog is easily drowned in the multiple feeds I get from my MobileRSS app. So whenever I want to go back to a paper featured on Nuit Blanche or to a conversation I had with one of you or I want to recall a specific line of thought, articulated here, it takes a while to make that recall efficiently. I just stumbled on a way to make an app that could be made available through the iTunes app store and I am now wondering how much I should charge for it. As I stated before for the newsletter (I am still contemplating how to go about it), all the information that will be available on this app will really be an RSS feed of this blog and attendant pages (big picture, job, hardware, videos,...). So with all this in mind, how much would you be willing to pay for a Nuit Blanche iPhone/iPod Touch app ? Please come to the site and answer the poll below. Each of the numbers have been carefully thought of, even the most extreme ones. Thanks!

Monday, January 04, 2010

CS: RIC, Orientation-Aware Localization, Data Acquisition through joint Compressive Sensing and Principal Component Analysis, Streams of Pulses

During the exchange over the week-end started with the initial question of Zainul Charbiwala on computating the Restricted Isometry Constant (part 1, part 2, part 3), Gabriel Peyré reminded me that the following paper is different from the one I had advertized so here is the full paper:

A Numerical Exploration of Compressed Sampling Recovery by Charles Dossal , Gabriel Peyré and Jalal Fadili. The abstract reads:
This paper explores numerically the efficiency of L1 minimization for the recovery of sparse signals from compressed sampling measurements in the noiseless case. This numerical exploration is driven by a new greedy pursuit algorithm that computes sparse vectors that are difficult to recover by L1 minimization. The supports of these pathological vectors are also used to select sub-matrices that are ill-conditionned. This allows us to challenge theoretical identifiability criteria based on polytopes analysis and on restricted isometry conditions. We evaluate numerically the theoretical analysis without resorting to Monte-Carlo sampling, which tends to avoid worst case scenarios.
and of related interest: Challenging Restricted Isometry Constants with Greedy Pursuit by Charles Dossal , Gabriel Peyré and Jalal Fadili. The abstract reads:
This paper proposes greedy numerical schemes to compute lower bounds of the restricted isometry constants that are central in compressed sensing theory. Matrices with small restricted isometry constants enable stable recovery from a small set of random linear measurements. We challenge this compressed sampling recovery using greedy pursuit algorithms that detect ill-conditionned sub-matrices. It turns out that these sub-matrices have large isometry constants and hinder the performance of compressed sensing recovery.
The attendant code is here.



Here is a generalization from sparsity in Sparse Recovery from Combined Fusion Frame Measurements by Petros Boufounos, Gitta Kutyniok, Holger Rauhut. The abstract reads:

Sparse representations have emerged as a powerful tool in signal and information processing, culminated by the success of new acquisition and processing techniques such as Compressed Sensing (CS). Fusion frames are very rich new signal representation methods that use collections of subspaces instead of vectors to represent signals. This work combines these exciting fields to introduce a new sparsity model for fusion frames. Signals that are sparse under the new model can be compressively sampled and uniquely reconstructed in ways similar to sparse signals using standard CS. The combination provides a promising new set of mathematical tools and signal models useful in a variety of applications. With the new model, a sparse signal has energy in very few of the subspaces of the fusion frame, although it does not need to be sparse within each of the subspaces it occupies. This sparsity model is captured using a mixed l1/l2 norm for fusion frames.
A signal sparse in a fusion frame can be sampled using very few random projections and exactly reconstructed using a convex optimization that minimizes this mixed l1/l2 norm. The provided sampling conditions generalize coherence and RIP conditions used in standard CS theory. It is demonstrated that they are sufficient to guarantee sparse recovery of any signal sparse in our model. Moreover, an average case analysis is provided using a probability model on the sparse signal that shows that under very mild conditions the probability of recovery failure decays exponentially with increasing dimension of the subspaces.

In the reference section, I note the following lecture notes of Alexander Barvinok entitled Measure concentration.

I also found the following on the interwebs:

Orientation-Aware Indoor Localization using Affinity Propagation and Compressive Sensing by Chen Feng, Wain Sy Anthea Au, Shahrokh Valaee, and Zhenhui Tan. The abstract
The sparse nature of location finding makes it desirable to exploit the theory of compressive sensing for indoor localization. In this paper, we propose a received signal strength (RSS)-based localization scheme in Wireless Local Area Networks (WLANs) using the theory of compressive sensing (CS), which offers accurate recovery of sparse signals from a small number of measurements by solving an ℓ1-minimization problem. In order to mitigate the effects of RSS variations due to channel impediments and mobile device orientation, a two-step localization scheme is proposed by exploiting affinity propagation for coarse localization followed by a CS-based fine localization to further improve the accuracy. We implement the localization algorithm on a WiFi-integrated mobile device to evaluate the performance. Experimental results indicate that the proposed system leads to substantial improvements on localization accuracy and complexity over the widely used traditional fingerprinting methods.

Compressive Sensing Based Positioning Using RSS of WLAN Access Points by Chen Feng, Wain Sy Anthea Au, Shahrokh Valaee, and Zhenhui Tan. The abstract reads:
The sparse nature of location finding problem makes the theory of compressive sensing desirable for indoor positioning in Wireless Local Area Networks (WLANs). In this paper, we address the received signal strength (RSS)-based localization problem in WLANs using the theory of compressive sensing (CS), which offers accurate recovery of sparse signals from a small number of measurements by solving an ℓ1-minimization problem. A pre-processing procedure of orthogonalization is used to induce incoherence needed in the CS theory. In order to mitigate the effects of RSS variations due to channel impediments, the proposed positioning system consists of two steps: coarse localization by exploiting affinity propagation, and fine localization by the CS theory. In the fine localization stage, access point selection problem is studied to further increase the accuracy. We implement the positioning system on a WiFi-integrated mobile device (HP iPAQ hx4700 with Windows Mobile 2003 Pocket PC) to evaluate the performance. Experimental results indicate that the proposed system leads to substantial improvements on localization accuracy and complexity over the widely used traditional fingerprinting methods.

In this paper we look at the problem of accurately reconstructing distributed signals through the collection of a small number of samples at a data gathering point. The techniques that we exploit to do so are Compressive Sensing (CS) and Principal Component Analysis (PCA). PCA is used to find transformations that sparsify the signal, which are required for CS to retrieve, with good approximation, the original signal from a small number of samples. Our approach dynamically adapts to non-stationary real world signals through the online estimation of their correlation properties in space and time; these are then exploited by PCA to derive the transformations for CS. The approach is tunable and robust, independent of the specific routing protocol in use and able to substantially outperform standard data collection schemes. The effectiveness of our recovery algorithm, in terms of number of transmissions in the network vs reconstruction error, is demonstrated for synthetic as well as for real world signals which we gathered from an actual wireless sensor network (WSN) deployment.We stress that our solution is not limited toWSNs but it can be readily applied to other types of network infrastructures that require the online approximation of large and distributed data sets.
Compressive Sensing (CS) has developed as an enticing alternative to the traditional process of signal acquisition. For a length-N signal with sparsity K, merely M = O(K logN) \lt\lt N random linear projections (measurements) can be used for robust reconstruction in polynomial time. Sparsity is a powerful and simple signal model; yet, richer models that impose additional structure on the sparse nonzeros of a signal have been studied theoretically and empirically from the CS perspective. In this work, we introduce and study a sparse signal model for streams of pulses, i.e., S-sparse signals convolved with an unknown F-sparse impulse response. Our contributions are threefold: (i) we geometrically model this set of signals as an infinite union of subspaces; (ii) we derive a sufficient number of random measurements M required to preserve the metric information of this set. In particular this number is linear merely in the number of degrees of freedom of the signal S + F, and sublinear in the sparsity K = SF; (iii) we develop an algorithm that performs recovery of the signal from M measurements and analyze its performance under noise and model mismatch. Numerical experiments on synthetic and real data demonstrate the utility of our proposed theory and algorithm. Our method is amenable to diverse applications such as the high resolution sampling of neuronal recordings and ultrawideband (UWB) signals.

and finally, On Local Dimension Estimation and Its Applications by Kevin Carter, Raviv Raich, and Alfred Hero, The abstract reads:
In this paper, we present multiple novel applications for local intrinsic dimension estimation. There has been much work done on estimating the global dimension of a data set, typically for the purposes of dimensionality reduction. We show that by estimating dimension locally, we are able to extend the uses of dimension estimation to many applications, which are not possible with global dimension estimation. Additionally, we show that local dimension estimation can be used to obtain a better global dimension estimate, alleviating the negative bias that is common to all known dimension estimation algorithms. We illustrate local dimension estimation’s uses towards additional applications, such as learning on statistical manifolds, network anomaly detection, clustering, and image segmentation.


A Graduate Summer School announcement on “Image Processing” at the Institute for Advanced Study (IAS),/Park City Mathematics Program (PCMI). APPLICATION DEADLINE JANUARY 31, 2010.

The program features the following course titles and descriptions:

The 2010 Summer Session in “Image Processing” will consist of eight graduate level lecture series. On any day during the summer session, three lectures will be offered. Graduate students are asked to attend the lectures as well as two daily problem sessions associated with the lecture and led by a graduate TA.

Richard Baraniuk, Rice University

Compressive Sensing: Sparsity-Based Signal Acquisition and Processing

Sensors, imaging systems, and communication networks are under increasing pressure to accommodate ever larger and higher-dimensional data sets; ever faster capture, sampling, and processing rates; ever lower power consumption; communication over ever more difficult channels; and radically new sensing modalities. The foundation of today’s digital data acquisition systems is the Shannon/Nyquist sampling theorem, which asserts that to avoid losing information when digitizing a signal or image, one must sample at least two times faster than the signal’s bandwidth, at the so-called Nyquist rate. Unfortunately, the physical limitations of current sensing systems combined with inherently high Nyquist rates impose a performance brick wall to a large class of important and emerging applications.

This lecture will overview some of the recent progress on compressive sensing, a new approach to data acquisition in which analog signals are digitized not via uniform sampling but via measurements using more general, even random, test functions. In stark contrast with conventional wisdom, the new theory asserts that one can combine “sub-Nyquist-rate sampling” with digital computational power for efficient and accurate signal acquisition. The implications of compressive sensing are promising for many applications and enable the design of new kinds of analog-to-digital converters; radio receivers, communication systems, and networks; cameras and imaging systems, and sensor networks.

Antonin Chambolle, École Polytechnique

Total-Variation based image reconstruction.

In the introduction we will recall the reason for which the Total Variation (TV) was introduced as a powerful tool for image recovery. The focus of the first lectures will be mostly on theoretical aspects. The definition and essential properties of the TV will be detailed, variational problems involving the related perimeter functional will also be considered. Then, we will study the “Rudin-Osher-Fatemi” problem (from a convex analysis point of view, the proximal operator associated to the TV). We will try to analyse some interesting properties of the solutions, including regularity issues.

A second part of the lectures will address algorithmic issues and describe the standard and less standard numerical methods for solving efficiently TV-like problems. In a last lecture, we will discuss original extensions which involve TV-like functionals.

Michael Elad, Israel Institute of Technology

Sparse & Redundant Representations – From Theory to Applications in Image Processing

Modeling natural image content is key in image processing. Armed with a proper model, one can handle various tasks such as denoising, restoration, separation, interpolation and extrapolation, compression, sampling, analysis and synthesis, detection, recognition, and more. Indeed, a careful study of the image processing literature reveals that there is an evolution of such models and their use in applications.

This short-course is all about one such model, which I call Sparse-Land for brevity. This specific model is intriguing and fascinating because of the beauty of its theoretical foundations, the superior performance it leads to in various applications, its universality and flexibility in serving various data sources, and its unified view, which makes all the above processing tasks clear and simple. In this course we shall starts with the mathematical foundations of this model, and then turn to present several image processing applications, where it is shown to lead to state-of-the-art results.

Selim Esedoglu, University of Michigan

Numerical methods for problems involving interfaces in imaging and vision.

We will discuss numerical methods for solving a number of interfacial problems that arise in image processing and computer vision applications. The applications we focus on will include image segmentation, image inpainting, as well as some inverse problems. Mathematical models for these typically involve an unknown curve in 2D or a surface in 3D. The numerical methods we discuss will include not only phase field, level sets, and threshold dynamics, but also certain globally optimal methods that convert non-convex optimization problems over curves and surfaces to convex optimization problems, which can then be solved to find the global minimum in a guaranteed fashion.

Anna Gilbert, University of Michigan

A survey of sparse approximation

The past 10 years have seen a confluence of research in sparse approximation amongst computer science, mathematics, and electrical engineering. Sparse approximation encompasses a large number of mathematical, algorithmic, and signal processing problems which all attempt to balance the size of a (linear) representation of data and the fidelity of that representation. I will discuss several of the basic algorithmic problems and their solutions, including connections to streaming algorithms and compressive sensing.

Yann LeCun, New York University

Learning Image Feature

Image recognition systems have traditionally consisted of a hard-wired feature extractor, followed by a trainable supervised classifier. One could argue that the next challenge of computer vision, machine learning, and image processing, is to devise methods that can automatically learn the feature extractor from labeled and unlabeled data. a particularly relevant task for image recognition is the so-called “Deep Learning” problem, whose object is to learn hierarchies of features with multiple levels of abstraction, and suitable invariances.

I will discuss the foundations of unsupervised learning in the probabilistic and non-probabilistic (energy-based) frameworks, and will present several feature-learning models, including sparse coding, sparse auto-encoders, denoising auto-encoders, and Restricted Boltzmann Machines. I will also discuss supervised and semi-supervised methods for deep learning, including metric learning criteria. I will then discuss specific model architectures for image recognition, based on stacks on non-linear filter banks. A number of applications to object dectection, object recognition, and vision-based navigation for mobile robots will be described, and some will be demonstrated live.

Guillermo Sapiro, University of Minnesota

Dictionary learning for efficient signal representation

The goal of this class is to introduce participants to the area of dictionary learning for sparse representations. We will cover fundamental theory and computational algorithms as well as applications in signal processing. Topics we plan to cover include:

  • Sparse coding (OMP, LASSO, group LASSO, LARS, soft thresholding, etc).
  • Metric learning and k-flats.
  • Dictionary learning (MOD, K-SVD, on-line learning, etc).
  • Data as dictionaries and sparse graphs.

Zuowei Shen, National University of Singapore

Wavelet and Wavelet Frames in Imaging Science

From the beginning of sciences, visual observations have played major roles. With the rapid progress in video and computer technology, computers have become powerful enough to process image data. As a result, image processing techniques are now applied to virtually all natural sciences and technical disciplines.

Mathematical analysis makes image processing algorithms predictable, accurate and, in some cases, optimal. New mathematical methods often result in novel approaches that can solve previously intractable problems or that are much faster or more accurate than previous approaches. The speed up that can be gained by fast algorithm is considerable. Fast algorithms make many image processing techniques applicable and reduce the hardware cost considerably.

Wavelet and Wavelet frame based methods are relatively new mathematical tools that allow us to quickly manipulate images, for example, high-resolution image reconstructions in some applications, or image compressions in other applications. The wavelet or wavelet frame algorithms decompose and arrange an image data into strata reflecting their relative importance. This allows a rapid access to good coarse resolution of the image while retaining the flexibility for increasingly fine representations. It leads to algorithms that give sparse and accurate representations of image and medical image for efficient computation, analysis, storage, restorations and communication. In this series talk, I will illustrate how the wavelet theory is developed and applied to various applications in image processing which includes deblurring, denoising, inpainting and image decomposition.

Joseph M. Teran, UCLA

Numerical Methods for Elasticity Problems in Biomechanics

Elasticity plays a fundamental role in many biomechanics related problems. I will talk about numerical methods used for simulating elastic phenomena in soft tissues, skeletal muscles and non-Newtonian fluids. Specifically, I will discuss common difficulties encountered and my recent algorithm developments to address them. Topics include robust resolution of: severe nonlinearity, near incompressibility, extremely large deformation, collision/contact and solid/fluid coupling. I will also discuss the impact of multi-core accelerated computation for such problems and the potentially revolutionary applications it will admit.

Sunday, January 03, 2010

CS: Finding the Restricted Isometry Constant, Part Three

Gabriel Peyré just sent me the address of the Matlab implementation of the algorithm featured in A Numerical Exploration of Compressed Sampling Recovery (see part deux). It is at:

CS: Finding the Restricted isometry Constant, Part Deux.

Gabriel Peyré sent me the following:
Dear Igor,

...Regarding your last post, you might be interested in a recent paper I co-authored with Charles Dossa and Jalal Fadili

[the pdf is here]
that presents a greedy algorithm to estimate RIP constants. In practice, for matrix of size ~10000 measures, it gets quite close to the asymptotic upper bounds of Blanchard et al, that are thus quite sharp.

It is fast, and does not requires any convex optimization, but does a much better job than picking sub-dictionary at random using Monte Carlo. It can also be used to find vectors that cannot be recovered by L1 minimization, and gets very close to the asymptotic bounds of Donoho and Tanner....


I covered that paper last March and when I gave my answer in the last entry, I knew there was something newer. This is fixed. Thanks Gabriel ! As a result of this query, I will also alter the section starting the measurement matrix paragraph of the big picture.

Saturday, January 02, 2010

CS: Finding the Restricted Isometry Constant, Random SVD, ART in CTs ?, Patents, Cheap CS Sensing ?

In the previous post, Zainul Charbiwala asks the following question:
Thanks for listing my paper. It's our tiny attempt at contributing to the CS field.

I'd like to point out something about this paper. I did the completely unthinkable, and *computed* the RIP constant explicitly through a Monte Carlo type simulation. Now, I know that this is technically incorrect, because RIP is defined over *all* possible matrices, but I found this technique to provide fairly consistent results and that match our intuition about the "goodness" of sensing matrices, especially when we're trying to compare one type of sensing system with another.

I confess that I could have taken an anlytical route to illustrate my point, but could you (or other readers) comment on their experience with computing the RIP explicitly ?



Thanks Zainul for asking the question. In the following presentation, Tractable Upper Bounds on the Restricted Isometry Constant. by Alexandre d’Aspremont, Francis Bach, Laurent El Ghaoui, there is an attempt at computing bounds for the Restricted Isometry constant. The Sparse PCA code can be found here. Sicne the RIP is only a sufficient condition, there is also the necessary and sufficient condition called Null Space Property for which some bounds can be found as follows:
To see the differences and connections between these two properties, you really want to check out the description given by Jared Tanner and Remi Gribonval in the following entry CS: RIP vs NSP, Clarifications by Jared Tanner and Remi Gribonval. If anybody else has a better answer, please feel free to add to the discussion.



While reading, Hal Daume III's excellent blog on NIPS, I noticed a description made by one of his grad student, Piyush Rai on Gunnar Martinsson's NIPS Tutorial entitled: Randomization: Making Very Large Scale Linear Algebraic Computations Possible. The presentation hints on the possibility of performing faster diffusion maps when one deals with very large problems,. Diffusion maps are one of the few techniques in Machine Learning that enables the parametrization of nonlinear manifolds. What is interesting here is how this SVD algorithm uses random projections (see slides 132-134 for a connection to CS, concentration of measures and structured random projections). The reference paper related to the tutorial is: Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions by Nathan Halko, Per-Gunnar Martinsson, Joel A. Tropp. The abstract
Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys recent research which demonstrates that \emph{randomization} offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. In particular, these techniques offer a route toward principal component analysis (PCA) for petascale data.
This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed - either explicitly or implicitly - to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, speed, and robustness. These claims are supported by extensive numerical experiments and a detailed error analysis.
Mark Tygert's page has an implementation of that algorithm here. So at some point either, the practicing Machine Learning Engineer uses random projections and diffusion maps to evaluate the non-linear manifold or she could use directly the SVD method above to produce diffusion maps from the high dimensional data. While interesting, the second approach still expects the kernel matrix to be computed and sometimes this is just not possible in a reasonable amount of time (that's what I would stick with the first option).



...3.2 Commercial patents

There is hardly better evidence for the value of projection methods than the many patents for commercial purposes that include them. Projection methods are used in commercial devices in many areas. Unfortunately, if a device is truly commercial, then the algorithm that is actually used in it is proprietary and usually not published. Many commercial emission tomography scanners use now some sort of iterative algorithms. A prime example is provided by the commercially-successful Philips Allegro scanners (see http://www.healthcare.philips.com/main/products/ and [29]). In x-ray computerized tomography (CT), there are reports emanating from companies that sell such scanners indicating that variants of ART are used in heart imaging; an example is presented in [54]. The first EMI (Electric & Musical Industries Ltd., London, England, UK) CT scanner, invented by G.N. Hounsfield [53], used a variant of ART. For this pioneering invention, Hounsfield shared the Nobel Prize with A.M. Cormack in 1979. Thirty years later (on September 29, 2009), a patent was issued to Philips (Koninklijke Philips Electronics N.V., Eindhoven, The Netherlands) for a “Method and device for the iterative reconstruction of cardiac images” [77]. The role of projection methods is demonstrated by the following quote from the “Summary of the Invention” included in the Patent Description:

“The iterative reconstruction applied here may particularly be based on an Algebraic Reconstruction Technique (ART) (cf. R. Gordon, R. Bender, and G.T. Herman: “Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography”, J. Theor. Biol., 29:471–481, 1970) or on a Maximum Likelihood (ML) algorithm (K. Lange and J.A. Fessler: “Globally convergent algorithms for maximum a posteriori transmission tomography”, IEEE Transactions on Image Processing, 4(10):1430–1450, 1995), wherein each image update step uses the projections of a selected subset, i.e., projections corresponding to a similar movement phase.”
The knowledge that ART seems to be employed in current CT scanners seems at odd with the review entitled: Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? by Xiaochuan Pan, Emil Sidky and Michael Vannier. Also of interest, Richard Gordon a co-inventor of ART for CT-scanners (with Gabor T. Herman an author of the paper above) responded to that review in this entry: MIA'09 and Richard Gordon's ART CT algorithm.

And if you think some of these patenting issues are germane, you might want to take a look at the Bilski case currently in front of the U.S. Supreme Court, from the wikipedia entry, there is a mention of CT algorithms:

....Some Federal Circuit decisions, however, had held some transformations of signals and data patent-eligible. For example, the Abele decision approved a dependent claim to a method transforming X-ray attenuation data produced in a X-Y field by an X-ray tomographic scanner to an image of body organs and bones — while at the same time the Abele court rejected a more generic and abstract independent claim to a process of graphically displaying variances from their average values of unspecified data obtained in an unspecified manner.
From the Abele decision, there was the following determination:

....In Johnson, supra, the interrelationship of the algorithm to the remaining limitations of a claim was held to be determinative of whether the claim defined statutory subject matter. Relying on the same reasoning, in In re Walter,618 F.2d 758, 205 USPQ 397 (CCPA 1980), the second part of the two-step analysis5 was defined as follows:

If it appears that the mathematical algorithm is implemented in a specific manner to define structural relationships between the physical elements of the claim (in apparatus claims) or to refine or limit claim steps (in process claims), the claim being otherwise statutory , the claim passes muster under §101. If, however, the mathematical algorithm is merely presented and solved by the claimed invention, as was the case in Benson and Flook, and is not applied in any manner to physical elements or process steps, no amount of post-solution activity will render the claim statutory; nor is it saved by a preamble merely reciting the field of use of the mathematical algorithm....

Is compressive sensing going to change patents ?

Finally, two projects that are dirt cheap and resonate with me for some reasons:

  • The EyeWriter


  • and Structured Light 3D scanning

    Point Clouds with Depth of Field from Kyle McDonald on Vimeo.


    It might be a good little project to try Compressive Structured Light
  • Friday, January 01, 2010

    CS: Compressed Sensing Approach for High Throughput Carrier Screen, Compressive Oversampling for Robust Data Transmission in Sensor Networks


    After the thank you entry, Yaniv Erlich sent me the following:

    ...This is the time to thank you for running the blog.
    As an outsider (I study genomics), the blog is my only way of keep track on what is going on in the field.
    In addition, Noam Shental and I are started collaboration through reading each other papers in your blog.
    The collaboration led already to one paper in Allerton 2009, and we are working together on a bigger project now...

    You cannot believe how ecstatic I am when I read this, especially on the worthy subject these guys are undertaking (see below). 2010 is already starting nicely. The Allerton paper is (my webcrawler missed it!): Compressed Sensing Approach for High Throughput Carrier Screen by Yaniv Erlich, Noam Shental, Amnon Amir, Or Zuk . The abstract reads:
    Carrier screens are widely used in medical genetics to prevent rare genetic disorders. Current detection methods are based on serial processing which is slow and expensive. Here, we discuss a highly efficient compressed sensing approach for ultra-high throughput carrier screens, and highlight both similarities and unique features of our setting compared to the standard compressed sensing framework. Using simulations, we demonstrate the power of compressed carrier screens in a real scenario - finding carriers for rare genetic diseases in Ashkenazi Jews, a population that has well established wide-scale carrier screen programs. We also compare the decoding performance of two typical reconstruction approaches in compressed sensing - GPSR and Belief Propagation. Our results show that Belief Propagation confers better decoding performance in the current application.

    The attendant slides are here. Here are some extracts:

    Analog parallel processing, here is a good way to summarize the concept


    The paws of Dror are all over :-)


    These numbers are significant, I wonder how these numbers shrink further when one takes into consideration that individuals are genetically linked to each other, especially when one makes the choice to screen an entire population. While the screening is very important, I also wonder how this group testing approach could be applied to the discovery process.


    Finally, on a lighter note, I liked the acknowledgment slide, and more importantly, I liked the fact that one of the members of that team is a real marine biologist. For more information on that, you may want to refresh your mind with this Seinfeld video (which can be put in context with this video):




    Quite by accident, I also found the following interesting papers: Compressive Oversampling for Robust Data Transmission in Sensor Networks by Zainul Charbiwala, Supriyo Chakraborty, Sadaf Zahedi, Younghun Kim, Mani B. Srivastava, Ting He, Chatschik Bisdikian. The abstract reads:
    Data loss in wireless sensing applications is inevitable and while there have been many attempts at coping with this issue, recent developments in the area of Compressive Sensing (CS) provide a new and attractive perspective. Since many physical signals of interest are known to be sparse or compressible, employing CS, not only compresses the data and reduces effective transmission rate, but also improves the robustness of the system to channel erasures. This is possible because reconstruction algorithms for compressively sampled signals are not hampered by the stochastic nature of wireless link disturbances, which has traditionally plagued attempts at proactively handling the effects of these errors. In this paper, we propose that if CS is employed for source compression, then CS can further be exploited as an application layer erasure coding strategy for recovering missing data. We show that CS erasure encoding (CSEC) with random sampling is efficient for handling missing data in erasure channels, paralleling the performance of BCH codes, with the added benefit of graceful degradation of the reconstruction error even when the amount of missing data far exceeds the designed redundancy. Further, since CSEC is equivalent to nominal oversampling in the incoherent measurement basis, it is computationally cheaper than conventional erasure coding. We support our proposal
    through extensive performance studies.

    and Improving Data Integrity with Randomness -- A Compressive Sensing Approach by Zainul Charbiwala, Sadaf Zahedi, Younghun Kim, Supriyo Chakraborty, Chatschik Bisdikian, Mani B Srivastava. The introduction starts with:
    Data loss in wireless sensor systems is inevitable, either due to exogenous (such as transmission medium impediments) or endogenous (such as faulty sensors) causes. While there have been many attempts at coping with this issue, recent developments in the area of Compressive Sensing (CS) enable a new perspective. Since many natural signals are compressible, it is possible to employ CS, not only to reduce the effective sampling rate, but to improve the robustness of the system at a given Quality of Information (QoI). This is possible because reconstruction algorithms for compressively sampled signals are not hampered by the stochastic nature of wireless link disturbances and sensor malfunctions, which has traditionally plagued attempts at proactively handling the effects of these errors. In this paper, we show how reconstruction error remains unchanged despite extreme independent data losses by
    marginally increasing the average sampling rate. We also show that a simple re-ordering of samples prior to communication could enable successful reconstruction when losses display bursty behavior.



    Credit: NASA, The Sun as seen by the Soho spacecraft.

    Printfriendly