Summary: Paris Machine Learning #4, Fake and Real Bayesian Worlds

On Wednesday, we had the fourth installment of the Paris Machine Learning Meetup that took place at DojoEvents. The meetup featured some Bayesian talks.

Gabriel Synnaeve talked to us about how he used Bayesian formalism to develop bots for Starcraft in his PhD thesis Bayesian Programming and Learning for Multi-Player Video Games (the HTML version is here), he even showed us a demo of his bot in action. His talk is:

• Bayesian Programming and Learning for Multi-Player Video Games

The attendant videos can be found here. Other presentations slide related to this presentation included:

• A Bayesian Model for Plan Recognition in RTS Games applied to StarCraft, Gabriel Synnaeve, Pierre Bessière, AIIDE (AAAI) 2011 (slides)
• A Bayesian Model for RTS Units Control applied to StarCraft, Gabriel Synnaeve, Pierre Bessière, CIG (IEEE) 2011 (slides)

The rest of his interesting papers and talks can be found here.

Then Andrew Gelman gave a talk (in French) entitled Modélisation hiérarchique, pooling partiel et l’interrogation de bases de données virtuelles

On top of being a well known researcher, Andrew also publishes a few blogs including Statistical Modeling, Causal Inference, and Social Science. His other presentations are here. The home page for his book Bayesian Data Analysis (75 best lines from his course). Andrew is also behind Stan ( see Stan: a program for Bayesian data analysis with complex models )

Of note:

• Of beauty, sex, and power: Statistical challenges in estimating small effect

Thank you to both Gabriel  and Andrew for presenting their work. 

The next meetup is tentatively scheduled for November 13th. More on that later. In the meantime, we also have a LinkedIn Paris Machine Learning Group you can join.

 

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: Space, Gravity, an old Geiger counter and how kilowatt-hour meters work

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.

Direct deconvolution of radio synthesis images using L1 minimisation - implementation -

Stephen Hardy just sent me the following:

Hi Igor,

I recently published a paper in Astronomy and Astrophysics describing an algorithm (called SL1M) that applies L1 minimisation to allow direct deconvolution of radio synthesis images. The new part here is the on-demand calculation of the projection matrix from the image space onto the observed interferometric visibilities, combined within an iterative thresholding algorithm. This allows arbitrary image pixel placement, non coplanar base lines and direction dependent gains to be modelled. The calculations can be done exactly or with several different approximations. Combining this technique with estimation of the regularisation parameter has the potential to produce a parameter free radio deconvolution algorithm.

Open access at A&A: http://www.aanda.org/articles/aa/abs/2013/09/aa21833-13/aa21833-13.html

Implementation (tuned to EC2 GPU instances): https://github.com/StephenJHardy/SL1M

Hope this interest to you - it certainly is to me!

cheers,

Stephen Hardy

Thanks Stephen ! As an aside, I wonder if a combination of earth rotation and antenna manipulation could provide the type of sampling required by the recent infinite dimensional CS business. Anyway, here is the paper. Direct deconvolution of radio synthesis images using L1 minimisation by Stephen J. Hardy

We introduce an algorithm for the deconvolution of radio synthesis images that accounts for the non-coplanar-baseline effect, allows multiscale reconstruction onto arbitrarily positioned pixel grids, and allows the antenna elements to have direcitonal dependent gains.

Methods. Using numerical L1-minimisation techniques established in the application of compressive sensing to radio astronomy, we directly solve the deconvolution equation using graphics processing unit (GPU) hardware. This approach relies on an analytic expression for the contribution of a pixel in the image to the observed visibilities, and the well-known expression for Dirac delta function pixels is used along with two new approximations for Gaussian pixels, which allow for multi-scale deconvolution. The algorithm is similar to the CLEAN algorithm in that it fits the reconstructed pixels in the image to the observed visibilities while minimising the total flux; however, unlike CLEAN, it operates on the ungridded visibilities, enforces positivity, and has guaranteed global convergence. The pixels in the image can be arbitrarily distributed and arbitrary gains between each pixel and each antenna element can also be specified.

Results. Direct deconvolution of the observed visibilities is shown to be feasible for several deconvolution problems, including a 1 megapixel wide-field image with over 400 000 visibilities. Correctness of the algorithm is shown using synthetic data, and the algorithm shows good image reconstruction performance for wide field images and requires no regridding of visibilities. Though this algorithm requires significantly more computation than methods based on the CLEAN algorithm, we demonstrate that it is trivially parallelisable across multiple GPUs and potentially can be scaled to GPU clusters. We also demonstrate that a significant speed up is possible through the use of multi-scale analysis using Gaussian pixels.

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.

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

Following up on his recent ArXiv preprint (An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals) , Phil Schniter just sent me the following:

Hi Igor, 

My grad student Jeremy Vila created a nice website that summarizes our non-negative (NN) AMP work (which we call EM-NN-AMP) and presents concise Matlab examples of how to use it. Hopefully your readers will find it useful. The link is 

http://www2.ece.ohio-state.edu/~vilaj/EMNNAMP/EMNNAMP.html 

In particular, the examples presented there are:

1) Recovering a non-negative signal in noise. This also shows how to toggle between our three proposed algorithms: NNLS-AMP, EM-NNL-AMP, and EM-NNGM-AMP.

2) Recovering linearly constrained non-negative sparse signals in noise.

3) Recovering a NN satellite image from compressive linear (fast Hadamard) measurements.

4) Robustly recovering signals in the presence of outliers.

Cheers,

Phil

--

Phil Schniter

Thanks Phil  and Jeremy !

From the page:

Advantages of EM-NN-AMP
We highlight some of EM-NN-AMP's advantages below:

• EM-NNL-AMP removes the need to hand tune for the NN LASSO problem.
• State-of-the-art noiseless phase transitions of simplex-obeying sparse Dirichlet signals using EM-NNGM-AMP.
• State-of-the-art noisy recovery of a NN image for all undersampling ratios using EM-NNGM-AMP.
• Excellent performance on the portfolio optimization problem using the return-adjusted Markowitz mean-variance framework. When coupled with the additive white Laplacian noise model, performance improves further.
• Very good complexity scaling with problem dimensions and can leverage fast operators such as FFTs.

Three tiny notes:

• the reason the phase transitions are even better than the traditional Donoho-Tanner phase transition is probably embedded in the additional structure given to the signal (positivity) and the nice structure of AMP. We know that additional structure in the signal such as structured sparsity will push that phase transition further. 
• We have known for quite some time that some solvers enforced positivity by default but never knew why. This implementation might shed some light there but mathematically there is something deeper at play. And really the answer to that question is yes: yes we expect the mathematicians to clear the waters there. If we were to draw a parallel with previous discoveries, one could sat that while NMF is synonymous with matrix factorization in the research world (and even though the matrix factorization jungle is much richer)  the standard algorithm for NMF was uncovered in 2000 but remained out of sounder theoretical basis until recently. That did not stop scores of applied work to be using it. Let us hope that EM-NN-AMP a similar push to a wider audience.
• EM-NN-AMP will be added shortly to the CS reconstruction algorithm section of the Big Picture in Compressive Sensing.

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.

Tonight / Ce Soir: Fourth Paris Machine Learning Meetup: Fake and Real Bayesian Worlds

Foreword, if you are interested in making a presentation at one of these meetups, please contact me.

Pick the version you are most comfortable with:

English version:

Franck Bardol, Frederic Demback and I are inviting you tonight at 7 PM to the Fourth Paris Machine Learning Meetup. The event will take place at DojoEvents (41 Bd St Martin, 75010 Paris )

First, Gabriel Synnaeve will talk to us about how he used Bayesian formalism to develop bots for Starcraft ( Bayesian Programming and Learning for Multi-Player Video Games). Then, Andrew Gelman will talk to us about hierarchical models and how they were applied to think differently about U.S. voting behaviors (Hierarchical Modeling, Partial Pooling, and the Virtual Database Query). Presentations will be in French and so will the Champagne.  To attend please register at the meetup.com site. 

Version Francaise:

Franck Bardol, Frederic Demback et Igor Carron vous invitent au quatrième meetup Parisien des applications du Machine Learning qui se tiendra à DojoEvents (41 Bd St Martin, 75010 Paris) le ce soir a partir de 19h00.

Nous aurons deux invités qui ont une vue bayésienne du monde. Le premier est Gabriel Synnaeve (http://goo.gl/niwQuu ) qui nous parlera de son utilisation du formalisme bayésien pour créer des bots sur Starcraft [1]. Le deuxième invité sera le célèbre Andrew Gelman (http://goo.gl/DNwUEe) qui nous parlera de modèles hierarchiques utilisés, entres autres, pour comprendre les comportements de vote aux États-Unis. [2]. Les présentations seront en Français. Le champagne sera lui aussi français.

[1] Bayesian Programming and Learning for Multi-Player Video Games

[2] Hierarchical Modeling, Partial Pooling, and the Virtual Database Query

Pour s'inscrire, c'est gratuit, mais il faut le faire à travers le site de Meetup.com: http://goo.gl/2CZDiA

Vous pouvez nous aidez à organiser des évènements comme celui-la en vous decommandant de cet évènement si vous ne pouvez y assister (même une heure avant): un très grand merci d'avance. Les présentations seront mis en ligne ultérieurement. 

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.

Application of compressed sensing to genome wide association studies and genomic selection

As we were talking about phase transition, the next paper has already been covered by at least two of its authors on their respective blogs:

• Paper on compressed sensing and genomics by Carson C. Chow
• The human genome as a compressed sensor by Steve Hsu [update: a new entry here]

Go check them out, I'll wait.

Roughly speaking, the authors put GWAS findings in a regression setting and use the Donoho-Tanner (DT) phase transition to get a rule of thumb in the number of people needed in a study to detect a connection between SNP results and a phenotype with a certain amount of loci with nonzero effects. This is outstanding! I note the use additive noise and how it affects the DT phase transition to get a realistic rule of thumb (much like what was done in [1])

The paper is: Application of compressed sensing to genome wide association studies and genomic selection by Shashaank Vattikuti, James J. Lee, Stephen D. H. Hsu, Carson C. Chow

We show that the signal-processing paradigm known as compressed sensing (CS) is applicable to genome-wide association studies (GWAS) and genomic selection (GS). The aim of GWAS is to isolate trait-associated loci, whereas GS attempts to predict the phenotypic values of new individuals on the basis of training data. CS addresses a problem common to both endeavors, namely that the number of genotyped markers often greatly exceeds the sample size. We show using CS methods and theory that all loci of nonzero effect can be identified (selected) using an efficient algorithm, provided that they are sufficiently few in number (sparse) relative to sample size. For heritability h2 = 1, there is a sharp phase transition to complete selection as the sample size is increased. For heritability values less than one, complete selection can still occur although the transition is smoothed. The transition boundary is only weakly dependent on the total number of genotyped markers. The crossing of a transition boundary provides an objective means to determine when true effects are being recovered. For h2 = 0.5, we find that a sample size that is thirty times the number of nonzero loci is sufficient for good recovery.

If you are already aware of CS but not much into GWAS studies, here are some interesting tidbits from the paper (my emphasis underlined):

More importantly, we provide an independent quantitative criterion for when the method will work. In addition, the choice of optimization parameters has led some researchers to adopt computationally intensive procedures for integrating over the continuum of possible values as well as effectively reducing the statistical power by reserving data for cross-validation (Park and Casella 2008; Makowsky et al. 2011; Zhou et al. 2013). We show how the lasso penalization parameter can be determined theoretically rather than empirically through cross-validation (Candes` and Wakin 2008; Candes` and Plan 2009; Candes` and Plan 2011; Candes` 2011), preserving all the data for training.

what the Donoho-Tanner phase transition is really used for in this context:

Using more than 12,000 subjects from the ARIC European-American and GENEVA cohorts and nearly 700,000 single-nucleotide polymorphisms (SNPs) we show that the matrix of genotypes acquired in GWAS obeys properties suitable for the application application of CS theory. In particular, a given sample size determines the maximum number of nonzero loci that will be fully selected using a technique such as lasso

One notes the use of an additive noise that is connected to a heritability trait:

...The transition between poor and complete selection is sharp in the noiseless case (heritability equal to one). It is smoothed in the presence of noise (heritability less than 6one) but fully detectable. Consistent with CS theory, we find in cases with realistic residual noise that the minimal sample size is primarily determined by the number of nonzero locis and depends very weakly on the number of genotyped markers p (Candes` et al. 2006; Donoho et al. 2011; Candes` and Plan 2011).

The detail of the measurement matrix:

The SNP genotype matrix (A) consisted of 12,464 subjects and 693,385 SNPs. SNPs were coded by their minor allele and alleles were combined resulting in values of 0, 1, or 2. SNP vectors were standardized across subjects. Missing genotypes were replaced with 0’s after standardization.

with another Rosetta stone moment: 

Very roughly, we can say that the goal of GWAS [genome-wide association studies] per se is to identify the s nonzero elements of x, whereas the goal of GS [genomic selection]  is to determine Ax.

How does additive noise influence the number of samples, quite typically it is the main reason one ought to use these Donoho-Tanner phase transition diagrams, here we have (the lower h, the higher the noise)

Given the assumptions of h2 = 0.5 for height (Yang et al. 2010; Vattikuti et al. 2012) and a critical ρ = 0.03 per the simulations above, this suggests that the number of height-associated SNPs is greater than four hundred. This lower bound agrees with GWAS findings to date that have identified hundreds of height-associated SNPs while accounting for only a fraction of the genetic variance (Yang et al. 2012; Turchin et al. 2012).

and from the additive noise study, we get a rule of thumb, much like we do when designing hardware sensors:

For example, if h2 = 0.5, which is roughly the narrow-sense heritability of height and a number of other quantitative traits (Yang et al. 2010; Davies et al. 2011; Vattikuti et al. 2012), we find that irrespective of δ, ρ should be less than 0.03 for recovery. There is no hope of recovering x above this threshold. For example, if we have prior knowledge that s = 1, 200, then this means that the sample size should be no less than 40,000 subjects. As a rough guide, for h2 ∼ 0.5 we expect that n ∼ 30s is sufficient for good recovery of the loci with nonzero effects.

What's next ?

Phil Schniter just let us know about An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals that uses an AMP approach to LASSO with better phase diagrams than the ones allowed by l_1 minimization. That ought to be looked into as we know that the DT phase transition is also dependent on the actual algorithm used.

A second take is if one could also include multiplicative noise in the study as SNP measurements might have some errors. In that case, one wonders what an MMV approach might mean or even be feasible.

A third take on this is if one would allow for some sort of block structure to be dsiscovered  in the regression, one would probably decrease the number of samples and begin to provide some explanation as to which loci are really the important ones. In particular, the mapping between the regression coefficients within either a tree like or block like structure  might give a clue as to which biochemical network is really at play and the ones affected as a side effect.

Note: Unless I am mistaken, the earliest use of these DT diagrams to judge a physical setting/hardware was in [1] which happened to be in the recently mentioned Radar setting.

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

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.

Two postdocs: UC Davis Math, EPFL

Thomas Strohmer just sent me the following:

Dear Igor,

Would you be so kind and announce the postdoc position described below on your Nuit Blanche blog?

best regards,

Thomas

Sure Thomas!

----------------------------

POST-DOCTORAL POSITION IN MATHEMATICS University of California, Davis

The Department of Mathematics at the University of California, Davis, is soliciting applications for a Postdoctoral Scholar position with a starting date between March 2014 and October 2014.

To be considered for the Postdoctoral Scholar position, the Department seeks applicants with a strong knowledge base in Sparse Approximations, Compressive Sensing, Numerical Algorithms and/or Optimization. A Ph.D. in Mathematics or the equivalent is required by August 31, 2014. The position requires working on research related to a defense-based project (sponsored by DTRA/NSF), led by Professor Thomas Strohmer. The research is concerned with developing theory and algorithms for phase retrieval, hyper spectral imaging, and signal recovery in connection with threat detection. The candidate should also have excellent programming skills in Matlab. The annual salary of this position is $60,000, plus some travel funds. The position carries no teaching duties the first two years, but teaching may be possible upon request. The third year may be a 9-month position with 50% teaching and 50% research. The appointment is renewable for a total of up to three years, assuming satisfactory performance. The UC Davis Math and Applied Math programs have been ranked among the nation’s top programs by the National Research Council in its most recent report. Additional information about the Department may be found at https://www.math.ucdavis.edu/. Our postal address is Department of Mathematics, University of California, One Shields Avenue, Davis, CA 95616-8633. Applications will be accepted until the positions are filled. To guarantee full consideration, the application should be received by December 15, 2013 by submitting the AMS Cover Sheet and supporting documentation electronically through http://www.mathjobs.org/. The University of California is an affirmative action/equal opportunity employer.

Also in the latest NA Digest:

Subject: Postdoc Positions, Lab for Information & Inference Systems, EPFL 

The Laboratory for Information and Inference Systems(http://lions.epfl.ch/) at Ecole Polytechnique Federale de Lausanne (EPFL) has multiple openings for energetic postdoctoral fellows in thebroad fields of Applied Mathematics, Theoretical Computer Science, and Statistics as part of Prof. Volkan Cevher's 5-year European Research Council project.

Our lab provides a fun, collaborative research environment with state-of-the-art facilities at EPFL, one of the leading technical universities worldwide. EPFL is located in Lausanne next to Lake Geneva in a scenic setting.

Topics of interest include, but are not limited to Analysis and design of advanced convex and non-convex optimization methods with applications to inverse problems; Analysis and design of advanced discrete optimization methods with particular emphasis on sublinear, submodular, and approximation algorithms; Learning theory and methods for non-parametric, sparse additive models; Encoder design for compressive and adaptive measurement schemes, including information extractors (e.g., polar codes) and expanders; Advanced linear algebra methods for optimized information extraction from very large dimensional datasets; Analysis and applications of non-iid probabilistic models.

Applicants are expected to have finished, or are about to finish their Ph.D. degrees. They must have an exceptional background at least in one of the following topics: numerical convex optimization, combinatorial optimization, statistics, coding theory, and algorithms.A track record of relevant publications at top applied mathematics,theoretical computer science, statistics, or engineering journals or conferences is essential. The working language at EPFL is English.

Starting date: available immediately

For informal enquiries, please contact Bubacarr Bah,bubacarr.bah@epfl.ch

The application letter including a curriculum vitae with a list of publications, statement of research, contact details for 3 references should be sent via email to Gosia Baltaian gosia.baltaian@epfl.ch

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.

Around the Blogs in 78 Summer Hours: Phase transitions, infinite CS and earliest version of phase transitions ?

Ever since the last around the blogs, we had quite a few interesting blog entries but first things first. Here are some feedbacks. Following up on the CoSeRa blog entry pointing to the presentations slides there, I felt there was a connection between those and the inifinite dimensional issues arising in a later blog entry and sent an email out to both Anders Hansen and Holger Rauhut. Holger responded with: 

Dear Igor,

Thanks for your remark and for mentioning CoSeRa 2013 in your blog. There is another recent paper of Rachel Ward and myself which goes into a similar direction, see

http://arxiv.org/abs/1308.0759

Best wishes,

Holger

while Anders Hansen sent me the following:

Thanks so much for again writing about infinite-dimensional compressed sensing on your blog (you are doing a great job). This is an important topic that is getting more and more attention. Just to let you know, there will be a mini-symposium at the "8th International Conference on Curves and Surfaces (2014)" entitled "Sampling and compressive sensing over the continuum", that will focus specifically on these issues.

http://smai.emath.fr/curves2014/

Best wishes,

Anders

Yes, we all agree that in the context of dealing with field equations, the theory needs to provide as much input as possible to the hardware folks. If this issue of phase transition can be added to the current infinite dimensional CS or in the context of TV/weighted series, then we ought to witness a Donoho-Tao moment in the Radar community at the next CoSeRa meeting :-). As a reminder the Donoho-Tao moment was well put in this 2008 IPAM newsletter:

....It’s David Donoho [5] reportedly exclaiming a panel of NSF folks “You’ve got Terry Tao (a Fields medalist [6]) talking to geoscientists, what do you want?” ....

Fall 2008 UCLA Math Department Newsletter, Mark Green Ends His Remarkable Odyssey at IPAM 

Also, following up on a comment I made in comment on a comment on "The Mathematical Shape of Things to Come", Emmanuel Candes reminded me that the phenomenon of phase transition was initially observed  in the June 2004 Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information specifically in Figures 2 and 3. 

Which gets me to be thinking: Is this phenomenon of phase transition new provided that we already established there was a 200 year gap ? While anybody come up with signs of the phase transition in 1-D, is there an earlier version of a phase transition in 2D or 3D ?
Thanks Anders, Holger and Emmanuel for the insights and informations.
The blogs provided some very insightful subjects to read on. Here there are in no particular order. Let us note that one of them (Andrew) will be speaking at the upcoming Paris Machine Learning Meetup on Wednesday. For more, check and register here if you want to attend. In the meantime, enoy:
Dusty

• A fully automatic problem solver with human-style output
• Probably Approximately Correct

Olimex

• Weekend Programming Challenge: Week #28 Sudoku Solver

Danny

• Kaggle Titanic Contest Tutorial
• First Spark Summit
• New SOSP paper: a lightweight infrastructure for graph analytics
• Spark raises 14M $ to compete with Hadoop
• GraphLab Internship Program (Machine Learning Summer Internship)

Andrew

• Visualization, “big data”, and EDA
• Gladwell and Chabris, David and Goliath, and science writing as stone soup
• Chris Chabris is irritated by Malcolm Gladwell
• Mister P: What’s its secret sauce?
• A Bayesian approach for peer-review panels? and a speculation about Bruno Frey
• Ideas that spread fast and slow
• Give me a ticket for an aeroplane
• Scientific communication that accords you “the basic human dignity of allowing you to draw your own conclusions”

Larry

• Assumption-Free High-Dimensional Inference
• Estimating Undirected Graphs Under Weak Assumptions

SAGE

• A Symphony of Cursors" (guest post by Jason Grout)

Christian

• Statistics for spatio-temporal data [book review]
• relativity of falsification?
• interacting particle systems as… facebook

Albert

• Post-Doc Opening at TU Delft

Vladimir

• Samsung Invests in Structured Light 3D Imager Startup
• Bacterial Imager Proposed
• Crosstalk Reduction Between Multiple Structured Light Cameras
• European IR Sensor Industry Consolidates

NoI

• What stops us defining Truth?

Pip

• Proving Cook’s Theorem

Dick

• Rating FOCS 1973
• Stealing Strategies

Mikael

• Random generalized linear models

WR

• Python division by zero is not IEEE compliant

Laurent

• Conference: Is there a place for beauty in our research? A few thoughts inspired by Richard Hamming

Meena

• The connection between Linus Pauling and fMRI

Djalil

• Vieillissement
• Premier cours à Dauphine

Anand

• GmailTeX

Cable

• Manifold Flow
• Phase Separator in Operation

Dirk

• The Kurdyka-Łojasiewicz inequality and gradient descent methods
• Post-it for convex optimization for optimal transport, value functions, accelerated forward backward and Bayesion inversion

Kaggle

• POWERDOT awarded $500,000 and Announcing Heritage Health Prize 2.0

David

• Chomsky vs. Hinton
• The Free Lunch Theorem

While on Nuit Blanche, we had:

• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• OrderedLASSO : Statistical Estimation and Testing via the Ordered L1 Norm - implementation 
• Phase Retrieval: Covariance Estimation, Sparse Signals
• Infinity Continues to Matter: Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum
• Slides: Second Edition of the International Workshop on Compressed Sensing applied to Radar (CoSeRa 2013)
• Compressed Counting Meets Compressed Sensing
• Imaging strong localized scatterers with sparsity promoting optimization
• About t'em breakthroughs and a comment on a comment on "The Mathematical Shape of Things to Come"
• Ceci n'est toujours pas le blog de Nuit Blanche
• Saturday Morning Video: The mathematics of weight loss
• Paris Machine Learning LinkedIn group and Meetup #4
• The Tale of Three Breakthroughs: Matrix Sketches, Face Recognition and an AMP based LASSO
• CfP: ITWIST'14: "international - Traveling Workshop on Interactions between Sparse models and Technology"
• Videos: Succinct Data Representations and Applications
• Nuit Blanche In Review (September 2013)
• Internet of Things #2 Paris Meetup summary
• 2497..2498..2499..
• Videos: Big Data Boot Camp Day 2,3 and 4, Simons Institute, Berkeley
• Accurate Profiling of Microbial Communities from Massively Parallel Sequencing using Convex Optimization - implementation -
• Videos: Big Data Boot Camp Day 1, Simons Institute, Berkeley
• Around the blogs in 78 Summer hours: Dina Katabi Mac Arthur Fellow, Big Data at the Simons Institute and more ....

Credit photo: Interphase Transport Lab, Texas A&M University.
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.

An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals

Phase transitions, AMP and hyperspectral, I already like it. Phil Schniter just sent me the following:

Hi Igor,

[Our] paper ...is now public: http://arxiv.org/abs/1310.2806

The main objective is to solve a special case of the compressed sensing problem: that where the signal is non-negative and also satisfies given linear equality constraints, such as simplex-constrained signals. Since you enjoy phase transition curves, you may find interest in Figures 1-2.

A by-product of our work on this problem is a method to tune AMP-based LASSO (or variants on LASSO) using the EM algorithm. Figure 4 shows (among other things) a comparison of our EM-tuned non-negative LASSO with that of a convex solver (TFOCS) tuned using an oracle: we are basically matching the mean-squared-error performance at all points (while running 1-2 orders of magnitude faster).

Cheers,

Phil

Thank you Phil ! Here is the paper: An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals by Jeremy Vila, Phil Schniter

We propose two novel approaches to the recovery of an (approximately) sparse signal from noisy linear measurements in the case that the signal is apriori known to be non-negative and obey given linear equality constraints, such as simplex signals. This problem arises in, e.g., hyperspectral imaging, portfolio optimization, density estimation, and certain cases of compressive imaging. Our first approach solves a linearly constrained non-negative version of LASSO using the max-sum version of the generalized approximate message passing (GAMP) algorithm, where we consider both quadratic and absolute loss, and where we propose a novel approach to tuning the LASSO regularization parameter via the expectation maximization (EM) algorithm. Our second approach is based on the sum-product version of the GAMP algorithm, where we propose the use of a Bernoulli non-negative Gaussian-mixture signal prior and a Laplacian likelihood, and propose an EM-based approach to learning the underlying statistical parameters. In both approaches, the linear equality constraints are enforced by augmenting GAMP's generalized-linear observation model with noiseless pseudo-measurements. Extensive numerical experiments demonstrate the state-of-the-art performance of our proposed approaches.

GAMP is available here.

Phil also has three review talks of generic interest:

• Adaptive Compressive Noncoherent Change Detection, 
• AMP Tools for Large-Scale Inference,
• A Primer on Compressive Sensing, 

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.

OrderedLASSO : Statistical Estimation and Testing via the Ordered L1 Norm - implementation -

Here is a new instance (and an implementation) of LASSO: Statistical Estimation and Testing via the Ordered L1 Norm by Malgorzata Bogdan, Ewout van den Berg Weijie Su, Emmanuel J. Candes

We introduce a novel method for sparse regression and variable selection, which is inspired by modern ideas in multiple testing. Imagine we have observations from the linear model , then we suggest estimating the regression coefficients by means of a new estimator called the ordered lasso, which is the solution to

here, and is the order statistic of the magnitudes of . In short, the regularizer is an ordered norm which penalizes the regression coefficients according to their rank: the higher the rank — the closer to the top — the larger the penalty. This is similar to the famous Benjamini-Hochberg procedure (BHq) [1], which compares the value of a test statistic taken from a family to a critical threshold that depends on its rank in the family. The ordered lasso is a convex program and we demonstrate an efficient algorithm for computing the solution. We prove that for orthogonal designs with variables, taking ( is the cumulative distribution function of the errors), , controls the false discovery rate (FDR) for variable selection. This holds under the assumption that the errors are i.i.d. symmetric and continuous random variables. When the design matrix is nonorthogonal there are inherent limitations on the FDR level and the power which can be obtained with model selection methods based on -like penalties. However, whenever the columns of the design matrix are not strongly correlated, we demonstrate empirically that it is possible to select the parameters as to obtain FDR control at a reasonable level as long as the number of nonzero coefficients is not too large. At the same time, the procedure exhibits increased power over the lasso, which treats all coefficients equally. The paper illustrates further estimation properties of the new selection rule through comprehensive simulation studies.

The attendant code in Matlab and R is located 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.