Nuit Blanche in Review ( March 2015 )

This past month, we were shocked to hear about Ernie Esser's Passing (and Legacy), a new Highly technical Reference Page was created (The Superiorization Methodology and Perturbation Resilience of Algorithms), the Paris Machine Learning Meetup #7 Season 2 took place (Automatic Statistician, ML et Entreprise, Algo Fairness/ Certifying and removing Disparate Impact). In the meantime, we are collectively waiting for something new (No Pressure) 20 years later. our part of the blogosphere showed us The great Convergence in Action.

 

The previous Nuit Blanche in Review for February 2015 is here.

In the meantime, a few implementations were made available by their authors: 

• Python version of SPGL1 - implementation -
• Thesis: Spectral classification using convolutional neural networks, Pavel Hála - implementation -
• DECOPT - DEcomposition Convex OPTimization - implementation -
• Variational Inference for Sparse Spectrum Approximation in Gaussian Process Regression -implementation - 

 We had two Sunday Morning Insights:

• Sunday Morning Insight: Muon Tomography of Fukushima Daiichi's reactor #1
•  Sunday Morning Insight: Another Strange PSF in the Wild

Two theses

• Thesis: Gravimetric Anomaly Detection using Compressed Sensing by Ryan Kappedal   
• Thesis: Compressive Power Spectral Analysis by Dyonisius Ariananda

A few insights from deep architectures

• Deep Transform: Time-Domain Audio Error Correction via Probabilistic Re-Synthesis, Cocktail Party Source Separation via Probabilistic Re-Synthesis
• Real-time Dynamic MRI Reconstruction using Stacked Denoising Autoencoder
• Enhanced Image Classification With a Fast-Learning Shallow Convolutional Neural Network 

and some from compressive sensing:

• Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty
• LiSens, Photometric stereo using BRDF dictionaries, CS-MUVI
• Infinite-dimensional $\ell^1$ minimization and function approximation from pointwise data
• Devising Measurement Matrices
• Single and multiple snapshot compressive beamforming
• Everybody wants to be shallow: Compact Nonlinear Maps and Circulant Extensions
• High-resolution and broadband all-fiber spectrometers
• Learning Co-Sparse Analysis Operators with Separable Structures
• VLSI Design of a Monolithic Compressive-Sensing Wideband Analog-to-Information Converter (and other FPGA implementations)
• Phase Transitions in Sparse PCA
• Sparse Coding: 20 years later
• Adaptive-Rate Sparse Signal Reconstruction With Application in Compressive Background Subtraction
• Various Announcements 

 Around the blogs

• Around The Blogs in 78 Hours
• The great Convergence in Action.
 

Meetings

• Meeting: missDATA 2015, Rennes, Brittany, France

 Slides/courses

• Slides: Stanford's CS231n: Convolutional Neural Networks for Visual Recognition
• Slides: Learning Sparse Representations for Signal Processing @IISc
• Saturday Morning Videos: Nando de Freitas' Machine Learning course (Lecture 7 to 12) and slides

Videos:

• Saturday Morning Videos: February Fourier Talks 2015 Proceedings
• Video (and attendant code): A 3D Map of the Human Genome
• Video: Rambus Lensless Smart Sensor Demo at MWC 2015
• Saturday Morning Video: The Automatic Statistician, Certifying and removing Disparate Impact, Machine Learning et Entreprise
• Saturday Morning Videos: Nando de Freitas' Machine Learning course (Lecture 7 to 12) and slides

 Other:

• On aurait pu regarder l'éclipse à Paris ....

Courtesy of NASA/SDO and the AIA, EVE, and HMI science teams.

    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.

Sparse Spikes Deconvolution on Thin Grids / Compressive Sensing in Electromagnetics - A Review

Jong Chul Ye let me now that a second version of Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty is out. It is here: http://arxiv.org/pdf/1503.06679v2.pdf

Gabriel Peyré let me know of the following:

Hi Igor,

A paper that might interest the CS community http://gpeyre.github.io/2015/03/24/thin-grids/
The numerical section contains some findings on support (in)stability of CS with l^1.

-- best

From his blog post:

Vincent Duval and myself just released a new paper on the asymptotic performance of L1-type methods for deconvoluton, when the grid-size tends to zero. This paper extends our previous results on the subject. It basically proves that both the classical lasso/basis-pursuit method, and the less known continuous basis-pursuit method estimate twice the number of spikes. This is not so surprising because approximating arbitrary spikes locations on a quantized grid somehow necessitates this slight delocalization of the positions. An interesting feature of our analysis is that we are able to perfectly predict which of the neighboring grid points will be selected using a careful analysis of so-called dual certificates. Another interesting feature of these theoretical findings is that we provide an “abstract” analysis of L1-like methods that extend the classical results of J. J. Fuchs to the setting where the support is not necessarily stable (which is always the case for coherent inverse problems like deconvolution). This abstract analysis can be used beyond deconvolution problems. In the numerical section, we show how it can be used to assess numerically support-instability in compressed sensing reconstruction. This is a somehow under-studied problem. Indeed, the literature only focus on the case where the support is stable or only on L2 stability, never on the “gray area” where support is unstable but the method is successful when there is no noise.

Here is the paper: Sparse Spikes Deconvolution on Thin Grids by Vincent Duval,  Gabriel Peyré

Abstract : This article analyzes the recovery performance of two popular finite dimensional approximations of the sparse spikes deconvolution problem over Radon measures. We examine in a unified framework both the L1 regularization (often referred to as Lasso or Basis-Pursuit) and the Continuous Basis-Pursuit (C-BP) methods. The Lasso is the de-facto standard for the sparse regularization of inverse problems in imaging. It performs a nearest neighbor interpolation of the spikes locations on the sampling grid. The C-BP method, introduced by Ekanadham, Tranchina and Simoncelli, uses a linear interpolation of the locations to perform a better approximation of the infinite-dimensional optimization problem, for positive measures. We show that, in the small noise regime, both methods estimate twice the number of spikes as the number of original spikes. Indeed, we show that they both detect two neighboring spikes around the locations of an original spikes. These results for deconvolution problems are based on an abstract analysis of the so-called extended support of the solutions of L1-type problems (including as special cases the Lasso and C-BP for deconvolution), which are of an independent interest. They precisely characterize the support of the solutions when the noise is small and the regularization parameter is selected accordingly. We illustrate these findings to analyze for the first time the support instability of compressed sensing recovery when the number of measurements is below the critical limit (well documented in the literature) where the support is provably stable.

Giacomo Oliveri also sent me the following link to a review:

Dear Dr. Carron,

this is to kindly ask if you could consider posting the following contribution (published journal paper on the IEEE Antennas and Propagation Magazine) in your excellent Nuit Blanche blog (http://nuit-blanche.blogspot.it/)

================================================================================================
Title: Compressive Sensing in Electromagnetics - A Review
Authors: Andrea MASSA, Paolo ROCCA, and Giacomo OLIVERI
Journal: IEEE Antennas and Propagation Magazine
Volume: 57
Issue: 1
Pages: 224-238
Month: February
Year: 2015
Link: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7046378
DOI: 10.1109/MAP.2015.2397092
Abstract
Several problems arising in electromagnetics can be directly formulated or suitably recast for an effective solution within the compressive sensing (CS) framework. This has motivated a great interest in developing and applying CS methodologies to several conventional and innovative electromagnetic scenarios. This work is aimed at presenting, to the best of the authors’ knowledge, a review of the state-of-the-art and most recent advances of CS formulations and related methods as applied to electromagnetics. Toward this end, a wide set of applicative scenarios comprising the diagnosis and synthesis of antenna arrays, the estimation of directions of arrival, and the solution of inverse scattering and radar imaging problems are reviewed. Current challenges and trends in the application of CS to the solution of traditional and new electromagnetic problems are also discussed.
================================================================================================

Please let us know if you need any further information on this contribution.

Many thanks in advance for your kindness,
Best regards,
Giacomo Oliveri

Thanks Jong, Giacomo and Gabriel !

Image Credit: NASA/JPL-Caltech/Space Science Institute 

N00236618.jpg was taken on March 27, 2015 and received on Earth March 29, 2015. The camera was pointing toward IAPETUS, and the image was taken using the CL1 and IR3 filters.

    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.

Deep Transform: Time-Domain Audio Error Correction via Probabilistic Re-Synthesis, Cocktail Party Source Separation via Probabilistic Re-Synthesis

From the same author, two preprints using deep neural networks to perform a task that is traditionally performed in other domains such as communication/information theory (Error Correction) or advanced matrix factorization (BSS). Welcome to the great convergence:

Deep Transform: Time-Domain Audio Error Correction via Probabilistic Re-Synthesis by Andrew J.R. Simpson

In the process of recording, storage and transmission of time-domain audio signals, errors may be introduced that are difficult to correct in an unsupervised way. Here, we train a convolutional deep neural network to re-synthesize input time-domain speech signals at its output layer. We then use this abstract transformation, which we call a deep transform (DT), to perform probabilistic re-synthesis on further speech (of the same speaker) which has been degraded. Using the convolutive DT, we demonstrate the recovery of speech audio that has been subject to extreme degradation. This approach may be useful for correction of errors in communications devices.

Deep Transform: Cocktail Party Source Separation via Probabilistic Re-Synthesis by Andrew J.R. Simpson

In cocktail party listening scenarios, the human brain is able to separate competing speech signals. However, the signal processing implemented by the brain to perform cocktail party listening is not well understood. Here, we trained two separate convolutive autoencoder deep neural networks (DNN) to separate monaural and binaural mixtures of two concurrent speech streams. We then used these DNNs as convolutive deep transform (CDT) devices to perform probabilistic re-synthesis. The CDTs operated directly in the time-domain. Our simulations demonstrate that very simple neural networks are capable of exploiting monaural and binaural information available in a cocktail party listening scenario.

      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.

Thesis: Compressive Power Spectral Analysis by Dyonisius Ariananda

Compressive Power Spectral Analysis by Dyonisius Ariananda

At the heart of digital signal processing (DSP) are the sampling and quantization processes, which convert analog signals into discrete samples and which are implemented in the form of analog to digital converters (ADCs). In some recent applications, there is an increased demand for DSP applications to process signals having a very wide bandwidth. For such signals, the minimum allowable sampling rate is also very high and this has put a very high demand on the ADCs in terms of power consumption. Recently, the emergence of compressive sampling (CS) has offered a solution that allows us to reconstruct the original signal from samples collected from a sampling device operating at sub-Nyquist rate. The application of CS usually involves applying an additional constraint such as a sparsity constraint on the original signal. However, there are also applications where the signal to deal with has a high bandwidth (and thus sub-Nyquist rate sampling is still important) but where only the second-order statistics (instead of the original signal) are required to be reconstructed. In the latter case, depending on the characteristics of the signals, it might be possible to reconstruct the second-order statistics of the received analog signal from its sub-Nyquist rate samples without applying any additional constraints on the original signals. This idea is the key starting point of this thesis.

We first focus on time-domain wide-sense stationary (WSS) signals and introduce a method for reconstructing their power spectrum from their sub-Nyquist rate samples without requiring the signal or the power spectrum to be sparse. Our method is examined both in the time- and frequency-domain and the solution is computed using a simple least-squares (LS) approach, which produces a solution if the rank condition of the resulting system matrix is satisfied. To satisfy this rank condition, two options of sampling design are proposed, one of which is the so-called multi-coset sampling. It is show in this thesis that any of the so-called sparse ruler can produce a multi-coset sampling design that guarantees the full rank condition of the system matrix, and thus the optimal compression is achieved by a minimal sparse ruler.

While the approach in the previous paragraph is related to time-domain signals, we could extend the discussion about the power spectrum reconstruction from sub-Nyquist rate samples in the context of the spatial-domain signal, which is defined as a sequence of outputs of the antennas in the antenna array at a particular time instant. Given the compressed spatial domain signals, which are obtained from the output of a uniform linear array (ULA) with some antennas turned off, of particular interest is to reconstruct the angular power spectrum, from which the direction of arrival (DOA) of the sources can generally be located. In this thesis, a method to estimate the angular power spectrum and the DOA of possibly fully correlated sources based on second-order statistics of the compressed spatial-domain signals is proposed by employing a so-called dynamic array which is built upon the so-called underlying ULA. In this method, we present the spatial correlation matrices of the output of the dynamic active antenna arrays at all time slots as a linear function of the spatial correlation matrix of the entire underlying uniform array and we solve for this last correlation matrix using LS. The required theoretical condition to ensure the full column rank condition of the system matrix is formulated and designs are proposed to satisfy this condition.

Next, we consider both spatio-angular and time-frequency domains and propose a compressive periodogram reconstruction method as our next contribution. We introduce the multibin model, where the entire band is divided into equal-size bins such that the spectra at two frequencies or angles, whose distance is at least equal to the bin size, are uncorrelated. This model results in a circulant structure in the so-called coset correlation matrix, which enables us to introduce a strong compression. We propose the sampling patterns based on a circular sparse ruler to guarantee the full column rank condition of the system matrix and to allow the LS reconstruction of the periodogram. We also provide a method for the case when the bin size is reduced such that the spectra at two frequencies or angles, whose distance is larger than the bin size, can still be correlated.

To combine frequency and DOA processing, we also introduce a compressive two-dimensional (2D) frequency- and angular-domain power spectrum reconstruction for multiple uncorrelated time-domain WSS signals received from different sources by a linear array of antennas. We perform spatial-domain compression by deactivating some antennas in an underlying ULA and time-domain compression by multi-coset sampling.

Finally, we propose a compressive cyclic spectrum reconstruction approach for wide-sense cyclostationary (WSCS) signals, where we consider sub-Nyquist rate samples produced by non-uniform sampling. This method is proposed after first observing that the block Toeplitz structure emerges in theWSCS signal correlation matrix. This structure is exploited to solve the WSCS signal correlation matrix by LS. The condition for the system matrix to have full column rank is provided and some possible non-uniform sampling designs to satisfy this full column rank condition are presented.

Based on all the works that have been done, we have found that focusing on reconstructing the statistical measure of the received signals has significantly relax the sampling requirements and the constraints on both the statistics and the signals themselves. Hence, we would like to conclude that, for given tasks of applications in hand, we should ask ourselves whether statistical measure reconstruction is sufficient since the answer for this question will likely to determine how we should collect the data from the observed phenomena. This underlines the importance of awareness on what kind of information is necessary and sufficient for the tasks in hand before conducting the sensing/sampling process.

    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.

Real-time Dynamic MRI Reconstruction using Stacked Denoising Autoencoder

Great convergence, here we come ! From the paper:

The dataset contains about 17424 volumes; and multiple slices in each volume. In total we have used about 100,000 images for training the SDAE's...Unfortunately, for these datasets, the fully sampled k-space scans are not available. Therefore the reconstruction results obtained from [8] is taken as the basis images for comparison.

Using time dependent images reconstructed from some unknown algorithm and comparing it with the temporal reconstruction capability of Deep Neural Networks is a first step and it may set the comparison with a CS reconstruction in an unfair light. But the next step ought to be obvious :-) Thank you Angshul for this provocative preprint (provocative because deep neural nets have very little theory associated with them whereas there is more of it for compressive sensing and MRI)

Real-time Dynamic MRI Reconstruction using Stacked Denoising Autoencoder by Angshul Majumdar

In this work we address the problem of real-time dynamic MRI reconstruction. There are a handful of studies on this topic; these techniques are either based on compressed sensing or employ Kalman Filtering. These techniques cannot achieve the reconstruction speed necessary for real-time reconstruction. In this work, we propose a new approach to MRI reconstruction. We learn a non-linear mapping from the unstructured aliased images to the corresponding clean images using a stacked denoising autoencoder (SDAE). The training for SDAE is slow, but the reconstruction is very fast - only requiring a few matrix vector multiplications. In this work, we have shown that using SDAE one can reconstruct the MRI frame faster than the data acquisition rate, thereby achieving real-time reconstruction. The quality of reconstruction is of the same order as a previous compressed sensing based online reconstruction technique.

    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.

Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty

This is very interesting. In the area of sparsity seeking solvers M-SBL is with AMP one of the interesting solvers to follow. This is in part due to the good results Zhilin Zhang got with block sparsity and non sparse signals in the past.The authors of the following paper change the regularization term of that algorithm and seem to have even better phase transitions for sparse signals. Without further ado:

Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty by Jong Chul Ye, Jong Min Kim, Yoram Bresler

The multiple measurement vector problem (MMV) is a generalization of the compressed sensing problem that addresses the recovery of a set of jointly sparse signal vectors. One of the important contributions of this paper is to reveal that the seemingly least related state-of-art MMV joint sparse recovery algorithms - M-SBL (multiple sparse Bayesian learning) and subspace-based hybrid greedy algorithms - have a very important link. More specifically, we show that replacing the $\log\det(\cdot)$ term in M-SBL by a rank proxy that exploits the spark reduction property discovered in subspace-based joint sparse recovery algorithms, provides significant improvements. In particular, if we use the Schatten-$p$ quasi-norm as the corresponding rank proxy, the global minimiser of the proposed algorithm becomes identical to the true solution as $p \rightarrow 0$. Furthermore, under the same regularity conditions, we show that the convergence to a local minimiser is guaranteed using an alternating minimization algorithm that has closed form expressions for each of the minimization steps, which are convex. Numerical simulations under a variety of scenarios in terms of SNR, and condition number of the signal amplitude matrix demonstrate that the proposed algorithm consistently outperforms M-SBL and other state-of-the art algorithms. 

I wonder how that change of the regularization proxy would change Zhilin's codes

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.

LiSens, Photometric stereo using BRDF dictionaries, CS-MUVI

Aswin Sankaranarayanan just let me know of the following papers:

Hi Igor
Hope you are well.

I wanted to point out a few recent papers.


1) LiSens http://arxiv.org/abs/1503.04267

This paper describes a multi-pixel extension to the single pixel camera. We show that it is possible to obtain videos at spatial resolution of nearly mega-pixel resolution and at 10 frames-per-second using a sensor array with 1000s of pixel.

2) Photometric stereo using BRDF dictionaries. http://arxiv.org/abs/1503.04265

This paper is on shape estimation of non-Lambertian objects. While not mainstream CS work, at the heart of this work is a bilinear problem that we solve using some interesting techniques.

3) CS-MUVI (journal version) http://arxiv.org/abs/1503.02727

This paper uses motion-flow models for video CS using the single-pixel camera. We demonstrate many results on real data obtained from our lab prototype. This is the extended version of a conference publication in 2012.

Both LiSens and the photometric stereo work will appear in the proceedings of Intl. conf. computational photography (ICCP), 2015.

Am hoping this will be interesting to you and the broader nuit-blanche readership. 

Outstanding ! thanks Aswin

LiSens --- A Scalable Architecture for Video Compressive Sensing by Jian Wang, Mohit Gupta, Aswin C. Sankaranarayanan

The measurement rate of cameras that take spatially multiplexed measurements by using spatial light modulators (SLM) is often limited by the switching speed of the SLMs. This is especially true for single-pixel cameras where the photodetector operates at a rate that is many orders-of-magnitude greater than the SLM. We study the factors that determine the measurement rate for such spatial multiplexing cameras (SMC) and show that increasing the number of pixels in the device improves the measurement rate, but there is an optimum number of pixels (typically, few thousands) beyond which the measurement rate does not increase. This motivates the design of LiSens, a novel imaging architecture, that replaces the photodetector in the single-pixel camera with a 1D linear array or a line-sensor. We illustrate the optical architecture underlying LiSens, build a prototype, and demonstrate results of a range of indoor and outdoor scenes. LiSens delivers on the promise of SMCs: imaging at a megapixel resolution, at video rate, using an inexpensive low-resolution sensor.

A Dictionary-based Approach for Estimating Shape and Spatially-Varying Reflectance  by Zhuo Hui, Aswin C. Sankaranarayanan

We present a technique for estimating the shape and reflectance of an object in terms of its surface normals and spatially-varying BRDF. We assume that multiple images of the object are obtained under fixed view-point and varying illumination, i.e, the setting of photometric stereo. Assuming that the BRDF at each pixel lies in the non-negative span of a known BRDF dictionary, we derive a per-pixel surface normal and BRDF estimation framework that requires neither iterative optimization techniques nor careful initialization, both of which are endemic to most state-of-the-art techniques. We showcase the performance of our technique on a wide range of simulated and real scenes where we outperform competing methods.  

Video Compressive Sensing for Spatial Multiplexing Cameras using Motion-Flow Models by Aswin C. Sankaranarayanan, Lina Xu, Christoph Studer, Yun Li, Kevin Kelly, Richard G. Baraniuk

Spatial multiplexing cameras (SMCs) acquire a (typically static) scene through a series of coded projections using a spatial light modulator (e.g., a digital micro-mirror device) and a few optical sensors. This approach finds use in imaging applications where full-frame sensors are either too expensive (e.g., for short-wave infrared wavelengths) or unavailable. Existing SMC systems reconstruct static scenes using techniques from compressive sensing (CS). For videos, however, existing acquisition and recovery methods deliver poor quality. In this paper, we propose the CS multi-scale video (CS-MUVI) sensing and recovery framework for high-quality video acquisition and recovery using SMCs. Our framework features novel sensing matrices that enable the efficient computation of a low-resolution video preview, while enabling high-resolution video recovery using convex optimization. To further improve the quality of the reconstructed videos, we extract optical-flow estimates from the low-resolution previews and impose them as constraints in the recovery procedure. We demonstrate the efficacy of our CS-MUVI framework for a host of synthetic and real measured SMC video data, and we show that high-quality videos can be recovered at roughly 60× compression.

  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.

Python version of SPGL1 - implementation -

David Relyea just let me know of his porting the famous SPGL1 solver to Python, woohoo !

Hi Igor,


I've entirely ported the Matlab version of SPGL1 to python. It has full functionality (it heavily leverages numpy) and I haven't caught any bugs in it at all, so I'm letting everyone know. I got the ok from Michael Friedlander to distribute it (under the same license, of course). It's at https://github.com/drrelyea/SPGL1_python_port. Please let people know!

I also intend to clean it up a bit and have it added to scikit-learn, as it's the fastest L1 solver I know of that can handle complex numbers.


All the best,


David Relyea 

Thanks David !

  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.

Sunday Morning Insight: Muon Tomography of Fukushima Daiichi's reactor #1

Here is a followup to a previous Sunday Morning Insight (Muon Tomography as a Moore's Law Enabled Technology). I took notice of it on Rod Adams twitter feed: The result of a 26-day Muon Tomography study of Fukushima Daiichi reactor 1. The report is entitled: Reactor imaging technology for fuel debris detection by cosmic ray muon Measurement status report in Unit-1 and features a two angle tomography of reactor #1 and the attendant Spent Fuel Pool in that same building.

Several remarks:

• The detectors are not low enough to image the reactor material where it probably is (i.e. at the bottom of the Pressure Containment Vessel).
• There is a discrepancy between the readings of detector 1 and 2. It seems to my untrained eye that this may have to do with detector 1 having a line of sight that includes the spent fuel pool whereas detector 2 has less contribution from that component. The reconstruction algorithm using readings from detector 1 might be putting more emphasis from the higher density of material in the spent fuel than contribution from the reactor core.
• The algorithm performing the reconstruction does not seem to be using the scattering component as featured in Imaging Damaged Reactors and Volcanoes, Let us note that 26 days is the same ballpark as the 6 weeks mentioned in that study.

Relevant: Sunday Morning Insight: Muon Tomography as a Moore's Law Enabled Technology

    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.

Saturday Morning Video: The Automatic Statistician, Certifying and removing Disparate Impact, Machine Learning et Entreprise

Here is the video and attendant slides of the Paris Machine Learning Meetup #7 Season 2. I am providing the links that start directly at the beginning of each talk.

• The Automatic Statistician, Zoubin Ghahramani, Cambridge University, 
• site: The Automatic Statistician 
• Video in English at 30m50s)
• Certifying and removing Disparate Impact, Suresh Venkatasubramanian,University of Utah and Sorelle Friedler, Haverford College, 
• Site: Computational Fairness  
• Video in English at 5m28s
• Machine Learning et Entreprise , Francois-Xavier Rousselot 
• Video in French at  1h16m )

All the slides and videos of the previous Paris Machine Learning Meetups are available here.

  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.

Around The Blogs in 78 Hours

We got pre-selected into the iLab competition, woohoo !

Ben Lorica just wrote about tensors in Let’s build open source tensor libraries for data science . One of the author whose work was featured in that blog, Anima Anandkumar, kindly responded to one of my comment there:

 ...Indeed, there are many types of decompositions on tensors, we are certainly not the only ones to be working on them. The paper you point out about tensors states that there can be ill-posed tensors, which is true. In fact, there is another paper which states that most tensor problems are NP-hard http://arxiv.org/abs/0911.1393 However, the tensors we study, which are relevant for machine learning, turn out to be "easy cases" establish is that under some very reasonable non-degeneracy. I talk about some of these points in the podcast that Ben will post in due course. Stay tuned!

I look forward to the podcast 

Within the blogs we generally cover, here are some items that grabbed my interest:

 Sebastien

• Deep stuff about deep learning?

Djalil

• Entropy ubiquity

John

• A subtle way to over-fit

Charles

• Convex Relaxations of Transductive Learning
• Why does Deep Learning work?

Afonso

• Optimizing in smooth waters: optimization on manifolds

Dirk

• Farewell Ernie Esser

Ben

• How Digital Light Processing (DLP) works

While on Nuit Blanche, we had:

• Infinite-dimensional $\ell^1$ minimization and function approximation from pointwise data
• Devising Measurement Matrices
• On aurait pu regarder l'éclipse à Paris ....
• Single and multiple snapshot compressive beamforming
• Thesis: Spectral classification using convolutional neural networks, Pavel Hála - implementation -
• Everybody wants to be shallow: Compact Nonlinear Maps and Circulant Extensions
• Meeting: missDATA 2015, Rennes, Brittany, France
• Enhanced Image Classification With a Fast-Learning Shallow Convolutional Neural Network
• Adaptive-Rate Sparse Signal Reconstruction With Application in Compressive Background Subtraction
• DECOPT - DEcomposition Convex OPTimization - implementation -
• Variational Inference for Sparse Spectrum Approximation in Gaussian Process Regression -implementation -
• Slides: Stanford's CS231n: Convolutional Neural Networks for Visual Recognition
• Saturday Morning Videos: Nando de Freitas' Machine Learning course (Lecture 7 to 12) and slides
• Various Announcements
• High-resolution and broadband all-fiber spectrometers
• Learning Co-Sparse Analysis Operators with Separable Structures
• No Pressure
• VLSI Design of a Monolithic Compressive-Sensing Wideband Analog-to-Information Converter (and other FPGA implementations)
• Ce soir / Tonight : Paris Machine Learning Meetup #7 Season 2: Automatic Statistician, ML et Entreprise, Algo Fairness/ Certifying and removing Disparate Impact
• Ernie Esser's Passing and Legacy
• Slides: Learning Sparse Representations for Signal Processing @IISc
• A new Highly technical Reference Page: The Superiorization Methodology and Perturbation Resilience of Algorithms
• Sunday Morning Insight: Another Strange PSF in the Wild
• Saturday Morning Videos: February Fourier Talks 2015 Proceedings
• Video (and attendant code): A 3D Map of the Human Genome
• Around the blogs: The great Convergence in Action
• Video: Rambus Lensless Smart Sensor Demo at MWC 2015
• Phase Transitions in Sparse PCA
• Sparse Coding: 20 years later
• Thesis: Gravimetric Anomaly Detection using Compressed Sensing by Ryan Kappedal
• Nuit Blanche in Review ( February 2015 )

    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.

Infinite-dimensional $\ell^1$ minimization and function approximation from pointwise data

Infinite-dimensional $\ell^1$ minimization and function approximation from pointwise data by Ben Adcock

We consider the problem of approximating a function from finitely-many pointwise samples using $\ell^1$ minimization techniques. In the first part of this paper, we introduce an infinite-dimensional approach to this problem. Three advantages of this approach are as follows. First, it provides interpolatory approximations in the absence of noise. Second, it does not require a priori bounds on the expansion tail in order to be implemented. In particular, the truncation strategy we introduce as part of this framework is completely independent of the function being approximated. Third, it allows one to explain the crucial role weights play in the minimization, namely, that of regularizing the problem and removing so-called aliasing phenomena. In the second part of this paper we present a worst-case error analysis for this approach. We provide a general recipe for analyzing the performance of such techniques for arbitrary deterministic sets of points. Finally, we apply this recipe to show that weighted $\ell^1$ minimization with Jacobi polynomials leads to an optimal, convergent method for approximating smooth, one-dimensional functions from scattered data.

    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.

Devising Measurement Matrices

 Figure from Volkan Cevher's Lions labs

The following four preprints feature different ways to build measurement matrices for compressive sensing (or related) purposes:

Nonadaptive group testing with random set of defectives via constant-weight codes by Arya Mazumdar 

In a group testing scheme, set of tests are designed to identify a small number $t$ of defective items that are present among a large number $N$ of items. Each test takes as input a group of items and produces a binary output indicating whether any defective item is present in the group. In this paper we consider the nonadaptive scenario where defective items are random and follow simple probability distributions. In particular we consider the cases where 1) each item can be defective independently with probability $\frac{t}{N}$ and 2) each $t$-set of items can be defective with uniform probability. In both cases our aim is to design a testing matrix that successfully identifies the set of defectives with high probability. Both of these models have been studied in the literature before and it is known that $O(t\log N)$ tests are necessary as well as sufficient (via random coding) in both cases. Our main focus is explicit deterministic construction of the test matrices amenable to above scenarios. One of the most popular ways of constructing test matrices relies on constant-weight error-correcting codes and their minimum distance. In particular, it is known that codes result in test matrices with $O(t^2 \log N)$ rows that identify any $t$ defectives. With our relaxed requirements, we show that using an explicit constant-weight code we may achieve a number of tests equal to $O(t \log^2 N/ \log t)$ for the first case and $O(t^{3/2} \log^{3/2} N/\log t)$ for the second case. While still away by a factor of $\frac{\log N}{\log t}$ and $\frac{\sqrt{t\log N}}{\log t}$ respectively from the optimal number of tests, one may note that our constructions are deterministic and the main contribution lies in relating the group testing properties to parameters of constant-weight codes.

Linear-time list recovery of high-rate expander codes by Brett Hemenway, Mary Wootters

We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have been useful recently in constructing efficiently list-decodable codes, as well as explicit constructions of matrices for compressive sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate $1 - \epsilon$ for any $\epsilon > 0$. We can plug our high-rate codes into a construction of Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates, which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code. While list-recovery is interesting on its own, our primary motivation is applications to list-decoding. A slight strengthening of our result would implies linear-time and optimally list-decodable codes for all rates, and our work is a step in the direction of solving this important problem.

Deterministic construction of sparse binary and ternary matrices from existing binary sensing matrices by Pradip Sasmal, R. Ramu Naidu, C. S. Sastry, P. V. Jampana 

In the present work, we discuss a procedure for constructing sparse binary and ternary matrices from existing two binary sensing matrices. The matrices that we construct have several attractive properties such as smaller density, which supports algorithms with low computational complexity. As an application of our method, we show that a CS matrix of general row size different from $p, p^2, pq$ (for different primes $p,q$) can be constructed.

A new method on deterministic construction of the measurement matrix in compressed sensing by Qun Mo 

Construction on the measurement matrix $A$ is a central problem in compressed sensing. Although using random matrices is proven optimal and successful in both theory and applications. A deterministic construction on the measurement matrix is still very important and interesting. In fact, it is still an open problem proposed by T. Tao. In this paper, we shall provide a new deterministic construction method and prove it is optimal with regard to the mutual incoherence.

  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.

On aurait pu regarder l'éclipse à Paris ....

This is a rant in French (translation in English below)

Le rectorat de Paris a décider d'interdire purement et simplement les sorties et les récréations demain pendant l'éclipse. C'est dommage, on aurait pu utiliser ces deux heures pour:

• expliquer aux enfant qu'il ne faut jamais regarder le soleil dans les yeux que cela soit pendant une éclipse ou avant ou après.
• expliquer aux enfants qu'il n'y a pas besoin d'être dépendant de journaux qui vendent des lunettes appropriées car on peut regarder l'éclipse par projection avec une passoire sur le mode de camera obscura. Il suffit d'une passoire ou d'un bout de papier avec un trou dedans (ou plus). On peut aussi regarder le soleil sur le sol quand il est passé par des feuillages. On peut aussi voir le soleil tout les jours sans les nuages.
• expliquer aux enfants que justement ces cameras obscura sont les premiers moyens de créer une image depuis l'antiquité et que la photographie est née en France. Que la première photo au monde a été faite ici.
• s'amuser à expliquer que la France a open sourcer le brevet de la photographie pour le monde entier dans l'intérêt de l'humanité ... sauf pour l'Angleterre.
• expliquer que le soleil est une étoile.

....mais on l'a pas fait. 

« View from the Window at Le Gras, Joseph Nicéphore Niépce » par Joseph Nicéphore Niépce — Rebecca A. Moss, Coordinator of Visual Resources and Digital Content Library, via email. College of Liberal Arts Office of Information Technology, University of Minnesota. http://www.dcl.umn.edu. Sous licence Domaine public via Wikimedia Commons.

The Paris school district has decided a ban on outdoors activities for kids (including recess) tomorrow during the eclipse. It's a shame we could have used those two hours:

• to explain to the kids that they should never look directly at the Sun during an eclipse or before or after.to explain to the kids that there is no need to be dependent on newspapers that sell appropriate glasses for the event because you can watch the eclipse as a projection in a camera obscura mode. Use a sieve or a piece of paper with a (or more) hole in it and look down.
• to explain to children that these cameras obscura were the first means to create an image in ancient times and that photography was born in France. The first picture in the world was made here.
• to have fun in explaining that France open sourced the patent of photography in the interest of humanity to the rest of the world except for England where you had to get a special licence to use that process.
• to explain that the Sun is a star.

But we didn't.

  credit photo: Solar eclipse 2005 seen through the leaves of a tree. Source http://www.flickr.com/photos/juanjaen/49068696/Author juanjaen DateOctober 3, 2005 License cc-by-sa-2.0
  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.

Single and multiple snapshot compressive beamforming

Single and multiple snapshot compressive beamforming by Peter Gerstoft, Angeliki Xenaki, Christoph F. Mecklenbräuker

For a sound field observed on a sensor array, compressive sensing (CS) reconstructs the direction-of-arrivals (DOAs) of multiple sources using a sparsity constraint. The DOA estimation is posed as an underdetermined problem expressing the acoustic pressure at each sensor as a phase-lagged superposition of source amplitudes at all hypothetical DOAs. Regularizing with an $\ell_1$-norm constraint renders the problem solvable with convex optimization, while promoting sparsity resulting in high-resolution DOA maps. Here, the sparse source distribution is derived using maximum a posteriori estimates for both single and multiple snapshots. CS does not require inversion of the data covariance matrix and thus works well even for a single snapshot resulting in higher resolution than conventional beamforming. For multiple snapshots, CS outperforms conventional high-resolution methods, even with coherent arrivals and at low signal-to-noise ratio. The superior resolution of CS is demonstrated with vertical array data from the SWellEx96 experiment for coherent multi-paths.

    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.