M87 reconstruction by the Event Horizon Telescope project

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

Credit: Event Horizon Telescope Collaboration

We talked about M87 before but as far as I can see the most recent black hole images do not seem to use sparsity driven reconstruction techniques. Here is the Event Horizon Telescope page that featured this beautiful reconstruction of the M87 black hole and the attendant papers connected to this press release:

• Paper I: The Shadow of the Supermassive Black Hole
• Paper II: Array and Instrumentation
• Paper III: Data processing and Calibration
• Paper IV: Imaging the Central Supermassive Black Hole
• Paper V: Physical Origin of the Asymmetric Ring
• Paper VI: The Shadow and Mass of the Central Black Hole

Earlier:

The Size, Shape, and Scattering of Sagittarius A* at 86 GHz: First VLBI with ALMA by S. Issaoun, M. D. Johnson, L. Blackburn, C. D. Brinkerink, M. Mościbrodzka, A. Chael, C. Goddi, I. Martí-Vidal, J. Wagner, S. S. Doeleman, H. Falcke, T. P. Krichbaum, K. Akiyama, U. Bach, K. L. Bouman, G. C. Bower, A. Broderick, I. Cho, G. Crew, J. Dexter, V. Fish, R. Gold, J. L. Gómez, K. Hada, A. Hernández-Gómez, M. Janßen, M. Kino, M. Kramer, L. Loinard, R.-S. Lu, S. Markoff, D. P. Marrone, L. D. Matthews, J. M. Moran, C. Müller, F. Roelofs, E. Ros, H. Rottmann, S. Sanchez, R. P. J. Tilanus, P. de Vicente, M. Wielgus, J. A. Zensus, G.-Y. Zhao

The Galactic Center supermassive black hole Sagittarius A* (Sgr A*) is one of the most promising targets to study the dynamics of black hole accretion and outflow via direct imaging with very long baseline interferometry (VLBI). At 3.5 mm (86 GHz), the emission from Sgr A* is resolvable with the Global Millimeter VLBI Array (GMVA). We present the first observations of Sgr A* with the phased Atacama Large Millimeter/submillimeter Array (ALMA) joining the GMVA. Our observations achieve an angular resolution of ~87{\mu}as, improving upon previous experiments by a factor of two. We reconstruct a first image of the unscattered source structure of Sgr A* at 3.5 mm, mitigating effects of interstellar scattering. The unscattered source has a major axis size of 120 ±34{\mu}as (12 ± 3.4 Schwarzschild radii), and a symmetrical morphology (axial ratio of 1.2+0.3−0.2), which is further supported by closure phases consistent with zero within 3{\sigma}. We show that multiple disk-dominated models of Sgr A* match our observational constraints, while the two jet-dominated models considered are constrained to small viewing angles. Our long-baseline detections to ALMA also provide new constraints on the scattering of Sgr A*, and we show that refractive scattering effects are likely to be weak for images of Sgr A* at 1.3 mm with the Event Horizon Telescope. Our results provide the most stringent constraints to date for the intrinsic morphology and refractive scattering of Sgr A*, demonstrating the exceptional contribution of ALMA to millimeter VLBI.

Computational Imaging for VLBI Image Reconstruction by Katherine L. Bouman, Michael D. Johnson, Daniel Zoran, Vincent L. Fish, Sheperd S. Doeleman, William T. Freeman

Very long baseline interferometry (VLBI) is a technique for imaging celestial radio emissions by simultaneously observing a source from telescopes distributed across Earth. The challenges in reconstructing images from fine angular resolution VLBI data are immense. The data is extremely sparse and noisy, thus requiring statistical image models such as those designed in the computer vision community. In this paper we present a novel Bayesian approach for VLBI image reconstruction. While other methods often require careful tuning and parameter selection for different types of data, our method (CHIRP) produces good results under different settings such as low SNR or extended emission. The success of our method is demonstrated on realistic synthetic experiments as well as publicly available real data. We present this problem in a way that is accessible to members of the community, and provide a dataset website (this http URL) that facilitates controlled comparisons across algorithms.

Of interest:

• VLBI Reconstruction Dataset
• EHT Imaging github

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

Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation

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

Quantization does not seem to be an issue for Random Features !

Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation by Jian Zhang, Avner May, Tri Dao, Christopher Ré

We investigate how to train kernel approximation methods that generalize well under a memory budget. Building on recent theoretical work, we define a measure of kernel approximation error which we find to be more predictive of the empirical generalization performance of kernel approximation methods than conventional metrics. An important consequence of this definition is that a kernel approximation matrix must be high rank to attain close approximation. Because storing a high-rank approximation is memory intensive, we propose using a low-precision quantization of random Fourier features (LP-RFFs) to build a high-rank approximation under a memory budget. Theoretically, we show quantization has a negligible effect on generalization performance in important settings. Empirically, we demonstrate across four benchmark datasets that LP-RFFs can match the performance of full-precision RFFs and the Nyström method, with 3x-10x and 50x-460x less memory, respectively.

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

GAN-based Projector for Faster Recovery in Compressed Sensing with Convergence Guarantees

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

GAN-based Projector for Faster Recovery in Compressed Sensing with Convergence Guarantees by Ankit Raj, Yuqi Li, Yoram Bresler

A Generative Adversarial Network (GAN) with generator G trained to model the prior of images has been shown to perform better than sparsity-based regularizers in ill-posed inverse problems. In this work, we propose a new method of deploying a GAN-based prior to solve linear inverse problems using projected gradient descent (PGD). Our method learns a network-based projector for use in the PGD algorithm, eliminating the need for expensive computation of the Jacobian of G. Experiments show that our approach provides a speed-up of 30-40× over earlier GAN-based recovery methods for similar accuracy in compressed sensing. Our main theoretical result is that if the measurement matrix is moderately conditioned for range(G) and the projector is δ-approximate, then the algorithm is guaranteed to reach O(δ) reconstruction error in O(log(1/δ)) steps in the low noise regime. Additionally, we propose a fast method to design such measurement matrices for a given G. Extensive experiments demonstrate the efficacy of this method by requiring 5-10× fewer measurements than random Gaussian measurement matrices for comparable recovery performance.

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

Compressed Sensing with Deep Image Prior and Learned Regularization - implementation -

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

Taking Deep Priors to compressive sensing !

Compressed Sensing with Deep Image Prior and Learned Regularization by David Van Veen, Ajil Jalal, Eric Price, Sriram Vishwanath, Alexandros G. Dimakis

We propose a novel method for compressed sensing recovery using untrained deep generative models. Our method is based on the recently proposed Deep Image Prior (DIP), wherein the convolutional weights of the network are optimized to match the observed measurements. We show that this approach can be applied to solve any differentiable inverse problem. We also introduce a novel learned regularization technique which incorporates a small amount of prior information on the network weights. Compared to previous unlearned methods for compressed sensing, our algorithm requires fewer measurements in most cases. Unlike previous learned approaches based on generative models, our method does not require pre-training over large datasets. As such, we can apply our method to various medical imaging datasets for which data acquisition is expensive and generative models are difficult to train.

Implementation is here: https://github.com/davevanveen/compsensing_dip

We mentioned Deep Prior before and featured Dmitry Ulyanov at one of LightOn's meetup/workshop.

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: New Approaches to Image and Video Reconstruction Using Deep Learning (Jeremy Howard, Jason Antic, and Uri Manor)

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

Jeremy Howard one of the founding research behind Fast.ai as well as Jason Antic (Deoldify), and Uri Manor (Salk Institute) present New Approaches to Image and Video Reconstruction Using Deep Learning in this video.

abstract: We often want to improve our images and videos, such as increasing their resolution or adding color to black & white film. Much progress has been made in recent years through deep learning, and specifically the use of generative adversarial networks (GANs). However, GANs can be slow, and both difficult and expensive to train. In this session, we’ll show you how to colorize old black & white movies and drastically increase the resolution of microscopy images using new PyTorch-based tools from fast.ai, the Salk Institute, and DeOldify that can be trained in just a few hours on a single GPU.

The attendant blog post with all the information on the video can be found here entilted: Decrappification, DeOldification, and Super Resolution

Github: DeOldify

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: Andreas C. Müller's COMS W4995 Applied Machine Learning, Columbia/NYU CDS, Spring 2019

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

Andreas is a contributor of Scikit-learn and just posted the videos of his course at the Institute for Data Science at NYU and Columbia. 

1:16:53

Applied Machine Learning 2019 - Lecture 19 - Word embeddings

1:18:24

Applied Machine Learning 2019 - Lecture 18 - Topic Models

1:16:45

Applied Machine Learning 2019 - Lecture 17 - Introduction to text data

1:04:24

Applied Machine Learning 2019 - Lecture 16 - NMF; Outlier detection

1:09:32

Applied Machine Learning 2019 - Lecture 15 - Clustering and Mixture models

1:15:24

Applied Machine Learning 2019 - Lecture 14 - Dimensionality Reduction

1:22:07

Applied Machine Learning 2019 - Lecture 13 - Parameter Selection and Automatic Machine Learning

1:17:05

Applied Machine Learning 2019 - Lecture 12 - Model Interpretration and Feature Selection

1:03:48

Applied Machine Learning 2019 - Lecture 11 - Imbalanced data

1:15:23

Applied Machine Learning 2019 - Lecture 10 - Model Evaluation

1:16:22

Applied Machine Learning 2019 - Lecture 09 - Gradient boosting; Calibration

1:18:29

Applied Machine Learning 2019 - Lecture 08 - Trees, Forests and Ensembles

1:17:39

Applied Machine Learning 2019 - Lecture 07 - Linear Models for Classifications, SVMs

1:15:59

Applied Machine Learning 2019 - Lecture 06 - Linear Models for Regression

1:17:09

Applied Machine Learning 2019 - Lecture 05 - Preprocessing

1:17:55

Applied Machine Learning 2019 - Lecture 04 - Introduction to supervised learning

1:17:12

Applied Machine Learning 2019 - Lecture 03 - Visualization and Matplotlib

1:14:41

Applied Machine Learning 2019 - Lecture 02 - Version control and Testing

1:23:22

Applied Machine Learning 2019 - Lecture 01 - Introduction to Machine Learning

3:14

A short history of scikit-learn

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

Nuit Blanche in Review (July 2018 - April 2019)

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

The last Nuit Blanche in Review was back on July 9th, 2018 and much has happened as regards to LightOn as we raised $3M+ in December and are looking forward to make our technology more available to the Machine Learning community. Coming to this place, Nuit Blanche is back !

I think one of the most interesting theoretical development has the ability to study nonlinearities in Deep Learning thanks in part to the work of Jeffrey Pennington as featured here before. Some of the papers that cite his work are featured in this review and bring much freshness to the field. In other news, Nuit Blanche is also on Twitter at this address @NuitBlog. In the meantime, here is what happened for the past few months here in this 66th Nuit Blanche in Review, enjoy !

Implementations

• Manopt 5.0, toolbox release: Optimization on Manifolds: - implementation -
• SPORCO: Convolutional Dictionary Learning - implementation -
• Rank Minimization for Snapshot Compressive Imaging - implementation -

In-depth:

• Data-Driven Design for Fourier Ptychographic Microscopy
• Quantifying entanglement in a 68-billion dimensional quantum system
• Neumann Networks for Inverse Problems in Imaging
• Beyond Thunderspline: Mad Max: Affine Spline Insights into Deep Learning/ From Hard to Soft: Understanding Deep Network Nonlinearities via Vector Quantization and Statistical Inference
• Phase Retrieval Under a Generative Prior
• Projecting "better than randomly": How to reduce the dimensionality of very large datasets in a way that outperforms random projections
• Why are Big Data Matrices Approximately Low Rank?
• Eigenvalue distribution of nonlinear models of random matrices
• Enhanced Expressive Power and Fast Training of Neural Networks by Random Projections
• A Neural Architecture for Bayesian CompressiveSensing over the Simplex via Laplace Techniques

LightOn

• LightOn: Forward We Go !
• Shedding Light on the “Grand Débat”

Hardware: 

• CSHardware: Development of sparse coding and reconstruction subsystems for astronomical imaging, João Rino-Silvestre
• Ghost imaging with the human eye

CfPs:

• CfP: Khipu 2019: Latin American Meeting in Artificial Intelligence, Montevideo, Uruguay, November 11-15th, 2019
• CfP: 2019 Conference on Mathematical Theory of Deep Neural Networks (DeepMath 2019)
• CfP: Call for Papers: Special Issue on Information Theory Applications in Signal Processing

References: 

• Book: High-Dimensional Probability An Introduction with Applications in Data Science by Roman Vershynin
• Highly Technical Reference Page: The Rice University Compressive Sensing page.
• #ICML2018 Tutorial: Toward theoretical understanding of deep learning, Sanjeev Arora

Videos: 

• Saturday Morning Videos: Statistical Modeling for Shapes and Imaging, 11 March 2019 - 15 March 2019, IHP
• Videos: New Deep Learning Techniques, February 5 - 9, 2018, IPAM Workshop
• Videos: Sublinear Algorithms and Nearest-Neighbor Search workshop, Nov. 27 – Nov. 30, 2018 (Simon Institute and Kavli Foundation)
• Video: Robust and High-Dimensional Statistics workshop - Oct. 29 – Nov. 2, 2018, (Simon Institute and Kavli Foundation)
• Video: Randomized Numerical Linear Algebra and Applications Workshop - Sep. 24 – Sep. 27, 2018, (Simon Institute and Kavli Foundation)
• Videos: Foundations of Data Science Boot Camp workshop, Aug. 27 – Aug. 31, 2018 (Simon Institute and Kavli Foundation)
• Videos: Variational Methods and Optimization in Imaging, at IHP Paris, February 4th – 8th , 2019
• Ce soir Paris Machine Learning #6 Season 6: Adversarial Attacks, ML in Production, XAI, Photo Editing
• Ce soir, Paris Machine Learning #5 season 6: Explainable AI, Unity Challenge, Ethical AI
• The 100th Paris Machine Learning meetup tonight: La revanche des neurones, DL on Healthrecords, Search-Oriented Conversational AI, Nanotechnology and electricity consumption
• Paris ML E#2 S#6: Conscience, Code Analysis, Can a machine learn like a child?
• Paris Machine Learning #1 S6 at Vente-Privée
• Sunday Morning Video (in french): Les travaux de Grothendieck.sur les espaces de Banach, Gilles. Pisier (Lectures grothendieckiennes)
• WiMLDS and Paris Machine Learning meetup Hors série #1: Scalable Automatic Machine Learning with H2O with Erin Ledell
• “And we’re back for Season 6” Paris Machine Learning Newsletter, September 2018 (in French)

Jobs:

• Job: Postdoctoral Researcher in Small Data Deep Learning and Explainable Machine Learning, Livermore, CA
• CSJob: PhD and Postdoc positions KU Leuven: Optimization frameworks for deep kernel machines

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

Ghost imaging with the human eye

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

This is fascinating ! letting the human eye perform one operation in a ghost imaging experiment.

Ghost imaging with the human eye by Alessandro Boccolini, Alessandro Fedrizzi, and Daniele Faccio

Computational ghost imaging relies on the decomposition of an image into patterns that are summed together with weights that measure the overlap of each pattern with the scene being imaged. These tasks rely on a computer. Here we demonstrate that the computational integration can be performed directly with the human eye. This builds upon the known persistence time of the human eye and we use our ghost imaging approach as an alternative to evaluate the temporal response of the eye. We verify that the image persistence time is of order 20 ms, followed by a further 20 ms exponential decay. These persistence times are consistent with previous studies but can now potentially be extended to include a more precise characterisation of visual stimuli and provide a new experimental tool for the study of visual perception.

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

Quantifying entanglement in a 68-billion dimensional quantum system

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

Following up on previous work, using compressive sensing to probe a large quantum system !

Quantifying entanglement in a 68-billion dimensional quantum system by James Schneeloch, Christopher C. Tison, Michael L. Fanto, Paul M. Alsing, Gregory A. Howland

Entanglement is the powerful and enigmatic resource central to quantum information processing, which promises capabilities in computing, simulation, secure communication, and metrology beyond what is possible for classical devices. Achieving a quantum advantage requires scaling quantum systems to sizes that can support a large amount of entanglement. Because real-world systems are varied and imperfect, the quantum resources they provide must be characterized before use. However, exactly quantifying the entanglement of an unknown system requires completely determining its quantum state, a task which requires an intractable number of measurements even for modestly sized systems. Here we demonstrate a new method for rigorously quantifying high-dimensional entanglement from extremely limited data. We improve an entropic, quantitative entanglement witness to operate directly on compressed experimental data acquired via an adaptive, multilevel sampling procedure. Only 6,456 measurements are needed to certify an entanglement-of-formation of 7.11±.04 ebits shared between spatially-entangled photon pairs. With a Hilbert space exceeding 68 billion dimensions, this is 10-million-fold fewer measurements than traditional approaches. The procedure does not computationally recover an underlying state and allows straightforward error analysis. Our technique offers a universal method for quantifying entanglement in any large quantum system shared by two parties.

Quantifying high-dimensional entanglement with Einstein-Podolsky-Rosen correlations by James Schneeloch, Gregory A. Howland

Quantifying entanglement in a quantum system generally requires a complete quantum tomography followed by the NP-hard computation of an entanglement monotone --- requirements that rapidly become intractable at higher dimensions. Observing entanglement in large quantum systems has consequently been relegated to witnesses that only verify its existence. In this article, we show that the violation of recent entropic witnesses of the Einstein-Podolsky-Rosen paradox also provides tight lower bounds to multiple entanglement measures, such as the entanglement of formation and the distillable entanglement, among others. Our approach only requires the measurement of correlations between two pairs of complementary observables---not a tomography---so it scales efficiently at high dimension. Despite this, our technique captures almost all the entanglement in common high-dimensional quantum systems, such as spatially or temporally entangled photons from parametric down-conversion.

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

Projecting "better than randomly": How to reduce the dimensionality of very large datasets in a way that outperforms random projections

So, datasets are becoming so large that we now have investigations on the difference between Random Projections and Randomized PCA !

Projecting "better than randomly": How to reduce the dimensionality of very large datasets in a way that outperforms random projections by Michael Wojnowicz, Di Zhang, Glenn Chisholm, Xuan Zhao, Matt Wolff

For very large datasets, random projections (RP) have become the tool of choice for dimensionality reduction. This is due to the computational complexity of principal component analysis. However, the recent development of randomized principal component analysis (RPCA) has opened up the possibility of obtaining approximate principal components on very large datasets. In this paper, we compare the performance of RPCA and RP in dimensionality reduction for supervised learning. In Experiment 1, study a malware classification task on a dataset with over 10 million samples, almost 100,000 features, and over 25 billion non-zero values, with the goal of reducing the dimensionality to a compressed representation of 5,000 features. In order to apply RPCA to this dataset, we develop a new algorithm called large sample RPCA (LS-RPCA), which extends the RPCA algorithm to work on datasets with arbitrarily many samples. We find that classification performance is much higher when using LS-RPCA for dimensionality reduction than when using random projections. In particular, across a range of target dimensionalities, we find that using LS-RPCA reduces classification error by between 37% and 54%. Experiment 2 generalizes the phenomenon to multiple datasets, feature representations, and classifiers. These findings have implications for a large number of research projects in which random projections were used as a preprocessing step for dimensionality reduction. As long as accuracy is at a premium and the target dimensionality is sufficiently less than the numeric rank of the dataset, randomized PCA may be a superior choice. Moreover, if the dataset has a large number of samples, then LS-RPCA will provide a method for obtaining the approximate principal components.

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