CS: Herschel, Toeplitz Random Encoding for Reduced Acquisition Using Compressed Sensing

Following up on yesterday's entry (Godspeed Herschel), I went ahead and talked to the initiators of the CS scheme for this project on Herschel. Jean-Luc Starck mentioned to me that the initial study with the compressive sensing encoding was made from some idealized star fields but that they now have access to a real sky simulator which should improve their confidence in the scheme. Utlimately, the proof will be in the pudding with the real data from the spacecraft. We will only know then if the CS scheme was a good solution to transfer data to the ground. Data should stream from the spacecraft (with no encoding/compression) within the first three months of the launch. A trial period will then take place to check the CS scheme. Eventually the hope is for the CS encoding scheme to be the one preferred to download data from the spacecraft. May 6th is our next date and then they should go in this trial mode at the beginning of August.

In other news, Muthu's arms are up :-)



In a different area, I think this is the first time we have this sort of encoding in MRI:

Toeplitz Random Encoding for Reduced Acquisition Using Compressed Sensing by Haifeng Wang, Dong Liang, Kevin F. King, Leslie Ying. The abstract reads:

Considerable attention has been paid to compressed sensing (CS) in the MRI community recently (1,2). CS theory allows exact recovery of a sparse signal from a highly incomplete set of samples (3,4), and thus has the potential for significant reduction in MRI scan time. While most existing work has focused on Fourier encoding, non-Fourier encoding has shown some promise (5,6). In this abstract, we design a pulse sequence to implement the Toeplitz random encoding method proposed earlier (6). The experimental results show that Toeplitz random encoding can be realized in practice as an alternative method for CS MRI.

The attendant poster is here.

Godspeed Herschel ! [Updated]

[ Udpate: the launch will take place on May 6th]

If you check the Compressive Sensing calendar, you'll see that today is the launch of the Herschel spacecraft. As you know. One of the camera on Herschel has a code implementing a compressive sensing encoding. If I understand correclty, the underlying reason of this late integration in the camera is that CS allows for simple encoding techniques that can be done easily with a normal rad-hard computer. As for any launches they are uncertainties with regards to the weather. As you can see sideways, the spacecraft has been hoisted to the adapter to be put on top of the Ariane 5 rocket. ESA's website also tells us that Herschel has been fueled. Since today is April 16th, the graph showing the launch window (see above) that takes into account all the scientific, technical and orbital constraints, seems to say that the launch window opens in about an hour and will last an hour and 45 minute. Godspeed Herschel.

For more information on Compressive Sensing on Herschel, check this paper by Jerome Bobin, Jean-Luc Starck, and Roland Ottensamer entitled Compressed sensing in astronomy,

and these entries:

• CS: CS on Herschel

• CS: Compressive Sensing Hardware Update
  

CS: Becoming Mainstream.

Muthu Muthukrishnan just wrote the following blog entry entitled: What is NOT Compressed Sensing?

Will someone ... explain to the world what is NOT compressed sensing. It is NOT

• Any sparse representation with small number of nonzeros.
• Any dimensionality reduction by random projections.
• Any operation that replaces L_0 optimization by L_1.
• Any heavy hitters algorithm.
  

I do not want to listen to so many machine learning, signal processing, data mining, statistics, image processing researchers tell me that they do compressed sensing. Or may be I should throw up my hands and let the world embrace Compressed Sensing, after all they are sensing something, and it is compressed.

One of the anonymous commenter wrote:

You should explain why it matters that things are mislabeled. Do Compressed Sensing techniques apply to the things you consider *not* to be Compressed Sensing? If so, what is the harm in mislabeling? Is the harm that techniques are incorrectly applied?

I don't think this is a question of applying techniques incorrectly. I was about to write a longer post but then went ahead and discussed the subject with one of you on how s/he and I interpreted what CS was and what was not CS. After a fruitful discussion, we agreed to disagree that there was no easy definition except that CS had provided a mathematically strong framework for totally new approaches to sampling and to other fields. It doesn't really mean that everything goes, rather that everybody has a different appreciation of where this is leading and what is the most important problem is.

In a different field, I am sure that Haar wavelets were not considered real wavelets by the leaders of the field. but they have nonetheless allowed specialists from several fields to speak the same language and normalized their approaches.

The effect of a field becoming popular has happened before. By serendipity I found, the following 1956 paper by Claude Shannon himself bemoaning the use of the term Information Theory.

A study of the use of the word "Information Theory" on Google timeline since 1956 seems to show that the best policy is to probably "throw up one's hands and let the world embrace the subject.":-)

CS: Analysis for Iterative Reweighted l_1, Projection proximal-point algorithm,Subsampling Algorithms, Imaging of moving targets with multi-static SAR

Weiyu Xu just sent me the following very interesting news on the re-weighted L1 mentioned a while ago:

...Please see [ below] our recent paper on the analysis for the iterative reweighted l_1 minimization algorithm. This algorithm was proposed by Candes, Wakin, and Boyd in 2007, but there has not be a rigorous proof for it even though it has been observed to outperform the l_1 minimization in experimentations.

In this paper, we rely on new developments of the Grassmann angle analytical framework for compressive sensing and proved rigorously that this iterative reweighted l_1 minimization algorithm can indeed provably boost the signal recovery sparsity thresholds....

The paper is entitled : Breaking through the Thresholds: an Analysis for Iterative Reweighted $\ell_1$ Minimization via the Grassmann Angle Framework by Weiyu Xu, M. Amin Khajehnejad, Salman Avestimehr, Babak Hassibi. The abstract reads:

It is now well understood that $\ell_1$ minimization algorithm is able to recover sparse signals from incomplete measurements [2], [1], [3] and sharp recoverable sparsity thresholds have also been obtained for the $\ell_1$ minimization algorithm. However, even though iterative reweighted $\ell_1$ minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted $\ell_1$ algorithms. In particular, we show that for a nontrivial class of signals, the iterative reweighted $\ell_1$ minimization can indeed deliver recoverable sparsity thresholds larger than that given in [1], [3]. Our results are based on a high-dimensional geometrical analysis (Grassmann angle analysis) of the null-space characterization for $\ell_1$ minimization and weighted $\ell_1$ minimization algorithms.

I am sure glad that this Grassman Angle framework provides more than one of the numerous NP-Hard property for sparse signal recovery :-). Thank you Weiyu.

Here is another paper investigating proximal point method in A projection proximal-point algorithm for l^1-minimization by Dirk A. Lorenz. The abstract reads:

The problem of the minimization of least squares functionals with $\ell^1$ penalties is considered in an infinite dimensional Hilbert space setting. While there are several algorithms available in the finite dimensional setting there are only a few of them which come with a proper convergence analysis in the infinite dimensional setting. In this work we provide an algorithm from a class which have not been considered for $\ell^1$ minimization before, namely a proximal-point method in combination with a projection step. We show that this idea gives a simple and easy to implement algorithm. We present experiments which indicate that the algorithm may perform better than other algorithms if we employ them without any special tricks. Hence, we may conclude that the projection proximal-point idea is a promising idea in the context of $\ell^1$-minimization.

I note the word "zoo" to characterize the plentiful solutions for reconstructing CS solution . This is fair to say :-) I also noted and the following:

...The contribution of the paper is hence twofold: one the one hand, we add another class of algorithms, namely a proximal-point-like algorithm, to the zoo of available methods and on the other hand we provide an algorithm which is globally and strongly convergent in the infinite dimensional setting. We stress, that the purpose of this paper is not to develop an algorithm which outperforms other existing methods....

The conclusion is itself very interesting:

The projection proximal point algorithm as proposed in [20] is applicable for the problem of ℓ1-minimization. It could be shown that under the FBI assumption the algorithm even converges linearly. Both the iterated soft-thresholding and the generalized conditional gradient method are applicable methods to solve the regularized subproblems. For the iterated soft-thresholding the projection proximal-point algorithm does not lead to a significant improvement. On the theoretical side, the iterated soft-thresholding itself converges linearly [4, 14] and on the practical side, both methods behave comparable (see Figure 3). However, for the generalized conditional gradient method the situation is different. For the algorithm itself as stated in [3] the distance to the minimizer only converges like O(n−1/2) but the projection proximal-point extension gives linear convergence. Moreover, also the practical behavior is better, see Figure 3. In total, it seems that the generalized conditional gradient method combines well with the projection proximal point idea. However, the aim of this paper was not to develop the fastest available method for ℓ1-minimization but to provide an algorithm from a different class of methods. Hence, it may be expected that after considerable fine tuning (parameter choice rules, more efficient solvers for the subproblems, backtracking. . . ) the projection proximal-point algorithm will become comparable to state-of-the-art methods.

Finally we remark, that Algorithm 4 does not rest upon linearity of the operator
and may also be applied to non-linear operators. Also for the solution of the subproblems either iterated soft-thresholding [1] or the generalized condition
gradient method may be used.

I think I mention this paper before, but now there is a code associated with it: Subsampling Algorithms for Semidefinite Programming by Alexandre d'Aspremont. The abstract reads:

We derive two stochastic gradient algorithms for semidefinite optimization using randomization techniques. One is based on the robust stochastic approximation method and uses random sparsifications of the current iterate to both accelerate eigenvalue computations and reduce memory requirements. The other relies on gradient sampling techniques to reduce the per iteration cost of smooth semidefinite optimization methods.

The source code is here.

Finally, found on arxiv: Imaging of moving targets with multi-static SAR using an overcomplete dictionary by Ivana Stojanovic, William C. Karl. The abstract reads:

This paper presents a method for imaging of moving targets using multi-static SAR by treating the problem as one of spatial reflectivity signal inversion over an overcomplete dictionary of target velocities. Since SAR sensor returns can be related to the spatial frequency domain projections of the scattering field, we exploit insights from compressed sensing theory to show that moving targets can be effectively imaged with transmitters and receivers randomly dispersed in a multi-static geometry within a narrow forward cone around the scene of interest. Existing approaches to dealing with moving targets in SAR solve a coupled non-linear problem of target scattering and motion estimation typically through matched filtering. In contrast, by using an overcomplete dictionary approach we effectively linearize the forward model and solve the moving target problem as a larger, unified regularized inversion problem subject to sparsity constraints.

Image Credit: NASA/JPL/Space Science Institute, Saturn's rings taken 3 days ago from Cassini.

CS: dental CT, Fast MRI, Joint-sparse recovery from multiple measurements, Counting the Scaled +1/-1 Matrices with RIP, Sparse Event Detection in SN

Compressed sensing metal artifact removal in dental CT by JiYoung Choi, Min Woo Kim, W. Seong and Jong Chul Ye, The abstract reads;

Metal artifact removal (MAR) has been an important issue in dental X-ray CT due to the presence of metal implant and fillings. The practical use of most existing MAR methods have limitations due to their inherent drawbacks. In this research, we propose a novel MAR algorithm in dental CT. Based on the sparse volume occupation of the metallic inserts, we can formulate the MAR problem as a sparse recovery problem within the compressed sensing framework. One of the main advantages of employing compressed sensing theory in MAR problem is that the sparseness of the metallic objects allows us to reduce the view samples significantly without loss of image quality, accelerating the proposed MAR algorithm drastically. Experimental results using real dental CT scanner measurements show that our algorithm can perform accurate metallic artifact removal very quickly.

I like what I see near the end, emphasis are mine:

Even though most of MAR methods have been evaluated based on the reconstruction quality of axial sections, in diagnosis of teethridge infection, sagittal and coronal sections are, however, important as much as axial sections. Especially, the dark shadow between metallic inserts are often misdiagnosed as inflammation. So the removal of such artifacts are one of the most important criteria from a clinical perspective. In Figure 5, we can confirm that CS-MAR outperforms conventional MAR method for the sagittal and coronal sections, as well as axial sections.

I don't think that I have seen that the main reason for undersampling is to reduce the radiation dose to the patient, which as a nuclear engineer I am always sensitive to.

Performance evalution of accelerated functional MRI acquisition using compressed sensing by Hong Jung and Jong Chul Ye. The abstract reads:

Functional MRI (fMRI) has been widely accepted as a standard tool to study the function of brain. However, because of the limited temporal resolution of MR scanning, researchers have experienced difficulties in various event related cognitive studies which usually require higher temporal resolution than the current acquisition protocol. Even if several accelerated fMRI methods have been proposed to overcome the limited temporal resolution, the results have not been widely accepted since there were concerns whether the result came from blood oxygen level-dependent (BOLD) signal or artifacts due to down sampling. The main contribution of this paper is to propose a new high spatio-temporal resolution fMRI technique based on compressed sensing theory and to justify the performance using receiver operating characteristic (ROC) curve.

Joint-sparse recovery from multiple measurements by Ewout van den Berg and Michael Friedlander. The abstract reads:

The joint-sparse recovery problem aims to recover, from sets of compressed measurements, unknown sparse matrices with nonzero entries restricted to a subset of rows. This is an extension of the single-measurement-vector (SMV) problem widely studied in compressed sensing. We analyze the recovery properties for two types of recovery algorithms. First, we show that recovery using sum-of-norm minimization cannot exceed the uniform recovery rate of sequential SMV using L1 minimization, and that there are problems that can be solved with one approach but not with the other. Second, we analyze the performance of the ReMBo algorithm [M. Mishali and Y. Eldar, IEEE Trans. Sig. Proc., 56 (2008)] in combination with L1 minimization, and show how recovery improves as more measurements are taken. From this analysis it follows that having more measurements than number of nonzero rows does not improve the potential theoretical recovery rate.

The attendant code allowing one to reproduce the figures of this paper can be found here.


The Rice repository added two new additions:

Counting the Scaled +1/-1 Matrices that Satisfy the Restricted Isometry Property by Gilles Gnacadja. The abstract reads:

An mxn real matrix \phi is said to satisfy the Restricted Isometry Property (RIP) of order k if it nearly preserves the l2-norm of all vectors in Rn that have no more than k nonzero entries. Matrices that satisfy the RIP are useful in compressed sensing, a fast-expanding eld of mathematics and signal processing. The mxn matrices with entries +1 and -1 and scaled by 1/sqrt(m) are often mentioned as an example of matrices that satisfy the RIP with high probability. We show that if n \lt 2^m-1, then the precise count of these matrices that satisfy the RIP of order k = 2 is

\rho(m,n) = 2^n Product( 2^(m-1) -j)

and the restricted isometry constants do not exceed 1 - 2/m. If n ¡\gt 2^(m-1), then there are no scaled +1/-1 matrices of size mxn that satisfy the RIP, except for the order k = 1.

and Sparse Event Detection in Wireless Sensor Networks using Compressive Sensing by Jia Meng, Husheng Li, and Zhu Han, The abstract reads:

Compressive sensing is a revolutionary idea proposed recently to achieve much lower sampling rate for sparse signals. For large wireless sensor networks, the events are relatively sparse compared with the number of sources. Because of deployment cost, the number of sensors is limited, and due to energy constraint, not all the sensors are turned on all the time. In this paper, the first contribution is to formulate the problem for sparse event detection in wireless sensor networks asa compressive sensing problem. The number of (wake-up) sensors can be greatly reduced to the similar level of the number of sparse events, which is much smaller than the total number of sources. Second, we suppose the event has the binary nature, and employ the Bayesian detection using this prior information. Finally, we analyze the performance of the compressive sensing algorithms under the Gaussian noise. From the simulation results, we show that the sampling rate can reduce to 25% without sacrificing performance. With further decreasing the sampling rate, the performance is gradually reduced until 10% of sampling rate. Our proposed detection algorithm has much better performance than the l1-magic algorithm proposed in the literature.

Image Credit: NASA/JPL/Space Science Institute, Saturn Moon shadow as explained here.

CS: split bregman, Bregmanized Nonlocal Regularization, One Sketch For All, A Sparse and Non-Negative Solution of Ax=b, MMSE Est. for Sparse Rep.

Today we have a paper that are not strictly CS but rather hover on the subject, however, if you feel like you ought to put your head for a challenge, you may want to hit this one.

Geometric Applications of the Split Bregman Method: Segmentation and Surface Reconstruction by Tom Goldstein, Xavier Bresson and Stanley Osher.The attendant code is here. The abstract reads:

Variational models for image segmentation have many application, but can be slow to compute. Recently, globally convex segmentation models have been introduced which are very reliable, but contain TV-regularizers, making them diffcult to compute. The previously introduced Split Bregman method is a technique for fast minimization of L1 regularized functionals, and has been applied to denoising and compressed sensing problems. By applying the Split Bregman concept to image segmentation problems, we build fast solvers which can out-perform more conventional schemes, such as duality based methods and graph-cuts. We also consider the related problem of surface reconstruction from unorganized data points, which is used for constructing level set representations in 3 dimensions.

Bregmanized Nonlocal Regularization for Deconvolution and Sparse Reconstruction by Xiaoqun Zhang, Martin Burger, Xavier Bresson, and Stanley Osher.

We propose two algorithms based on Bregman iteration and operator splitting technique for nonlocal TV regularization problems. The convergence of the algorithms is analyzed and applications to deconvolution and sparse reconstruction are presented.

One Sketch For All: Theory and Application of Conditional Random Sampling by Ping Li, Kenneth W. Church and Trevor J. Hastie. The abstract reads:

Conditional Random Sampling (CRS) was originally proposed for efficiently computing pairwise (l2, l1) distances, in static, large-scale, and sparse data. This study modifies the original CRS and extends CRS to handle dynamic or streaming data, which much better reflect the real-world situation than assuming static data. Compared with many other sketching algorithms for dimension reductions such as stable random projections, CRS exhibits a significant advantage in that it is “one-sketch-for-all.” In particular, we demonstrate the effectiveness of CRS in efficiently computing the Hamming norm, the Hamming distance, the lp distance,and the l2 distance. A generic estimator and an approximate variance formula are also provided, for approximating any type of distances. We recommend CRS as a promising tool for building highly scalable systems, in machine learning, data mining, recommender systems, and information retrieval.

Compressible Dictionary Learning for Fast Sparse Approximation by Mehrdad Yaghoobi and Mike Davies. ( also in Poster). The abstract reads:

By solving a linear inverse problem under a sparsity constraint, one can successfully recover the coefficients, if there exists such a sparse approximation for the proposed class of signals. In this framework the dictionary can be adapted to a given set of signals using dictionary learning methods. The learned dictionary often does not have useful structures for a fast implementation, i.e. fast matrix-vector multiplication. This prevents such a dictionary being used for the real applications or large scale problems. The structure can be induced on the dictionary throughout the learning progress. Examples of such structures are shift-invariance and being multi-scale. These dictionaries can be efficiently implemented using a filter bank. In this paper a well-known structure, called compressibility, is adapted to be used in the dictionary learning problem. As a result, the complexity of the implementation of a compressible dictionary can be reduced by wisely choosing a generative model. By some simulations, it has been shown that the learned dictionary provides sparser approximations, while it does not increase the computational complexity of the algorithms, with respect to the pre-designed fast structured dictionaries.

a little old (2008) but I don't recall featured it is a presentation by Michael Elad entitled:
A Sparse and Non-Negative Solution of Ax=b is Necessarily Unique (also in pdf) by Alfred Bruckstein, Michael Elad, and Michael Zibulevsky

An underdetermined linear system of equations Ax = b with non-negativity constraint is considered. It is shown that for matrices A with a row-span intersecting the positive orthant, if this problem admits a sufficiently sparse solution, it is necessarily unique. The bound on the required sparsity depends on a coherence property of the matrix A. It is further shown that A undergoes a conditioning stage with some degrees of freedom, which may be used to improve the coherence measure and strengthen the claimed result

newer is MMSE Estimation for Sparse Representation Modeling (also in ppt) by Michael Elad,

Cleaning of noise from signals is a classical and long-studied problem in signal processing. Algorithms for this task necessarily rely on an a-priori knowledge about the signal characteristics, along with information about the noise properties. For signals that admit sparse representations over a known dictionary, a commonly used denoising technique is to seek the sparsest representation that synthesizes a signal close enough to the corrupted one. As this problem is too complex in general, approximation methods, such as greedy pursuit algorithms, are often employed. In this line of reasoning, we are led to believe that detection of the sparsest representation is key in the success of the denoising goal. Does this means that other competitive and slightly inferior sparse representations are meaningless? Suppose we are served with a group of competing sparse representations, each claiming to explain the signal differently. Can those be fused somehow to lead to a better result? Surprisingly, the answer to this question is positive; merging these representations can form a more accurate, yet dense, estimate of the original signal even when the latter is known to be sparse. In this talk we demonstrate this behavior, propose a practical way to generate such a collection of representations by randomizing the Orthogonal Matching Pursuit (OMP) algorithm, and produce a clear analytical justification for the superiority of the associated Randomized OMP (RandOMP) algorithm. We show that while the Maximum a-posterior Probability (MAP) estimator aims to find and use the sparsest representation, the Minimum Mean-Squared-Error (MMSE) estimator leads to a fusion of representations to form its result. Thus, working with an appropriate mixture of candidate representations, we are surpassing the MAP and tending towards the MMSE estimate, and thereby getting a far more accurate estimation, especially at medium and low SNR. Another topic covered in thistalk concerns the case of a unitary dictionary. In such a case it is well-known that the MAP estimators has a closed-form and exact solution, and OMP is accurately computing it. Can a similar result be derived for MMSE? We show that this is indeed possible, obtaining a recursive formula that computes the MMSE simply and exactly.

Credit & Copyright: Ralf Vandebergh, this photo shows an atronaut walking next to one of the truss of the international space station. this photo was tekn from the ground (i.e. from 250 miles up). Via APOD.

Sparsity in Everything: Amazing Talents

The World is surrounded by a host of power laws. When one sets some threshold in groups following these power laws, one is evidently producing sparse sets. Here is a case from "Britain's got talent", a similar show to "American Idol" in the U.S. and "Nouvelle Star" in France:

and the less sparse set:

From a compressive sensing point of view, the big question is: could we determine which one is a good singer among many when all of them are singing at the same time while randomly modulating each of their voices ?


Other examples of Sparsity in Everything can be found in this collection of entries.
Credit: The idea of that first video came from reading Seth Goldin's blog on the dip.

CS: Irregular tiling in retina, Recognition using information-optimal adaptive feature-specific imaging, other CS hardware encoding.

I wanted to do an entry on it, but David Brady beat me to it in his blog entry entitled Irregular Image Sampling about the recent PloS paper entitled: Receptive Fields in Primate Retina Are Coordinated to Sample Visual Space More Uniformly by Jeffrey L. Gauthier, Greg D. Field, Alexander Sher, Martin Greschner, Jonathon Shlens, Alan M. Litke, E. J. Chichilnisky. It echoes previous entries such as these:

• CS: Tilings, Islamic Art, Our Retina, Papoulis Sub-Nyquist Theorem
• CS: a job, Golden Ratio Radial Imaging, Model-based CS MRI, Rate Distortion Behavior of Sparse Sources, MP Shrinkage in Hilbert Spaces
• Compressed Sensing in the Primary Visual Cortex ?

Pawan Baheti, a reader of this blog, let me know of some of his papers. The "work in this [first] paper is based on compressive imaging architecture; however it does not uses random projections rather figures out the optimal basis based on a priori information and already measured projections data."

Here they are:

Recognition using information-optimal adaptive feature-specific imaging by Pawan Baheti and Mark A. Neifeld. The abstract reads:

We present an information-theoretic adaptive feature-specific imaging (AFSI) system for a M-class recognition task. The proposed system utilizes the recently developed task-specific information (TSI) framework to incorporate the knowledge from previous measurements and adapt the projection matrix at each step. The decision-making framework is based on sequential hypothesis testing. We quantify the number of measurements required to achieve a specified probability of misclassification (P_e), and we compare the performances of three approaches: the new TSI-based AFSI system, a previously reported statistical AFSI system, and static FSI (SFSI). The TSI-based AFSI system exhibits significant improvement compared with SFSI and statistical AFSI at low signal-to-noise ratio (SNR). It is shown that for M=4 hypotheses, SNR=−20 dB and desired P_e=10⁻², TSI-based AFSI requires 3 times fewer measurements than statistical AFSI, and 16 times fewer measurements than SFSI. We also describe an extension of the proposed method that is suitable for recognition in the presence of nuisance parameters such as illumination conditions and target orientations.

Pawan has told me the following:

...I am currently at Qualcomm research and have applied compressed sensing framework to biomedical signals like PPG, ECG for reducing acquisition power, task-specific estimation and concealment from channel-errors. Some of the work is published in 2009 Bodynets and BSN conferences.

Here are the paper titles: Heart Rate and Blood Pressure Estimation from Compressively Sensed Photoplethysmograph by Pawan Baheti and Harinath Garudadri. The abstract reads:

In this paper we consider the problem of low power ${\textmd{S}}_{p}{\textmd{O}}_{2}$ sensors for acquiring Photoplethysmograph (PPG) signals. Most of the power in ${\textmd{S}}_{p}{\textmd{O}}_{2}$ sensors goes to lighting red and infra-red LEDs. We use compressive sensing to lower the amount of time LEDs are lit, thereby reducing the signal acquisition power. We observe power savings by a factor that is comparable to the sampling rate. At the receiver, we reconstruct the signal with sufficient integrity for a given task. Here we consider the tasks of heart rate (HR) and blood pressure (BP) estimation. For BP estimation we use ECG signals along with the reconstructed PPG waveform. We show that the reconstruction quality can be improved at the cost of increasing compressed sensing bandwidth and receiver complexity for a given task. We present HR and BP estimation results using the MIMIC database.

and An Ultra Low Power Pulse Oximeter Sensor Based On Compressed Sensing.

Thanks Pawan !

One more word, while papers are properties of most journals, journals also allow authors to post their preprints/postprints on their website for archival purposes. For instance, this is the case for the JOSAa.

CS: A Class of Novel STAP Algorithms Using Sparse Recovery Technique, Space-optimal Heavy Hitters, Image reconstruction, CiteULike

Found on the interwebs:

A Class of Novel STAP Algorithms Using Sparse Recovery Technique by Hao Zhang, Gang Li, Huadong Meng. The abstract reads:

A class of novel STAP algorithms based on sparse recovery technique were presented. Intrinsic sparsity of distribution of clutter and target energy on spatial-frequency plane was exploited from the viewpoint of compressed sensing. The original sample data and distribution of target and clutter energy was connected by a ill-posed linear algebraic equation and popular $L_1$ optimization method could be utilized to search for its solution with sparse characteristic. Several new filtering algorithm acting on this solution were designed to clean clutter component on spatial-frequency plane effectively for detecting invisible targets buried in clutter. The method above is called CS-STAP in general. CS-STAP showed their advantage compared with conventional STAP technique, such as SMI, in two ways: Firstly, the resolution of CS-STAP on estimation for distribution of clutter and target energy is ultra-high such that clutter energy might be annihilated almost completely by carefully tuned filter. Output SCR of CS-STAP algorithms is far superior to the requirement of detection; Secondly, a much smaller size of training sample support compared with SMI method is requested for CS-STAP method. Even with only one snapshot (from target range cell) could CS-STAP method be able to reveal the existence of target clearly. CS-STAP method display its great potential to be used in heterogeneous situation. Experimental result on dataset from mountaintop program has provided the evidence for our assertion on CS-STAP.

Nice article but my attention was focused on a tidbit. It looks to me that we are bound to see this again and again as soon as engineering fields are going to adopt compressive sensing:

Although many methods to construct matrix satisfying RIP (especially randomization method) have been brought forward[17], a lack of effective means for testing RIP and estimating RIP constant of a given deterministic matrix is still a hidden trouble for practitioners and user of compressed sensing technique[26], no exception for us. It is very hard to verify RIP of matrix used in STAP operation based on sparse recovery algorithm theoretically. So the detailed conditions for L0/L1 equivalence will not be checked in our research. Fortunately, no severe consequence was encountered generally, because simply using L1 optimization could we find the solution of (13) with some characteristic of sparsity (although it maybe isn’t the most sparse one). That is just what we want in most cases.

See my remark on the presentation by Hongkai Zhao on "A fast solver for radiative transport equation and applications in optical imaging". In few words, we are bound to see more and more engineering fields not liking random matrices mostly because they are not physically feasible and it is urgent that the community focuses on making mainstream the tools that checks whether a given a measurement matrix is acceptable for l1 recovery such as the tools presented in On verifiable sufficient conditions for sparse signal recovery via L1 minimization by Anatoli Juditsky and Arkadi Nemirovski. An implementation is available at this site:

http://sites.google.com/site/testsensingmatrices/

or in Testing the Nullspace Property using Semidefinite Programming by Alexandre d'Aspremont and Laurent El Ghaoui where the NSProp implementation is now available at:

http://www.princeton.edu/~aspremon/NSPcode.htm

Both programs check a condition on a constant \alpha_k. The study of the value of \alpha_k with small matrices could allow one to investigate low order models as well as specific dictionaries.... These two programs are prominently listed in the measurement matrix section of the Big Picture.

I also found this paper entitled: Space-optimal Heavy Hitters with Strong Error Bounds by Radu Berinde, Graham Cormode, Piotr Indyk and Martin Strauss. The abstract reads:

The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of “counter-based algorithms” (including the popular and very space-efficient FREQUENT and SPACESAVING algorithms) provide much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining “tail.” This shows that counter-based methods are the most space efficient (in fact, space-optimal) algorithms having this strong error bound. This tail guarantee allows these algorithms to solve the “sparse recovery” problem. Here, the goal is to recover a faithful representation of the vector of frequencies, f. We prove that using space O(k), the algorithms construct an approximation f to the frequency vector f so that the L1 error ||f − f||1 is close to the best possible error minf′ ||f′ − f||1, where f′ ranges over all vectors with at most k non-zero entries. This improves the previously best known space bound of about O(k log n) for streams without element deletions (where n is the size of the domain from which stream elements are drawn). Other consequences of the tail guarantees are results for skewed (Zipfian) data, and guarantees for accuracy of merging multiple summarized streams.

Finally, Anna Scaife, made a presentation on Image reconstruction using Compressed Sensing a work with Yves Wiaux, Laurent Jacques, Gilles Puy, Pierre Vandergheynst.

And The Big Picture site has recently been put on Citeulike:

http://www.citeulike.org/user/PaperCollector/article/4248192

woohoo, it now has a bibtex entry:

@article{citeulike:4248192,
citeulike-article-id = {4248192},
keywords = {compressivesensin},
posted-at = {2009-03-31 23:11:32},
priority = {2},
title = {Igor Carron - Compressive Sensing: The Big Picture},
url = {http://igorcarron.googlepages.com/cs}
}

Credit Photo: NASA, Soyuz Landing in Kazakhstan.

Sparsity in Everything: Natural Laws from Experimental Data

There are many examples of sparsity in real life such as Solutions to Everyday Decision Making, Noisy Protein-Protein Interaction, Non-Junk DNA and here is a new one. We are already seeing this in the numerous bayesian approaches to compressive sensing but there are other approaches to sparse approximation that look like combinatorial trials such as in the latest paper by Michael Schmidt and Hod Lipson entitled Distilling Free-Form Natural Laws from Experimental Data. The abstract reads:

For centuries, scientists have attempted to identify and document analytical laws that underlie physical phenomena in nature. Despite the prevalence of computing power, the process of finding natural laws and their corresponding equations has resisted automation. A key challenge to finding analytic relations automatically is defining algorithmically what makes a correlation in observed data important and insightful. We propose a principle for the identification of nontriviality. We demonstrated this approach by automatically searching motion-tracking data captured from various physical systems, ranging from simple harmonic oscillators to chaotic double-pendula. Without any prior knowledge about physics, kinematics, or geometry, the algorithm discovered Hamiltonians, Lagrangians, and other laws of geometric and momentum conservation. The discovery rate accelerated as laws found for simpler systems were used to bootstrap explanations for more complex systems, gradually uncovering the “alphabet” used to describe those systems.

To fit the phenomena at hand, a combinatorial search is performed using genetic algorithms. As one can see in the graph above, the trade-off between parsimony and accuracy tends to lean towards simpler and therefore unique models. I note that the learning is performed using videos of the effects being studied. I also note that the examples being studied do not seem to have much occlusion effects ( see the entry on the non-differentiability in images featuring occluding elements) and therefore they are really learning on a smooth manifold like in [1], [2]. Here is a video presentation of the work and their site:

This experiment really begs the question as to whether a compressive sensing technique avoiding the combinatorial search could be attempted. Anyway, if you have other examples, send them to me by E-mail, or in the comment section or by Twitter.

[1] Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain by Robert Calderbank, Sina Jafarpour, and Robert Schapire,
[2] Richard Baraniuk: Manifold models for signal acquisition, compression, and processing, Slides (pdf), Video (flv), a joint work with Mark Davenport, Marco Duarte, Chinmay Hegde, and Michael Wakin.