Sunday Morning Insight: Structured Sparsity and Structural DNA Folding Information

In Application of compressed sensing to genome wide association studies and genomic selection, one realizes that connecting GWAS and phenotypes is difficult. One of the underlying reason may lie in part due to the loss of structural information thanks to linear DNA sequencing (such as nanopore sequencing). To comprehend the structural information better, I gathered several figures from the interwebs in a series of figures below. As can be seen, the same DNA can be folded differently and yield different outcomes because non-DNA elements such as histones have a direct impact on allowing certain parts of the DNA to be active (or not). The folding itself may also be behind the reason why some diseases are connected to a large number of genes. Given all this, one wonders if a structured sparsity approach to GWAS studies might be more fruitful in that it could potentially highlight elements of the DNA that are closer to each other and therefore pinpoint to folding information. At the very least, there ought to be a trace of the cyclicality induced by the 147 base pairs wrapped into the nucleosomes.

For some related information, we had a small discussion with Mohammed AlQuraishi 's blog entry on CASP10, and the Future of Structure in Biology a while back.

Different scales in the DNA all the way to the chromosome [2]

Different scales in the DNA all the way to the chromosome [4]

More detailed scales in the DNA all the way to the chromosome [2]

Detailed Sketch of the Histone-DNA complex[1]

Nucleosomes can slide along DNA. When nucleosomes are spaced closely together (top), transcription factors cannot bind and gene expression is turned off. When the nucleosomes are spaced far apart (bottom), the DNA is exposed. Transcription factors can bind, allowing gene expression to occur. Modifications to the histones and DNA affect nucleosome spacing. From [3]

Same figure as before but with different scales [5]

In transformed cells, this scenario is disrupted by the loss of the 'active' histone-marks on tumour-suppressor gene promoters, and by the loss of repressive marks such as the trimethylation of K20 of H4 or trimethylation of K27 of histone H3 at subtelomeric DNA and other DNA repeats. This leads to a more 'relaxed' chromatin conformation in these regions. [6]

[1] From Binding of Histone peptides to Chromatin assembly factor I (CAF-I) p48 subunit

[2] From Beyond the Dish, Stem Cell Differentiation Requires Proper Compaction of DNA and Molecular Signature Distinguished Old Stem Cells from New Stem Cells

[3] Epigenetic Control: Regulating Access to Genes within the Chromosome, Connexions course

[4] Basic Plant Cytology 1, http://plantphys.info

[5] Group 1 - Assignment 6

[6] Histone-modification maps for a typical chromosome in normal and cancer cells. From Cancer epigenomics: DNA methylomes and histone-modification maps

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Sunday Morning Insight: Watching P vs NP

Last year, I somehow argued that it would be difficult for Quantum Computing to compete with the Steamrollers even if it meant they could solve NP problems (which we don't really know if they can [6]). This time, it is a little different. See, if you recall, sharp phase transitions are now part of our landscape. By landscape, I do not only mean their discovery [3], but also their use starting with [1] in 2010 and as recently as last week [4]. We collectively yearn for those limits to move (see The Wall in Sunday Morning Insight: Game of Thrones and the History of Compressive Sensing [5]

From Manjhi's Myth

And like we said last week [2]

"...yes, we expect the mathematicians to clear the waters there..."

or like in the case of Manjhi, move a mountain.

Go read Tim Gowers' What I did in my summer holidays on TiddlySpace and his proposal for Polymath9 and Terry Tao's G+ post on Gilles Pisier's paper on Grothendieck's Theorem, past and present [7] (a more recent version of that paper is here) set up on the SelectedPapers network. 

It might happen right in front of our eyes.

[1] Compressive Radar Imaging Using White Stochastic Waveforms by Mahesh C. Shastry, Ram M. Narayanan and Muralidhar Rangaswamy [Published in 2010]

[2] Implementation: EM-NN-AMP: Recovering Linearly-Constrained Non-Negative Sparse Signals

[3] Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing by Jared Tanner and David Donoho

[4] Compressed sensing and genomes and on Nuit Blanche ( Application of compressed sensing to genome wide association studies and genomic selection )

[5] Sunday Morning Insight: Game of Thrones and the History of Compressive Sensing

[6] Randomized Thoughts and Around the Blogs in 78 hours

[7] Grothendieck's Theorem, past and present by Gilles Pisier

Probably the most famous of Grothendieck's contributions to Banach space theory is the result that he himself described as "the fundamental theorem in the metric theory of tensor products". That is now commonly referred to as "Grothendieck's theorem" (GT in short), or sometimes as "Grothendieck's inequality". This had a major impact first in Banach space theory (roughly after 1968), then, later on, in $C^*$-algebra theory, (roughly after 1978). More recently, in this millennium, a new version of GT has been successfully developed in the framework of "operator spaces" or non-commutative Banach spaces. In addition, GT independently surfaced in several quite unrelated fields:\ in connection with Bell's inequality in quantum mechanics, in graph theory where the Grothendieck constant of a graph has been introduced and in computer science where the Grothendieck inequality is invoked to replace certain NP hard problems by others that can be treated by "semidefinite programming" and hence solved in polynomial time. In this expository paper, we present a review of all these topics, starting from the original GT. We concentrate on the more recent developments and merely outline those of the first Banach space period since detailed accounts of that are already available, for instance the author's 1986 CBMS notes.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Saturday Morning Videos: This is why we fly; a phase separator in different gravity levels; concurrent vertical two phase flow

 




H/t Christian and Cable Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Startup News: GraphLab, InView Corp., Centice

Advice for startups: Please make it easy for people who like what you do. Set up an RSS feed.

GraphLab

• Go check http://beta.graphlab.com it will be worth your time

InView Corp.

• Why settle for just a SWIR camera in your lab, when you could have a visible plus multiband SWIR camera instead?
• Dealer response to the InView210 SWIR camera has been gratifying.

Centice

• Centice MFL-3000 helps Law Enforcement identify MDMA (Molly) and Potentially Lethal Cutting Agents

Other blog entries of startups we like


Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Sparse FFT implementation: FFAST, Fast Fourier Aliasing-based Sparse Transform

ClickThroughs on an implementation mentioned here on Nuit Blanche

Think of Nuit Blanche as a crossroad. Often times, I request access to implementations so that you can become a rockstar (Nobody Cares About You and Your Algorithm ), Back in May, I asked Kannan Ramchandran and Sameer Pawar about whether an implementation of their paper 

( Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity ) would be out. I wrote about their answer:

"Kannan t[old] me ...that an implementation should be out by the end of the summer. woohoo! "

Sameer  and Kannan followed through on that e-mail this week with:

 Dear Igor,  

It's been a while since we communicated. At our end, we have made some development towards making the implementation of FFAST accessible to the people. Although we promised a summer- release of the code, it took us more time to get C++ implementation ready than we estimated. To release the FFAST code to general public still needs some more work in terms of web/user interface. But to get started we thought we can at least release it to you. So for now, we have created a guest login account to one of our servers at Berkeley. You can login remotely as follows:....

Unfortunately, I don't have much time to kick the tires on this implementation but Kannan let me know that if you want to have access to the FFAST implementation as is, you can do so by directly contacting Sameer directly at: spawar@eecs.berkeley.edu

Related: 

• Sparse FFT implementations
• Slides of the recent Workshop on Sparse Fourier Transform

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Robust Sparse Signal Recovery for Compressed Sensing with Sampling and Representation Uncertainties - implementation -

Yipeng Liu just sent me the following

Dear Igor,

....We propose one method that is more robust to multiplicative uncertainty when recovering sparse signal from compressive measurements. I guess it may be interesting to some of your nuit blanche blog reader. It is online available at: ftp://ftp.esat.kuleuven.ac.be/pub/SISTA//yliu/rl0.pdf

Thank you very much for the daily updating posting! Your blog really help me a lot!
Best Regards, 
2013-10-23

Yipeng Liu （刘翼鹏）, PhD, Research Fellow
ESAT-STADIUS, Department of Electrical Engineering, University of Leuven
Email: yipeng.liu@esat.kuleuven.be; dr.yipengliu@gmail.com
Kasteelpark Arenberg 10, box 2446, 3001 Heverlee, Belgium

Here is the report:

``Robust Sparse Signal Recovery for Compressed Sensing with Sampling and Representation Uncertainties'', Yipeng Liu, Maarten De Vos. Sabine Van Huffel, Internal Report 12-177, ESAT-SISTA, K.U.Leuven (Leuven, Belgium), 2012.

Compressed sensing (CS) shows that a signal having a sparse or compressible representation can be recovered from a small set of linear measurements. In classical CS theory, the sampling matrix and dictionary are assumed be known exactly in advance. However, uncertainties exist due to sampling distortion, finite grids of the parameter space of dictionary, etc. In this paper, we take a generalized sparse signal model, which simultaneously considers the sampling and dictionary uncertainties. Based on the new signal model, a new optimization model for robust sparse signal recovery is proposed. This optimization model can be deduced with stochastic robust approximation analysis. Both convex relaxation and greedy algorithm are used to solve the optimization problem. For the convex relaxation method, a sufficient condition for recovery by convex relaxation method and the uniqueness of solution are given too; For the greedy sparse algorithms, it is realized by the introduction of a pre-processing of the sensing matrix and the measurements. In numerical experiments, both simulated data and real-life ECG data based results show that the proposed method has a better performance than the current methods.

The implementation is here.
"In Folder A, the codes for Fig. 3 are given. Fig. 4 and 5 can be provided by just a few parameters. In Folder B,  all the data and Figures can be generated by the codes."
Thank you Yipeng
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

1-Bit Matrix Completion - implementation -

Here is a newer version of a paper with an attendant implementation: 1-Bit Matrix Completion by Mark Davenport, Yaniv Plan, Ewout van den Berg, Mary Wootters

In this paper we develop a theory of matrix completion for the extreme case of noisy 1-bit observations. Instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question we ask is whether or not it is possible to obtain an accurate estimate of M from this data. In general this would seem impossible, but we show that the maximum likelihood estimate under a suitable constraint returns an accurate estimate of M when ||M||_{\infty} <= \alpha, and rank(M) <= r. If the log-likelihood is a concave function (e.g., the logistic or probit observation models), then we can obtain this maximum likelihood estimate by optimizing a convex program. In addition, we also show that if instead of recovering M we simply wish to obtain an estimate of the distribution generating the 1-bit measurements, then we can eliminate the requirement that ||M||_{\infty} <= \alpha. For both cases, we provide lower bounds showing that these estimates are near-optimal. We conclude with a suite of experiments that both verify the implications of our theorems as well as illustrate some of the practical applications of 1-bit matrix completion. In particular, we compare our program to standard matrix completion methods on movie rating data in which users submit ratings from 1 to 5. In order to use our program, we quantize this data to a single bit, but we allow the standard matrix completion program to have access to the original ratings (from 1 to 5). Surprisingly, the approach based on binary data performs significantly better.

Of note in the conclusion

However, matrix completion from noiseless binary measurements is extremely ill-posed, even if one collects a binary measurement from all of the matrix entries. Fortunately, when there are some stochastic variations (noise) in the problem, matrix reconstruction becomes well-posed.

The toolbox can be downloaded from Mark's code page.



Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

CSJob: Postdoc, imaging techniques for earthquake science and geophysics, Harvard

Brendan Meade just sent me the following:

Igor-
   .....I'm sharing the below postdoc advertisement because it may be of interest to some of your readers.  
Brendan
Brendan Meade
Professor of Earth & Planetary Sciences
Harvard University
Cambridge, MA 02138
meade@fas.harvard.edu

   The Department of Earth & Planetary Sciences at Harvard University invites applications from prospective postdoctoral scholars for positions in the application of contemporary imaging techniques to problems in earthquake science and geophysics.  We seek novel applications of sparse recovery and machine learning algorithms to the analysis of geodetic data networks and imaging with physics based kernels.  The duration of the fellowship is one year and renewable for up to two additional years with satisfactory progress and continued availability of funding. Applicants should send (1) a statement of experience and interests, (2) curriculum vitae, and (3) the names and addresses of three references electronically to Professor Brendan Meade (c/o Bridget Mastandrea, bmastandrea@fas.harvard.edu).  Review of applications will begin on December 19th, 2013. Harvard University is an affirmative action/equal opportunity employer and applications from women and minorities are encouraged.

Thanks Brendan ! Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

The Red Wedding in Science and Technology

At meetups and other places, I am always surprised by how the idea of science and technology being at the center of epic fights of ideas is not more widely known. I think it probably has to do with the lack of scientific background most science reporters have. Then again, not everybody is really that interested in hearing about those battles, so it might be just a bias. In the end, most people are customers of technologies and rarely care about how it got in front of them. Yet, it is a story, I should have described in Game of Thrones and the History of Compressive Sensing. 

A year ago, I wrote about the steamrollers, (see Predicting the Future: The Steamrollers) i.e a set of "laws" that we are all following without realizing it. The resurgence of neural networks in recent years or simply the ability to do complex Bayesian computations is just an outgrowth of this phenomena. On the hardware side of things, I commented earlier (see Do Not Mess with CMOS) that it is always risky to bet the farm on a technology that competes with one of these steamrollers, i.e. CMOS. And yesterday, I noted Vladimir's feed showing off a video of the IMEC hyperspectral camera.

Outdoor demonstration of IMEC's hyperspectral imaging camera from IMEC imaging on Vimeo.

From Vladimir's text:

This technology is said to enable new possibilities for non-scanning, real-time acquisition of hyperspectral image data-cubes at video-rates.

We've seen a similar set up here on Nuit Blanche, namely a video summary of the work on coded aperture ( Video Compressive Sensing by Larry Carin , compressive hyperspectral camera and Compressive video ). What is the difference between these two approaches ? They both use CMOS technology ! well not exactly in the same manner, see, one is fully using CMOS with no care for signal compression while it expects economies of scale to build very large FPAs, while the other restricts itself to a certain CMOS size and expects an intelligent approach to get more information. 

In the IMEC camera, the signal is directly acquired and stored in memory while in the aecond approach, we yearn for the coded aperture to reconstruct the hyperspectral cubes faster than a blink of an eye. In effect, the compressive approach is contingent on having faster reconstruction algorithms or in simpler terms, is the embodiement between dumb economies of scale and an intelligent approach to dealing with data. 

In the end, the race for getting faster solvers is all about winning a war. As spectators who have sometimes invested too much of their thought processes in a particular technology, the winning of a dumb CMOS solution might trigger the same reactions as those of numerous watchers of Games of Thrones's Red Wedding (do not click on the previous link nor watch the video below if you haven't seen Episode 9, Season 3)

Which one do you think will win ?

PS: I am not saying that CS cannot be included in the IMEC camera, it surely can but if the architecture is easy to build, there is no reason to expect that or similar cameras get more information through CS, as they will always look to increase the silicon instead of bettering the  algorithm.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

CSJob: Shell-MIT Postdoctoral Researcher

Piotr Indyk just sent me the following:

Hi Igor,

Hope things are going well with you. I was wondering if it would be possible for you to announce our new postdoc position on your blog ? It did wonders last time:)

Thanks!

Piotr

No problem Piotr! Here it is:

Shell, a global group of energy and petrochemicals companies, and Massachusetts Institute of Technology seek applications for a postdoctoral researcher to pursue energy research at MIT in Cambridge, Massachusetts with MIT faculty on a Shell-sponsored research project. The goal of the project is to examine applications of compressive sensing and machine learning methods to geophysical and petroleum engineering problems. This postdoctoral candidate will focus specifically on applications of these methods to estimating reservoir fluid flow parameters given observations in drilled wells.

Application due date: November 22, 2013.

Eligibility Requirements:

* Ph.D. and excellent academic record

* Strong background in one or more of the following fields:

- Petroleum and reservoir engineering

- Control theory

- Data assimilation

- Statistical inference, probability theory

- Numerical methods

We seek candidates with demonstrated experience and interest in energy research; an excellent academic record; and academic background in the appropriate field(s) specified above. Candidates should have interest in integrating the following focus areas of the current project into their research: machine learning; compressive sensing/sparse approximations; convex optimization. Successful candidates should have received their Ph.D. within three years of the post-doc start date. Postdoctoral Researchers must be in residence in Cambridge and must participate in Shell-MIT Postdoctoral Researcher activities coordinated by the MIT Energy Initiative (MITEI).

Each Shell-MIT Postdoctoral Researcher in Energy will be hired as an MIT employee and will receive an annual stipend of $50,000-$52,000 including benefits. This is a one-year position with opportunity for one-year renewal, contingent on satisfactory performance. Target start date is February 2014.

Applications should be submitted directly to the MIT Energy Initiative. Program description and application information can be found at http://mitei.mit.edu/shell-mit-postdoc

Contact us at energypostdoc@mit.edu with questions.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.