One-shot distributed ridge regression in high dimensions - implementation-

One-shot distributed ridge regression in high dimensions by Edgar Dobriban, Yue Sheng

In many areas, practitioners need to analyze large datasets that challenge conventional single-machine computing. To scale up data analysis, distributed and parallel computing approaches are increasingly needed. Datasets are spread out over several computing units, which do most of the analysis locally, and communicate short messages. Here we study a fundamental and highly important problem in this area: How to do ridge regression in a distributed computing environment? Ridge regression is an extremely popular method for supervised learning, and has several optimality properties, thus it is important to study. We study one-shot methods that construct weighted combinations of ridge regression estimators computed on each machine. By analyzing the mean squared error in a high dimensional random-effects model where each predictor has a small effect, we discover several new phenomena.
1. Infinite-worker limit: The distributed estimator works well for very large numbers of machines, a phenomenon we call "infinite-worker limit".
2. Optimal weights: The optimal weights for combining local estimators sum to more than unity, due to the downward bias of ridge. Thus, all averaging methods are suboptimal.
We also propose a new optimally weighted one-shot ridge regression algorithm. We confirm our results in simulation studies and using the Million Song Dataset as an example. There we can save at least 100x in computation time, while nearly preserving test accuracy.

An implementation can be found here: https://github.com/dobriban/dist

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

Compressive Single-pixel Fourier Transform Imaging using Structured Illumination

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

Here is some new CS related hardware 

Compressive Single-pixel Fourier Transform Imaging using Structured Illumination by Amirafshar Moshtaghpour, José M Bioucas-Dias, Laurent Jacques

Single Pixel (SP) imaging is now a reality in many applications, e.g., biomedical ultrathin endoscope and fluorescent spectroscopy. In this context, many schemes exist to improve the light throughput of these device, e.g., using structured illumination driven by compressive sensing theory. In this work, we consider the combination of SP imaging with Fourier Transform Interferometry (SP-FTI) to reach high-resolution HyperSpectral (HS) imaging, as desirable, e.g., in fluorescent spectroscopy. While this association is not new, we here focus on optimizing the spatial illumination, structured as Hadamard patterns, during the optical path progression. We follow a variable density sampling strategy for space-time coding of the light illumination, and show theoretically and numerically that this scheme allows us to reduce the number of measurements and light-exposure of the observed object compared to conventional compressive SP-FTI.

Related: Single Pixel Hyperspectral Imaging using Fourier Transform Interferometry


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

A Fast Noniterative Algorithm for Compressive Sensing Using Binary Measurement Matrices

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

A Fast Noniterative Algorithm for Compressive Sensing Using Binary Measurement Matrices by Mahsa Lotfi, Mathukumalli Vidyasagar

In this paper we present a new algorithm for compressive sensing that makes use of binary measurement matrices and achieves exact recovery of ultra sparse vectors, in a single pass and without any iterations. Due to its noniterative nature, our algorithm is hundreds of times faster than ℓ1-norm minimization, and methods based on expander graphs, both of which require multiple iterations. Our algorithm can accommodate nearly sparse vectors, in which case it recovers index set of the largest components, and can also accommodate burst noise measurements. Compared to compressive sensing methods that are guaranteed to achieve exact recovery of all sparse vectors, our method requires fewer measurements However, methods that achieve statistical recovery, that is, recovery of almost all but not all sparse vectors, can require fewer measurements than our method.

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

Saturday Morning Video: ISSCC 2019, Deep Learning Hardware: Past, Present, and Future, Yann LeCun

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

Yann LeCun mentioned his recent talk at ISSCC 2019 on his twitter feed.

Slides are here.

Lots of good lessons learned. Because I am involved with LightOn, I liked the last slide. I like challenges. 

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

Saturday Morning Videos: Workshop III: Geometry of Big Data, Geometry and Learning from Data in 3D and Beyond, IPAM

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

So Workshop III: Geometry of Big Data, part of Geometry and Learning from Data in 3D and Beyond just finished at IPAM and we have videos ! Thanks to the organizers.

Pradeep Ravikumar (Carnegie Mellon University)

DAGs with NO TEARS: Continuous Optimization for Structure Learning 

Ronen Talmon (Technion - Israel Institute of Technology)

Data Analysis with the Riemannian Geometry of Symmetric Positive-Definite Matrices 

Yusu Wang (Ohio State University)

Metric learning for persistence-based summaries and application to graph classification

Dejan Slepcev (Carnegie Mellon University)

Proper regularizers for semi-supervised learning 

Jianfeng Lu (Duke University)

Solving for committor functions in high dimension

Lorenzo Rosasco (Università di Genova)

A consistent framework for structure machine learning 

Frederic Chazal (Institut National de Recherche en Informatique et Automatique (INRIA))

On the density of expected persistence diagrams and its kernel based estimation 

Richard Samworth (University of Cambridge)

Log-concave density estimation: adaptation and high dimensions 

Nathan Srebro (TTI-Chicago)

Infinite-Width Bounded-Norm Networks: A View from Function Space

Andrea Montanari (Stanford University)

Some geometric surprises in modern machine learning

Amit Singer (Princeton University)

Multi-target detection and cryo-EM imaging by autocorrelation analysis

Rebecca Willett (University of Chicago)

Learning to Solve Inverse Problems in Imaging 

Bin Dong (Peking University)

Bridging Deep Neural Networks and Differential Equations for Image Restoration and Beyond 

Marina Meila (University of Washington)

Manifold Learning for the Sciences 

Mahdi Soltanolkotabi (University of Southern California (USC))

Towards demystifying over-parameterization in deep learning

Stanley Osher (University of California, Los Angeles (UCLA))

PDE Approaches for Deep Learning 

Imre Risi Kondor (University of Chicago)

Covariant neural networks for learning physical systems 

Naftali Tishby (Hebrew University)

Topological transitions (and symmetries) of input representations in Deep Learning

Richard Tsai (University of Texas at Austin)

Machine learning approaches for a few optimization problems involving lines-of-sight

Bin Yu (University of California, Berkeley (UC Berkeley))

PCS workflow, interpretable machine learning, and DeepTune

Hongkai Zhao (University of California, Irvine (UCI))

Intrinsic complexity: from approximation of random vectors and random fields to solutions of PDEs

Zuowei Shen (National University of Singapore)

Deep Approximation via Deep Learning 

Joel Tropp (California Institute of Technology)

SketchySVD 

Jianfeng Cai (Hong Kong University of Science and Technology)

Solving Systems of Phaseless Equations: Riemannian Optimization and Global Geometry

Anastasia Dubrovina (Lyft)

Structured embedding spaces for shape completion and synthesis

Chao Gao (University of Chicago)

Robust Estimation and Generative Adversarial Nets 

Mauro Maggioni (Duke University)

Learning Interaction kernels in agent-based systems

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

Compressive optical interferometry

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

When interferometry is done with radiowaves, then compressive sensing reconstruction makes immediately sense as we get phase measurements. In the case of light, phase retrieval is required or something has to be done at the hardware level.  Something along the lines of some of throughts put in this entry on These Technologies Do Not Exist.

Compressive optical interferometry by Davood Mardani, H. Esat Kondakci, Lane Martin, Ayman F. Abouraddy, George K. Atia

Compressive sensing (CS) combines data acquisition with compression coding to reduce the number of measurements required to reconstruct a sparse signal. In optics, this usually takes the form of projecting the field onto sequences of random spatial patterns that are selected from an appropriate random ensemble. We show here that CS can be exploited in `native' optics hardware without introducing added components. Specifically, we show that random sub-Nyquist sampling of an interferogram helps reconstruct the field modal structure. The distribution of reduced sensing matrices corresponding to random measurements is provably incoherent and isotropic, which helps us carry out CS successfully.

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