Page Views on Nuit Blanche since July 2010







Please join/comment on the Google+ Community (1454), the CompressiveSensing subreddit (749),
the LinkedIn Compressive Sensing group (3248) or the Advanced Matrix Factorization Group (1017)

Tuesday, March 31, 2015

Nuit Blanche in Review ( March 2015 )

 
Two theses
A few insights from deep architectures
and some from compressive sensing:

 Around the blogs
Meetings

 Slides/courses

Videos:
 Other:

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.

Monday, March 30, 2015

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






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.

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.

Friday, March 27, 2015

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 in other domain such as communication/information theory (Error Correction) or advanced matrix factorization (BSS). Welcome to the great convergence:

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.

Thursday, March 26, 2015

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.

Wednesday, March 25, 2015

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.

Tuesday, March 24, 2015

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.

Monday, March 23, 2015

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, March 22, 2015

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.

Printfriendly