Nuit Blanche: 05/01/2019

Friday, May 31, 2019

"Generative models are the new sparsity": The spiked matrix model with generative priors - implementation -

** Nuit Blanche is now on Twitter: @NuitBlog **

Out of all the good things coming out of this paper, here is what I note: The Great Convergence continues and we also find phase transitions. Also even though reconstruction is noisy, it is still perceptually ok because humans have been dealing with all sorts of imprecisions in their vision systems.

The spiked matrix model with generative priors by Benjamin Aubin, Bruno Loureiro, Antoine Maillard, Florent Krzakala, Lenka Zdeborová

Using a low-dimensional parametrization of signals is a generic and powerful way to enhance performance in signal processing and statistical inference. A very popular and widely explored type of dimensionality reduction is sparsity; another type is generative modelling of signal distributions. Generative models based on neural networks, such as GANs or variational auto-encoders, are particularly performant and are gaining on applicability. In this paper we study spiked matrix models, where a low-rank matrix is observed through a noisy channel. This problem with sparse structure of the spikes has attracted broad attention in the past literature. Here, we replace the sparsity assumption by generative modelling, and investigate the consequences on statistical and algorithmic properties. We analyze the Bayes-optimal performance under specific generative models for the spike. In contrast with the sparsity assumption, we do not observe regions of parameters where statistical performance is superior to the best known algorithmic performance. We show that in the analyzed cases the approximate message passing algorithm is able to reach optimal performance. We also design enhanced spectral algorithms and analyze their performance and thresholds using random matrix theory, showing their superiority to the classical principal component analysis. We complement our theoretical results by illustrating the performance of the spectral algorithms when the spikes come from real datasets.

An implementation of the results can be found here: https://github.com/sphinxteam/StructuredPrior_demo

h/t Lenka's tweet.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn or the Advanced Matrix Factorization group on LinkedIn

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.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup< br/> About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Thursday, May 30, 2019

Learning step sizes for unfolded sparse coding

** Nuit Blanche is now on Twitter: @NuitBlog **

The Great Convergence continues in the realm of Matrix Factorization ! Learning step sizes for unfolded sparse coding by Pierre Ablin, Thomas Moreau, Mathurin Massias, Alexandre Gramfort

Sparse coding is typically solved by iterative optimization techniques, such as the Iterative Shrinkage-Thresholding Algorithm (ISTA). Unfolding and learning weights of ISTA using neural networks is a practical way to accelerate estimation. In this paper, we study the selection of adapted step sizes for ISTA. We show that a simple step size strategy can improve the convergence rate of ISTA by leveraging the sparsity of the iterates. However, it is impractical in most large-scale applications. Therefore, we propose a network architecture where only the step sizes of ISTA are learned. We demonstrate that for a large class of unfolded algorithms, if the algorithm converges to the solution of the Lasso, its last layers correspond to ISTA with learned step sizes. Experiments show that our method is competitive with state-of-the-art networks when the solutions are sparse enough.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn or the Advanced Matrix Factorization group on LinkedIn

Wednesday, May 29, 2019

Sparse-Plex library and a fast OMP implementation

** Nuit Blanche is now on Twitter: @NuitBlog **

Shailesh (also Shailesh1729) sent me the following a few months ago:

Hi Igor,

I have been a regular reader of your blog Nuit Blanche.

I would like to draw your attention to a fast C OMP implementation with MATLAB interfaces written by me. Its documentation is available here. It is up to 4 times faster than the OMP implementation in OMPBOX. I hope you will find this information useful and worth sharing on your blog / twitter.

I have written fast C implementations of other algorithms whose documentation I am updating currently.

With regards,
- Shailesh

Thanks Shailesh ! Of obvious interest is his Sparse-Plex library to learn about Compressive Sensing. It is here.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn or the Advanced Matrix Factorization group on LinkedIn

Tuesday, May 28, 2019

Differentially Private Compressive k-Means

** Nuit Blanche is now on Twitter: @NuitBlog **

Differentially Private Compressive k-Means by Vincent Schellekens, Antoine Chatalic, Florimond Houssiau, Yves-Alexandre De Montjoye, Laurent Jacques, Rémi Gribonval

This work addresses the problem of learning from large collections of data with privacy guarantees. The sketched learning framework proposes to deal with the large scale of datasets by compressing them into a single vector of generalized random moments, from which the learning task is then performed. We modify the standard sketching mechanism to provide differential privacy, using addition of Laplace noise combined with a subsampling mechanism (each moment is computed from a subset of the dataset). The data can be divided between several sensors, each applying the privacy-preserving mechanism locally, yielding a differentially-private sketch of the whole dataset when reunited. We apply this framework to the k-means clustering problem, for which a measure of utility of the mechanism in terms of a signal-to-noise ratio is provided, and discuss the obtained privacy-utility tradeoff.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn or the Advanced Matrix Factorization group on LinkedIn

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.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Monday, May 27, 2019

Estimating the inverse trace using random forests on graphs

** Nuit Blanche is now on Twitter: @NuitBlog **

Using Machine learning techniques to perform machine learning computation, I really like the meta aspect of this paper. Estimating the inverse trace using random forests on graphs by Simon Barthelmé, Nicolas Tremblay, Alexandre Gaudillière, Luca Avena, Pierre-Olivier Amblard

Some data analysis problems require the computation of (regularised) inverse traces, i.e. quantities of the form $\Tr (q \bI + \bL)^{-1}$. For large matrices, direct methods are unfeasible and one must resort to approximations, for example using a conjugate gradient solver combined with Girard's trace estimator (also known as Hutchinson's trace estimator). Here we describe an unbiased estimator of the regularized inverse trace, based on Wilson's algorithm, an algorithm that was initially designed to draw uniform spanning trees in graphs. Our method is fast, easy to implement, and scales to very large matrices. Its main drawback is that it is limited to diagonally dominant matrices $\bL$.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn or the Advanced Matrix Factorization group on LinkedIn

Saturday, May 25, 2019

Saturday Morning Videos: Imaging and Machine Learning Workshop, @IHP Paris, April 1st – 5th , 2019

** Nuit Blanche is now on Twitter: @NuitBlog **

This is the third Workshop «Imaging and Machine Learning» within the Mathematics of Imaging series organized in Paris this semester (videos of Workshop 1 are here, videos of Workshop 2 are here)