Challenge: Compute a high dimensional integral, Win a 1,000 Euros.

To give some context, the following is related to the approach developed in The information associated with a sample, by Bernard Beauzamy. At issue is the possibility of building probability distributions from data as opposed to matching probabilistic models to data. It is an important problem and for this reason a 1,000 euros prize is offered by the SCM company to compute a high dimensional integral in an efficient manner. As of today, this translates into a US$1,400 or 9,889 Yuans any other local currency. The text of the challenge is as follows:

September 1st, 2009

The document "Robust Mathematical Methods for Extremely Rare Events" dated August 2009, by Bernard Beauzamy, uses the computation of a multiple integral, over a complicated domain in a many-dimensional space, in order to estimate a probability. This approach is inherent to the method itself.

However, the computation of the integral is done in a way which might not be the best : the function to integrate is a polynomial in one variable (with degree higher than 100 in our case), with rational coefficients (all coefficients are of the form m/n, where m and n are very large integers). In the paper, all coefficients are computed exactly, using the symbolic capabilities of Maple.

Therefore, the integration is slow and requires considerable memory in the computer. Typically, at this point, our method requires 30 multiple integrations, each of which takes around 20 minutes on an ordinary computer.

We would be interested to know if other numerical approaches are possible in order to compute such multiple integrals, with sufficient accuracy.

We offer a prize of Euros 1,000 to the best solution : a solution that can handle the requirements of speed, accuracy, and adaptability (not just our example, but any such example).

Solutions may be provided by individuals or by teams. The solutions should be sent by email to :

scm.sa@orange.fr

no later than March 31st, 2010.

The best solution, besides the prize, will be posted on the "Robust Mathematical Modeling" web site and will be communicated to all participants to the RMM program, worldwide.

If you have any questions, let me know and I'll forward them to the SCM folks.

CS: Update previous posts, Actual reach stats, Practical band-limited extrapolation relying on Slepian series and compressive sampling

Yonina Eldar let me know that a video where she explains the The Technion Modulated Wideband Converter can be found here. Both this hardware and the bio based Compressed Genotyping and Compressed Sequencing have been adding to the Compressive Hardware page.

With regards to the statistics of Nuit Blanche, there are currently 531 people using feedreaders to access posts of this site. According to Feedburner, 47% are "reach" so we have about on average 250 people actually reading the entries. We also have 201 people receiving every posts by e-mail. Finally, about 300 people come to site daily through search engines. The most surprising statistics is that the Big Picture in Compressive Sensing reaches about 120 people daily while the Compressive Sensing Hardware page reaches about 10 to 20 people daily even though neither of these pages are updated daily.

Finally, here is a new paper: Practical band-limited extrapolation relying on Slepian series and compressive sampling by Laurent Gosse. The abstract reads:

We consider a rather simple algorithm to address the fascinating field of numerical extrapolation of (analytic) band-limited functions. It relies on two main elements: namely, the lower frequencies are treated by projecting the known part of the signal to be extended onto the space generated by ``Prolate Spheroidal Wave Functions" (PSWF, as originally proposed by Slepian), whereas the higher ones can be handled by the recent so--called ``Compressive Sampling" (CS, proposed by Cand\`es) algorithms which are independent of the largeness of the bandwidth. Slepian functions are recalled and their numerical computation is explained in full detail whereas Compressive Sampling techniques are summarized together with a recent iterative algorithm which has been proved to work efficiently on so--called ``compressible signals" which appear to match rather well the class of smooth bandlimited functions. Numerical results are displayed for both numerical techniques and the accuracy of the process consisting in putting them altogether is studied for several test-signals.

CS: Compressed Genotyping, DNA Sudoku - Harnessing high throughput sequencing for multiplexed specimen analysis

Yaniv Erlich just sent me the following:

We came up with a framework, named compressed genotyping, of using compressed sensing for detecting carriers of rare genetic diseases, which somehow resembles the interesting work of Noam Shomron et al. (http://nuit-blanche.blogspot.com/2009/09/cs-rare-allele-detection-using.html).

In addition to the theoretical framework (found here), we have already tested large parts of it in a real experiment in which we genotyped more than 40,000 bacterial colonies in one run of DNA sequencing platform.
For comparison, regular (non-compressed) genotyping techniques can only process few hundreds samples in one run, which emphasizes the rigor of compressed sensing! The experimental work was published in Genome Research (July 2009), and a pre-print is found here.

In addition, I am going to present some aspects of compressed genotpying in Allerton 2009.

We would appreciate comments on our work. It seems that some aspects of DNA Sequencing has intriguing connections to compressed sensing.

Thanks Yaniv !

The first paper is: Compressed Genotyping by Yaniv Erlich, Assaf Gordon, Michael Brand, Gregory J. Hannon and Partha P. Mitra. The abstract reads:

Significant volumes of knowledge have been accumulated in recent years linking subtle genetic variations to a wide variety of medical disorders from Cystic Fibrosis to mental retardation. Nevertheless, there are still great challenges in applying this knowledge routinely in the clinic, largely due to the relatively tedious and expensive process of DNA sequencing. Since the genetic polymorphisms that underlie these disorders are relatively rare in the human population, the presence or absence of a disease-linked polymorphism can be thought of as a sparse signal. Using methods and ideas from compressed sensing and group testing, we have developed a cost-effective genotyping protocol. In particular, we have adapted our scheme to a recently developed class of high throughput DNA sequencing technologies, and assembled a mathematical framework that has some important distinctions from ’traditional’ compressed sensing ideas in order to address different biological and technicalconstraints.

This paper uses a Belief Propagation Reconstruction algorithm and makes the point that fewer measurement is not the only cost function.

The second paper is: DNA Sudoku - Harnessing high throughput sequencing for multiplexed specimen analysis by Yaniv Erlich, Kenneth Chang, Assaf Gordon, Roy Ronen, Oron Navon, Michelle Rooks, and Gregory J. Hannon. The abstract reads:

Next-generation sequencers have sufficient power to analyze simultaneously DNAs from many different specimens, a practice known as multiplexing. Such schemes rely on the ability to associate each sequence read with the specimen from which it was derived. The current practice of appending molecular barcodes prior to pooling is practical for parallel analysis of up to many dozen samples. Here, we report a strategy that permits simultaneous analysis of tens of thousands of specimens. Our approach relies on the use of combinatorial pooling strategies in which pools rather than individual specimens are assigned barcodes. Thus, the identity of each specimen is encoded within the pooling pattern rather than by its association with a particular sequence tag. Decoding the pattern allows the sequence of an original specimen to be inferred with high confidence. We verified the ability of our encoding and decoding strategies to accurately report the sequence of individual samples within a large number of mixed specimens in two ways. First, we simulated data both from a clone library and from a human population in which a sequence variant associated with cystic fibrosis was present. Second, we actually pooled, sequenced, and decoded identities within two sets of 40,000 bacterial clones comprising ~20,000 different artificial MicroRNAs targeting Arabidopsis or human genes. We achieved greater than 97% accuracy in these trials. The strategies reported here can be applied to a wide variety of biological problems, including the determination of genotypic variation within large populations of individuals.

Here are some items that pop-up my mind but I am sure there are others:

• The article has no mention of any CS papers or CS pooling papers, it looks like a huge opportunity to bring some knowledge that has built up in the CS domain recently.
• In an offline conversation, Nicolas Thierry-Mieg pointed out to me that this Sudoku approach does not seem closely related to the sudocode approach of Dror Baron, Rich Baraniuk and Shriram Sarvotham in Sudocodes: Fast Measurement and Reconstruction of Sparse Signals. Dror tells me that they are improving on this Sudocode code.
• Page 42 makes a tangent note to quantization. A similar issue was mentioned in the Rare-Allele Detection Using Compressed Se(que)nsing paper. At some point, unless reconstruction is exact and algebraic, we are going to have to face this issue of quantization. Some work has been performed in this arena, check the blog with that keyword.
• Maybe, at some point we need a similar table to that of Piotr Indyk released his Tutorial on Compressed Sensing (or Compressive Sampling or Linear Sketching), specific for pooling arguments in the bio world.

CS: The Technion Modulated Wideband Converter, From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals

[Update: Yonina also let me know that a video where she explains the subject can be found here.]

Moshe Mishali just let me know that he and Yonina Eldar have recently updated their manuscript about sub-Nyquist sampling using CS techniques with the title: From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals (version 1 was covered here). There abstract reads:

Conventional sub-Nyquist sampling methods for analog signals exploit prior information about the spectral support. In this paper, we consider the challenging problem of sub-Nyquist sampling of multiband signals, whose unknown frequency support occupies only a small portion of a wide spectrum. Our primary design goals are efficient hardware implementation and low computational load on the supporting digital processing. We propose a system, named the modulated wideband converter, which first multiplies the analog signal by a bank of periodic waveforms. The product is then lowpass filtered and sampled uniformly at a low rate, which is orders of magnitude smaller than Nyquist. Perfect recovery from the proposed samples is achieved under certain necessary and sufficient conditions.We also develop a digital architecture, which allows either reconstruction of the analog input, or processing of any band of interest at a low rate, that is, without interpolating to the high Nyquist rate. Numerical simulations demonstrate many engineering aspects: robustness to noise and mismodeling, potential hardware simplifications, realtime performance for signals with time-varying support and stability to quantization effects. We compare our system with two previous approaches: periodic nonuniform sampling, which is bandwidth limited by existing hardware devices, and the random demodulator, which is restricted to discrete multitone signals and has a high computational load. In the broader context of Nyquist sampling, our scheme has the potential to break through the bandwidth barrier of state-of-the-art analog conversion technologies such as interleaved converters.

Also of importance, Moshe tells me that they are also publishing the code for the simulations at:

http://www.technion.ac.il/~moshiko/software.html

They are working on the electronic implementation of the scheme as can be seen from the photos.

I am adding this entry in the Compressive Hardware page.

CS: SODA papers

Andrew McGregor has a blog entry on the SODA entries some of which related to compressive sensing ideas. The abstracts of all the SODA papers can be found in this blog entry.

CS: Rare-Allele Detection Using Compressed Se(que)nsing, Shifted Transversal Design smart-pooling for high coverage interactome mapping

Noam Shental sent me the following:

Together with my colleagues, Amnon Amir (Physics of Complex System, Weizmann Institute Of Science, Israel) and Or Zuk (Broad Institute, Boston), we are currently working on a Compressed Sensing (CS) approach to a problem in genomics, namely the detection of rare genetic mutations in large populations.

As far as we know, our work is the first to apply CS in the context of next-generation sequencing technology in genomics. As we are not CS experts, we would highly appreciate comments from people in this field. A draft of our article has been submitted to the arxiv (http://arxiv.org/abs/0909.0400), and any feedback will be very welcome. We also believe that this application may be of interest to people in the CS community.

The paper is: Rare-Allele Detection Using Compressed Se(que)nsing by Noam Shental, Amnon Amir and Or Zuk. The abstract reads:

Detection of rare variants by resequencing is important for the identification of individuals carrying disease variants. Rapid sequencing by new technologies enables low-cost resequencing of target regions, although it is still prohibitive to test more than a few individuals. In order to improve cost trade-offs, it has recently been suggested to apply pooling designs which enable the detection of carriers of rare alleles in groups of individuals. However, this was shown to hold only for a relatively low number of individuals in a pool, and requires the design of pooling schemes for particular cases. We propose a novel pooling design, based on a compressed sensing approach, which is both general, simple and efficient. We model the experimental procedure and show via computer simulations that it enables the recovery of rare allele carriers out of larger groups than were possible before, especially in situations where high coverage is obtained for each individual. Our approach can also be combined with barcoding techniques to enhance performance and provide a feasible solution based on current resequencing costs. For example, when targeting a small enough genomic region (∼100 base-pairs) and using only ∼ 10 sequencing lanes and ∼10 distinct barcodes, one can recover the identity of 4 rare allele carriers out of a population of over 4000 individuals.

This work looks very similar to the work done by Raghu Kainkaryam and Anna Gilbert using sparse random matrices to perform high throughput testing as mentioned here, here and here. Raghu then mentioned to me that:

I don't know if you saw Nicolas Thierry-Mieg's recent paper on applying the STD pooling strategy (the equivalent of DeVore's deterministic constructions of CS matrices) to protein-protein interaction mapping:

http://genome.cshlp.org/content/19/7/1262.abstract

After further investigation, Nicolas then mentioned to me that this paper is available here. It is: Shifted Transversal Design smart-pooling for high coverage interactome mapping by Xiaofeng Xin, Jean-Francois Rual, Tomoko Hirozane-Kishikawa, David E. Hill, Marc Vidal, Charles Boone, and Nicolas Thierry-Mieg. The abstract reads:

‘‘Smart-pooling,’’ in which test reagents are multiplexed in a highly redundant manner, is a promising strategy for achieving high efficiency, sensitivity, and specificity in systems-level projects. However, previous applications relied on low redundancy designs that do not leverage the full potential of smart-pooling, and more powerful theoretical constructions, such as the Shifted Transversal Design (STD), lack experimental validation. Here we evaluate STD smartpooling in yeast two-hybrid (Y2H) interactome mapping. We employed two STD designs and two established methods to perform ORFeome-wide Y2H screens with 12 baits. We found that STD pooling achieves similar levels of sensitivity and specificity as one-on-one array-based Y2H, while the costs and workloads are divided by three. The screening-sequencing approach is the most cost- and labor-efficient, yet STD identifies about twofold more interactions. Screening-sequencing remains an appropriate method for quickly producing low coverage interactomes, while STD pooling appears as the method of choice for obtaining maps with higher coverage.

Unrelated to these papers, an example of sparsity in everything I mentioned yesterday are the non-functioning Protein-Protein Interactions.

CS: Providing insight on Compressive Sensing, GEOCAM

Sometimes, it is important to take a step back and provide to a wider readership some form of insight about compressive sensing. Let me do that today by connecting the dots between some entries on Nuit Blanche and elements found in the presentation slides of researchers in the field. On the slides for "Testing the Nullspace Property using Semidefinite Programming", Alexandre d'Aspremont, Francis Bach, Laurent El Ghaoui make the excellent point in slide 4 that:

• Sparsity is a proxy for power laws. Most results stated here on sparse vectors apply to vectors with a power law decay in coefficient magnitude.
• Power laws appear everywhere. . .

and this is indeed what I have tried to elaborate in the Sparsity in Everything series of entries. One the same subject, a new idea is also emerging that says that power-laws do not fit well with outliers particularly on the high end of it. Didier Sornette, in his recent arxiv preprint entitled Dragon-Kings, Black Swans and the Prediction of Crises thinks there is a positive feedback mechanism that produces even larger elements making them much sparser. Could compressive sensing be used to detect events with positive feedbacks out of the many unpredictable ones that fit a power law and therefore are much smaller in effects ?

Terry Tao also has a new presentation on Compressive Sensing where one can find this nugget:

An analogy would be with the classic twelve coins puzzle: given twelve coins, one of them counterfeit (and thus heavier or lighter than the others), one can determine the counterfeit coin in just three weighings, by weighing the coins in suitably chosen batches. The key point is that the counterfeit data is sparse.

It also looks like this example helps journalists and the public at large get the idea on group testing as the example is used in this article on Terry's series of lectures in Australia. You may recall a similar example and treatment here on this blog of that problem with balls instead of coins.

Further in the presentation, he also makes the more cryptic statement :

There are now several theoretical results ensuring that basis pursuit works whenever the measurement matrix A is sufficiently “incoherent”, which roughly means that its matrix entries are uniform in magnitude. (It’s somewhat analogous to how the secret to solving the twelve coins problem is to weigh several of the coins at once.)

Finally, on a totally different note, here is a presentation done by some NASA contractor folks that uses the same name as our 2005 GEOCAM project and uses the same concepts. Low tech cameras and an aerial capability can provide real time data in case of catastrophes. My students and I worked on this as a student project a little bit after what happened to New Orleans with Katrina. All the photos taken during that flight are here and were assembled using a low cost off-the-shelf software called Autopano Pro ( that uses SIFT markers) to produce these beautiful maps. Eventually, we never got any interest by other parties about what we had done. I am very glad the idea is continuing to live on.

CS: Compressed Sensing: How Sharp is the RIP ?, Blogroll redux.

Following the slides for "Testing the Nullspace Property using Semidefinite Programming" by Alexandre d'Aspremont, Francis Bach, Laurent El Ghaoui featured yesterday which highlight that the Null Space Property is weaker than RIP , Jeffrey D. Blanchard, Coralia Cartis, and Jared Tanner asked themselves and answered the question: Compressed Sensing: How Sharp is the RIP ? . The abstract reads:

Consider a measurement matrix A of size n×N, with n \lt N, y a signal in RN, and b = Ay the observed measurement of the vector y. From knowledge of (b,A), compressed sensing seeks to recover the k-sparse x, k \lt n, which minimizes ||b − Ax||. Using various methods of analysis — convex polytopes, geometric functional analysis, and the restricted isometry property (RIP) — it has been proven that x can be reconstructed via l_q-regularization (q element of (0, 1]) provided A satisfies conditions dictated by the method of analysis. This article focuses on the RIP approach and A with entries drawn i.i.d. from the Gaussian distribution N(0, 1/pn), developing more precise bounds on the restricted isometry constants, and using these bounds in an asymmetric RIP formulation to quantify the region of ( n N , k n ) in which RIP implies that `q-regularization will typically recover all k-sparse signals. Letting n N !  and k n !  as n ! 1, the aforementioned recoverability region is characterized by all  \lt (1 − )RIP S (; q) for any \gt 0, where RIP S (; q) is a lower bound of the true phase transition below which l_q-regularization will typically recover all k-sparse signals. This phase transition framework, proposed in this context by Donoho (2005), is applied to compressed sensing results obtained by the analysis techniques of centro-symmetric polytope theory (Donoho), geometric functional analysis (Rudelson and Vershynin), and the RIP (Cand`es, Romberg and Tao; Foucart and Lai; Chartrand). Recasting the results from different methods of analysis into a common phase transition framework allows for the direct comparison of the efficacy of the respective results.

I need to understand how the null space property being a necessary and sufficient condition for sparse recovery can be weaker than a sufficient condition based on the RIP. Maybe this is the case for RIP-2 ?

Laurent Jacques mentioned a possible collision of notations in the comment section of this entry:

I noticed also that Rick Chartrand and Valentina Staneva, in

"Restricted isometry properties and nonconvex compressive sensing", Inverse Problems, vol. 24, no. 035020, pp. 1--14, 2008

introduced also a RIP_p definition, with an existence proof for Gaussian matrices, but .... for 0 \lt p \le 1

In conclusion, the RIP_p makes sense for p in R^* now ;-)

Following the latest entry on the subject, here are two blogs I will be adding to my blogroll:

• The polylog blog of Andrew McGregor
• The Natural Language Processing Blog of Hal Daume III

Image Credit: NASA/JPL/Space Science Institute, Saturn's rings as seen by Cassini the day before yesterday.

CS: LMaFit, KSVD-Box v12, Null Space Conditions and Thresholds for Rank Minimization, Radu Berinde's thesis, Testing the Nullspace Property

Yin Zhang just released version beta 1 of LMaFit -- A package for low-rank matrix optimization. You can read the User's Guide for LMaFit here.

Ron Rubinstein just released KSVD-Box v12, an implementation of the K-SVD and Approximate K-SVD dictionary training algorithms, and the K-SVD Denoising algorithm. It requires OMP-Box v9. It can be downloaded here. This version optimizes several parts of the K-SVD implementation, and achieves faster running times and lower memory requirements.

And here are some updates or additional information on subjects/publications covered here before:

• Null Space Conditions and Thresholds for Rank Minimization which is a full and updated version of "Necessary and Sufficient Condtions for Success of the Nuclear Norm Heuristic for Rank Minimization" by Benjamin Recht, Weiyu Xu, and Babak Hassibi.
• Radu Berinde's M. Eng thesis can be found here
• The slides for "Testing the Nullspace Property using Semidefinite Programming" by Alexandre d'Aspremont, Francis Bach, Laurent El Ghaoui are here.

CS: Compressed sensing reconstruction of a string signal from interferometric observations of the cosmic microwave background

If you thought some of the previous posts were too esoteric, watch out! we're now talking about doing inverse problems on strings :-). Enjoy.

Compressed sensing reconstruction of a string signal from interferometric observations of the cosmic microwave background by Yves Wiaux, Gilles Puy, Pierre Vandergheynst. The abstract reads:

We propose an algorithm for the reconstruction of the signal induced by cosmic strings in the cosmic microwave background (CMB), from radio-interferometric data at arcminute resolution. Radio interferometry provides incomplete and noisy Fourier measurements of the string signal, which exhibits sparse or compressible magnitude of the gradient due to the Kaiser-Stebbins (KS) effect. In this context the versatile framework of compressed sensing naturally applies for solving the corresponding inverse problem. Our algorithm notably takes advantage of a model of the prior statistical distribution of the signal fitted on the basis of realistic simulations. Enhanced performance relative to the standard CLEAN algorithm is demonstrated by simulated observations under noise conditions including primary and secondary CMB anisotropies.