Monday, June 23, 2014

Multidimensional Compressed Sensing and their Applications - implementation -


Multidimensional Compressed Sensing and their Applications by Cesar F. Caiafa,Andrzej Cichocki
Compressed Sensing (CS) comprises a set of relatively new techniques thatexploit the underlying structure of data sets allowing their reconstruction fromcompressed versions or incomplete information. CS reconstruction algorithmsare essentially non-linear, demanding heavy computation load and large storage memory, especially in the case of multidimensional signals. Excellent review papers discussing CS state-of-the-art theory and algorithms already existin the literature which mostly consider data sets in vector forms. In this article,we give an overview of existing techniques with special focus on the treatmentof multidimensional signals (tensors) and discuss recent trends that exploit thenatural multidimensional structure of signals (tensors) achieving simple and efficient CS algorithms. The Kronecker structure of dictionaries is emphasizedand its equivalence to the Tucker tensor decomposition is exploited allowing usto use tensor tools and models for CS. Several examples based on real world multidimensional signals are presented illustrating common problems in signal processing such as: the recovery of signals from compressed measurements for MRI signals or for hyper-spectral imaging, and the tensor completion problem (multidimensional inpainting).
The demo page with implementation 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.

Saturday, June 21, 2014

Saturday Morning Video: Europe Wide Machine Learning Meetup: Andrew Ng and more....

When Franck and I were initally thinking about this last Paris Machine Learning meetup of the season, we did not imagine in our wildest assumptions what eventually became a Europe Wide Machine Learning Meetup. 
 We counted 250 people in one room in Paris but other numbers included: 2 Continents, 3 Time Zones, 4 Meetups, 5 locations connected at any one point, 7 presenters such as Francois Sterin, Bastien Legras, Andrew Ng, S. Muthu Muthukrishnan, Yaroslav Bulatov, Camille Couprie and Sam Bessalah. Here is the video of the meetup:



Time  of appearance and attendant presentation slides

Besides the presenters, our thanks go to:

The sponsor Bastien Legras at Google.

The people who quite simply made it **all** happen in the back end room in Paris: Colin Hunter, Dom Egan and Antoine Bourdain. Seven presentations, three of them on a different continent, interactions between five different locations on three different time zones at any one point of the meetup. The control of three different outputs (what we saw in Paris, what the folks on YouTube saw and a local recording) and a continuous behind the scene discussion with each of the participants (meetups and speakers). Cool under pressure and a flawless execution. Franck and I are still shell schocked it worked out like it did. Just Wow !

The organizers of the Zurich (Martin Jaggi) Berlin (Daniel Nouri, Andreas Mueller) and London (Jacqueline Forien, Libby Kinsey , Jurgen van Gael, Martin Goodson) meetups. They were bold enough to say yes to a meetup during the World Cup. It takes guts, that's all we are going to say about this.

It is obvious to Franck and I that we are collectively more intelligent as a result of that meetup. I'll do a write up of what tool we used and the type of organizations it eventually required to get 250 people in one room.




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.

Friday, June 20, 2014

Takens' Embedding and Riemannian preconditioning

If wish I had known about the Johnson-Lindenstrauss Lemma or the Taken's embedding theorem or even surfing on manifolds to do things faster much earlier than I did. For the sake of putting things in context, here is the connection between compressive sensing and the Johnson-Lindenstrauss lemma (from The Johnson-Lindenstrauss Lemma Meets Compressed Sensing):

...In Compressed Sensing (CS) [2, 7], for example, a random projection of a highdimensional but sparse signal vector onto a lower-dimensional space has been shown, with high probability, to contain enough information to enable signal reconstruction with small or zero error. Random projections also play a fundamental role in the study of point clouds in high-dimensional spaces. The Johnson-Lindenstrauss (JL) lemma [12], for example, shows that with high probability the geometry of a point cloud is not disturbed by certain Lipschitz mappings onto a space of dimension logarithmic in the number of points. The statement and proofs of the JL-lemma have been simplified considerably by using random linear projections and concentration inequalities [1]....

Equally, why should we care about Takens' embedding theorem ? here is some insight (from the first paper) as to why we should care:

"...The underlying problem is that while Takens’ theorem guarantees the preservation of the attractor’s topology, it does not guarantee that the geometry of the attractor is also preserved. To be precise, Takens’ result guarantees that two points on the attractor do not map to the same point in the reconstruction space, but there are no guarantees that close points on the attractor remain close under this mapping (or far points remain far). Consequently, relatively small imperfections could have arbitrarily large, unwanted effects when the delay coordinate map is used in applications..."

The second paper takes on a somewhat related route, where, beyond defining specific metrics for specific objects like Toeplitz or psd matrices and whatnot, the next step is to use those to perform some computations faster ( see also some of these recent comments)



Takens' Embedding Theorem asserts that when the states of a hidden dynamical system are confined to a low-dimensional attractor, complete information about the states can be preserved in the observed time-series output through the delay coordinate map. However, the conditions for the theorem to hold ignore the effects of noise and time-series analysis in practice requires a careful empirical determination of the sampling time and number of delays resulting in a number of delay coordinates larger than the minimum prescribed by Takens' theorem. In this paper, we use tools and ideas in Compressed Sensing to provide a first theoretical justification for the choice of the number of delays in noisy conditions. In particular, we show that under certain conditions on the dynamical system, measurement function, number of delays and sampling time, the delay-coordinate map can be a stable embedding of the dynamical system's attractor.


Riemannian preconditioning by Bamdev Mishra, Rodolphe Sepulchre
The paper exploits a basic connection between sequential quadratic programming and Riemannian gradient optimization to address the general question of selecting a metric in Riemannian optimization. The proposed method is shown to be particularly insightful and efficient in quadratic optimization with orthogonality and/or rank constraints, which covers most current applications of Riemannian optimization in matrix manifolds.

A Riemannian approach to low-rank algebraic Riccati equations - implementation -

Somehow related to neutron transport theory and a different kind of matrix factorization, here is: A Riemannian approach to low-rank algebraic Riccati equations by Bamdev Mishra, B. Vandereycken
We propose a Riemannian optimization approach for computing low-rank solutions of the algebraic Riccati equation. The scheme alternates between fixed-rank optimization and rank-one updates. The fixed-rank optimization is on the set of fixed-rank symmetric positive definite matrices which is endowed with a particular Riemannian metric (and geometry) that is tuned to the structure of the objective function. We specifically discuss the implementation of a Riemannian trust-region algorithm that is potentially scalable to large-scale problems. The rank-one update is based on a descent direction that ensures a monotonic decrease of the cost function. Preliminary numerical results on standard small-scale benchmarks show that we obtain solutions to the Riccati equation at lower ranks than the standard approaches.


from the code page of Bamdev Mishra

We solve the equation $ATX + XA + X BBT X = CTC$ for X on the low rank manifold of symmetric and positive definite matrices, where A is large and sparse, B is a tall matrix, and C is a fat matrix. For $B = 0$, this boils down to the Lyapunov equation.
The code has been tuned for large scale problems. Computationally, the numerical bottleneck involes solving the linear system $Px = b$, where P is a sparsely-structured matrix.
In the present code, $Px = b$ for smaller to moderate size problems (about 10 000 x 10 000) is solved with the backslash operator of Matlab without any tuning. For larger size matrices, we employ the Matlab's built-in iterative pcg solver without any tuning, which may not be efficient for all problems. Specific problems call for specific solvers! If you are interestd in a particular setup and have a solver, then do look for the function "use_iterative_solver" in the file "Main_files/Riemannian_lowrank_riccati.m" and modify it accordingly.
The code is built on the Manopt platform. Feel free to contact me on any issue.
It will be added to the Advanced Matrix Factorization Jungle page.

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

Thursday, June 19, 2014

Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics




Principal component analysis (PCA) aims at estimating the direction of maximal variability of a high-dimensional dataset. A natural question is: does this task become easier, and estimation more accurate, when we exploit additional knowledge on the principal vector? We study the case in which the principal vector is known to lie in the positive orthant. Similar constraints arise in a number of applications, ranging from analysis of gene expression data to spike sorting in neural signal processing.
In the unconstrained case, the estimation performances of PCA has been precisely characterized using random matrix theory, under a statistical model known as the `spiked model.' It is known that the estimation error undergoes a phase transition as the signal-to-noise ratio crosses a certain threshold. Unfortunately, tools from random matrix theory have no bearing on the constrained problem. Despite this challenge, we develop an analogous characterization in the constrained case, within a one-spike model.
In particular: $(i)$~We prove that the estimation error undergoes a similar phase transition, albeit at a different threshold in signal-to-noise ratio that we determine exactly; $(ii)$~We prove that --unlike in the unconstrained case-- estimation error depends on the spike vector, and characterize the least favorable vectors; $(iii)$~We show that a non-negative principal component can be approximately computed --under the spiked model-- in nearly linear time. This despite the fact that the problem is non-convex and, in general, NP-hard to solve exactly.
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.

Randomized Comments: Code for GWAS and CS study, a new blog, Geometric theory of information


... There will be a "before" and "after" this paper ..., I mentioned that my review could be found starting at page 4 of this author's comment. If you read this response from the author, you'll note the location of the GitHub repository for the solver used in the paper. It is made available by the authors thanks to the request made in the review and it is here:


check the section  'compressed sensing; scripts for "Applying compressed sensing to genome-wide association studies"'



Pierre Vandergheynst has a blog and his first entry is on his upcoming course on Harmonic analysis on graphs and networks.



The foundation of all these geometries is given by hessian geometry of Jean-Louis Koszul. The important concept is the Koszul-Vinberg Characteristic function. By selecting the inner product deduced from Cartan-Killing form, we recover the good geometry of covariance matrix.
This idea has been extended by Jean-Marie Souriau in statistical physics, where the metric is introduced through symplectic cocycle, proving that the metric is invariant by dynamic groups in physics.
Entropy could be introduced by Legendre transform of minus the logarithm of Koszul-Vinberg characteristc function.
I have recently developed these Koszul and Souriau works in a long paper published in Springer book "geometric theory of information" edited by Frank Nielsen (also on Google Books)

This paper also deals with quantum Fisher metric introduced by Roger Balian in 1986. Another paper Will be published soon in MDPI journal "Entropy" with title "Koszul Information Geometry and Geometric Temperature/Capacity of Souriau Lie Group Thermodynamics".
For MaxEnt'14, a special issue will be published in MDPI Journal "entropy": Entropy, Information and their Geometric Structures
Frédéric Barbaresco
Thanks Frédéric

[1] and [2] have same idea. [1] using a fixed threshold, while [2] using a weight process. In [2], there are some difference between implementation and presentation. I don't like this :)).

Then Zaidao Wen mentioned

Maybe a smoothed idea of logdet or related has been involved in "Generalized Nonconvex Nonsmooth Lowrank Minimization" CVPR2014




Image Credit: NASA/JPL-Caltech
This image was taken by Navcam: Left B (NAV_LEFT_B) onboard NASA's Mars rover Curiosity on Sol 664 (2014-06-19 09:28:28 UTC).
Full Resolution

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, June 18, 2014

The SwAMP Thing! Sparse Estimation with the Swept Approximated Message-Passing Algorithm -implementation -




Florent just let me know of the following paper and attendant implementation:


Dear Igor

As you know, the AMP/GAMP approach is a very good one for sparse estimation but often suffer fro convergence problems.

With Lenka, Eric and Andre, we have been working on a modified update scheme for AMP/GAMP where we update the estimates "sequentially" rather than "in parallel". The resulting algorithm, though different from AMP just in few re-ordering details, has very good convergence performances. In fact, it seems to converge for all the cases we have tried.


More information can be found on our arxiv preprint here: http://arxiv.org/abs/1406.4311 and our Matlab implementation is on github: https://github.com/eric-tramel/SwAMP-Demo

Comment welcome

Regards

Florent
-----------------------------------------------
Florent KRZAKALA http://krzakala.org 
Laboratoire de Physique Statistique
Ecole Normale Supérieure, Paris


Approximate Message Passing (AMP) has been shown to be a superior method for inference problems, such as the recovery of signals from sets of noisy, lower-dimensionality measurements, both in terms of reconstruction accuracy and in computational efficiency. However, AMP suffers from serious convergence issues in contexts that do not exactly match its assumptions. We propose a new approach to stabilizing AMP in these contexts by applying AMP updates to individual coefficients rather than in parallel. Our results show that this change to the AMP iteration can provide theoretically expected, but hitherto unobtainable, performance for problems on which the standard AMP iteration diverges. Additionally, we find that the computational costs of this swept coefficient update scheme is not unduly burdensome, allowing it to be applied efficiently to signals of large dimensionality.

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, June 17, 2014

... There will be a "before" and "after" this paper ...



A while back, I was asked to perform some peer review on a paper. I usually shy away from this task as I believe the blog is sufficient enough to show my goodwill to the community at large. This being said, the peer review had a little twist. First it was on a paper I deemed important and second the peer review, while being a pre-publication review, offered the ability to make my views/comments public if and when the paper would be published. Here iare the final words of my review:

...This paper makes a connection between a central problem in large datasets found in GWAS with deep high dimensional geometry combinatorics and establishes how some of these very high dimensional problems ought to be considered in the future. There will be a "before" and "after" this paper.

Here is the paper: Applying compressed sensing to genome-wide association studies by Shashaank Vattikuti, James J Lee, Christopher C Chang, Stephen D H Hsu and Carson C Chow

Background
The aim of a genome-wide association study (GWAS) is to isolate DNA markers for variants affecting phenotypes of interest. This is constrained by the fact that the number of markers often far exceeds the number of samples. Compressed sensing (CS) is a body of theory regarding signal recovery when the number of predictor variables (i.e., genotyped markers) exceeds the sample size. Its applicability to GWAS has not been investigated.

Results

Using CS theory, we show that all markers with nonzero coefficients can be identified (selected) using an efficient algorithm, provided that they are sufficiently few in number (sparse) relative to sample size. For heritability equal to one (h2 = 1), there is a sharp phase transition from poor performance to complete selection as the sample size is increased. For heritability below one, complete selection still occurs, but the transition is smoothed. We find for h2 ~ 0.5 that a sample size of approximately thirty times the number of markers with nonzero coefficients is sufficient for full selection. This boundary is only weakly dependent on the number of genotyped markers.

Conclusion

Practical measures of signal recovery are robust to linkage disequilibrium between a true causal variant and markers residing in the same genomic region. Given a limited sample size, it is possible to discover a phase transition by increasing the penalization; in this case a subset of the support may be recovered. Applying this approach to the GWAS analysis of height, we show that 70-100% of the selected markers are strongly correlated with height-associated markers identified by the GIANT Consortium.


You can find my review and that of two other researchers in Pre-publication history section of the Journal (GigaScience), the comments to my review can be found starting at page 4 of this author's comment
Reviewer's Report Can YANG 24 Jan 2014
Reviewer's Report Igor Carron 21 Feb 2014
Reviewer's Report Or Zuk 12 Mar 2014
Resubmission - Version 2 Author's comment 18 Apr 2014
Reviewer's Report Can YANG 23 Apr 2014
Resubmission - Version 3 Author's comment 29 Apr 2014
Resubmission - Version 4 19 May 2014
Editorial acceptance 23 May 2014
Published 16 Jun 2014
Then again, this can become a post publication peer review, if you feel like adding to this comment section.



Sunday, June 15, 2014

Europe Wide Machine Learning Meetup and Paris Machine Learning #12: Season 1 Finale, Andrew Ng and More...

Franck and I were initially discussing what a season finale for the Paris Machine Learning Meetup would look like. After some back and forth discussion, an idea emerged: Since the remote presentations have been a great add-on for the whole season, what about asking a big name in ML to join us and share some insights. But that was too easy: what about sharing that exchange with three other European meetups since most of us are in the same time zone ? Deal.

We then contacted Martin Jaggi in Zurich, then Daniel Nouri and Andreas Muller in Berlin and finally Jurgen Van Gael, Jacqueline Forien and Martin Goodson in London who all said yes. Ok this is good, what about the big name ? We did not go far on our common list, in fact we stayed on the first name: Andrew Ng. Quite a few of our meetup participants have taken courses at Coursera, so Andrew was a natural choice. The Email was sent and Andrew Ng was kind enough to answer positively in less than a week. Bingo !

Since then, Andrew has gotten a position as Chief Scientist at Baidu, coincidence?! I think not :-)

So today or tomorrow (whenever you read this blog entry) i.e. Monday June 16th, there will be four Machine Learning Meetups across Europe and they will all share a session with Andrew. The streaming will be here:


The YouTube Link is here. The streaming is for the Paris meetup, which means that it starts at 7:00PM Paris time with Andrew coming up at 7:30PM Paris time.

We aim for a twitter hashtag to be: #MLEurope and #MLParis

it looks smooth and all but as I am writing this there are still many ways Murphy's law could strike. Fingers crossed.

Each of the meetups have their own programs aside from Andrew's presentation. Here they are:

PARIS


Naturally, all the presentations are available on the Paris Meetup archive page.

18h30+ Ouverture des portes. Badging, Pizzas, Champagne,....

19h00+ Introduction: Franck Bardol, Igor Carron

19h05+ Bastien Legras, Google Cloud Platform Solution Engineer and Francois Sterin, Principal, Global Infrastructure
How Google Uses Machine Learning And Neural Networks To Optimize Data Centers, and how you can benefit from it with Google Cloud Platform"

19h30+ Andrew Ng (Coursera, Baidu Chief Scientist), Deep Learning: Machine learning and AI via large-scale neural networks 

20h10+ Muthu Muthukrishnan, On Sketching

20h30+ Yaroslav Bulatov (Google SF), CNN and Google Streetview.

20h45+ Camille Couprie (IFPEN), Semantic scene labeling using feature learning (Joint work with Clément Farabet, Laurent Najman and Yann LeCun)
In this talk, we address the problem of assigning an semantic category to every pixel of an image, or video. We introduce a model architecture that allows us to learn hierarchies of multi-scale features while being computationally efficient. We present results on different datasets, including one that contains depth information, which may be handled in our trainable model very easily. As the output predictions may be noisy in videos, we propose a temporal smoothing method using minimum spanning trees, providing an efficient solution for embedded, real-time applications.
21h00+ Sam Bessalah, Abstract algebra for stream learning.
A quick introduction into some common algorithms and data structures to handle data in streaming fashion, like bloom filters, hyperloglog or min hashes. Then in a second part how abstract algebra with monoids, groups or semi groups help us reason and build scalable analytical systems beyond stream processing. 
ZURICH


All the slides are already here.

Program: 

Andrew Ng, co-founder of Coursera, director of the Stanford AI Lab, soon Chief Scientist at Baidu (via video, starting at 19:30)

• Apache Giraph for Applications in Machine Learning & Recommendation Systems, Maria Stylianou, HPC Software Engineer at Novartis (start 19:00)

Abstract: Over the last years, companies have turned to big data analytics to better understand their customers and drive their services according to customers' needs. In many cases, data is represented in graphs, for instance, describing user connections in a social network or user-item ratings in an online retailer. So far, Hadoop has been the swiss army knife of analytics, but has proven to be inefficient for graph mining and machine learning algorithms. This gave rise to a new generation of processing systems designed for this type of analytics. Apache Giraph is a representative of such systems. In this presentation, we showcase Giraph, its model and characteristics. We then demonstrate its suitability with machine learning algorithms and finally walk through an example algorithm for recommendation systems built on top of Giraph. 
• Smarter than Smart Sharpen - Advances in Image Deconvolution in Digital and Computational Photography, Michael Hirsch, Postdoc at University College London and the Max Planck Institute in Tübingen (start around 20:30) 

Abstract: Image Deconvolution is a key area in signal and image processing, that is receiving an ever increasing interest from the academic as well the industrial world due to both its theoretical and practical implications. It involves many challenging problems, including modeling the image formation process, formulating tractable priorsincorporating generic image statistics, and devising efficient methods for optimization. This renders image deconvolution an intriguing but also intricate task, which has recently seen much attention as well as progress in both the image and signal processing but also the computer vision and graphics community.
In this talk I will present some recent advances, that not only help sharpen blurry photos but might also change the design of future cameras.

We'll also keep you updated about the outcome of the Germany-Portugal soccer game of course!

BERLIN


1. Deep Learning: Machine learning and AI via large-scale neural networks (Andrew Ng, 40min) 

The co-founder of Coursera, director of the Stanford AI Lab and general Machine Learning legend is going to join us (as well as three other European ML meetups) via video.
2. Deep Neural Nets Study Group (Marcel Ackermann, 10min)

Marcel is going to present the new Deep Learning study group here in Berlin.

3. Kaggle contests (Abhishek Thakur, 5min) 

4. Structured Prediction and PyStruct (Andreas Mueller, 45min) 

Structured Prediction is a generalization of classification and regression to structured output spaces like sequences or trees. Unlike standard classification algorithms, structured prediction methods can exploit correlation in output variables.
The general form of a structured predictor f is f(x) = argmax_y g(x, y) where g is a compatibility function between an output structure y and the input x. Most methods for learning structured prediction are closely related to graphical models, which also have the constraint of g(x, y) being a probability distribution over y (in the conditional case).
The talk will give an introduction into structured prediction methods and the library PyStruct that implements many common learning algorithms in python. 
LONDON


A special edition of London Machine Learning Meetup where we join forces with our London, Paris, Berlin and Zurich colleagues to hear from Andrew Ng, known to many of us for his Coursera introductory Machine Learning course, and recently announced as Baidu's chief scientist. 

Andrew Ng will present Deep Learning: Machine Learning and AI via large-scale neural networks during 40 minutes.

We are delighted to be able to announce that Andrew's webcast will be followed with a special panel of UK-based academics who will each present for 15 minutes and allow plenty of time for Q&A. 

Our panelists:

David Barber, Author of 'Bayesian Reasoning and Machine Learning', Reader in Computational Statistics and Machine Learning at University College London.

Deep and Shallow
David will discuss aspects related to deep and shallow learning. He will show data compression results that outperform standard deep learning methods and at a fraction of the computational cost.

David Duvenaud, Final year Ph.D. candidate at Cambridge University

Visualizing Priors on Deep Functions 
David will discuss properties of deep, infinitely-wide neural nets giving rise to deep Gaussian processes and deep kernels. David will visually explore these relatively simple models, and show what happens when one performs dropout in Gaussian processes.

Printfriendly