Around the blogs in 80 summer hours

Even since the last Around the blogs in 80 hours, The seeds of a conversation starting on Nuit Blanche could be found on the topic of Compressive Sensing in 

• Sparse projections onto the simplex
• Vanishingly Sparse Matrices and Expander Graphs, with application to compressed sensing
• Calibrating a Kaleidoscopic Imaging System

or on the topic of Genomics in 

• And so it begins ... Compressive Genomics (which was a huge success: +8 Google +1s), 
• All you wanted to know about Human Genomics but were afraid to ask and 
• International Biomedical and Astronomical Signal Processing (BASP) Frontiers Workshop 2013

or finally on the topic of Space in 

• Sweeping Low Earth Orbit from Space Debris with Sling-Sat

But they could be found also in a suprisingly non sparse set of blogs. Summer is indeed a nice period as people ponder more deeply certain subjects or find new references or even meet people. The first four items are directly connected to compressive sensing:

• Andrew wrote about the Day 1 at Data Streaming in Dortmund: while Suresh wrote about the Day 2 of the same Data Streaming meeting, Andrew wrote about Day 3 here.
• Dustin was in Aggieland and found out about a paper on Quantum Tomography Under Prior Information  that seems to yield some insight on phaseless measurements in compressive sensing. 
• Dirk wrote about Estimating unknown sparsity, sparse signal processing and proximal Newton-type methods
• Larry wrote that Minimax Theory Saves The World nut also about The Amazing Mean Shift Algorithm, a question on Statistical Principles?, and a rant on Perfunctory Examples and the Role of Applications, 
• Greg has two videos by students of his Coffee can radar course (here and here). He also has an announcement for the Next Generation Medical Imaging Workshop: Innovations Enabled by Advances in Computing, Signal Processing, and Sensor Technology . This will take place at CMU in September.  The program is here.
• Brian tells us about Solving the Maximum Diversity Integer Program
• Danny tells us about the CRAY XMT hardware.
• Laurent tells us about Baroness Daubechies
• Ken tells us about Benford’s Law and Baseball
• John lets us know about MUCMD and BayLearn
• Ben Mabey let me know of the appropriate link to Recommendations @Netflix: Big Data, Smart Models & Scalable Systems by Xavier Amatriain in the previous entry on the GraphLab presentations.
• Jason points to two opposing view of academic life. I suspect the first view is a little more accurate.
• Saw that on the comments of Andrew's blog, Frederik Pohl is 92 years old and he blogs !
• Make has an entry on Laser-cut Punch Cards for Jacquard Looms. I'll have to finish my entry on a loom that predates the Jacquard Looms and even seems to have been the first fully automated machine in human history.

Image Credit: NASA/JPL/Space Science Institute, N00193252.jpg was taken on July 25, 2012 and received on Earth July 25, 2012. The camera was pointing toward TITAN at approximately 259,617 miles (417,813 kilometers) away, and the image was taken using the CL1 and CB3 filters. 

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.

GraphLab workshop presentations

Some of the GraphLab presentations are out, enjoy!

• GraphLab Keynote Slides Carlos Guestrin
• Large scale ML challenges Ted Willke, Intel Labs
• Bloom: Disorderly Programming for Distributed Systems (30 mins) Joseph Hellerstein, UC Berkeley 
• Schism: Graph Partitioning for Scalable Query Processing on Large OLTP Databases Sam Madden – MIT 
• Visualization and Interactive Data Analysis Jeffrey Heer, Stanford
• The ParameterServrer Alexander Smola, Yahoo! Labs
• Vowpal Wabbit for Extremely Fast Machine Learning Lihong Li, Yahoo! Research
• Cassovary Graph Processing System Pankaj Gupta, Twitter 
• Tera Scale Deep Learning Quoc Le, Stanford & Google
• Identifying densely overlapping clusters in large networks Jure Leskovec, Stanford 
• Large-scale Single-pass k-Means Clustering at Scale Ted Dunning, MapR Technologies 
• Recommendations @Netflix: Big Data, Smart Models & Scalable Systems Xavier Amatriain - Netflix
• Large scale ML at Pandora Tao Ye, Pandora Internet Radio
• NIMBLE - A toolkit for the implementation of parallel data mining and machine learning algorithms on Map-Reduce, Amol Ghoting, IBM Watson (presented by: Prabhanjan Kambadur)
• Machine learning in One Kings Lane, Mohit Singh, One Kings Lane

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.

Calibrating a Kaleidoscopic Imaging System

On Twitter, Laurent reminded me of this excellent paper using Kaleidoscopes to produce a multi-view of a scene in Three-Dimensional Kaleidoscopic Imaging by Ilya Reshetouski, Alkhazur Manakov, Hans-Peter Seidel, and Ivo Ihrke. 

Surely this is an instance of compressive sensing but it doesn't seem like the authors have looked into compressive reconstruction solvers to get back images. One of the reason is the time they spend in the calibration of this camera. This brought me back to this question on the LinkedIn Group:

What about hardware implementations of CS? Is TI's DMD the only solution for building a real "single-pixel" camera. Are there any interesting hardware implementations of CS?

And the answer is yes there are other interesting hardware implementation even if sometimes, people do not use the words compressive imaging. The earliest instance I can think of, besides coded aperture, is the random lens imager but other instances exist such as this optically multiplexed imaging  [2,3] system. Eventually, one wonders if parts of the calibration process could not come easier if it were to use some sort of dynamic scene and structured sparsity approach such as featured in How many lightbulbs does it take to locate somebody ?

[1] Three-Dimensional Kaleidoscopic Imaging by Ilya Reshetouski, Alkhazur Manakov, Hans-Peter Seidel, and Ivo Ihrke: Paper [pdf], Supplemental materials [pdf], Presentation [ppt]

[2] Optically multiplexed imaging with superposition space tracking by Shikhar Uttam, Nathan A.Goodman,Mark A. Neifeld, Changsoon Kim, Renu John, Jungsang Kim, and David Brady.

[3] Fast disambiguation of superimposed images for increased field of view by Roummel Marcia, Changsoon Kim, Jungsang Kim, David Brady, and Rebecca Willett

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 seeds of a conversation

It starts with 1.3 million pageviews on the blog, or through the 1648 people on the compressive sensing group on LinkedIn or the 375 people on the Advanced Matrix Factorization group. It may also start through comments on the blog or on Google+ like Sergey just did. Sometimes, an author, like Jared or Volkan, wants to bring additional insight and make that available here. It can be done anonymously or not. In any event, make no mistake, those are the cherished seeds of a conversation you are bound to have, on subjects you care...  

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 projections onto the simplex

Volkan just sent me the following: 

Hi Igor,

I wanted to follow up on our preprint: http://arxiv.org/abs/1206.1529.

In the paper, we consider projecting sparsely onto the simplex-- a constraint that mars the application of the ell1-norm as a regularizer or as a constraint for sparsification. Interestingly, simplex constraints naturally happen in many applications, such as Markowitz portfolio optimization and density learning, where we need to find a K-sparse solution in such a way that the coefficients also sum up to a constant. The empirical results are quite encouraging. 

.....

best,

Volkan

Thanks  Volkan for reminding us of this technique and its empirical results. The paper is: Sparse projections onto the simplex by Anastasios Kyrillidis , Stephen Becker and Volkan Cevher. The abstract reads:

The past decade has seen the rise of $\ell_1$-relaxation methods to promote sparsity for better interpretability and generalization of learning results. However, there are several important learning applications, such as Markowitz portolio selection and sparse mixture density estimation, that feature simplex constraints, which disallow the application of the standard $\ell_1$-penalty. In this setting, we show how to efficiently obtain sparse projections onto the positive and general simplex with sparsity constraints. We provide an exact sparse projector for the positive simplex constraints, and derive a novel approach with online optimality and approximation guarantees for sparse projections onto the general simplex constraints. Even for small sized problems, this new approach is three orders of magnitude faster than the alternative, state-of-the-art branch-and-bound based CPLEX solver with no sacrifice in solution quality. We also empirically demonstrate that our projectors provide substantial benefits in portfolio selection and density estimation.

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.

All you wanted to know about Human Genomics but were afraid to ask

It's one of the videos that popped up on the GenomeTV channel. The title is "The Human Genome and Individualized Medicine" by David Valle. The Q&A is also very informative, as this extract shows:

.
..First of all, acute lymphoblastic leukemia. When I was a house officer in the later '60s and early '70s, acute lymphoblastic leukemia was the most common form of childhood leukemia and had a 95 percent mortality rate - 95 percent mortality. Nowadays, acute lymphoblastic leukemia remains the most common chilhood leukemia. It has 95 percent survival rate, 95 percent survival/ So it went from 95 percent mortality to 95 percent survival. So what account for that change ? So actually if you look at it, the medicines that are currently being used are very similar, if not identical, to the medicines that we used all those years ago. So it's not the kinds of medicines that are being used. What it is, I would argue, is that oncologists have learned that this diagnosis is actually a heterogeneous group of disorders. And they've learned how to use gene expression profiling, age of onset, DNA sequence variation and other tools to subdivide the patients. In other words, move from one collective diagnosis to subcategories of diagnosis moving towards individualizing the diagnosis to individual patients and the manipulating their treatment according to which subdivision the patient falls. And that approach. a more informed approach in terms of differences between individual patient with the same diagnosis, has had a dramatic effect on the consequences of having ALL....

Enjoy.

As I suspected, the definition for gene is not as straightforward.

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.

Vanishingly Sparse Matrices and Expander Graphs, with application to compressed sensing

Just in time as Sparse Measurement Matrices are of potential use in Genomics, Jared Tanner just sent me the following:

Dear Igor,

...

Thought it worth mentioning a new paper of Bubacarr Bah and I. You may recall that manuscript "Combining geometry and combinatorics: a unified approach to sparse signal recovery" by Berinde, Gilbert, Indyk, Karloff, and Strauss [IC: presentation here]. Their manuscript, they considered an l1-norm variant of the RIP, showed that can be used to give recovery guarantees for l1-minimizatin, and showed that the l1-norm RIP is quite different in character form the traditional l2-norm RIP. In particular, sparse and non-mean zero matrices can be used. This has been further extended by a number of authors, introducing algorithms specifically for such sparse matrices, often analyzed using the l1-norm RIP.

Bubacarr Bah and I have worked out some large deviation bounds on l1-RIP bounds for matrices with a fixed number of equal magnitude nonzeros per column. The bounds are sufficiently accurate that we can accurately characterize the tail bounds, but of course there is likely quite a bit of slack from the union bound. Even so, the resulting phase transition that Berinde et al. above proved for l1-minimization using l1-RIP ends up being higher than the best known l2-RIP phase transition for dense Gaussian matrices; and this l1-RIP proof is valid for sensing matrices with a fixed number of ones per column and all other entries set to zero. In fairness, the results are far below what the polytope approach gives, but we believe these are the most accurate estimates known for non-mean zero matrices.

The manuscript is available at:

http://people.maths.ox.ac.uk/tanner/papers/BaTa_expanders.pdf

All the best,

Jared

Thanks Jared, here is the paper: Vanishingly Sparse Matrices and Expander Graphs, with application to compressed sensing by Bubacarr Bah, and Jared Tanner. The abstract reads:

We consider a probabilistic construction of sparse random matrices where each column has a fixed number of nonzeros whose row indices are drawn uniformly at random. These matrices have a one-to-one correspondence with the adjacency matrices of fixed left degree expander graphs. We present formulae for the expected cardinality of the set of neighbors for these graphs, and present tail bounds on the probability that this cardinality will be less than the expected value. Deducible from these bounds are similar bounds for the expansion of the graph which is of interest in many applications. These bounds are derived through a more detailed analysis of collisions in unions of sets using a dyadic splitting technique. The exponential tail bounds yield the best known bounds for the ℓ1 norm of large rectangular matrices when restricted to act on vectors with few nonzeros; this quantity is referred to as the ℓ1 norm restricted isometry constants (RIC1) of the matrix. These bounds allow for quantitative theorems on existence of expander graphs and hence the sparse random matrices we consider and also quantitative compressed sensing sampling theorems when using sparse non mean-zero measurement matrices.

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.

Sweeping Low Earth Orbit from Space Debris with Sling-Sat

Daniele Mortari, the person behind the flower constellation, and Jonathan Missel present the Sling-Sat, a solution designed to use space debris own's momentum as a way to cleaning up Low Earth Orbit and beyond.

Some publications on the subject can be found here.



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.

And so it begins ... Compressive Genomics

You probably recall last month's "What is Faster than Moore's Law and Why You Should Care" where we noticed two facts: one, the rapid rise of computing power or imaging capabilities leading to a difficulty in keeping up with data understanding. Two, a new technology (sequencing) promises to deliver larger datasets at an even faster pace. As stated then, our only recourse is developing better algorithms....fast. Here is an instance of that need being addressed in a new Nature paper entitled  Compressive genomics by Po-Ru Loh,Michael Baym, Bonnie Berger. The introduction starts with: 

In the past two decades, genomic sequencing capabilities have increased exponentially1, 2, 3, outstripping advances in computing power4, 5, 6, 7, 8. Extracting new insights from the data sets currently being generated will require not only faster computers, but also smarter algorithms. However, most genomes currently sequenced are highly similar to ones already collected9; thus, the amount of new sequence information is growing much more slowly.

Here we show that this redundancy can be exploited by compressing sequence data in such a way as to allow direct computation on the compressed data using methods we term 'compressive' algorithms. This approach reduces the task of computing on many similar genomes to only slightly more than that of operating on just one. Moreover, its relative advantage over existing algorithms will grow with the accumulation of genomic data. We demonstrate this approach by implementing compressive versions of both the Basic Local Alignment Search Tool (BLAST)10 and the BLAST-Like Alignment Tool (BLAT)11, and we emphasize how compressive genomics will enable biologists to keep pace with current data.

The Compression-accelerated BLAST (CaBLAST) and Compression-accelerated BLAT (CaBLAT).implementations are here.

This compressive BLAST approach is not unlike what we call Compressive Signal Processing (see The Fundamentals of Compressive Sensing by Mark Davenport) , where signal recovery is not a central issue anymore 

Within the context of genomics, this approach is also just the beginning as BLAST is not seen by experts to be the end-all for some genomic data comparison. Parallel to that argument, vanilla Compressive Sensing is not seen by most advanced users to be the end-all either as we are navigating now towards removing some complexity through the use of additional information through structured sparsity,  highly correlated non sparse signals, analysis operators,  streaming algorithms , structured norms, hardware solver implementation, sparse measurement implementation and their recent extension and so on...

Closer to the intersection of genomics and compressive sensing, we have the different attempts at reverse engineering biochemical networks, some hardware that can inspect the interior of a cell such as Quadriwave lateral shearing interferometry (maybe provide some data on gene expression through some proxy) or the denovo and inventive Machine Learning approach featured in Catching an aha moment with compressive sensing, better yet we have new ways perform Bacterial Community Reconstruction Using A Single Sequencing Reaction or Simulating and analyzing compressed-sensing pooling design experiments for next-generation sequencing projects, and the list goes on.

It might even be a good idea to have a session on the subject at the next BASP meeting or even sooner. We need to get that conversation going on a large scale as we don't have much time before the field begins to crumble into many little subfields.


For videos on issues related to biology, compressive sensing, streaming algorithms you may want to watch:

• Videos: Group Testing Designs, Algorithms, and Applications to Biology
• Tell them you went surfing in Kazakhstan for the week-end: More Videos 
• Videos for the Berkeley streaming meeting:  Part 1, Part 2, Part 3, Part 4, Part 5

other Synthetic Biology and Compressive Sensing related posts are here.

Hat tip to @JohnDCook, Gerd Moe-Behrens and Integrated DNA Technologies

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.

International Biomedical and Astronomical Signal Processing (BASP) Frontiers Workshop 2013

Yves Wiaux just sent me the following announcement foe the new BASP meeting. The previous and first meeting's presentations can be found here.

Dear Colleagues,

It is our pleasure to announce the INTERNATIONAL BIOMEDICAL AND ASTRONOMICAL SIGNAL PROCESSING (BASP) FRONTIERS WORKSHOP 2013, which will take place in a small resort of the Swiss Alps (Villars-sur-Ollon, 2 hours by train from Geneva Airport) from January 27th until February 1st, 2013: http://baspfrontiers.epfl.ch/.

Abstract submission for posters/demos contributions (or talk upon availability) will open on September 1st and close on October 21st 2012.

Synopsis: The BASP Frontiers workshop was created in 2011 to promote synergies between selected topics in astronomy and biomedical sciences, around common challenges for signal processing. The 2013 workshop will gather 75 participants around the themes of sparse signal sampling and reconstruction, for radio interferometry and MRI, but will also open its floor to many other interesting hot topics in theoretical, astrophysical, and biomedical signal processing.

Higgs Note: Following the recent historical discovery at CERN announced in July, we will have a renowned particle physicist (Prof. A Parker Cavendish) to make a general interest talk "Higgs within reach - our understanding of the universe is about to change" to open the workshop.

Contributions: The workshop is organized in 10 sessions comprising 3 to 5 talks, and 3 posters/demos. While the majority of the talks are by invitation, proposals for posters/demos contributions (or talk upon availability) for a given session, are open to all interested researchers. The maximum 1-page abstract to be submitted (a latex template is provided on the workshop website) will undergo a rapid review process. The presentation of the 3 *truly deluxe* posters/demos contributions selected for each session will take place just after the talks during a 45' coffee break or apero.

Practical information: All information regarding session list, confirmed participants, program, important dates, abstract submission, registration, workshop fees, extra activities etc. are available from the workshop website.

Please forward this call to any potentially interested researcher.

Looking forward to receiving your contributions

Best regards

On behalf of the SOC

Yves Wiaux, chair

Jason McEwen, co-chair 

Thanks Yves !

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.