Survey: Randomized methods for matrix computations and analysis of high dimensional data

Here is an interesting survey:

 

Randomized methods for matrix computations and analysis of high dimensional data by Per-Gunnar Martinsson

This report surveys a number of randomized techniques that have recently been proposed for computing matrix factorizations and for analyzing high dimensional data sets. It presents some modifications to algorithms that have previously been published that increase efficiency and broaden the range of applicability of the methods. The report also describes classical (non-randomized) techniques for solving the same problems such as, e.g., Krylov methods, subspace iteration, and rank-revealing QR factorizations. Differences and similarities between classical and new methods are discussed, and guidance is provided on when to use which set of techniques. One chapter discusses so called "structure preserving" factorizations such as the Interpolative Decomposition (ID) and the CUR decomposition. The factors in these decompositions preserve certain properties of the original matrix such as sparsity of non-negativity, which both improves computational efficiency and helps with data interpretation.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

The Replica-Symmetric Prediction for Compressed Sensing with Gaussian Matrices is Exact

Galen just sent me the following:

Hi Igor,

This week I presented some work at ISIT that might be of interest. In joint work with Henry Pfister, we have shown that the replica-symmetric prediction for compressed sensing with Gaussian matrices is exact. ( https://arxiv.org/abs/1607.02524 ) In fact, I gave a talk about the proof of this result in March (https://www.youtube.com/watch?v=vmd8-CMv04I ), which you were kind enough to feature on your website (Its my fault that the abstract did not reflect the content of the talk).

Moreover, some people might be interested relationship between this paper and the recent work by Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala titled, "The Mutual Information in Random Linear Estimation”. [Note: mentioned earlier on Nuit Blanche]  I would like to point that there proof techniques are very different and that there are some important difference in the assumptions that are required. Perhaps the most significant difference is that their approach requires discrete and bounded distributions that satisfy a certain “three-solution” property. By contrast, our result applies to any distribution that has bounded fourth moment and also satisfies a certain ``single-crossing’’ property, which is more general then the three-solution property. (See, e.g., Figure~1 in our paper for an example).

cheers,
Galen

Let me make a small comment here with regards to pre- and post- publication peer review. In this case of two groups arriving to a very similar results on an open conjecture, the question has become "who needs pre-publication peer review ?" Indeed, the Arxiv date stamps for the preprints and the date the video was posted on YouTube somehow prove that both groups have proven an interesting conjecture independently albeit with different assumptions. In previous times, I am absolutely sure that one of the two groups could have thought that an anonymous pre-publication reviewer was slowing down the review for other reasons than a scientific one.  In the end, the result is even stronger: since both proofs and assumptions are different, there is even a sense, to a non-specialist like myself, that the result will hold the test of time. Congratulations to both groups !
And thanks Galen for the heads-up. Here is the paper:

The Replica-Symmetric Prediction for Compressed Sensing with Gaussian Matrices is Exact by Galen Reeves, Henry D. Pfister

This paper considers the fundamental limit of compressed sensing for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Jobs: 2 Postdocs, LIONS lab @ EPFL,

Volkan just sent me the following:

Dear Igor,

I hope this email finds you well.
I have some postdoc position openings in machine learning & compressive sensing:

http://lions.epfl.ch/opportunities
Would it be possible to feature it at nuit-blanche?

thanks.

-------
Prof. Volkan Cevher
Laboratory for Information and Inference Systems
http://lions.epfl.ch

From the page:

Postdoc Positions

The Laboratory for Information and Inference Systems (LIONS) at EPFL is looking for postdoctoral fellows with a strong theory background in machine learning, discrete optimization, information theory, statistics, compressive sensing, or other related areas. Strong coding skills is a big plus.

There are two positions that revolve around the following two topics: 

1) Bayesian optimization, bandits, and reinforcement learning

We seek to develop online algorithms for Bayesian optimization, as well as related problems such as multi-armed bandits, level-set estimation, and reinforcement learning.  The algorithms will be characterized theoretically, and also tested in real-world applications including automated hyperparameter optimization with neural networks and personalized education.

2) Discrete optimization and submodularity with applications to subsampling

We seek to develop techniques for discrete optimization, with submodularity and related concepts playing a key role.  These techniques will be targeted at the application of using data in order to optimally subsample for the purpose of performing a given task, such as estimation in compressive sensing or classification in machine learning.  Specific applications will also be explored, including medical resonance imaging (MRI) with multiple coils.

 

LIONS provides a stimulating, collaborative and fun research environment with state-of-the-art facilities at EPFL. Personal initiative and independent research tasks related with the candidate’s interests are also encouraged.

The working language at EPFL is English.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Slides: Computational and statistical trade-offs in learning @IHES

 Laurent recently pointed me to the slides of a workshop that took place at IHES this past March. Here they are:

Figure from Remi Gribonval's talk.

• Ohad Shamir Trade-offs in Distributed Learning  
• Alain Celisse Using kernels to detect abrupt changes in time series
• Alexandre d'Aspremont Renegar's Condition Number and Compressed Sensing Performance
• Emilie Kaufmann Optimal Best Arm Identification with Fixed Confidence
• Vianney Perchet Highly-Smooth Zero-th Order Online Optimization 
• Garvesh Raskutti Algorithmic and statistical perspectives of randomized sketching for ordinary least-squares
• Pierre Alquier On the Properties of Variational Approximations of Gibbs Posteriors
• Quentin Berthet Trade-offs in Statistical Learning 
• Remi Gribonval Projections, Learning, and Sparsity for Efficient Data Processing 
• Silvia Villa Generalization properties of multiple passes stochastic gradient method

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula / The Mutual Information in Random Linear Estimation

Jean mentioned to me his recent two preprints, the second preprint featuing an example of interest to compressive sensing, CDMA, error correction via sparse superposition codes [6], or Boolean group testing  and more. From the first preprint:

"...From this point of view, the theorem proved in this paper is relevant in a broader context going beyond low-rank matrix estimation. Hundreds of papers have been published in statistics, machine learning or information theory using the non-rigorous statistical physics approach. We believe that our result helps setting a rigorous foundation of a broad line of work. While we focus on rank-one symmetric matrix estimation, our proof technique is readily extendable to more generic low-rank symmetric matrix or low-rank symmetric tensor estimation. We also believe that it can be extended to other problems of interest in machine learning and signal processing, such as generalized linear regression, features/dictionary learning, compressed sensing or multi-layer neural networks...."

Here are the two preprints: Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula by Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborova

Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models in the Bayes optimal setting, a general expression for the mutual information has been proposed using heuristic statistical physics computations, and proven in few specific cases. Here, we show how to rigorously prove the conjectured formula for the symmetric rank-one case. This allows to express the minimal mean-square-error and to characterize the detectability phase transitions in a large set of estimation problems ranging from community detection to sparse PCA. We also show that for a large set of parameters, an iterative algorithm called approximate message-passing is Bayes optimal. There exists, however, a gap between what currently known polynomial algorithms can do and what is expected information theoretically. Additionally, the proof technique has an interest of its own and exploits three essential ingredients: the interpolation method introduced in statistical physics by Guerra, the analysis of the approximate message-passing algorithm and the theory of spatial coupling and threshold saturation in coding. Our approach is generic and applicable to other open problems in statistical estimation where heuristic statistical physics predictions are available.

The Mutual Information in Random Linear Estimation by Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala

We consider the estimation of a signal from the knowledge of its noisy linear random Gaussian projections, a problem relevant in compressed sensing, sparse superposition codes or code division multiple access just to cite few. There has been a number of works considering the mutual information for this problem using the heuristic replica method from statistical physics. Here we put these considerations on a firm rigorous basis. First, we show, using a Guerra-type interpolation, that the replica formula yields an upper bound to the exact mutual information. Secondly, for many relevant practical cases, we present a converse lower bound via a method that uses spatial coupling, state evolution analysis and the I-MMSE theorem. This yields, in particular, a single letter formula for the mutual information and the minimal-mean-square error for random Gaussian linear estimation of all discrete bounded signals.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Gene expression prediction using low-rank matrix completion

Laurent pointed me to this interesting use of low-rank matrix completion. Interestingly enough, it would seem to me the following graph is an instance of a phase transition. I'd love to hear the meaning of it, i.e. what it says about the structure of the problem at hand:

 

 
 

 

Gene expression prediction using low-rank matrix completion by Arnav Kapur, Kshitij Marwah and Gil Alterovitz

Background

An exponential growth of high-throughput biological information and data has occurred in the past decade, supported by technologies, such as microarrays and RNA-Seq. Most data generated using such methods are used to encode large amounts of rich information, and determine diagnostic and prognostic biomarkers. Although data storage costs have reduced, process of capturing data using aforementioned technologies is still expensive. Moreover, the time required for the assay, from sample preparation to raw value measurement is excessive (in the order of days). There is an opportunity to reduce both the cost and time for generating such expression datasets.

Results

We propose a framework in which complete gene expression values can be reliably predicted in-silico from partial measurements. This is achieved by modelling expression data as a low-rank matrix and then applying recently discovered techniques of matrix completion by using nonlinear convex optimisation. We evaluated prediction of gene expression data based on 133 studies, sourced from a combined total of 10,921 samples. It is shown that such datasets can be constructed with a low relative error even at high missing value rates ( superior to 50 %), and that such predicted datasets can be reliably used as surrogates for further analysis.

Conclusion

This method has potentially far-reaching applications including how bio-medical data is sourced and generated, and transcriptomic prediction by optimisation. We show that gene expression data can be computationally constructed, thereby potentially reducing the costs of gene expression profiling. In conclusion, this method shows great promise of opening new avenues in research on low-rank matrix completion in biological sciences.

 
 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Nuit Blanche in Review (June 2016)

Since the last Nuit Blanche in Review (May 2016), Juno inserted into Jupiter's orbit, We started LightOn,  Nuit Blanche reached five million page views. We also had our last Paris Machine Learning meetup of season 3 and heard about how Machine Learning had begun operations on Mars and much much more. In fact, it's all listed here. Enjoy !

Implementations

• DropNeuron: Simplifying the Structure of Deep Neural Networks - implementation -
• FMR: Fast randomized algorithms for covariance matrix computations - implementation -
• Highly Technical Reference Page: Laplacian Linear Equations, Graph Sparsification, Local Clustering, Low-Stretch Trees, etc. + implementation
• RedEye: Analog ConvNet Image Sensor Architecture for Continuous Mobile Vision - implementation -
• Discovering Causal Signals in Images - implementation -
• RSVDPACK: Subroutines for computing partial singular value, interpolative, and CUR decompositions via randomized sampling on multi core and GPU architectures - implementation -
• A Deep Learning Approach to Block-based Compressed Sensing of Images - implementation -
• A Riemannian gossip approach to decentralized matrix completion - implementation -

Theses

• Thesis: Statistical physics of linear and bilinear inference problems by Christophe Schülke
• Thesis: Rich and Efficient Visual Data Representation, Mohammad Rastegari
• Thesis: Recovering structured signals in high dimensions via non-smooth convex optimization: Precise performance analysis by Christos Thrampoulidis
• Thesis: Learning with Scalability and Compactness by Wenlin Chen
• Thesis: From dependence to causation by David Lopez-Paz
• Thesis: Cosparse regularization of physics-driven inverse problems, Srđan Kitić

Around the blogs

• Around The Blogs in 78 Summer hours

Surveys/Reviews

• Literature survey on low rank approximation of matrices
• Optimization Methods for Large-Scale Machine Learning
• Kernel Mean Embedding of Distributions: A Review and Beyonds
• A brief Review of the ChaLearn AutoML Challenge: Any-time Any-dataset Learning without Human Intervention

In-depth

• Group Sparse Regularization for Deep Neural Networks
• The "Horse'' Inside: Seeking Causes Behind the Behaviours of Music Content Analysis Systems
• Learning to learn by gradient descent by gradient descent
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• A Powerful Generative Model Using Random Weights for the Deep Image Representation
• Large-Scale Kernel Methods for Independence Testing
• Sketching for Large-Scale Learning of Mixture Models
• Learning Infinite-Layer Networks: Beyond the Kernel Trick
• Recycling Randomness with Structure for Sublinear time Kernel Expansions
• Image Restoration and Reconstruction using Variable Splitting and Class-adapted Image Priors / Image Restoration with Locally Selected Class-Adapted Models
• Of Li-Ion Batteries and Biochemical networks: Finding a Low Dimensional Models in Haystacks
• Compressive light-field microscopy for 3D neural activity recording
• SparkleGeometry: Glitter Imaging for 3D Point Tracking / Cloudmaps from Static Ground-View Video

CS/ML Hardware:

• RedEye: Analog ConvNet Image Sensor Architecture for Continuous Mobile Vision - implementation -

Meetings/Meetups/conferences:

• Ce Soir: Paris Machine Learning Meetup #14 Season 3: Dare Mighty Things
• international - Traveling Workshop on Interactions between Sparse models and Technology" (iTWIST)
• Research workshop: HORSE 2016 On “Horses” and “Potemkin Villages” in Applied Machine Learning at QMUL, London
• Slides, papers some videos: ICML, CVPR, NIPS
• CVPR papers are out !

Jobs:

• CSjob: Two Postdocs, C-SENSE: Exploiting low dimensional signal models for sensing, computation and processing, Edinburgh,, Scotland.
• CSjob: Postdoc, Signal processing & inverse problems for the future SKA, Nice, France
• Post-doc Causality and Machine Learning, University Paris-Saclay, France

Videos:

• Saturday Morning Video: Machine Learning in Computational Biology Workshop, @NIPS2015
• Saturday Morning Videos: Nonparametric Methods for Large Scale Representation Learning NIPS 2015 Workshop
• Saturday Morning Videos: Probabilistic Integration Workshop at NIPS 2015 (and slides)
• Saturday Monring Videos: Deep Reinforcement Learning Workshop @NIPS 2015 (and slides)
• Saturday Morning Videos: Machine Learning For Healthcare (MLHC) workshop @NIPS2015

LightOn

• First Light
• LightOn. And so it begins. 

Nuit Blanche

• Five million page views: The Numbers Game in Long Distance Blogging

 

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Group Sparse Regularization for Deep Neural Networks

If group-LASSO improves compressive sensing reconstruction, why shouldn't it do the same for training nets in deep architectures. This is what today's preprint investigates. Woohoo !

Group Sparse Regularization for Deep Neural Networks by Simone Scardapane, Danilo Comminiello, Amir Hussain, Aurelio Uncini

In this paper, we consider the joint task of simultaneously optimizing (i) the weights of a deep neural network, (ii) the number of neurons for each hidden layer, and (iii) the subset of active input features (i.e., feature selection). While these problems are generally dealt with separately, we present a simple regularized formulation allowing to solve all three of them in parallel, using standard optimization routines. Specifically, we extend the group Lasso penalty (originated in the linear regression literature) in order to impose group-level sparsity on the network's connections, where each group is defined as the set of outgoing weights from a unit. Depending on the specific case, the weights can be related to an input variable, to a hidden neuron, or to a bias unit, thus performing simultaneously all the aforementioned tasks in order to obtain a compact network. We perform an extensive experimental evaluation, by comparing with classical weight decay and Lasso penalties. We show that a sparse version of the group Lasso penalty is able to achieve competitive performances, while at the same time resulting in extremely compact networks with a smaller number of input features. We evaluate both on a toy dataset for handwritten digit recognition, and on multiple realistic large-scale classification problems.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

Thesis: Statistical physics of linear and bilinear inference problems by Christophe Schülke

Congratulations Dr. Schulke !

Statistical physics of linear and bilinear inference problems by Christophe Schülke

The recent development of compressed sensing has led to spectacular advances in the understanding of sparse linear estimation problems as well as in algorithms to solve them. It has also triggered a new wave of developments in the related fields of generalized linear and bilinear inference problems, that have very diverse applications in signal processing and are furthermore a building block of deep neural networks. These problems have in common that they combine a linear mixing step and a nonlinear, probabilistic sensing step, producing indirect measurements of a signal of interest. Such a setting arises in problems as different as medical or astronomical imaging, clustering, matrix completion or blind source separation. The aim of this thesis is to propose efficient algorithms for this class of problems and to perform their theoretical analysis. To this end, it uses belief propagation, thanks to which high-dimensional distributions can be sampled efficiently, thus making a Bayesian approach to inference tractable. The resulting algorithms undergo phase transitions just as physical systems do. These phase transitions can be analyzed using the replica method, initially developed in statistical physics of disordered systems. The analysis reveals phases in which inference is easy, hard or impossible. These phases correspond to different energy landscapes of the problem. The main contributions of this thesis can be divided into three categories. First, the application of known algorithms to concrete problems: community detection, superposition codes and an innovative imaging system. Second, a new, efficient message-passing algorithm for a class of problems called blind sensor calibration. Third, a theoretical analysis of matrix compressed sensing and of instabilities in Bayesian bilinear inference algorithms.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.

First Light

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.