Thursday, January 17, 2013

Compressed Sensing with Correlation Between Measurements and Noise - implementation -





Existing convex relaxation-based approaches to reconstruction in compressed sensing assume that noise in the measurements is independent of the measurements themselves. We consider the case of noise correlated with the compressed measurements and introduce a simple technique for improvement of compressed sensing reconstruction from such measurements.The technique is based on a linear model of the correlation of additive noise with the measurements. The modification of there construction algorithm based on this model is very simple and has negligible additional computational cost compared to standard reconstruction algorithms. The proposed technique reduces reconstruction error considerably in the case of correlated measurements and noise. Numerical experiments confirm the efficacy of the technique. The technique is demonstrated with application to low-rate quantization of compressed measurements, which is known to introduce correlated noise, and improvements in reconstruction error up to approximately 7 dB are observed for 1 bit/sample quantization.
The attendant code to replicate the figures is here.


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.

Wednesday, January 16, 2013

Convergence Speed of a Dynamical System for Sparse Recovery - implementation -



Convergence Speed of a Dynamical System for Sparse Recovery by Aurele Balavoine, Christopher J. Rozell, and Justin Romberg. The abstract reads:

This paper studies the convergence rate of a continuous-time dynamical system for `1-minimization, known as the Locally Competitive Algorithm (LCA). Solving `1-minimization problems efficiently and rapidly is of great interest to the signal processing community, as these programs have been shown to recover sparse solutions to underdetermined systems of linear equations and come with strong performance guarantees. The LCA under study differs from the typical `1 solver in that it operates in continuous time: instead of being specified by discrete iterations, it evolves according to a system of nonlinear ordinary differential equations. The LCA is constructed from simple components, giving it the potential to be implemented as a large-scale analog circuit. The goal of this paper is to give guarantees on the convergence time of the LCA system. To do so, we analyze how the LCA evolves as it is recovering a sparse signal from underdetermined measurements. We show that under appropriate conditions on the measurement matrix and the problem parameters, the path the LCA follows can be described as a sequence of linear differential equations, each with a small number of active variables. This allows us to relate the convergence time of the system to the restricted isometry constant of the matrix. Interesting parallels to sparse-recovery digital solvers emerge from this study. Our analysis covers both the noisy and noiseless settings and is supported by simulation results.

From Aurele's software page:
The Matlab code that I wrote to generate the figures in the paper "Convergence Speed of a Dynamical System for Sparse Recovery," currently under preparation, is made available for people to reproduce the experiments.

The .zip file containing all the necessary Matlab functions can be downloaded here. The file containing the code that generated the figures is titled LCA_CS_experiments.m

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.

Tuesday, January 15, 2013

SVDFeature: A Toolkit for Feature-based Collaborative Filtering - implementation -


In this paper we introduce SVDFeature, a machine learning toolkit for feature-based collaborative filtering. SVDFeature is designed to efficiently solve the feature-based matrix factorization. The feature-based setting allows us to build factorization models incorporating side information such as temporal dynamics, neighborhood relationship, and hierarchical information. The toolkit is capable of both rate prediction and collaborative ranking, and is carefully designed for efficient training on large-scale data set. Using this toolkit, we built solutions to win KDD Cup for two consecutive years.
The wiki for the project and attendant code is here. It will be included in the Matrix Factorization page shortly.


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.

Monday, January 14, 2013

CSJob: Faculty at University of Wisconsin-Madison

From this page:


Faculty Recruiting

The Department of Computer Sciences at the University of Wisconsin-Madison invites applications for faculty openings at all levels (Assistant, Associate, or Full professor). Successful candidates will occupy a new state-of-the-art and centrally located Wisconsin Institutes for Discovery (www.wid.wisc.edu) research facility specifically designed to spark and support cross-disciplinary collaborations. We are seeking candidates in the general area of optimization, example interests include, but are not limited to: (i) Development of core optimization technology and large scale computational methodology; (ii) Planning techniques within application domains that exploit unfolding understanding of the physical system; (iii) Applications of simulation and stochastic optimization techniques; (iv) Use of optimization and statistical methods to understand and predict systems phenomena, even when competition exists between entities; (v) Sparse optimization and image reconstruction leveraging compressed sensing frameworks, optimization algorithms, and powerful computational platforms. Outstanding candidates in any optimization-related area will be considered.
The official Position Vacancy Listing can be found at
You may ignore the application deadline of October 15th in the PVL. Applications will be accepted until the position is filled.
Electronic submission of all application materials can be performed through https://oberon.cs.wisc.edu/Recruiting. Contact Professor Michael Ferris at ferris@cs.wisc.edu for further information.



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.

Agents of Change

I recently went to a meeting of the Open Knowledge Foundation and decided to attend the open science section. The person in charge of the roundtable clearly did not believe me when I told him that:
  • reviewers are not paid
  • journals are not a warrant of quality per se and 
  • journal staff do little in the publication process.

If somebody in charge of a discussion on open science thinks that open science is mostly about science education and not know some of the root problems in academic publishing, then why would the general public be knowledgeable about how science work ? Why would the general public care about an overzealous unbecoming prosecution in academic publishing cases ?

Unless you've been hiding in a cave this week-end, you probably heard of Aaron Swartz's passing. 

Here on Nuit Blanche, a whole many papers are coming out of ArXiv but not everybody in our rather large community goes through that route. A tiny minority still publishes only the title of their papers out of fear of breaching some sorts of contract with the publisher. In most cases however, it's been my experience that these people did not read entirely the terms and conditions under which they "surrendered" the rights to their papers. 

The SHERPA/Romeo database allows you to figure out, given the journal you published in, the conditions under which you can put your articles on the web. In some areas, it is not difficult to find one that allows, at a minimum, the sharing of preprints. 


Our community has gone beyond some of these issues however. Most of you go the extra-length by even sharing your codes and implementations as witnessed in the long list of implementation featured here and the list of solvers on the big picture and the jungle page.

Let me say it out loud again, as a agent of change Nuit Blanche will make a specific entry of your paper if there is an implementation of your algorithm attached. If you implement an algorithm, however simple and not a duplicate of a previous implementation, you will be featured on Nuit Blanche  Quite simply, if you are an agent of change, you will be featured here on Nuit Blanche   

Saturday, January 12, 2013

The Technical Side of the Nuclear Rockets Option




So there is a petition on the White House site for a Nuclear Rocket initiative. No big news as this comes back and forth every once in while. Such a technical solution was considered as recently as JIMO/Prometheus. One wonders if it will be in consideration for a Mars mission with humans given the large size of hydrogen tank needed. The staggering numbers are in part due a combination of the low efficiency of chemical rockets and the need for better space plumbing. 


Of great importance and a subject I never see really mentioned anywhere: after six months in space, humans are really incapable of doing anything under gravity for a little while. It's one thing to land on Mars, it will be another before they can leave their seats. For that reason only and if one is serious about landing people on Mars and unless we find a pill to get space travelers to not deteriorate too much, getting there faster is really the only way. Hence the nuclear rocket option.

A nuclear rocket is singularly different from other kind of space nuclear projects that are (were)   currently in use

Nuclear Rockets that have been tested in the past, and that I am aware of, fall in a different category altogether. They use a reactor core and the propellant as its coolant. That gas coolant climbs in temperature as it goes through the reactor and then exits from the core and eventually a rocket nozzle. Unlike a chemical rocket, the temperature of the hydrogen can go higher and therefore can raise substantially the ISP of said rocket. Back in the 1960s, such program was conducted and went through several prototypes. A very nice technical summary of that story can be found in this write-up: Application of Proven Rover/NERVA Nuclear Thermal Rocket Technology for NearFuture Manned Planetary Missions by Stanley Gunn and Ernest Robinson. The ISP of those rockets can be double that of any chemical rockets. The Achille's heel of these system is their scrubbing mechanism i.e. make sure none of the reactor core material is stripped from its location and sent outside through the nozzle system. 

For the technically inclined data is sparse so it of substantial interest to find the results of some of the tests of the XE-Prime engine which was probably the most advanced engine in the Technology Readiness Level ladder of that program. You can find some of the reports here (search for "XE-Prime" in DOE's database.) that feature some of the most technically advanced data I have seen on the subject.
from [1]


I note the following segment from the first reference:

"...Then, after the Kiwi TNT safety reactor test was conducted (to learn how destructive the reactor assembly would be if its control rods went wildly out of control) and the reactor assembly was self-destructed, the Los Alamos NRDS Assistant Director, two of his associates, and again Rocketdyne's NTR  Section Chief were exposed to the after-test radiation surrounding the destroyed reactor assembly.  The measured environment radiation was approximately 10 rem. Fifty years have passed, and the health of the above-defined test programs participants (as determined  by the NTS Medical Surveillance Project Office's evaluation) remain unaffected by  radiation...."

Some videos of the tests can be found on Youtube:  


 h/t Various Consequences

[1]  XE-prime EP-4A startup tests. SPEAR report


All hopes may not be crushed all at once

Here is some feedback from yesterday's It's not a bad reconstruction, just the end of an illusion...  Maybe this is a good way to restore one's confidence that somewhere, somehow there is a metric you cannot not like :-)

Hey Igor,
You mentioned in today's post that what you assume about the unknowns is pretty important. Another aspect that my student Jin Tan (copied) has been studying is what you're prioritizing in your reconstruction. Traditionally, signal processing has emphasized the square error. But Jin has work that can minimize the ell_1 error, the support set error,... - her algorithm is very flexible in supporting a broad range of possible error metrics, and this might come in handy in some applications.
Dror





Friday, January 11, 2013

It's not a bad reconstruction, just the end of an illusion...

If there is something one learns with compressive sensing it is that your assumptions on the unknown is central to how your signal will be reconstructed. For 200 years, we had to minimized energy, since 2004, we are looking for the sparsest signal and we may eventually be able to look for additional structure [3,4, 5]. Here are two examples I gleaned over a few weeks where the current assumptions are probably not the good ones. Can compressive sensing help ? 

In the Genetics of Parkinson's Disease: I asked a question as to why GWAS studies on Parkinson's did not pick up on the GBA gene ? a review paper that aimed to answer specifically that question was sent to me by one of its author and here is what they said back in 2008: 

....The identification and recognition of this strong association between glucocerebrosidase and PD raises many questions. Why did epidemiologic studies of PD miss this association? Why did genetic linkage studies not pick out the glucocerebrosidase locus on chromosome 1q21 as a Parkinson susceptibility region? Why did the whole genome association studies not identify the locus? Epidemiologists probably missed the association because Gaucher disease is much rarer than PD and the clinical phenotype is usually so different from parkinsonism that it was never considered. Genetic linkage studies would have struggled to identify the locus because of the rare nature of glucocerebrosidase mutations in most datasets with the exception of the Ashkenazi population. Furthermore, none of the mutations seem to be fully penetrant and so they will show only weak evidence for segregation in families with PD. Finally, whole genome association studies apply an overly strict correction for multiple testing and rely on the assumption, incorrect in the case of glucocerebrosidase, that there is a single disease-associated allele at each locus. The existence of the multiple disease-associated allelic variants in the gene candidate could be a general phenomenon for other neurodegenerative disorders. Such heterogeneity has important implications for replication studies that would need to assess a battery of variations in the gene of interest using datasets with homogeneous genetic background. Hence, the glucocerebrosidase example is an illustration of how an important genetic risk factor for a complex disease can evade detection by systematic analysis: it only came onto the radar because of astute clinical observations. 3

If I understand correctly, an algorithm that looks for a certain type of variant would bin that variant in one category. But overall, every individual category found through this means would not match the disease phenotype. The matching would not be explanatory. In this case, while every variant is very unique, the larger set of all the variants (group of category) could be matched globally to the disease phenotype. The reason the disease has several forms (different phenotypes) is probably because the variants are acting differently in the diverse biochemical networks [2]. And then there is the curious case of Autism or the sparse set of signaling pathways for Cancer [6]


The second misunderstood assumption is explained in The Effects of Connection Reconstruction Method on the Interregional Connectivity of Brain Networks via Diffusion Tractography by Longchuan Li, James K. Rilling, Todd M. Preuss, Matthew F. Glasser, and Xiaoping Hu. The abstract reads:

Estimating the interregional structural connections of the brain via diffusion tractography is a complex procedure and the parameters chosen can affect the outcome of the connectivity matrix. Here, we investigated the influence of different connection reconstruction methods on brain connectivity networks. Specifically, we applied three connection reconstruction methods to the same set of diffusion MRI data, initiating tracking from deep white matter (method #1, M1), from the gray matter/white matter interface (M2), and from the gray/white matter interface with thresholded tract volume rather than the connection probability as the connectivity index (M3). Small-world properties, hub identification, and hemispheric asymmetry in connectivity patterns were then calculated and compared across methods. Despite moderate to high correlations in the graph-theoretic measures across different methods, significant differences were observed in small-world indices, identified hubs, and hemispheric asymmetries, highlighting the importance of reconstruction method on network parameters. Consistent with the prior reports, the left precuneus was identified as a hub region in all three methods, suggesting it has a prominent role in brain networks

As Matt says, "And, there are certainly unknown unknowns beyond that."

[1] Gaucher and Parkinson diseases: Unexpectedly related, Ekaterina Rogaeva, John Hardy

Thursday, January 10, 2013

Fast Functions via Randomized Algorithms: Linear Regression with Random Projections

Here is something interesting not far from the Random Features / Random Kitchen Sinks approach (see the recent Fast Functions via Randomized Algorithms: Fastfood versus Random Kitchen Sinks ). The comparison to Kitchen Sinks is actually mentioned in 5.3. Let us also note the Johnson-Lindenstrauss Lemma for Gaussian Objects in 3.3. Of related interest are [1] and the recent [2].




Linear Regression with Random Projections by Odalric Maillard, Rémi Munos. The abstract reads:

We investigate a method for regression that makes use of a randomly generated subspace $G_P$ (of finite dimension $P$) of a given large (possibly infinite) dimensional function space $F$, for example, $L_{2}([0,1]^d)$. $G_P$ is defined as the span of $P$ random features that are linear combinations of a basis functions of $F$ weighted by random Gaussian i.i.d.~coefficients. We show practical motivation for the use of this approach, detail the link that this random projections method share with RKHS and Gaussian objects theory and prove, both in deterministic and random design, approximation error bounds when searching for the best regression function in $G_P$ rather than in $F$, and derive excess risk bounds for a specific regression algorithm (least squares regression in $G_P$). This paper stresses the motivation to study such methods, thus the analysis developed is kept simple for explanations purpose and leaves room for future developments.

[1] Uniform Approximation of Functions with Random Bases, Ali Rahimi and Benjamin Recht 
[2] Nystrom Method vs Random Fourier Features:: A Theoretical and Empirical Comparison Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, Zhi-Hua Zhou



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.

Improving Dictionary Learning: Multiple Dictionary Updates and Coefficient Reuse - implementation -


Leslie just sent me the following:

Dear Igor,

Since sparse representations is a related topic you discuss on Nuit Blanche, I would like to mention a recent joint paper with Michael Elad on improving dictionary learning that has recently been published in IEEE Signal Processing Letters. The paper is titled "Improving Dictionary Learning: Multiple Dictionary Updates and Coefficient Reuse" and can be download at this link: http://www.cs.technion.ac.il/~elad/publications/journals/2012/IEEE-SPL-DL-2012.pdf 
Perhaps even more interesting is that we have made available the software for the methods described in the paper and information on this software can be found at http://www.cs.technion.ac.il/~elad/software/  
Thanks for all your efforts with the blog and related study groups (LinkedIn, Google+, etc.).
Best regards,
Leslie
Thanks Leslie.


In this paper we propose two improvements of the MOD and K-SVD dictionary learning algorithms, by modifying the two main parts of these algorithms – the dictionary update and the sparse coding stages. Our first contribution is a different dictionary-update stage that aims at finding both the dictionary and the representations while keeping the supports intact. The second contribution suggests to leverage the known representations from the previous sparse-coding in the quest for the updated representations. We demonstrate these two ideas in practice and show how they lead to faster training and better quality outcome.


Printfriendly