Tuesday, February 18, 2014

Nonlinear estimation of material abundances in hyperspectral images with L1-norm spatial regularization - implementation -

From this tutorial

Sometimes, the abundance in hyperpectral images is really a nonlinear function of different elemental abundances. Hence there is the need for the nonlinear dictionaries mentioned yesterday. Now we just need to have sensors that help in that deconvolution.



Integrating spatial information into hyperspectral unmixing procedures has been shown to have a positive effect on the estimation of fractional abundances due to the inherent spatial–spectral duality in hyperspectral scenes. However, current research works that take spatial information into account are mainly focused on the linear mixing model. In this paper, we investigate how to incorporate spatial correlation into a nonlinear abundance estimation process. A nonlinear unmixing algorithm operating in reproducing kernel Hilbert spaces, coupled with a 1-type spatial regularization, is derived. Experiment results, with both synthetic and real hyperspectral images, illustrate the effectiveness of the proposed scheme.

Matlab implementation is Cedric's 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.

Monday, February 17, 2014

Kernel LMS algorithm with forward-backward splitting for dictionary learning - implementation -

If you recall the Random Kitchen Sinks, you'll remember that one chooses randomly some of the coefficient and then evaluate the remaining coefficient with a least square approach. Those functionals using random numbers are part of what is called a (nonlinear) dictionary. Here is the state of the art with regards to approximating time series with the RHKSs with nonrandom "frequencies". Maybe one should look into random dictionaries:   

Nonlinear adaptive filtering with kernels has become a topic of high interest over the last decade. A characteristics of kernel-based techNonlinear adaptive filtering with kernels has become a topic of high interest over the last decade. A characteristics of kernel-based techter parameter update stage. It is surprising to note that most existing strategies for dictionary update can only incorporate new elements into the dictionary. This unfortunately means that they cannot discard obsolete kernel functions, within the context of a time-varying environment in particular. Recently, to remedy this drawback, it has been proposed to associate an ℓ1norm regularization criterion with the mean-square error criterion. The aim of this paper is to provide theoretical results on the convergence of this approach.


Matlab implementation is Cedric's page


Saturday, February 15, 2014

Sunday Morning Insight: Phase transitions and sample complexity in Bayes-optimal matrix factorization

We mentioned it before. Some of the advanced matrix factorizations now on the market have the particularity of having sharp phase transitions. This is a reflection that each of these problems are NP-Hard and that a relaxation on the assumptions of the unknowns can yield polynomial complexity algorithms as was the case of compressive sensing with the Donoho-Tanner phase transitions and attendant developments. The authors of the following paper try to devise a similar limit to what is achievable for generic matrix factorizations using Bayes optimal inference. Lenka Zdeborova's presentation at the latest Paris Machine Learning meetup on how to find a needle in a haystack? was in particular focused on clustering, a particular matrix factorization







We analyse the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis or factor analysis. We use the tools of statistical mechanics - the cavity and replica methods - to analyze the achievability and tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable in principle in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error, and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm.

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, February 14, 2014

Thursday, February 13, 2014

Signal to Noise Ratio in Lensless Compressive Imaging / Compressive and Adaptive Millimeter-wave SAR / Efficient Low Dose X-ray CT Reconstruction

It's been a while, at long last, some CS hardware and hardware/algorithm related papers :


Signal to Noise Ratio in Lensless Compressive Imaging by Hong Jiang, Gang Huang, Paul Wilford
We analyze the signal to noise ratio (SNR) in a lensless compressive imaging (LCI) architecture. The architecture consists of a sensor of a single detecting element and an aperture assembly of an array of programmable elements. LCI can be used in conjunction with compressive sensing to capture images in a compressed form of compressive measurements. In this paper, we perform SNR analysis of the LCI and compare it with imaging with a pinhole or a lens. We will show that the SNR in the LCI is independent of the image resolution, while the SNR in either pinhole aperture imaging or lens aperture imaging decreases as the image resolution increases. Consequently, the SNR in the LCI is much higher if the image resolution is large enough.



We apply adaptive sensing techniques to the problem of locating sparse metallic scatterers using high-resolution, frequency modulated continuous wave W-band RADAR. Using a single detector, a frequency stepped source, and a lateral translation stage, inverse synthetic aperture RADAR reconstruction techniques are used to search for one or two wire scatterers within a specified range, while an adaptive algorithm determined successive sampling locations. The two-dimensional location of each scatterer is thereby identified with sub-wavelength accuracy in as few as 1/4 the number of lateral steps required for a simple raster scan. The implications of applying this approach to more complex scattering geometries are explored in light of the various assumptions made.





Efficient Low Dose X-ray CT Reconstruction through Sparsity-Based MAP Modeling by SayedMasoud Hashemi, Soosan Beheshti, Patrick R. Gill, Narinder S. Paul, Richard S.C. Cobbold

Ultra low radiation dose in X-ray Computed Tomography (CT) is an important clinical objective in order to minimize the risk of carcinogenesis. Compressed Sensing (CS) enables significant reductions in radiation dose to be achieved by producing diagnostic images from a limited number of CT projections. However, the excessive computation time that conventional CS-based CT reconstruction typically requires has limited clinical implementation. In this paper, we first demonstrate that a thorough analysis of CT reconstruction through a Maximum a Posteriori objective function results in a weighted compressive sensing problem. This analysis enables us to formulate a low dose fan beam and helical cone beam CT reconstruction. Subsequently, we provide an efficient solution to the formulated CS problem based on a Fast Composite Splitting Algorithm-Latent Expected Maximization (FCSA-LEM) algorithm. In the proposed method we use pseudo polar Fourier transform as the measurement matrix in order to decrease the computational complexity; and rebinning of the projections to parallel rays in order to extend its application to fan beam and helical cone beam scans. The weight involved in the proposed weighted CS model, denoted by Error Adaptation Weight (EAW), is calculated based on the statistical characteristics of CT reconstruction and is a function of Poisson measurement noise and rebinning interpolation error. Simulation results show that low computational complexity of the proposed method made the fast recovery of the CT images possible and using EAW reduces the reconstruction error by one order of magnitude. Recovery of a high quality 512× 512 image was achieved in less than 20 sec on a desktop computer without numerical optimizations.


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, February 12, 2014

Ce soir/Tonight: Paris Machine Learning Meetup #8: Finding a needle in a Haystack, Beyond SGD, Analyzing Wikipedia, Kolibree, Winning Kaggle "Dogs vs Cats"


Using Advanced Matrix Factorization to perform not so trivial signal/image/video processing tasks ( for more see the videos at  It's CAI, Cable And Igor's Adventures in Matrix Factorization )


The streaming of tonight's meetup on Google Hangout is here and it should start at around 7h30pm Paris Time. The talks will be in French this time with slides (see below in English).

The meetup itiself should start at around 6:45pm.

The idea for this series of meetup is to bring together curious people, researchers, professionals in the same room. The attendant meetup group now has more than 570 members. Let us note that there is now a Berlin ML meetup group and a Machine Learning group in Zurich led by Martin Jaggi whom we have mentioned here before.

In particular, our focus is not on the actual technology (mostly web tech) but on the underlying algorithms that are becoming central to a large section of the economy. What is fascinating are really two aspects of this phenomena. On the one hand, we are producing more data than there are stars in the universe (and this is increasing at a higher rate with the Internet of Things), on the other hand, the field of machine learning is really maturing as a consequence of this new influx of data. Tonight,  Lenka Zdeborova will talk to us about some of the deep limits associated with some of the problems found in Machine Learning such as clustering and other advanced Matrix Factorizations. She and her collaborators are making significant contributions to our knowledge on what computations are feasible and those that are not feasible. In a different direction Francis Bach will show us some of the latest development on getting algorithms to perform online gradient descent, the central battery of many ML algorithms. Central to this theme is the issue of having access to the data only a few times because they are so large. In future meetups, we will have people talking to us about streaming/sketching and related issues. Pierre Sermanet will show us the strategy he used to win First Prize on the Kaggle contest on Dogs vs Cats. Here again, the deep neural networks used did not exist in this form until very recently. The level of accuracy of some of these contests make some people say that some of these algorithms are getting better than Humans. We are still at an early stage here because these deep networks require much tuning, but quite clearly, the trend is becoming clear for certain tasks. At the very least, there is this nagging question on how some of the Matrix Factorization techniques can help better understand how to tune these deep network algorithmsLoïc Cessot will talk to us about Kolibree , the world's first connected toothbrush as he is looking for Machine Learners in order to enrich the data produced by this hardware. Guillaume Pitel, will talk about how he explores Wikipedia with a specific Matrix Factorization technique of his own. 

The program and attendant speaker's slides:
Other references:

Tuesday, February 11, 2014

Is Bad Learning Learning ?

Yesterday, I mentioned the following use of an Advanced Matrix Factorization for evaluating what humans do and don't understand in learning from this preprint Sparse Factor Analysis for Learning and Content Analytics written by the good folks at Rice ( Andrew S. Lan,Andrew E. Waters , Christoph Studer, Richard G. Baraniuk ). A commenter, njh, noted the following:


An interesting paper with an interesting pair of algorithms, but I question the validity of this assumption:
"Our third observation is that the entries of W should be non-negative, since we postulate that having strong concept knowledge should never hurt a learner’s chances to answer questions correctly."
I've noticed that many people learn an incorrect model which harms their learning of other related concepts. Dijkstra once wrote "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration". This might be a little harsh, but I've seen the same effect with students, and with my own learning. To test this, it might be interesting to see whether relaxing the non-negative constraint leads to more sparse solutions.
(Or have I misunderstood something, making my understanding of this paper harder?)

and sometimes, sparse constraints yield non-negative outputs. But this is a valid question. To me the fascinating aspect of all this is that since these new crop of solvers are generally relaxations of NP-Hard problems, their attendant phase transitions might be delimiting our knowledge. More on that paper, this coming Sunday.

Related: 

Model-based Sketching and Recovery with Expanders / For-all Sparse Recovery in Near-Optimal Time

Expanders have been the basis for sparse measurement matrices ever since these experiments and attendant papers. It is a pretty fascinating subject as people are trying to push the limits further to see if there is a way to decrease further down the number of measurements. Today we have two papers on the subject. From the first paper:  

The recent work of [28] is the first to address model-based CS with sparse measurement matrices and in the for all case. They show that model-expanders exist when the structures (models) considered are binary trees and non-overlapping block structures and they provided bounds for the sketch sizes. They also propose a recovery algorithm that has exponential time complexity with respect to the dimension of the signal.
So the following paper seems to have found a better and simple algorithm to do this faster (with a surprising result see figure)




Model-based Sketching and Recovery with Expanders by Bubacarr Bah, Luca Baldassarre, Volkan Cevher

Linear sketching and recovery of sparse vectors with randomly constructed sparse matrices has numerous applications in several areas, including compressive sensing, data stream computing, graph sketching, and combinatorial group testing. This paper considers the same problem with the added twist that the sparse coefficients of the unknown vector exhibit further correlations as determined by a known sparsity model. We prove that exploiting model-based sparsity in recovery provably reduces the sketch size without sacrificing recovery quality. In this context, we present the model-expander iterative hard thresholding algorithm for recovering model sparse signals from linear sketches obtained via sparse adjacency matrices of expander graphs with rigorous performance guarantees. The main computational cost of our algorithm depends on the difficulty of projecting onto the model-sparse set. For the tree and group-based sparsity models we describe in this paper, such projections can be obtained in linear time. Finally, we provide numerical experiments to illustrate the theoretical results in action.

Related:



and the second paper: For-all Sparse Recovery in Near-Optimal Time by Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

An approximate sparse recovery system in ℓ1 norm consists of parameters k, ϵ, N, an m-by-Nmeasurement Φ, and a recovery algorithm, R. Given a vector, x, the system approximates x by xˆ=R(Φx), which must satisfy ∥xˆ−x∥1≤(1+ϵ)∥x−xk∥1. We consider the 'for all' model, in which a single matrix Φ, possibly 'constructed' non-explicitly using the probabilistic method, is used for all signals x. The best existing sublinear algorithm by Porat and Strauss (SODA'12) uses O(ϵ−3klog(N/k))measurements and runs in time O(k1−αNα) for any constant α>0.
In this paper, we improve the number of measurements to O(ϵ−2klog(N/k)), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O(k1+βpoly(logN,1/ϵ)), with a modest restriction that ϵ lt (logk/logN)γ, for any constants β,γ gt 0. When k lt logcN for some c gt 0, the runtime is reduced to O(kpoly(N,1/ϵ)). With no restrictions on ϵ, we have an approximation recovery system with m=O(k/ϵlog(N/k)((logN/logk)γ+1/ϵ)) measurements.




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, February 10, 2014

Sparse Factor Analysis for Learning and Content Analytics

A while back, we wondered If Education [was] a low Rank problem or probably how to use the fact Aha moments are sparse. How about using the fact that most key concepts are really sparse ? Looks like a probabilistic matrix factorization problem:
Armed with this model and given incomplete observations of the graded learner–question responses Yi;j, our goal is to estimate the factors W, C, and M. Such a factor-analysis problem is ill-posed in general, especially when each learner answers only a small subset of the collection of questions (see Harman (1976) for a factor analysis overview). Our first key observation that enables a well-posed solution is the fact that typical educational domains of interest involve only a small number of key concepts (i.e., we have K N; Q in Figure 1).


Sparse Factor Analysis for Learning and Content Analytics by Andrew S. Lan, Andrew E. Waters , Christoph Studer, Richard G. Baraniuk
We develop a new model and algorithms for machine learning-based learning analytics, which estimate a learner’s knowledge of the concepts underlying a domain, and content analytics, which estimate the relationships among a collection of questions and those concepts. Our model represents the probability that a learner provides the correct response to a question in terms of three factors: their understanding of a set of underlying concepts, the concepts involved in each question, and each question’s intrinsic difficulty. We estimate these factors given the graded responses to a collection of questions. The underlying estimation problem is ill-posed in general, especially when only a subset of the questions are answered. The key observation that enables a well-posed solution is the fact that typical educational domains of interest involve only a small number of key concepts. Leveraging this observation, we develop both a bi-convex maximum-likelihood-based solution and a Bayesian solution to the resulting SPARse Factor Analysis (SPARFA) problem. We also incorporate user-defined tags on questions to facilitate the interpretability of the estimated factors. Experiments with synthetic and real-world data demonstrate the efficacy of our approach. Finally, we make a connection between SPARFA and noisy, binary-valued (1-bit) dictionary learning that is of independent interest.



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.

Paris Machine Learning Meetup #8: Finding a needle in a Haystack, Beyond SGD, Analyser Wikipedia, Kolibree, Winning Kaggle "Dogs vs Cats"




On Wednesday evening, we will have five speakers for the 8th Paris Machine Learning MeetupLenka Zdeborova, Francis Bach, Guillaume Pitel, Pierre Sermanet et Loïc Cessot. The meetup will be hosted by DojoCrea/DojoEvents. You can register here. Please change your RSVP if you are not coming, it helps us in the long run. 

Lenka will talk to us about interesting results coming up in clustering and other problems, Francis will review some latest developments in convex optimization for robust and efficient large-scale supervised machine learning problems. Guillaume will show his project on how he makes sense of Wikipedia. Loïc will present a Wi-Fi connected toothbrush that requires some learning and finally, direct live from New York, we'll have Pierre who will talk to us about winning the lastest Kaggle competition on recognizing Dogs vs cats. Currently, we expect most of these presentations to be in French but the slides will be in English and will be available from the archives. The meetup will be streamed live on Google+ Hangout starting at 7:30 PM Paris time.

For any job announcement, please use directly the attendant Paris Machine Learning LinkedIn group.

Here are the summaries: 

Lenka Zdeborova, IPT, CEA,

Titre: How hard is it to find a needle in the haystack?
Everybody noticed that some problems in life are easy, some are hard and some are impossible. In machine learning this fact can be nicely formalized on simple examples. One example of interest in many application is clustering of data. Let us take a set of people, we split the people into several groups and consider that a given person is a friend with another person from the same group with probability p_in, and with a person from another group with probability p_out. Then we give the list of who is friend with who to a clever student and ask him to infer how were the people placed into the groups in the first place. Depending on the number of groups and the parameters p_in and p_out it can be analyzed whether the task we gave to the student is impossible, easy or possible but hard. We will describe these (sometimes counter-intuitive) results and their implications for the more generic task of clustering data. If time permits or in the discussion we will talk about other problems of interest in machine learning and signal processing where such situations were analyzed.

Francis Bach, INRIA

Titre: Beyond stochastic gradient descent for large-scale machine learning.
In this talk, I review some latest development sin convex optimization for robust and efficient large-scale supervised machine learning problems.

Guillaume Pitel, eXenSa
Titre: Analyser Wikipedia en long, en large, et en travers avec NCISC
Je présente l'utilisation d'un algorithme de ma création (NCISC) pour l'analyse de wikipedia selon différents critères : catégories, contenu textuel et liens entre pages. Je vais rapidement décrire le pipeline complet d'un tel projet, que nous avons totalement réécrit en Spark+Scala depuis octobre/novembre. Je donnerais quelques exemples de résultats obtenus avec notre approche sur des datasets standard, en le comparant par exemple aux méthodes orientées deep learning.

Loïc Cessot, Kolibree
Kolibree, the world's first connected toothbrush.
C'est un objet connecté présenté au CES 2014 de Las Vegas qui va incorporer des algorithmes d'apprentissage.
Pierre Sermanet , NYU, http://cs.nyu.edu/~sermanet/
Pierre vient de remporter le prix de Kaggle de reconnaissance Cats vs Dogs (http://www.kaggle.com/c/dogs-vs-cats/leaderboard). Il nous fera une presentation de comment il est arrive a cette premiere place en utilisant des algos de deep learning.

The organizers: Franck Bardol, Frederic Dembak, Igor Carron.

A savoir:

* Si vous ne pouvez pas venir, un grand merci d'avance pour changer votre RSVP.


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.

Printfriendly