CS: In this post I continue to not care about any proofs regarding P and NP... and more

I realize that I am commenting on the matter with some lateness .However, irrespective of the expected outcome (see Dick Lipton's latest entry on the subject), one could already make the following statement from day 1: It is very likely we should not care too much about this result in Compressive Sensing as shown in the argument developed here four months ago: In Compressive Sensing: P= NP + Additional Constraints. Let's not even add to that argument that being P also means an algorithm that scale in O(n^501) is OK as opposed to an NP algorithm that scales as O(exp(0.000000001n)).. At our level, the scales and their attendant constants are enormously important, asymptotics are not enough at least when it comes to the reconstruction solvers..

In unrelated news:

• I set up a static page on the Donoho-Tanner phase transition that helps document its uses and new result on the matter. It is here. Additional insights are welcome.
• The IPAM Modern Trends in Optimization and Its Application workshop has started on September 13th and will continue until December 17th. Some of you are there and you are reading Nuit Blanche while somebody is giving a presentation. Stop that, focus on the presentation, please.
• For $300 you can get your hands on an Emotiv EEG headset. This piece of equipment has just been hacked, so you can now get the raw EEG traces directly. Very nice. I'd like to play with that for sure.
• The LinkedIn Group on Compressive Sensing has reached 591 members, when will it reach its 1000th member is really what I'd like to know.
• Hurricane Igor is set to be monstrous but if History is any indication, all the Czars named Igor were abject failures. Let us hope this one follows their tracks into irrelevancy.

Credit: NOAA, NASA





If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

Hadi Zayyani's email has been hacked.

I received an email from Hadi this morning asking for some money to get him out of situation in Spain. The text was suspicious because it looked like somebody had used exactly the same text before. I then sent an email asking for where I could send the money in order to figure out if the account was still live. I just received confirmation that indeed somebody else has access to his account. If you know Hadi do not use email to let him know that he's been hacked, tell him directly. Thanks.

CS: Q&A with Pierre Vandergheynst about the CS-ECG system

[Update: Dear Hackaday readers, this ECG system is an instance of compressive sensing, where the encoding is very low power while the power hungry decoding of the signal is performed off line. A normal system requires the encoding of the signal (a power hungry process) to be performed during acquisition before sending the signal out.  The iPhone is a central piece and serves as a full scale computer . It performs state of the art optimization computations (l_1 minimization with wavelet frames) to decode the signal. ]


Following up on yesterday's entry on the CS-ECG trade studies performed by Pierre Vandergheynst at EPFL, and because of my commentary, I decided to ask him the following questions:

Pierre,

You may have noticed my remark on the blog about the CS-ECG. Yet, I think I am misunderstanding some part of the slide. Namely the right figure on this slide:

From your trade studies, you make the statement that CS is marginally better than no compression but I don't understand the point being made with the figure on the right. Can you enlighten me ?

Pierre kindly answered with

The improvement was only marginal for the msp430 system which revealed that its micro controller is too greedy in terms of power with respect to the antenna. However we show in the fig on the right that using truly low power microcontrollers can lead to dramatic reduction in power consumption: as the cs encoder becomes 7 to 8 times more efficient than an optimized wavelet coder...it was the first step in a more ambitious project. Second step is to build an analog to digital system that will use analog CS to sample the ECG, hence removing the power hungry a2d step

 I then asked:

Do you think this idea of classifier as an app has some legs  (Note: I personally do from experience)? Also can you also enlighten me as to why you are jailbreaking the iPhone, i.e. what part of the system is not currently available from the Apple API ?

Pierre answered

In fact the idea of performing classification on the measurements directly (if this is what you mean) is certainly very interesting and that is one of the directions in our bio cs node project. The idea would be to have a very reactive system that would just classify the heart signals and then if a specific situation is detected by the classifier the whole signal can be reconstructed, archived or sent to a physician.

As for the iPhone, the main problem was the bluetooth layer. Apple does not let you easily use it for general purpose communication. We thus had to break it to implement our own protocol.

All in all, I hope people realize that this is a complete system implementation from A to Z, and that using CS can become a crucial technology in a real life environment. It shows that there are many intricate but interesting issues when deploying CS in such a complete application.

 Thanks Pierre !

At the very least if a classifier is too difficult to implement on the multiple unhealthy cases revealed by an EKG, then a classifier could at the very least identify only those parts of the EKG traces when the heart is healthy. On a different note, I'll add this system on the compressive sensing hardware page.


If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

CS: The long post of the week : Ambulatory ECG, The brain and much mathematics...

This is how I wanted to start my post  today," Today we have mostly a post with a mathematical bent and two of them deal with ridgelets, mmmuhh, I also note that the inclusion of Compressive Sensing as a building block to our comprehension of the brain is building up ...Enjoy!" But then I checked the Twitter, and found out that Pierre Vandergheynst tweeted that he had posted his slide from a presentation in Marseille. So let us start with that and then you can all go for the mathematics:

Pierre Vandergheynst's slides are entitled Compressed Sensing,  Some experimental promises ?. Our french readers should be expecting to see images of slide 22 in La Recherche coming out in October. Aside from the the very nice MRI work mentioned before, I liked the use of the Donoho-Tanner phase transition to evaluate a hardware system.

Some new element of the presentation also included a very interesting trade study on a low-power ECG ambulatory system.

So it looks like this is not optimal in many respect. Yes, you reduce the power level but not with the dramatic effect initially expected. As I have said before, if you design your hardware to be providing exactly the same information as the one you are supposed to displace, then you are really asking to be irrelevant.....fast. The CS encoding not only has a clear advantage over no compression as it is robust to packet losses but more importantly, if Compressive Sensing is bringing one thing to the table, it is really that information is reduced and therefore that smaller classifiers can run some diagnostics on the jailbroken iPhone 3GS, I doubt that a similar classifier can do the job on the uncompressed data without using much needed power resources.

Coming back to the new papers and preprints, let us start with a more hardware oriented paper before diving into more mathematical matters:

Spatially regularized compressed sensing of diffusion MRI data by Oleg Michailovich, Yogesh Rathi. The abstract reads:

The present paper introduces a method for substantial reduction of the number of diffusion encoding gradients required for reliable reconstruction of HARDI signals. The method exploits the theory of compressed sensing (CS), which establishes conditions on which a signal of interest can be recovered from its under-sampled measurements, provided that the signal admits a sparse representation in the domain of a linear transform. In the case at hand, the latter is defined to be spherical ridgelet transformation, which excels in sparsifying HARDI signals. What makes the resulting reconstruction procedure even more accurate is a combination of the sparsity constraints in the diffusion domain with additional constraints imposed on the estimated diffusion field in the spatial domain. Accordingly, the present paper describes a novel way to combine the diffusion- and spatial-domain constraints to achieve a maximal reduction in the number of diffusion measurements, while sacrificing little in terms of reconstruction accuracy. Finally, details are provided on a particularly efficient numerical scheme which can be used to solve the aforementioned reconstruction problem by means of standard and readily available estimation tools. The paper is concluded with experimental results which support the practical value of the proposed reconstruction methodology.

At NIPS the accepted papers list came up but I could not find the actual presentations or papers so I went ahead and looked up the authors and found the following two: Adaptive compressed sensing – a new class of self-organizing coding models for neuroscience by William K. Coulter, Christopher J. Hillar, Guy Isely, Friedrich T. Sommer. The abstract reads:

Sparse coding networks, which utilize unsupervised learning to maximize coding efficiency, have successfully reproduced response properties found in primary visual cortex [1]. However, conventional sparse coding models require that the coding circuit can fully sample the sensory data in a one-to-one fashion, a requirement not supported by experimental data from the thalamo-cortical projection. To relieve these strict wiring requirements, we propose a sparse coding network constructed by introducing synaptic learning in the framework of compressed sensing. We demonstrate that the new model evolves biologically realistic spatially smooth receptive fields despite the fact that the feedforward connectivity subsamples the input and thus the learning has to rely on an impoverished and distorted account of the original visual data. Further, we demonstrate that the model could form a general scheme of cortical communication: it can form meaningful representations in a secondary sensory area, which receives input from the primary sensory area through a “compressing” cortico-cortical projection. Finally, we prove that our model belongs to a new class of sparse coding algorithms in which recurrent
connections are essential in forming the spatial receptive fields.

and Statistical Mechanics of Compressed Sensing by Surya Ganguli, Haim Sompolinsky. The abstract reads:

Compressed sensing (CS) is an important recent advance that shows how to reconstruct sparse high dimensional signals from surprisingly small numbers of random measurements. The nonlinear nature of the reconstruction process poses a challenge to understanding the performance of CS. We employ techniques from the statistical physics of disordered systems to compute the typical behavior of CS as a function of the signal sparsity and measurement density.We find surprising and useful regularities in the nature of errors made by CS, a new phase transition which reveals the possibility of CS for nonnegative signals without optimization, and a new null model for sparse regression.

Also found on Arxiv:
Average best m-term approximation by Jan Vybıral. The abstract reads:

We introduce the concept of average best m-term approximation widths with respect to a probability measure on the unit ball of ℓn p . We estimate these quantities for the embedding id : ℓn p → ℓn q with 0 \lt p \le q \le ∞ for the normalized cone and surface measure. Furthermore, we consider certain tensor product weights and show that a typical vector with respect to such a measure exhibits a strong compressible (i.e. nearly sparse) structure.

Detection boundary in sparse regression by Yuri Ingster. , Alexander Tsybakov, and Nicolas Verzelen.. The abstract reads:

We study the problem of detection of a p-dimensional sparse vector of parameters in the linear regression model with Gaussian noise. We establish the detection boundary, i.e., the necessary and sufficient conditions for the possibility of successful detection as both the sample size n and the dimension p tend to the infinity. Testing procedures that achieve this boundary are also exhibited. Our results encompass the high-dimensional setting (p \gt\gt n). The main message is that, under some conditions, the detection boundary phenomenon that has been proved for the Gaussian sequence model, extends to high-dimensional linear regression. Finally, we establish the detection boundaries when the variance of the noise is unknown. Interestingly, the detection boundaries sometimes depend on the knowledge of the variance in a high-dimensional setting.

Large deviations of the extreme eigenvalues of random deformations of matrices by Florent Benaych-Georges, Alice Guionnet, Mylène Maïda. The abstract reads:

Consider a real diagonal deterministic matrix $X_n$ of size $n$ with spectral measure converging to a compactly supported probability measure. We perturb this matrix by adding a random finite rank matrix of a certain form, with delocalized eigenvectors. We show that the joint law of the extreme eigenvalues of the perturbed model satisfies a large deviation principle, in the scale n with a good rate function given by a variational formula. We tackle both cases when the extreme eigenvalues of X_n converge to the edges of the support of the limiting measure and when we allow some eigenvalues of X_n, that we call outliers, to converge out of the bulk. We can also generalise our results to the case when X_n is random, with law proportional to e^{- Trace V(X)}d X, for V growing fast enough at infinity and any perturbation of finite rank with orthonormal eigenvectors.

Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices by Florent Benaych-Georges, Alice Guionnet, Mylène Maïda. The abstract reads:

Consider a deterministic self-adjoint matrix X_n with spectral measure converging to a compactly supported probability measure, the largest and smallest eigenvalues converging to the edges of the limiting measure. We perturb this matrix by adding a random finite rank matrix with delocalized eigenvectors and study the extreme eigenvalues of the deformed model. We show that the eigenvalues converging out of the bulk exhibit Gaussian fluctuations, whereas under additional hypotheses, the eigenvalues sticking to the edges are very close to the eigenvalues of the non-perturbed model and fluctuate in the same scale. We can also generalise these results to the case when X_n is random and get similar behaviour when we deform some classical models such as Wigner or Wishart matrices with rather general entries or the so-called matrix models.

Learning Functions of Few Arbitrary Linear Parameters in High Dimensions by Massimo Fornasier, Karin Schnass, Jan Vybíral. The abstract reads:

Let us assume that $f$ is a continuous function defined on the unit ball of $\mathbb R^d$, of the form $f(x) = g (A x)$, where $A$ is a $k \times d$ matrix and $g$ is a function of $k$ variables for $k \ll d$. We are given a budget $m \in \mathbb N$ of possible point evaluations $f(x_i)$, $i=1,...,m$, of $f$, which we are allowed to query in order to construct a uniform approximating function. Under certain smoothness and variation assumptions on the function $g$, and an {\it arbitrary} choice of the matrix $A$, we present in this paper 1. a sampling choice of the points $\{x_i\}$ drawn at random for each function approximation; 2. an algorithm for computing the approximating function, whose complexity is at most polynomial in the dimension $d$ and in the number $m$ of points. Due to the arbitrariness of $A$, the choice of the sampling points will be according to suitable random distributions and our results hold with overwhelming probability. Our approach uses tools taken from the {\it compressed sensing} framework, recent Chernoff bounds for sums of positive-semidefinite matrices, and classical stability bounds for invariant subspaces of singular value decompositions.

A variant of the Johnson-Lindenstrauss lemma for circulant matrices by Jan Vybíral. The abstract reads:

We continue our study of the Johnson-Lindenstrauss lemma and its connection to circulant matrices started in \cite{HV}. We reduce the bound on $k$ from $k=O(\epsilon^{-2}\log^3n)$ proven there to $k=O(\epsilon^{-2}\log^2n)$. Our technique differs essentially from the one used in \cite{HV}. We employ the discrete Fourier transform and singular value decomposition to deal with the dependency caused by the circulant structure.

An attendant presentation on the subject is here.

Finally we have: A Hierarchical Bayesian Framework for Constructing Sparsity-inducing Priors by Anthony Lee, Francois Caron, Arnaud Doucet, Chris Holmes. The abstract reads:

Variable selection techniques have become increasingly popular amongst statisticians due to an increased number of regression and classification applications involving high-dimensional data where we expect some predictors to be unimportant. In this context, Bayesian variable selection techniques involving Markov chain Monte Carlo exploration of the posterior distribution over models can be prohibitively computationally expensive and so there has been attention paid to quasi-Bayesian approaches such as maximum a posteriori (MAP) estimation using priors that induce sparsity in such estimates. We focus on this latter approach, expanding on the hierarchies proposed to date to provide a Bayesian interpretation and generalization of state-of-the-art penalized optimization approaches and providing simultaneously a natural way to include prior information about parameters within this framework. We give examples of how to use this hierarchy to compute MAP estimates for linear and logistic regression as well as sparse precision-matrix estimates in Gaussian graphical models. In addition, an adaptive group lasso method is derived using the framework

A new version of Compressed Genotyping is available.



Image Credit: NASA/JPL/Space Science Institute
N00163047.jpg was taken on September 10, 2010 and received on Earth September 11, 2010. The camera was pointing toward JANUS, and the image was taken using the CL1 and CL2 filters.

CS: Job offers, TFOCS: Templates for Convex Cone Problems with Applications to Sparse Signal Recovery, a course on Compressed Sensing in Belgium

This is the post I wanted to write for a long time since it contains information spanning education, algorithm development and actual jobs for hardware development.. Several job offers and an approach to reconstruction that is likely to provide a wide range of useful new reconstruction solvers. and a course are in the mix today. I'll leave the post up for the next few days, enjoy!

The job offers first (both of them are on the CS jobs page)

• September 10th, 2010,  Job Openings at InView Technology Corporation, Austin, TX InView is a manufacturer of CS based cameras and hyperspectral imagers, and is commercializing the research results of Rich Baraniuk and Kevin Kelly at Rice University. We are looking to fill a number of positions, especially a CS Signal Processing expert. Please see http://www.inviewcorp.com/careers.html
  
• September 10th, 2010, Compressed Sensing Scientist / 9month Research Project 2011
  We seek to collaborate with a scientist for a research project proposal. The Research Task is as follows:
  
  Contributors are sought to significantly advance the through-put and efficiency of collecting large amounts of useful data through novel, mission prioritized data acquisition and compression capabilities, without loss of signal integrity.
  
  Potential topics for consideration include, but are not limited to, the following:
  - Algorithm development or improvement allowing for user-defined prioritization of lossless data compression or extraction
  - Computational methods that assist in mission prioritized data collection, transmission or transfer
  - Development of machine learning methods to reduce total data collection
  - Investigation into compressed sensing techniques applicable for very large data collections
  
  If granted this project, a 9month payed task would be awarded. Our response, in form of 'Proposal' is due Sept 15. v/r, Eric

Now onto the new reconstruction approach: TFOCS

Templates for Convex Cone Problems with Applications to Sparse Signal Recovery by Stephen Becker, Emmanuel J. Candes and Michael Grant. The abstract reads:

This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields. The approach works as follows: fi rst, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal rst-order method. A merit of this approach is its flexibility: for example, all compressed sensing problems can be solved via this approach. These include models with objective functionals such as the total-variation norm, kWxk1 where W is arbitrary, or a combination thereof. In addition, the paper also introduces a number of technical contributions such as a novel continuation scheme, a novel approach for controlling the step size, and some new results showing that the smooth and unsmoothed problems are sometimes formally equivalent. Combined with our framework, these lead to novel, stable and computationally efficient algorithms. For instance, our general implementation is competitive with state-of-the-art methods for solving intensively studied problems such as the LASSO. Further, numerical experiments show that one can solve the Dantzig selector problem, for which no efficient large-scale solvers exist, in a few hundred iterations. Finally, the paper is accompanied with a software release. This software is not a single, monolithic solver; rather, it is a suite of programs and routines designed to serve as building blocks for constructing complete algorithms.

From the contribution section:

The formulation of compressed sensing models in conic form is not widely known. Yet the convex optimization modeling framework CVX [22] converts all models into conic form; and the compressed sensing package `1-Magic [13] converts problems into second-order cone programs (SOCPs). Both systems utilize interior-point methods instead of rst-order methods, however. As mentioned above, the smoothing step is inspired by [35], and is similar in structure to traditional Lagrangian augmentation. As we also noted, first-order methods have been a subject of considerable research. Taken separately, then, none of the components in this approach is new. However their combination and application to solve compressed sensing problems leads to e ective algorithms that have not previously been considered. For instance, applying our methodology to the Dantzig selector gives a novel and efficient algorithm (in fact, it gives several novel algorithms, depending on which conic form is used). Numerical experiments presentedlater in the paper show that one can solve the Dantzig selector problem with a reasonable number of applications of A and its adjoint; the exact number depends upon the desired level of accuracy. In the case of the LASSO, our approach leads to novel algorithms which are competitive with state-of-the-art methods such as SPGL1. Aside from good empirical performance, we believe that the primary merit of our framework lies in its flexibility. To be sure, all the compressed sensing problems listed at the beginning of this paper, and of course many others, can be solved via this approach. These include total-variation norm problems, `1-analysis problems involving objectives of the form kWxk1 where W is neither orthogonal nor diagonal, and so on. In each case, our framework allows us to construct an effective algorithm, thus providing a computational solution to almost every problem arising in sparse signal or low-rank matrix recovery applications.
Furthermore, in the course of our investigation, we have developed a number of additional technical contributions. For example, we will show that certain models, including the Dantzig selector, exhibit an exact penalty property: the exact solution to the original problem is recovered even when some smoothing is applied. We have also developed a novel continuation scheme that allows us to employ more aggressive smoothing to improve solver performance while still recovering the exact solution to the unsmoothed problem. The flexibility of our template also provides opportunities to employ novel approaches for controlling the step size.

The TFOCS page is here.


Also Jared Tanner asked me to announce a course on CS in Belgium:

Would you mind announcing a short course I am giving on compressed sensing in Belgium this November and December?
Details are at: http://sites.uclouvain.be/socn/Courses/Courses2010-1
It will assume no background on the topic, go through many of the celebrated proofs and main topics during the 18 hours of lectures.  I understand that although targeted for PhD students in Belgium, anyone is welcome to attend, but it isn't free.

The desciption of the course reads:

Description

A revolution is underway in how information is collected and analysed. Traditionally, vast amounts of data are compiled, the essential features are extracted, and the remaining data disposed of. For instance, the resolution of consumer grade digital cameras is rated in terms of millions of pixels (points) measured, whereas the resulting images are typically smaller by a factor of hundreds. To diminish this highly inefficient model, techniques have been developed that learn from their earlier measurements, and in doing so try to determine the essential features with fewer adaptive measurements. Unfortunately, adaptive measurements must be taken sequentially, which limits the usefulness of such techniques in our modern real-time distributed computing environment.

In 2004 the Compressed Sensing paradigm was introduced by Donoho as well as Candes and Tao. From completely non-adaptive measurements, this technique recovers the dominant information in data at the minimum possible sampling rate achievable by learning algorithms. This is possible by replacing traditional point samples with randomised sampling and a novel reconstruction algorithm. The underlying principal's of this technique has since been extended to other notion where some underlying simplicity can be exploited. For instance, matrix completion is a new technique where unknown entries in a matrix can be predicted from a small subset of its entries, provided the matrix can be well approximated by a low rank matrix.

This course will: review methods from numerical harmonic analysis and approximation theory that give sparse/simple representations, introduce compressed sensing and methods by which the fundamental results can be proven, and explore extensions of compressed sensing and sparse approximation to matrix completion.

Session 1: A tour of numerical harmonic analysis. Review classical approximation properties of fourier series and orthogonal polynomials. Introduce multiscale techniques, wavelets, and higher dimensional extensions such as curvelets and shearlets.

Session 2: Basis Pursuit as a method to construct data adaptive representations. Introduction to generic methods of analysis from sparse approximation: coherence, cumulative coherence, and the restricted isometry property. Prove basic results for linear programming and one step thresholding.

Session 3: Introduction to compressed sensing and encoder/decoder pairs. Analyze greedy decoders Orthogonal Matching Pursuit, Iterated Hard Thresholding, and two-step greedy methods.

Session 4: The phase transition framework for decoders. Establish bounds on the restricted isometry constants for matrix ensembles: Gaussian, Fourier, and sparse discrete matrices.

Session 5: Geometric models of sparsity. Analysis of the linear programming decoder, nonnegativity uniqueness, bound constraints, and nonconvex models.

Session 6: Introduction to matrix completion. Low rank approximation, sampling and subspace coherence, and applications.

Credit: NASA/JPL/Space Science Institute, Quartet and Crescent  September 10, 2010

CS: Q&As, Sensing Matrix Optimization for Block-Sparse Decoding

The Compressive Sensing Group on LinkedIn now features 578 members:. Some of the recent questions include:

• Juan asks a rather long question:CS for Stipmap SAR Radar Imaging
• Arun also asks: Can anyone tell me which algorithm works well for sparse reconstruction using complex matrices. I'm using OMP but the probability of error seems to be too large

On the CS Theory Q&A site, Suresh provided an answer to the complexity of the SL0 algorithm which sounds right. The CS Theory Q&A site has crossed the 1000 user mark. Woohoo.

On Arxiv, the following interesting paper just showed up: Sensing Matrix Optimization for Block-Sparse Decoding by: Kevin Rosenblum, Lihi Zelnik-Manor, Yonina C. Eldar. The abstract reads:

Recent work has demonstrated that using a carefully designed sensing matrix rather than a random one, can improve the performance of compressed sensing. In particular, a well-designed sensing matrix can reduce the coherence between the atoms of the equivalent dictionary, and as a consequence, reduce the reconstruction error. In some applications, the signals of interest can be well approximated by a union of a small number of subspaces (e.g., face recognition and motion segmentation). This implies the existence of a dictionary which leads to block-sparse representations. In this work, we propose a framework for sensing matrix design that improves the ability of block-sparse approximation techniques to reconstruct and classify signals. This method is based on minimizing a weighted sum of the inter-block coherence and the sub-block coherence of the equivalent dictionary. Our experiments show that the proposed algorithm significantly improves signal recovery and classification ability of the Block-OMP algorithm compared to sensing matrix optimization methods that do not employ block structure.

CS: Around the blogs in 80 hours, Compressive Phase Contrast Tomography, Wideband Spectrum Sensing at Sub-Nyquist Rates

First, we have some blog entries:

• Piotr: Geometry @ Barriers
• Image Sensors World: Caeleste on X-Ray Photon Counting Sensors
• Andrew: Data Stream Algorithms slides
• Bob: Post-doc opportunity at INRIA
• Frank: Entropy of exponential families
• Terry: A first draft of a non-technical article on universality
• Hal: Manifold Assumption versus Margin Assumption

Then, the ONR just set a challenge on ideas related to Compressive Sensing in Urban Warfare. How are these challenges any different from your usual RFPs ? I don't know.

The day before yesterday, we talked about Jacket being used in the context of a reconstruction. Today this GPU based reconstruction with Jacket is part of a larger undertaking as featured in: Compressive Phase Contrast Tomography by F. R. N. C. Maia, A. MacDowell, Stefano Marchesini, H. A. Padmore, D. Y. Parkinson, Jack. Pien, Andre Schirotzek, and C. Yang. The abstract reads:

When x-rays penetrate soft matter, their phase changes more rapidly than their amplitude. Interference effects visible with high brightness sources creates higher contrast, edge enhanced images. When the object is piecewise smooth (made of big blocks of a few components), such higher contrast datasets have a sparse solution. We apply basis pursuit solvers to improve SNR, remove ring artifacts, reduce the number of views and radiation dose from phase contrast datasets collected at the Hard X-Ray Micro Tomography Beamline at the Advanced Light Source. We report a GPU code for the most computationally intensive task, the gridding and inverse gridding algorithm (non uniform sampled Fourier transform).

On the acquisition side, we have: :Wideband Spectrum Sensing at Sub-Nyquist Rates by Moshe Mishali, Yonina Eldar. The abstract reads:

We present a mixed analog-digital spectrum sensing method that is especially suited to the typical wideband setting of cognitive radio (CR). The advantages of our system with respect to current architectures are threefold. First, our analog front-end is fixed and does not involve scanning hardware. Second, both the analog-to-digital conversion (ADC) and the digital signal processing (DSP) rates are substantially below Nyquist. Finally, the sensing resources are shared with the reception path of the CR, so that the lowrate streaming samples can be used for communication purposes of the device, besides the sensing functionality they provide. Combining these advantages leads to a real time map of the spectrum with minimal use of mobile resources. Our approach is based on the modulated wideband converter (MWC) system, which samples sparse wideband inputs at sub-Nyquist rates. We report on results of hardware experiments, conducted on an MWC prototype circuit, which affirm fast and accurate spectrum sensing in parallel to CR communication.

CS: Some thoughts, Distributed Basis Pursuit, LASSO, Replica Analysis, Combining Nonconvex Compressed Sensing and GRAPPA, Multi-Sensor CS

As I am enjoying re-reading Glenn Knoll's Radiation Detection and Measurement that is a source of much detailed information on radiation sensors, I am very inspired at how some of the compressed sensing techniques could be involved in these detection processes. When performing ionizing radiation detection, several stages of conversion from the initial radiation down to the electrical current are needed. While each of these stages introduces inefficiencies (admittedly a bad thing) one should look at them as an opportunity whereby the physical detector can be changed to include an instance of compressed sensing. Some of these ideas have already been featured before and I expect to add some more to the list as a result of reading this book. The other take away lesson from this is:: every time the sensing process has conversion stages, it is ripe for an application of compressed sensing/group testing techniques.

Piotr Indyk added to yesterday's post::

Hi Igor,

A quick correction: the paper

New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property by Felix Krahmer and Rachel Ward. 

shows that * RIP implies JL* (after randomizing the matrices). The opposite direction is also true, but it has been known for a while now.

Thanks Piotr !

Here is the list of preprints and paper I just caught:

The first is of interest in the context of the recent development of all kinds of activities related to distributed computing: Distributed Basis Pursuit by João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, and Markus Püschel. The abstract reads:

Nowadays we are witnessing major changes both in the acquisition and representation of signals and in the computing platforms for their processing. One new acquisition technique is provided by the new theory of compressed sensing, which places a greater burden on the reconstruction of signals, usually a largescale optimization problem called Basis Pursuit (BP). BP consists of finding the least ℓ1 norm solution of the underdetermined linear systemMz = b. Computing platforms, on the other hand, show a trend to distributed processing, for example in the form of sensor networks. In this paper we present distributed algorithms for solving BP. This means the algorithms have no notion of “central” or any special node during their computations. We consider two scenarios in which either the columns or the rows of M are distributed among the compute nodes. We analyze the convergence of the algorithms and validate them through numerical simulations in a computer cluster.

other papers/preprints include:
A local stochastic Lipschitz condition with application to Lasso for high dimensional generalized linear models by Zhiyi Chi. The abstract reads:

For regularized estimation, the upper tail behavior of the random Lipschitz coefficient associated with empirical loss functions is known to play an important role in the error bound of Lasso for high dimensional generalized linear models. The upper tail behavior is known for linear models but much less so for nonlinear models. We establish exponential type inequalities for the upper tail of the coefficient and illustrate an application of the results to Lasso likelihood estimation for high dimensional generalized linear models.

Extension of Replica Analysis to MAP Estimation with Applications to Compressed Sensing by Sundeep Rangan, Alyson K. Fletcher, and Vivek K Goyal. The abstract reads:

The replica method is a non-rigorous but widely accepted technique from statistical physics used in the asymptotic analysis of large, random, nonlinear problems. This paper applies the replica method to analyze non-Gaussian maximum a posteriori (MAP) estimation. The main result is a counterpart to Guo and Verd´u’s replica analysis of minimum mean-squared error estimation. The replica MAP analysis can be readily applied to many estimators used in compressed sensing, including basis pursuit, lasso, linear estimation with thresholding, and zero norm-regularized estimation. Among other benefits, the replica method provides a computationally-tractable method for exactly computing various performance metrics including mean-squared error and sparsity pattern recovery probability

Combining Nonconvex Compressed Sensing and GRAPPA Using the Nullspace Method by D. S. Weller, J. R. Polimeni, L. J. Grady, L. L. Wald, E. Adalsteinsson, and Vivek K Goyal. The abstract reads:

There has been substantial interest in combining parallel image reconstruction methods like GRAPPA [1] with compressed sensing (CS) [2-4] to improve image quality at higher accelerations. Recent efforts have approached combining these methods either by cascading or iterating GRAPPA type and CS-type reconstructions [5-6] or by performing joint optimization with multiple objective functions [7]. The proposed method extends CS reconstruction in the nullspace of the acquired data [8] to jointly minimize the ℓ0-norm sparsity penalty and the ℓ2-norm deviation from GRAPPA reconstruction. This method approximates the ℓ0-norm using continuation with a differentiable nonconvex regularizer [9-10]. While this method generalizes to any sparsifying transform, we choose the discrete contourlet sparsifying transform [11] to illustrate its effectiveness in representing brain images. We demonstrate the proposed method reconstructs images at higher accelerations than GRAPPA or CS alone would allow.

A Multi-Sensor Compressed Sensing Receiver: Performance Bounds and Simulated Results by Benjamin Miller, Joel Goodman, and Keith Forsythe, John Z. Sun and Vivek K Goyal. The abstract reads:

Multi-sensor receivers are commonly tasked with detecting, demodulating and geolocating target emitters over very wide frequency bands. Compressed sensing can be applied to persistently monitor a wide bandwidth, given that the received signal can be represented using a small number of coefficients in some basis. In this paper we present a multi-sensor compressive sensing receiver that is capable of reconstructing frequency-sparse signals using block reconstruction techniques in a sensor-frequency basis. We derive performance bounds for time-difference and angle of arrival (AoA) estimation of such a receiver, and present simulated results in which we compare AoA reconstruction performance to the bounds derived.

Estimating Higher-Order Distances Using Random Projections by Ping Li, Michael Mahoney, and Yiyuan She. The abstract reads:

We provide a simple method and relevant theoretical analysis for efficiently estimating higherorder lp distances. While the analysis mainly focuses on l4, our methodology extends naturally to p = 6; 8; 10:::, (i.e., when p is even). Distance-based methods are popular in machine learning. In large-scale applications, storing, computing, and retrieving the distances can be both space and time prohibitive. Efficient algorithms exist for estimating lp distances if 0 \lt p · 2. The task for p \gt 2 is known to be difficult. Our work partially fills this gap.

Credit: NASA / GSFC / ASU, Natural Bridge on the Moon.

CS: The long entry of the week

[Dear Boing Boing readers; Nuit Blanche does not fulfill the Physics.org criteria as that criteria asks for a "non-specialist audience". The audience of this blog is nothing but made up of specialists. The fact that compressed sensing is at the heart of a potential revolution in sensors is of interest to a larger audience but these people are specialists nonetheless. Sorry!. And yes we occasionally have fluff stories here, here or here.]

Today we have an exciting and long entry made up of the different tidbits orbiting the compressed sensing world. Let us first check the blogs:

• Bob; A Briefly Annotated Timeline of Similarity in Audio Signals
• Alex: How well do you know your basic facts about convexity? (interesting :-))
• Frank: Bregman operator divergence
• Christian: In{s}a(ne)!!
• David: Adaptive Lenses
• Gonzalo: How does a Cognitive Radio job look like?

How does the Johnson-Lindenstrauss Lemma implies the Restricted Isometry Property ? Well you need to read the interesting: New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property by Felix Krahmer and Rachel Ward. The abstract reads:

Consider a set E of O(e^k) points in R^N, and an m by N matrix Phi with the Restricted Isometry Property of order k and level delta, that is, (1 - delta) || x ||_2^2 <= || Phi x ||_2^2 <= (1 + delta) || x ||_2^2 for all k-sparse x in R^N. We show that with high probability, such a matrix with randomized column signs embeds E into R^m without distorting the distance between any two points by more than a factor of 1 +- epsilon, with epsilon = 4delta. Consequently, matrices with the Restricted Isometry Property and with randomized column signs provide optimal Johnson-Lindenstrauss embeddings up to logarithmic factors in N. Our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices, optimizing the dependence on the distortion epsilon. In particular, for partial Fourier and partial Hadamard matrices, we improve the recent bound m = O(epsilon^(-4) log(p) log^4(N)) appearing in Ailon and Liberty to m = O(epsilon^(-2) log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also yield new Johnson-Lindenstrauss bounds for several deterministic matrices with randomized column signs.

Also on arxiv: A* Orthogonal Matching Pursuit: Best-First Search for Compressed Sensing Signal Recovery by Nazim Burak Karahanoglu, Hakan Erdogan. The abstract reads:

Compressed sensing is a recently developing area which is interested in reconstruction of sparse signals acquired in reduced dimensions. Acquiring the data with a small number of samples makes the reconstruction problem under-determined. The required solution is the one with minimum $l_0$ norm due to sparsity, however it is not practical to solve the $l_0$ minimization problem. Some methods, such as Basis Pursuit (BP) propose casting the problem as an $l_1$ minimization. Greedy pursuit algorithms, such as Orthogonal Matching Pursuit (OMP) and Subspace Pursuit (SP), perform a greedy search among the vectors in the basis with the goal of stagewise constrained minimization of the residual error. This manuscript proposes a new semi-greedy algorithm which employs a best-first search technique, the A* search. This approach searches for the solution on several paths of a search tree, where the paths are evaluated and extended according to some cost function, which should be carefully selected to compensate for paths with different lengths. Each path on the tree grows similar to the Orthogonal Matching Pursuit algorithm, hence this new approach is called A* Orthogonal Matching Pursuit (A*OMP). In this manuscript, A*OMP algorithm is introduced and three different cost functions are discussed. We show that novel dynamic auxiliary cost functions provide improved results as compared to a conventional choice. Finally, we provide reconstruction results on both synthetically generated data and real images which show that the proposed scheme outperforms well-known CS reconstruction methods, BP, SP and OMP.

Fast Overlapping Group Lasso by Jun Liu, Jieping Ye. The abstract reads:

The group Lasso is an extension of the Lasso for feature selection on (predefined) non-overlapping groups of features. The non-overlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation, where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. We have performed empirical evaluations using the breast cancer gene expression data set, which consists of 8,141 genes organized into (overlapping) gene sets. Experimental results demonstrate the efficiency and effectiveness of the proposed algorithm.

From the same group here is a tutorial on Mining Sparse Representations: Formulations, Algorithms, and Applications. Jun Liu and  Jieping Ye are also the originators of the SLEP package which should be in the reconstruction section of the Big Picture. As you probably recall:

The SLEP (Sparse Learning with Efficient Projections) package provides a set of programs for sparse learning:

•  ℓ1-regularized (constrained) sparse learning
•  ℓ1/ℓq-regularized sparse learning (q>1)
•  Fussed Lasso
•  Sparse inverse covariance estimation
•  Trace norm regularized learning

I also found: Compressive Coded Aperture Computed Tomography — Part I: Coded Aperture Snapshot Spectral Imager (CASSI) by  Kerikil Choi, Ryoichi Horisaki, Ashwin Wagadarikar, and David Brady. The abstract reads:

Diverse physical measurements can be modeled by X-ray transforms. While X-ray tomography is the canonical example, reference structure tomography (RST) and coded aperture snapshot spectral imaging (CASSI) are examples of physically unrelated but mathematically equivalent sensor systems. Historically, most X-ray transform based systems sample continuous distributions and apply analytical inversion processes. On the other hand, RST and CASSI generate discrete multiplexed measurements implemented with coded apertures. Multiplexing of coded measurements allows for compressive sensing (CS). Using CS, an object sparse on some basis may be accurately described by fewer measurements than predicted by Nyquist sampling. This paper investigates the role of coded apertures in X-ray transform measurement systems (XTMs) in terms of data efficiency and reconstruction fidelity from a CS perspective. We construct a unified analysis using RST and CASSI measurement models. Using this analysis, we perform a qualitative study on how coded apertures can be exploited to implement physical compressive measurements by “regularizing” the measurement systems. Numerical studies and simulation results demonstrate several examples of the impact of coding.

Compressive Coded Aperture Computed Tomography — Part II: Compressive X-ray Tomography (CXT)  by  Kerikil Choi, Ryoichi Horisaki, Ashwin Wagadarikar, and David Brady. The abstract reads:

In the companion paper (Part I), we propose an analysis model for x-ray transform measurement systems. In particular, the model is applied to two compressive measurement systems that our group has recently developed: coded aperture snapshot spectral imagers and reference structure tomography. These modalities exploit the concepts of coding and multiplexing to create compressive sensing (CS) measurements. This second part of our paper extends the idea of coding and multiplexing to computed X-ray tomography to propose a novel compressive Xray tomography. We also propose a method of creating synthetic CS measurements that fall on the category of incoherent measurements in CS theory. These synthetic measurements combined with the proposed analysis model provides a means for evaluating and investigating the performance of CXT as a compressive sensing system. Various numerical studies illustrate the potential performance of our proposed system and suggest useful criteria for designing physical systems.

and (no link to the paper just the abstract): Sparse aperture coding for compressive sampling by David Brady, Alexander Mrozack, and Kerikil Choi. The abstract reads:

For many years, the basic goal of sparse aperture design has been to maximize the support of the modulation transfer function (MTF). Golay apertures and related nonredundant arrays are typically used to achieve this objective. Unfortunately, maximizing the support of the MTF has the necessary effect of decreasing the magnitude of the MTF at mid-band spatial frequencies. Fienup has shown that the decreased magnitude of the MTF for nonredundant arrays contributes as much as reduced throughput to the loss of SNR in sparse apertures relative to full aperture systems. This paper considers the use of periodic sparse arrays to improve the mid-band MTF at the cost of reduced spatial frequency coverage. We further consider methods to recover lost spatial frequencies using multispectral and multiframe sampling and decompressive inference.

The following poster proposes a different algorithm than the one based on compressed sensing/l1 reconstruction which it qualifies as the state of the art in this area. However, it uses an OMP greedy algorithm!

Rapid Face Recognition Using Hashing by Qinfeng Shi, Hanxi Li, Chunhua Shen. The abstract reads:

We propose a face recognition approach based on hashing. The approach yields comparable recognition rates with the random `1 approach [5], which is considered the state-of-the-art. But our method is much faster: it is up to 150 times faster than [5] on the YaleB dataset. We show that with hashing, the sparse representation can be recovered with a high probability because hashing preserves the restrictive isometry property. Moreover, we present a theoretical analysis on the recognition rate of the proposed hashing approach. Experiments show a very competitive recognition rate and significant speedup compared with the state-of-the art.

Sub-Nyquist Audio Fingerprinting for Song Identification by Kaichun K. Chang, Solon P. Pissis, Jyh-Shing R. Jang, Costas S. Iliopoulos. The abstract reads:

In recent years, Compressive Sampling (CS), a new research topic in signal processing, has piqued interest of a wide range of researchers in different fields. In this paper, we present a sub-Nyquist Audio Fingerprinting (AF) system for song identification, which utilizes CS theory to generate a compact signature, and to achieve significant reduction of the dimensionality of the input signal. The presented experimental results demonstrate that by using the CS-based AF system, which downsamples to 30%, the average accuracy is 93.43% under various distorted environments, compared to Nyquist sampling methods. The advantages of the proposed process lie in the comparable performance under sub-Nyquist sampling rate and more compact audio fingerprint.

In the upcoming NVIDIA GPU Technology Conference in San Diego, I found the following :

2300 - High-Performance Compressive Sensing using Jacket

This talk will present the ongoing work that I am doing in the L1-optimization group at Rice Universtiy. The purpose of the work is to merge both compressive sensing, for image/signal reconstructions and GPU computation, using NVIDIA’s GPUs to enhance the technology of CS. This talk will cover basic concepts in compressive sensing and the easy adaptation of operating on the GPU, in particular working with Jacket (by AccelerEyes). We willthen cover some of our numerical experiments that encompass the use of different flavors of algorithms.

Speaker:

Nabor Reyna

Topics:

Imaging, Tools & Libraries

Time:

Wednesday, September, 22nd, 10:30 - 10:50

Humm, Jacket, GPU and Compressed Sensing, we noted these subjects in one entry a while back. This is good, somebody had the same idea and implemented it, woohoo. The folks making Jacket are talking about it on their blog.

I also caught this:

Call for Papers: A Special Issue of Physical Communication on “Compressive Sensing in Communications”

Over the past few years, compressive sensing, also known as compressive sampling, has made a tremendous impact on signal processing and statistical learning, and has facilitated numerous applications in areas ranging from medical imaging and computational biology to astronomy. Recently, there has been a growing interest in applying the principles of compressive sensing to an even wider range of topics, including those in communications and networking. The basic thesis of compressive sensing—and its powerful appeal for many applications—is that under certain conditions, it suffices to collect only a small number of observations (linear projections of the signal of interest such as image, field, map, etc.) and still be able to efficiently reconstruct the signal in its entirety when the signal admits a sparse representation. This statement has a profound impact on the way in which a communication system can be designed. From compression of data —as necessitated by wireless transmission over band-limited channels, to estimation of channels that are naturally sparse, to active or passive delay, angle, and Doppler estimation of specific targets, to opportunistic spectrum sensing and collection of data in large sensor networks, the principles of compressive sensing can be applied to provide system designs that are more efficient than traditional ones. This special issue is devoted to those areas of communication system and network design where compressive sensing brings new insights, visions and tools to yield effective solutions for the problems of interest. We invite original, high-quality submissions in all such areas, ranging from physical link to system-level design, that offer innovative methodologies, algorithms, and/or theoretical results by appealing to or extending the existing results in the field of compressive sensing.

Manuscript submission:

December 15, 2010

Acceptance notification:

April 30, 2011

Final manuscript due:

June 30, 2011

Publication: 3rd quarter

2011

And finally two theses of relevance to our subject of interest:

• Derivative Compressive Sampling with Application to Inverse Problems and Imaging by Mahdi S. Hosseini

• VISUAL TRACKING AND ILLUMINATION RECOVERY VIA SPARSE REPRESENTATION by Mei Xue

At NIST there was an interesting presentation on September 1 :

10:30 AM - SIGMA XI / OPTICAL TECHNOLOGY SEMINAR: Hyperspectral Imaging, Compressive Sensing and Entrepreneurship?

The founding CEO of InView Technology Corporation, Bob Bridge, is an experienced entrepreneur, having worked in venture-capital backed technology start-ups since 1985. InView has licensed Compressive Sensing technology from Rice University, and is building high-performance infrared cameras and hyperspectral imagers based upon that technology. In contrast to Bob' earlier ventures which were venture capital funded, InView is receiving the bulk of its initial financing from various government sources. Bob has raised $51M in venture funding since 2001, including initial funding for three start-up companies. Before InView, Bob took Zilker Labs, a semiconductor start-up providing power management ICs to companies such as Cisco, from a marketing concept in 2002 to successful acquisition by public semiconductor company Intersil in 2008. Bob has also served as an Entrepreneur in Residence at Austin Ventures, vice president of marketing at Agere (a network processor IC startup), and vice president and general manager for communications ICs at Crystal Semiconductor/Cirrus Logic. Additionally, Bob has held engineering and management positions at Motorola, AT&T corporate headquarters and AT&T Bell Labs. Bob holds a Ph.D. in Electrical Engineering from The University of Texas at Austin and a bachelor's degree in Mathematical Sciences from Rice University. ***Dr. Bridges will describe his unique career path as well as the exciting new technology upon which is latest venture is based.*** Compressive Sensing technology allows InView to employ a low-cost sensor architecture to deliver unmatched camera/imager capabilities across the electromagnetic spectrum. For example, InView will offer a 2 mega-pixel Short Wavelength Infrared (SWIR) camera; the highest resolution SWIR available in the marketplace is 0.3 mega-pixels. High resolution images are reconstructed computationally from a set of measurements taken by a single element sensor. Each of these single-element measurements occurs after light from the entire image has been modulated by a random pattern and then focused onto the sensor. Mathematical processing then constructs the image using both the multiple sensor readings and the knowledge of the unique modulation pattern used to create each sensor reading as inputs to the algorithm.

Dr. Bob Bridges , CEO InView Technology.

Photo: Map of the last 100 readers who came to the new page on CS courses yesterday.

Compressed Sensing Courses

On top of the videos introducing compressed sensing that are a continuing success, here is a list of courses that have been offered so far on the subject. Enjoy!