Saturday, June 11, 2011

And Remember Kids ...

What Were Your Aha! Slides in Compressive Sensing ?


 Many aspects of Compressive Sensing are well explained when it comes to the compression aspect of it or when it comes to showing the difference between the l_0/l_1 and l_2 norm for the reconstruction stage (l_1/l_p balls). However, after one has gotten the point, additional levels of insight can be triggered by the view of simple and effective slides. Here are some of the few I have gleaned over the past two or three years. This entry is a draft version of a more complete post that will include more slides that made people say "Aha!". I have listed the authors of the presentation but I will eventually link to the full presentations in the more complete version of this post. If you have a slide for which you had an aha! moment or know of a slide that made others have this aha! moment, I am interested in hearing about them and why. You may notice that some slides have nothing to do with Compressive Sensing as presented.


Bhaskar Rao



Victoria Stodden





Jared Tanner




Deanna Needell



JohnWright















Mark Neifeld



Roummel Marcia and Rebecca Willett



Gerry Skinner



Felix Hermann


Anna Gilbert


From here.

ESA

Friday, June 10, 2011

Great Thoughts Friday: The Energy and Time of Being There.

It used to be that the question was "Can you hear me now ?". With Skype and others, now we have, " Can you see me now ?". Both of these means of communications are still primitive. I have traveled extensively and getting a sense that you are working with some people on the other side of the earth is an interesting exercise. Jet lag is one issue, but feeling a presence in the room is not instantiated in a technology that currently exist. When I first saw this video that enables the Kinect to perform some 3-D monitoring, my mind immediately raced in the same manner it did when I discovered Matlab, the web browser, the e-mail. Right at that moment, I immediately needed it in a project or two. Right at that moment, I knew, like the other times, that this was not a pillar. Call it the caveman reasoning, but the feeling of being there in the same cave before the woolly mammoth hunt is really sometimes the same reason we go to work. This technology seems to deliver that.

The kicker in my view is that you could have this 24/7  telepresence for nearly free and for long periods of time. Which bring me to the question of the day: At what point does it cost more energy wise to be in this "24/7" telepresence mode than take a plane flying for 12 or 24 hours to meet face to face ? What amount of energy/time of telepresence is equivalent to being there ? 1 day, 1 month, 1 year, 10 years ?

Random Tweets

Out of my favorites tweets, four seem more relevant to some aspect of the discussions taking place here, here they are:

Boris Reuderink made me aware of sessions in BCI conferences that featured papers on BCI with no need for calibration. I did not know people were actually contemplating doing this. I like the sound of this path very much.

David at electronsandholes let me know of the June issue of Laser Focus World featuring a four page article on Compressive Sensing (and the cover). It starts on page 31 and features mostly the single pixel camera work in the SWIR and IR regime.

Finally, Suresh let us know he is in Paris, His presentations at the CG Learning Summer School at IHP just before SOCG2011 are listed below::
Suresh Venkatasubramanian, School of Computing at the University of Utah 
Topic: The Geometry of Probability Distributions  


The program for the learning school is here. The detailed program for SoCG 2011 is here. A second satellite event MASSIVE 2011 will take place right after SoCG2011. The program is here.

Thursday, June 09, 2011

Follow-up on The Privacy Issues Involved in the Release of the Cell Phone Data to Locate the E.Coli / EHEC Outbreak ( a month later)

In the comment section of the previous entry, anonymous makes the following good point:
Hi Igor,
the situation is even more restricted than Peter wrote: The data you mentioned do not exist! According to the decision of the federal constitutional court (the highest German court) cell phone operators are just just allowed to collect data for charging issues and have to delete everything else as soon as possible.

To what I replied
Hello Anonymous,

If this is the case, how come Mr. Sptiz was able to get that data ?

what are the cases defined by the Supreme Court for the retaining of that information ? ( I am a little bit surprised that this information does not exist any more if the SC allowed for it to be used in cases of rape/murder, i.e. not immediately recognizable offences sometimes).

If the data has to be collected for charging purposes and somehow there is a litigation between a customer and the telco, what type of record can the telco show if everything has been erased ? Most billing are monthly or bi-monthly, so given what I just said, my take is that this data still exists as we speak.

Anonymous then kindly provided more context :

Hello Igor,
the court decided March 2010, before the cell phone operators had to save data for six month. The data of Mr. Spitz had been recorded before this decision. I don't know about exceptions for severe crimes or other cases where usage of the (few) existing data is permitted.

Up to my knowledge the triangulated position of the phone is not saved for charging issues. Elsewise, the data exist just if there was a phone call at this time. Nevertheless, in Germany there are a lot of mobile phones that are billed by flatrate or prepaid. In those cases there are most probably no data at all.

Ok, that was great information. Let me add something to this.. I initially pointed out that using the cell phone data of non-residents can also be more fruitful (because they are on average less in the region of interest). In the U.S., the law of the land (with clear upholding from the U.S. Supreme Court) has made it clear that there can be a legal difference between citizens and non-residents. In effect, the laws of privacy for a number of reasons may be different for the locals and for the non-residents. I am not saying it is a good thing, I am just saying that most democracies seem to make that legal distinction. The German SC may have been too focused on its citizens in its March 2010 ruling.

In the meantime, Thomas added:
Hi Igor,
As a follow up to my comment a couple of days ago, the Ingeniøren newspaper's website ran a short story today that mentions the mobile data approach: http://ing.dk/artikel/119887-saadan-hjaelper-netbanken-med-at-finde-danske-smittekilder
See if Google Translate can make any sense of it. Otherwise, let me know and I'll give you a summary. I'd be happy to discuss it.

Thanks  Thomas. The translation is here. I am getting out of it that they mostly talk about locating people through their credit cards purchases to find out the sources. But this approach hides one or two assumptions that are not factual in this specific case. Let me point out what those are in bracket in the translated text: below:
Problematic to use mobile data
Another possibility in the hunt for sources of infection, as one of ing.dk 's readers have pointed out could be to exploit the data being recorded by people's cell phones. Data as police also make use of in exploration contexts.

By cross-reference cellular data from affected persons could be a part of their whereabouts so mapped, so the example might be identified whether subjects had been attached to the same mobile phone mast within a certain period.

Consultant at SSI Steffen Glismann is not dismissive of that method could prove useful.

"We do not do it today, but it was one of the electronic footprints, one could consider using," says Steffen Glismann.

He does have his reservations about basing disease hunt for the cell tower people have been affiliated.

"This method says not so much about what people have done in an area. And there will be a lot of noise in the data. For example, many would come by the same mobile phone mast on the way down through Germany without it necessarily says anything about where they were infected, "says Steffen Glismann. [ Steffen makes the mistakes of assuming that all foreigners are Danish. They are not, about 11 different nationalities have been affected. In effect, the cross referencing of all the non-residents would clearly delineate the place or places of interest ]

In addition, experience Statens Serum Institut rare that a larger number of people have been infected the same geographic location. And that is precisely the method by looking at purchases with debit cards because it can be used to trace a product back to a single supplier, even if the goods have been sold across the country, explains Steffen Glismann. [Again Steffen makes the same mistake as the KRI folks have, they are solving a traceability issue, when in fact the issue is to reduce the number of sick people (2000 so far). These are different problems, in particular, the credit card problem won't solve people that have been exposed to the bacterium second hand].

And if more people have become infected while they were connected to the same cell tower, then a fully analog method prove to be faster than having to apply for permission to use data on mobile phones and then cross reference them, says Steen Glismann : [ Steen makes the assumption that there is no secondary infection such as hand to hand contacts, soiled surfaces like subway handles, etc.... ]

"It will be easier to ask people where they've been and what they've done." [ Again, the central assumption built in the questionnaire approach relies on the fact the that person is capable: it is not the case here as the bacterium has had a clear neurological impact on the sick,... some cannot count anymore. Eventually the other assumption is that people are sick because they ate something. ]

The Privacy Issues Involved in the Release of the Cell Phone Data to Locate the E.Coli / EHEC Outbreak ( a month later)


Igor, I can't help playing advocatus diaboli.

On the one hand, I think your idea of using cell phone data is great and somebody should really test it and see if it actually helps in such a situation.

On the other hand, the infrastructure needed is problematic. The highest German court restricted access to such data to investigations in connection with severe felonies (murder, rape etc); the original laws were unconstitutional.

Nevertheless, politicians in Germany constantly ask for more data to be collected -- after all the infrastructure is there and it creates many desires.

What I'm trying to say is that, if it works (which I think it will), there still might be sensible reasons not to follow the idea.

I have two words for this well taken privacy argument: Malte Sptiz. When someone wants to give out their information to the public in Germany, they can.

We are not talking about taking data away without consent. We are talking about citizens giving the OK to the telcos to release a certain type of information to the investigative teams. After this outbreak and the dust settles, a law could provide some framework for this. In particular, the legislator would be well advised to provide some sort of immunity to people giving this data away ( a little bit like the good samaritan laws in the books in most democracies in the world)

Around the blogs in 80 hours, ICALP2011GT program


Danny Bickson mentions a list of Matrix Factorization made by Marinka Zitnik and specifically the ones implemented in GraphLab (a competitor to Hadoop). Marinka Zitnik works on Orange for her Google Summer of Code project. From the Orange webpage:
Open source data visualization and analysis for novice and experts. Data mining through visual programming or Python scripting. Components for machine learning. Extensions for bioinformatics and text mining. Packed with features for data analytics.
Other matrix factorizations can be found here. Maybe we ought to have a place where all these are listed ?

Bob has three new entries:



Andrew: RANDOM/APPROX accepts…

Gonzalo: Is the PHY Layer Dead? about how sensing in hardware is dead or not in cognitive radio.. Fascinating stuff.

Dan: Simulating visual artifacts with Fourier optics

Meena: Shape analysis: on selecting a set of points or landmarks

Machine4Vision has a view from the trenches: Plan for the worst (and hope for the best)


The program for the ICALP2011GT is out (the meeting is mentioned in the meeting page), lots of interesting presentations:


Date 3rd July

9:00 Opening
9:05Invited talk (tba)
9:55Coffee break 
10:20Efficient two-stage group testing algorithms for DNA screening
Michael Huber
10:45 Optimal randomized group testing: A canonical form and the one-defective case
Peter Damaschke
11:10 Finding m of D defective elements in some group testing models
Rudolf Ahlswede, Christian Deppe, and Vladimir Lebedev 
11:35 small break 
11:45 Bacterial community reconstruction using compressed sensing
Amnon Amir and Or Zuk 
12:10 Identification of rare alleles and their carriers using compressed se(que)nsing
Noam Shental, Amnon Amir and Or Zuk
12:35 Lunch break 
14:00 Invited talk (tba)
14:50small break 
15:00 A group testing approach to improved corruption localizing hashing
Annalisa De Bonis and Giovanni Di Crescenzo  
15:25 A mutual information characterization for sparse signal processing
George Atia and Venkatesh Saligrama 
15:50 Meeting your neighbours
Avery Miller 
16:15 Coffee break 
16:35 Invited talk (tba)
17:25 Using group testing for pattern matching applications
Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, and Dekel Tsur 
17:50 From coding theory to efficient pattern matching
Raphael Clifford, Ely Porat, and Amir Rothschild 
18:15  Closing  

Credit: NASA, ISS027-E-036759 (23 May 2011) --- This image of the International Space Station and the docked space shuttle Endeavour, flying at an altitude of approximately 220 miles, was taken by Expedition 27 crew member Paolo Nespoli from the Soyuz TMA-20 following its undocking on May 23, 2011 (USA time). The pictures taken by Nespoli are the first taken of a shuttle docked to the International Space Station from the perspective of a Russian Soyuz spacecraft. Onboard the Soyuz were Russian cosmonaut and Expedition 27 commander Dmitry Kondratyev; Nespoli, a European Space Agency astronaut; and NASA astronaut Cady Coleman. Coleman and Nespoli were both flight engineers. The three landed in Kazakhstan later that day, completing 159 days in space.

Wednesday, June 08, 2011

Jacques Devooght's draft: Approximate Green's Function of the Linear Boltzmann Equation for Finite Media

[I don't know how to handle this, but I think this is the way to go since Google does a decent job at spidering this blog.]

 Jacques Devooght passed away back in August 1999. I had met him at Georgia Tech a mere three months earlier during the 16th Transport Theory Conference where I had presented a poster about using wavelets for decomposing the scattering kernel used in the linear transport equation, The idea was to show that for highly peaked scattering kernels such as those occurring in biological media for optics/IR, the sparser decomposition would permit fewer computations. Jacques, a very nice man with a soft voice, and I got to talk as I expressed my amazement on his finding elementary (polynomial) solutions in five variables (three dimensional space and two angles) to the linear Boltzmann equation [1]. Since his solutions were polynomial (but not positive) and wavelets were orthogonal to polynomials up to a certain order, we talked about how there could be some sorts of complementary approach. At the end of the dinner, he mentioned to me that he was working on something that might be interesting and decided that as soon as he would be back in Belgium, he would send me a draft. He did. I heard about his untimely passing a year later (as my email on the draft to him never got an answer). I recently went through some of my stuff and found the draft. I converted it in a pdf format to make it available to whoever think it might be interesting:



Compressive Sensing Literature this week Part 2

We have a strong entry today in compressive sensing and related field. I'll come back to some of these elements later. Here they are in the meantime:

Jim Fowler just sent me the following conference paper: Multiscale Block Compressed Sensing with Smoothed Projected Landweber Reconstruction by James E. Fowler, S. Mun, and Eric Tramel. The abstract reads:
A multiscale variant of the block compressed sensing with smoothed projected Landweber reconstruction algorithm is proposed for the compressed sensing of images. In essence, block-based compressed-sensing sampling is deployed independently within each subband of each decomposition level of a wavelet transform of an image. The corresponding multiscale reconstruction interleaves Landweber steps on the individual blocks with a smoothing filter in the spatial domain of the image as well as thresholding within a sparsity transform. Experimental results reveal that the proposed multiscale reconstruction preserves the fast computation associated with block-based compressed sensing while rivaling the reconstruction quality of a popular total-variation algorithm known for both its high-quality reconstruction as well as its exceedingly large computational cost.

The source code is here. Thanks Jim.

Since 2004, the field of compressed sensing has grown quickly and seen tremendous interest because it provides a theoretically sound and computationally tractable method to stably recover signals by sampling at the information rate. This thesis presents in detail the design of one of the world's first compressed sensing hardware devices, the random modulation pre-integrator (RMPI). The RMPI is an analog-to-digital converter (ADC) that bypasses a current limitation in ADC technology and achieves an unprecedented 8 effective number of bits over a bandwidth of 2.5 GHz. Subtle but important design considerations are discussed, and state-of-the-art reconstruction techniques are presented. Inspired by the need for a fast method to solve reconstruction problems for the RMPI, we develop two efficient large-scale optimization methods, NESTA and TFOCS, that are applicable to a wide range of other problems, such as image denoising and deblurring, MRI reconstruction, and matrix completion (including the famous Netflix problem). While many algorithms solve unconstrained $\ell_1$ problems, NESTA and TFOCS can solve the constrained form of $\ell_1$ inimization, and allow weighted norms. In addition to $\ell_1$ minimization problems such as the LASSO, both NESTA and TFOCS solve total-variation minimization problem. TFOCS also solves the Dantzig selector and most variants of the nuclear norm minimization problem. A common theme in both NESTA and TFOCS is the use of smoothing techniques, which make the problem tractable, and the use of optimal first-order methods that have an accelerated convergence rate yet have the same cost per iteration as gradient descent. The conic dual methodology is introduced in TFOCS and proves to be extremely flexible, covering such generic problems as linear programming, quadratic programming, and semi-definite programming. A novel continuation scheme is presented, and it is shown that the Dantzig selector benefits from an exact-penalty property. Both NESTA and TFOCS are released as software packages available freely for academic use.



I think this is the first time I see this lemma and I wonder how I can apply it directly to a specific problem where I know the eigenfunction of the null space of an operator.

We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty $l_1/l_2$-norm and the $l_1/l_\infty$-norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As the core building-block of this framework, we develop new algorithms using an alternating partial-linearization/splitting technique, and we prove that the accelerated versions of these algorithms require $O(\frac{1}{\sqrt{\epsilon}})$ iterations to obtain an $\epsilon$-optimal solution. To demonstrate the efficiency and relevance of our algorithms, we test them on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.

Fast Multidimensional NMR Spectroscopy Using Compressed Sensing by Dr. Daniel J. Holland, Mark J. Bostock, Prof. Dr. Lynn F. Gladden, Dr. Daniel Nietlispach. The abstract reads:
Make it snappy! The use of compressed sensing to reconstruct multidimensional NMR spectra enables significant reductions in recording time. Thus, 3D HNCA (blue) and HN(CO)CA spectra (green) of sufficient quality for rapid protein-backbone assignment were reconstructed from only 16 % of the fully sampled data. The generality of the method and its robustness to noise should make it more broadly applicable, for example, to solid-state NMR spectroscopy.
Re-designing the camera for computational photography by Roarke Horstmeyer. The introduction reads:
Modified optical setups enable new optical imaging functionalities, including the ability to capture depth, varied angular perspectives, and multispectral content.


Iterative aperture mask design in phase space using a rank constraint by Roarke Horstmeyer, Se Baek Oh, and Ramesh Raskar. The abstract reads:
We present an iterative camera aperture design procedure, which determines an optimal mask pattern based on a sparse set of desired intensity distributions at different focal depths. This iterative method uses the ambiguity function as a tool to shape the camera’s response to defocus, and shares conceptual similarities with phase retrieval procedures. An analysis of algorithm convergence is presented, and experimental examples are shown to demonstrate the flexibility of the design process. This algorithm potentially ties together previous disjointed PSF design approaches under a common framework, and offers new insights for the creation of future application-specific imaging systems.


The ambiguity function (AF) provides a convenient way to model how a camera with a modified aperture responds to defocus. We use the AF to design an optimal aperture distribution, which creates a depth-variant point spread function (PSF) from a sparse set of desired intensity patterns at different focal depths. Prior knowledge of the coherence state of the light is used to constrain the optimization in the mutual intensity domain. We use an assumption of spatially coherent light to design a fixed-pattern aperture mask. The concept of a dynamic aperture mask that displays several aperture patterns during one image exposure is also suggested, which is modeled under an assumption of partially coherent light. Parallels are drawn between the optimal aperture functions for this dynamic mask and the eigenmodes of
a coherent mode decomposition. We demonstrate how the space of design for a 3D intensity distribution of light using partially coherent assumptions is less constrained than under coherent light assumptions.


Highlighted Depth-of-Field Photography: Shining Light on Focus by Jaewon Kim, Roarke Horstmeyer, Ig-Jae Kim and Ramesh Raskar. The abstract reads:
We present a photographic method to enhance intensity differences between objects at varying distances from the focal plane. By combining a unique capture procedure with simple image processing techniques, the detected brightness of an object is decreased proportional to its degree of defocus. A camera-projector system casts distinct grid patterns onto a scene to generate a spatial distribution of point reflections. These point reflections relay a relative measure of defocus that is utilized in postprocessing to generate a highlighted DOF photograph. Trade-offs between three different projectorprocessing pairs are analyzed, and a model is developed to help describe a new intensity-dependent depth of field that is controlled by the pattern of illumination. Results are presented for a primary single snapshot design as
well as a scanning method and a comparison method. As an application, automatic matting results are presented.

Tuesday, June 07, 2011

Another Reason for Using Cell Phone Data to Pinpoint the E.Coli / EHEC Outbreak in Germany

I hate coming back to the subject, but I was a little taken aback by the following from Science Insider Today:
Usually neurological symptoms are seen in only a few percent of HUS cases, but in the current outbreak "about half the patients with HUS are developing neurological symptoms," Christian Gerloff, head of the neurology department at the University Medical Center Hamburg-Eppendorf, told Science Insider today.

Alarm bells started going off when some patients showed problems finding words or giving the date, Gerloff recalls. It quickly became clear that a lot of patients were developing problems reading or doing simple calculations. "Patients were mixing up words and were disoriented. Later they developed muscle twitching and then progressing to epileptic fits," Gerloff says. 

Major neurological symptoms ? how are the health and eating habits questionnaires being answered by the sick with any accuracy ? The cell phone data, i.e. the data owned by the cell phone operators that are used to triangulate your location to find out where you are (this is why they are called mobile phones), are the only data we can still gather from the 20 or so dead people (the most affected people). The cell phone data are the only means of figuring out second hand contamination from first hand contamination. Questionnaires will not help in that case.

I have already sent some e-mails out to some of the folks at RKI and other places but when I am reading  their reports, they seem focused on figuring out the bacterium's details but they don't seem too innovative in getting data that could focus them in the right direction (it is probably outside of their purview). The idea of using normal cell phone data to detect the spreading of this bacterium through direct or indirect exposure to the bacterium will not get traction unless :
  • You, the reader make it known to somebody who can make that happen (including your elected official in the 12 countries currently affected) or know a forum where specialists could refine the idea  (and own it).
  • Journalists start asking question to elected officials at press conferences (and there will be plenty when it comes to pointing fingers on the current disintegration of the fruit and vegetable markets.)

Let's put this in perspective, a potent bacterium with consequential neurological impact has affected more than 2000 people in the heart of the one of the most technologically advanced countries in the world and  after a month, we are still not using the fact that everybody has a cell phone ?

Printfriendly