FrameSense: Near-Optimal Sensor Placement for Linear Inverse Problems / Acoustic echoes reveal room shape - implementation -

Juri  just sent me the following:

Dear Igor,

I follow your blog since I was working on my MSc thesis in 2009 and I always appreciated your efforts to spread news and interesting works related to CS and sparse signal processing.

.... I would like to point out a couple of recent results obtained in my lab that are of possible interest for the readers of your blog:

1) The first one, talks about an algorithm for near-optimal sensor placement to solve a linear inverse problem. It has some interesting similarities with CS and it is the first algorithm that has guaranteed performance w.r.t. MSE. It can be also viewed as the selection of $L$ out of $N$ rows of a matrix $\Psi$, such that the spectrum of $\Psi*\Psi$ has some favorable properties.

http://infoscience.epfl.ch/record/186804

2) This one just appeared on PNAS and is getting a big media coverage. It is about recovering the shape of a room using a set of microphones. You have already in the past talked about this work, when you featured an ICASSP paper wrote by Dokmanic et al. This journal paper has stronger results and shows some results obtained in a couple of real-word experiments.

http://www.pnas.org/content/early/2013/06/12/1221464110.abstract

Best,

Juri Ranieri

Thanks Juri , the second paper got some press, it even made the front page of Reddit. What is fascinating in this thread is the variety of comments and how many people mistakenly think  this is not news. The second insight here is that when I am being asked what a sensor is, that question is invariably limited to one sensor while even small sensor network have the possibility of providing much more information. Here are the two papers:

Near-Optimal Sensor Placement for Linear Inverse Problems

Ranieri, Juri, Chebira, Amina, Vetterli, Martin

A classic problem is the estimation of a set of parameters from measurements collected by few sensors. The number of sensors is often limited by physical or economical constraints and their placement is of fundamental importance to obtain accurate estimates. Unfortunately, the selection of the optimal sensor locations is intrinsically combinatorial and the available approximation algorithms are not guaranteed to generate good solutions in all cases of interest. We propose FrameSense, a greedy algorithm for the selection of optimal sensor locations. The core cost function of the algorithm is the frame potential, a scalar property of matrices that measures the orthogonality of its rows. Notably, FrameSense is the first algorithm that is near-optimal in terms of mean square error, meaning that its solution is always guaranteed to be close to the optimal one. Moreover, we show with an extensive set of numerical experiments that FrameSense achieves the state-of-the-art performance while having the lowest computational cost, when compared to other greedy methods.

Acoustic echoes reveal room shape
Ivan Dokmanića, Reza Parhizkara, Andreas Walthera, Yue M. Lub, and Martin Vetterlia

Imagine that you are blindfolded inside an unknown room. You snap your fingers and listen to the room’s response. Can you hear the shape of the room? Some people can do it naturally, but can we design computer algorithms that hear rooms? We show how to compute the shape of a convex polyhedral room from its response to a known sound, recorded by a few microphones. Geometric relationships between the arrival times of echoes enable us to “blindfoldedly” estimate the room geometry. This is achieved by exploiting the properties of Euclidean distance matrices. Furthermore, we show that under mild conditions, first-order echoes provide a unique description of convex polyhedral rooms. Our algorithm starts from the recorded impulse responses and proceeds by learning the correct assignment of echoes to walls. In contrast to earlier methods, the proposed algorithm reconstructs the full 3D geometry of the room from a single sound emission, and with an arbitrary geometry of the microphone array. As long as the microphones can hear the echoes, we can position them as we want. Besides answering a basic question about the inverse problem of room acoustics, our results find applications in areas such as architectural acoustics, indoor localization, virtual reality, and audio forensics.

The attendant code to duplicate the result of this study is 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.

Different Sensing Modalities: Compressive Object Tracking using Entangled Photons, Coded aperture, Single-pixel digital "ghost" holography, CT, MRI and ... faster cats

So that now we have a clearer view of sensing modalities [1], here are some examples that showed up on our collective radar screen in the past month:

The first one is akin to functional compressive sensing of the type: Hx = N(Ax). There, we are not interested in image reconstruction but rather the reconstruction of a specific item in a series of measurements (the moving objects). 

Compressive Object Tracking using Entangled Photons

Omar S. Magaña-Loaiza, Gregory A. Howland, Mehul Malik, John C. Howell, Robert W. Boyd

We present a compressive sensing protocol that tracks a moving object by removing static components from a scene. The implementation is carried out on a ghost imaging scheme to minimize both the number of photons and the number of measurements required to form a quantum image of the tracked object. This procedure tracks an object at low light levels with fewer than 3% of the measurements required for a raster scan, permitting us to more effectively use the information content in each photon.

Next, we have the typical indirect imaging of the coded aperture of X-ray observatories ( x = L(Ax) ). Let us note the reference to potential use of compressive sensing. It is just a question of time before they come to our side of the Force.

Simultaneous analysis of large INTEGRAL/SPI datasets: optimizing the computation of the solution and its variance using sparse matrix algorithms
L. Bouchet, P. Amestoy, A. Buttari, F.-H. Rouet, M. Chauvin

Nowadays, analyzing and reducing the ever larger astronomical datasets is becoming a crucial challenge, especially for long cumulated observation times. The INTEGRAL/SPI X-gamma-ray spectrometer is an instrument for which it is essential to process many exposures at the same time in order to increase the low signal-to-noise ratio of the weakest sources. In this context, the conventional methods for data reduction are inefficient and sometimes not feasible at all. Processing several years of data simultaneously requires computing not only the solution of a large system of equations, but also the associated uncertainties. We aim at reducing the computation time and the memory usage. Since the SPI transfer function is sparse, we have used some popular methods for the solution of large sparse linear systems; we briefly review these methods. We use the Multifrontal Massively Parallel Solver (MUMPS) to compute the solution of the system of equations. We also need to compute the variance of the solution, which amounts to computing selected entries of the inverse of the sparse matrix corresponding to our linear system. This can be achieved through one of the latest features of the MUMPS software that has been partly motivated by this work. In this paper we provide a brief presentation of this feature and evaluate its effectiveness on astrophysical problems requiring the processing of large datasets simultaneously, such as the study of the entire emission of the Galaxy. We used these algorithms to solve the large sparse systems arising from SPI data processing and to obtain both their solutions and the associated variances. In conclusion, thanks to these newly developed tools, processing large datasets arising from SPI is now feasible with both a reasonable execution time and a low memory usage.

Next we have some interesting phase retrieval imaging of the type: x = N2(N1(x)) 

Single-pixel digital "ghost" holography

Pere Clemente, Vicente Duran, Enrique Tajahuerce, Victor Torres-Company, Jesus Lancis

Since its discovery, the "ghost" diffraction phenomenon has emerged as a non-conventional technique for optical imaging with very promising advantages. However, extracting intensity and phase information of a structured and realistic object remains a challenge. Here, we show that a "ghost" hologram can be recorded with a single-pixel configuration by adapting concepts from standard digital holography. The presented homodyne scheme enables phase imaging with nanometric depth resolution, three-dimensional focusing ability, and shows high signal-to-noise ratio.

Here again we have sensing of the type: Hx = N(Ax)

In-vivo magnetic resonance imaging of hyperpolarized silicon particles

M. C. Cassidy, H. R. Chan, B. D. Ross, P. K. Bhattacharya, C. M. Marcus

Silicon-based micro and nanoparticles have gained popularity in a wide range of biomedical applications due to their biocompatibility and biodegradability in-vivo, as well as a flexible surface chemistry, which allows drug loading, functionalization and targeting. Here we report direct in-vivo imaging of hyperpolarized 29Si nuclei in silicon microparticles by MRI. Natural physical properties of silicon provide surface electronic states for dynamic nuclear polarization (DNP), extremely long depolarization times, insensitivity to the in-vivo environment or particle tumbling, and surfaces favorable for functionalization. Potential applications to gastrointestinal, intravascular, and tumor perfusion imaging at sub-picomolar concentrations are presented. These results demonstrate a new background-free imaging modality applicable to a range of inexpensive, readily available, and biocompatible Si particles.

and some indirect imaging of the type: x = N(Ax)

Automatic Calibration Method of Voxel Size for Cone-beam 3D-CT Scanning System

Min Yang, Xiaolong Wang, Yipeng Liu, Fanyong Men, Xingdong Li, Wenli Liu, Dongbo Wei

For cone-beam three-dimensional computed tomography (3D-CT) scanning system, voxel size is an important indicator to guarantee the accuracy of data analysis and feature measurement based on 3D-CT images. Meanwhile, the voxel size changes with the movement of the rotary table along X-ray direction. In order to realize the automatic calibration of the voxel size, a new easily-implemented method is proposed. According to this method, several projections of a spherical phantom are captured at different imaging positions and the corresponding voxel size values are calculated by non-linear least square fitting. Through these interpolation values, a linear equation is obtained, which reflects the relationship between the rotary table displacement distance from its nominal zero position and the voxel size. Finally, the linear equation is imported into the calibration module of the 3D-CT scanning system, and when the rotary table is moving along X-ray direction, the accurate value of the voxel size is dynamically exported. The experimental results prove that this method meets the requirements of the actual CT scanning system, and has virtues of easy implementation and high accuracy

There is a nice presentation on deep learning where you can read about sparse autoencoders: Deep Learning for NLP (without Magic) by Richard Socher and Christopher Manning

ABSTRACT
Machine learning is everywhere in today's NLP, but by and large machine learning amounts to numerical optimization of weights for human designed representations and features. The goal of deep learning is to explore how computers can take advantage of data to develop features and representations appropriate for complex interpretation tasks. This tutorial aims to cover the basic motivation, ideas, models and learning algorithms in deep learning for natural language processing. Recently, these methods have been shown to perform very well on various NLP tasks such as language modeling, POS tagging, named entity recognition, sentiment analysis and paraphrase detection, among others. The most attractive quality of these techniques is that they can perform well without any external hand-designed resources or time-intensive feature engineering. Despite these advantages, many researchers in NLP are not familiar with these methods. Our focus is on insight and understanding, using graphical illustrations and simple, intuitive derivations. The goal of the tutorial is to make the inner workings of these techniques transparent, intuitive and their results interpretable, rather than black boxes labeled "magic here". The first part of the tutorial presents the basics of neural networks, neural word vectors, several simple models based on local windows and the math and algorithms of training via backpropagation. In this section applications include language modeling and POS tagging. In the second section we present recursive neural networks which can learn structured tree outputs as well as vector representations for phrases and sentences. We cover both equations as well as applications. We show how training can be achieved by a modified version of the backpropagation algorithm introduced before. These modifications allow the algorithm to work on tree structures. Applications include sentiment analysis and paraphrase detection. We also draw connections to recent work in semantic compositionality in vector spaces. The principle goal, again, is to make these methods appear intuitive and interpretable rather than mathematically confusing. By this point in the tutorial, the audience members should have a clear understanding of how to build a deep learning system for word-, sentence- and document-level tasks. The last part of the tutorial gives a general overview of the different applications of deep learning in NLP, including bag of words models. We will provide a discussion of NLP-oriented issues in modeling, interpretation, representational power, and optimization.

Finally, Andrew Ng let us know we can perform the sparse autoencoder of the type x = N4(N3(N2(N1(x)))) that produced the cat experiment with off the shelf computer gear (COTS) in Deep learning with COTS HPC systems by Adam Coates, Brody Huval , Tao Wang , David J. Wu , Andrew Ng

Scaling up deep learning algorithms has been shown to lead to increased performance in benchmark tasks and to enable discovery of complex high-level features. Recent e orts to train extremely large networks (with over 1 billion parameters) have relied on cloud-like computing infrastructure and thousands of CPU cores. In this paper, we present technical details and results from our own system based on Commodity O -The-Shelf High Performance Computing (COTS HPC) technology: a cluster of GPU servers with In niband interconnects and MPI. Our system is able to train 1 billion parameter networks on just 3 machines in a couple of days, and we show that it can scale to networks with over 11 billion parameters using just 16 machines. As this infrastructure is much more easily marshaled by others, the approach enables much wider-spread research with extremely large neural networks.

[1] A Quick Panorama of Sensing from Direct Imaging to Machine Learning



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: A Quick Panorama of Sensing from Direct Imaging to Machine Learning

What is a sensor and how does sensing fit with Machine Learning ?  This is a common question that I think arise out of the fact that our fields are becoming too specific thereby attenuating our common sense of what the big picture entails. Be forewarned, the following brief exposition will be making numerous shortcuts and abuse of notation.

Everything starts with the simple notion that what you see is what you get:

x = x

In other words, on one side, you have x and on the other you "sense" x. This picture applies directly to what we call direct imaging: if you want to image something, you have to just sample it. A more mathy expression for this process is the simple:

x = I x

where I is the identity (yes, let's talk about matrices or operators when the explanation requires it.) Let us note that sometimes, when we remove certain rows from I by applying a restriction operator R, then we are undersampling. Reconstructing the full x from that subsampled version (RIx) is called interpolation or inpainting. Let us call IN that inpainting operator so that we have:

x = IN (R(Ix)) 

So far so good. Let us also note that in optics we generally do the following:

x = (BA) x

(BA) generally represents the lenses of the camera. In other words, the engineering behind lens design (using tools like Zemax) is geared towards designing BA (also called the PSF) to be as close as possible to I, the identity. The sensor or the measurement process obtains (BA)x. Both A and B are linear operators. The process is actually a little more complex see [1].

credit NASA

Then there is the case of indirect imaging as attempted since the early 1960s with coded aperture for instance. 

x = L(Ax)

L and A are linear operators. The sensors can only measure Ax (not x) but you are a matrix multiplication away from getting x back. Famous examples include coded aperture for X-ray imaging for orbital observatories, but also CT and MRI.  Encryption also fits that model.

Credit: Rice University

With compressive sensing, things get a little more complicated, it is indirect imaging but with a twist. There we have

x = N(Ax) or even x = N(A(Bx))

with A or A and B are linear operators, x is sparse (or compressible) in the canonical basis or in some other bases, N is a nonlinear operator. Here, as in indirect imaging, what is sensed is Ax or A(Bx). The difference between this new approach and traditional indirect imaging lies the nonlinearity of the reconstruction operator N. In compressive sensing, we seek a rectangular A (subsampling) and the nonlinearity of the N comes from the fact that we seek only sparse x's. Historically, N was initially tied to linear convex programming or greedy methods, but there are other different approaches such as IHT and eventually AMP. Additional insight can be found in [2].

Muthu (see [3]) points out that there ought to be other quantities we could extract from a linear sensing mechanism so that instead of:

x = N(Ax)

we ought to look at:

Hx = N(Ax)

The sensor obtains Ax, N is a nonlinear reconstruction solver of sorts that reconstruct Hx which is  an hopefully important feature of x (in compressive sensing, that feature is the sparsity pattern of x). Instead of the full reconstruction, we aim at detecting items of interest. In optics we sometimes talk about task specific imagers or detection of features in manifold signal processing, in MRI, we call it fingerprinting while in Theoretical Computer Science, we are concerned about the statistics of x since in the streaming model, we cannot even store x. There the process goes by the name of Heavy Hitters and related algorithms. It looks like homomorphic encryption would fit that model. One could also argue that current conventional direct imaging also falls in that category. (see [1]) 

Now let us go further by making the first sensing operator a nonlinear one. This is the approach that is typically seen in nonlinear compressive sensing and also in machine learning. There we have:

x = N2(N1(x))

from the Unsupervised Feature Learning and Deep Learning tutorial

In machine learning, in particular, with neural networks, we have:

x = N4(N3(N2(N1(x))))

This sort of very successful construct is known as autoencoders in deep learning. Each operator N is nonlinear. A specific choice of regularization for the layers and nodes can even make it look like a compressive sensing approach. In this case. we talk about sparse autoencoders, i.e. roughly speaking , there is sparse set of weights for every images that are part of the training set on which the neural network was trained. In traditional sensing, there are also natural nonlinear sampling schemes such as the one introduced by quantization (see Petros' resource on Quantization), or FROG or simply those found in phase retrieval  problems. 

From " Spatio-Temporal Convolutional Sparse Auto-Encoder for Sequence Classification" by Moez Baccouche, 

And then there is the traditional area of Machine Learning that does classification:

Hx = N4(N3(N2(N1(x))))

where Hx represents whether x belongs to a class (+1/-1).

As we have seen recently, the connection between Compressive Sensing and Machine Learning, stems in large part in the nonlinearities involved in the sampling stage and specifically how to grab the features of interest. Can we be guided on the preferable nonlinearities ? When one comes back to a linear case, there are interesting information that might eventually be useful for designing nonlinearities in the sampling system, from [4]: 

We show that the suggested instance optimality is equivalent to a generalized null space property of M and discuss possible relations with generalized restricted isometry properties.

There are also other lessons to be learned from [5] but this time it involves low rank issues and some condition on the nonlinearity. We are just at the beginning of seeing these two fields merging.

[1] Let us note that this is not entirely true in conventional imaging, a 2D scene is transformed into a 2D scene whereas a 3D scene is transformed into a 2D scene. So AB is not really the identity but some sort of the projection of it Let us further note that in conventional direct imaging, things are really more complicated as AB is really two nonlinear operators that include the nonlinearities of the FPA, quantization issues and compression (JPEG, ...). This is one the reason why Mark Neifeld tells us that we are already using compressive systems in a talk entitled Adaptation for Task-Specific Compressive Imaging

[2] One should note that the rapid convergence of some of these algorithms makes one think that they could be parallel to neural networks. There are conditions on A, x, N although those are better acknowledged than in the direct imaging case. But there is really no restriction due to the concept of sparsity, indeed other solvers N using l_infty, l_p and other norms as regularizers can find a signal with a certain structure within the set of signals that were not destroyed by A (or A(B.)). With an underdetermined system (rectangular A), what we are saying in essence is that by performing the measurement Ax, we are not losing information on x.

[3] From Muthu's 2010 Massive Data Streams Research: Where to Go:

Compressed Functional Sensing. Streaming and compressed sensing brought two groups of researchers (CS and signal processing) together on common problems of what is the minimal amount of data to be sensed or captured or stored, so data sources can be reconstructed, at least approximately. This has been a productive development for research with fundamental insights into geometry of high dimensional spaces as well as the Uncertainty Principle. In addition, Engineering and Industry has been impacted significantly with analog to information paradigm. This is however just the beginning. We need to extend compressed sensing to functional sensing, where we sense only what is appropriate to compute different function (rather than simply reconstructing) and furthermore, extend the theory to massively distributed and continual framework to be truly useful for new massive data applications above.

[4] Compressed Sensing and Best Approximation from Unions of Subspaces: Beyond Dictionaries by Tomer Peleg, Rémi Gribonval, Mike E. Davies

We propose a theoretical study of the conditions guaranteeing that a decoder will obtain an optimal signal recovery from an underdetermined set of linear measurements. This special type of performance guarantee is termed instance optimality and is typically related with certain properties of the dimensionality-reducing matrix M. Our work extends traditional results in sparse recovery, where instance optimality is expressed with respect to the set of sparse vectors, by replac- ing this set with an arbitrary finite union of subspaces. We show that the suggested instance optimality is equivalent to a generalized null space property of M and discuss possible relations with generalized restricted isometry properties.

[5] Learning non-parametric basis independent models from point queries via low-rank methods, Tyagi, Hemant; Cevher, Volkan

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 Videos

A supercell near Booker, Texas

A supercell near Booker, Texas from Mike Olbinski on Vimeo.
Instant Ice
 
Airbnb Tech Talk: Bjorn Freeman-Benson - Airplanes, Spaceships, and Missiles
 Information Overload: The Failure of NSA Intelligence [Shane Harris @ ForaTV
Everest -A time lapse short film

Everest -A time lapse short film from Elia Saikaly on Vimeo.

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.

This Week in Review: A Seinfeldian problem, Meet-Ups, GSI2013, Around the blogs in 78 hours.

This week we had quite a few interesting threads on the interwebs about signals acquisition and making sense of them. While the former seems to be feasible thanks to Moore's law, the latter is, in view of the different results mentioned here and elsewhere, likely substandard. The real issue is: do policymakers understand there is a difference between acquiring data and making sense of them in the same way that there is a difference between a rental car company taking a reservation and making that reservation a reality by delivering a car ?

   

If you are reading this blog and happen to be coming to (or living in) Paris and want to make a presentation in front of a technical audience, there is the possibility of doing so at a variety of Meet-ups. Lately, a good resource to find (or create) Meet-ups in Paris (and elsewhere) is Meetup.com. At the end of this entry, you'll find some of the meet-ups that I tend to attend to when time permits. In the past few weeks, there were some talks of interest:

• A few Python computing tricks by Gabriel Synnaeve
• Face Recognition on a subset of the Labeled Faces in the Wild dataset and Scikit-learn, Machine Learning in Python by by Olivier Grisel

But I am sure I missed some. There are no technical meetup groups in College Station as far as I can tell. There ought to be one, I am sure there are enough hardware hackers around there.

Frank Nielsen wants me to mention the Geometric Science of Information conference (www.gsi2013.org ) that will have an 800 pages proceedings and will take place at the end of August in Paris! The page of the conference reads:

The objective of this SEE Conference hosted by MINES ParisTech, is to bring together pure/applied mathematicians and engineers, with common interest for Geometric tools and their applications for Information analysis, with active participation of young researchers for deliberating emerging areas of collaborative research on “Information Geometry Manifolds and Their Advanced Applications”.

Current and ongoing uses of Information Geometry Manifolds in applied mathematics are the following: Advanced Signal/Image/Video Processing, Complex Data Modeling and Analysis, Information Ranking and Retrieval, Coding, Cognitive Systems, Optimal Control, Statistics on Manifolds, Machine Learning, Speech/sound recognition, natural language treatment, etc., which are also substantially relevant for the industry....This conference will be an interdisciplinary event and will federate skills from Geometry, Probability and Information Theory to address the following topics among others

• Computational Information Geometry

• Hessian/Symplectic Information Geometry

• Optimization on Matrix Manifolds

• Probability on Manifolds

• Optimal Transport Geometry 

• Divergence Geometry & Ancillarity

• Machine/Manifold/Topology Learning

• Tensor-Valued Mathematical Morphology

• Differential Geometry in Signal Processing

• Geometry of Audio Processing 

• Geometry for Inverse Problems

• Shape Spaces: Geometry and Statistic

• Geometry of Shape Variability

• Relational Metric

• Discrete Metric Spaces

Of related interest is a recently published book on Matrix Information Geometry.

Here what you could read around the interwebs this past week:

Larry

• Happy Birthday Normal Deviate

Greg

• Hiding from time? New design of a “temporal cloak” makes waves 
• The Kaye effect after dark! 

Brian

• 3D scanner uses structured light 
• Two articles on 3D machine vision 

2physics

• Quantum experiment preludes the endgame for local realism – photonic Bell violation closes the fair-sampling loophole 

Danny

• Stinger project 
• Notable presentations at Technion TCE conference 2013: RevMiner & Boom 

Dustin

• DETERMINATION OF ALL PURE QUANTUM STATES FROM A MINIMAL NUMBER OF OBSERVABLES

Patrick

• Post-Prism Data Science Venn Diagram
• State of the OpenStreetMap [Watching the Watchers?] 
• NYU Large Scale Machine Learning Class Notes 
• Easy mapping with Map Stack 
• The Pragmatic Haskeller, Episode 5 – Let’s Write a DSL! 
• The Filtering vs. Clustering Dilemma 
• Updated Database Landscape map – June 2013 
• SSNs: Close Enough for a Drone Strike? 
• Beyond NSA, the intelligence community has a big technology footprint [Funding] 

John

• Singular Value Consulting, LLC
• Computing skewness and kurtosis in one pass 
• A statistical problem with “nothing to hide” 
• The weight of code 

Gregory:

• Learn Phased Array Radar by building your own in 5 days at MIT, course open to everyone

Sebastien

• Embeddings of finite metric spaces in Hilbert space

Roger

• Testing MCMC code, part 2: integration tests

John

• The Large Scale Learning class notes

Ivan

• Fast solution of the Poisson equation

While on Nuit Blanche,

• CSJob: PostDoc, Research Associate in Compressive Sensing and Distributed Compressive Sensing for Energy Harvesting Wireless Sensor Networks, London
• PyHST2: an hybrid distributed code for high speed tomographic reconstruction with iterative reconstruction and a priori knowledge capabilities = implementation-
• Quantized Iterative Hard Thresholding: Bridging 1-bit and High-Resolution Quantized Compressed Sensing - implementation -
• Simple and Deterministic Matrix Sketches and Near-optimal Distributions for Data Matrix Sampling
• Sparse Recovery of Streaming Signals Using l_1-Homotopy - implementation -
• Saturday Morning Videos: Robot Programming through demonstration, Using Chrome to talk to an Arduino, Orbit Imagery, DYI Raman spectroscopy, Radar data of asteroid 1998 QE2
• This week in Review: COxSwAIN, Machine Learning and Sensors MeetUps, SigFox, Lensless Single Pixel camera, Around the Blogs in 78 hours

The meet-ups of interest around Paris are:

Big Data Developers in Paris

Graph Database - Paris

OpenCoffee Club Paris

Paris Arduino

Paris Machine learning applications group

Paris Tech Talks

Paris.py (Python, Django & friends)

ParisEmbedded

ParisHackers

Paris Datageeks

credit: wikipedia,

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.

CSJob: PostDoc, Research Associate in Compressive Sensing and Distributed Compressive Sensing for Energy Harvesting Wireless Sensor Networks, London

Found on the interwebs:

Research Associate in Compressive Sensing and Distributed Compressive Sensing for Energy Harvesting Wireless Sensor Networks

EPSRC funded project

We wish to recruit a Research Associate from 1^st October 2013 or as soon as possible thereafter to work on an EPSRC funded project, Efficient Energy Management in Energy Harvesting Wireless Sensor Networks: An Approach Based on Distributed Compressive Sensing.

The overarching objective of this research project is to develop transformative sensing mechanisms, which can be used in conjunction with current or upcoming energy harvesting capabilities, in order to enable the deployment of energy neutral or nearly energy neutral wireless sensor networks with practical network lifetime and data gathering rates up to two orders of magnitude higher than the current state-of-the-art. In particular, the project capitalizes on the emerging paradigms of compressive sensing and distributed compressive sensing as well as energy- and information-optimal data acquisition and transmission protocols in order to tightly the energy demand to the energy supply in wireless sensor networks in order to achieve the breakthroughs in data gathering capability.

This 3-years research project, which will also be carried out in collaboration with the University of Cambridge, involves both theoretical and practical work as well as proof-of-concept deployment via the various institutional and industrial partners. This research project will also explore the application of the technology in various domains such as the smart infrastructure and construction industry, the digital economy industry, healthcare systems and future cities.

The proposed research is also supported by the Cambridge Innovation and Knowledge Centre for Smart Infrastructure and Construction, Thales, Fujitsu Laboratories of Europe, STMicroelectronics and AquaMW.

The post is initially funded for a period of two years .Further funding to support the post may be available.

Candidates should hold a PhD degree in electrical engineering, computer science or mathematics with significant research experience in the area of compressive sensing or distributed compressive sensing or signal and information processing theory and methods.

The salary scales are as follows:

Research Associate: Grade 7, salary £32,375-£39,132 per annum, inclusive of £2834 London Allowance per annum

Interested applicants are encouraged to make informal enquiries to the Project Principal Investigator of the research project Dr Miguel Rodrigues, m.rodrigues@ucl.ac.uk, +44 (0)20 7679 3957.

Further details can be found here:

Advert

Further Particulars

All applications should be submitted via UCL online recruitment system here:

Post reference 1340734

You will need to upload the following documents with your application:

• CV (including the names and contact details of at least two referees who may be contacted prior to interview)
• An up to date list of publications

If you experience any problems please contact Vicky Coombes at v.coombes@ucl.ac.uk quoting reference 1340734

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.

PyHST2: an hybrid distributed code for high speed tomographic reconstruction with iterative reconstruction and a priori knowledge capabilities = implementation-

PyHST2: an hybrid distributed code for high speed tomographic reconstruction with iterative reconstruction and a priori knowledge capabilities by Alessandro Mirone, Emmanuelle Gouillart, Emmanuel Brun, Paul Tafforeau, Jerome Kieffer

We present the PyHST2 code which is in service at ESRF for phase-contrast and absorption tomography. This code has been engineered to sustain the high data flow typical of the third generation synchrotron facilities (10 terabytes per experiment) by adopting a distributed and pipelined architecture. The code implements, beside a default filtered backprojection reconstruction, iterative reconstruction techniques with a-priori knowledge. These latter are used to improve the reconstruction quality or in order to reduce the required data volume and reach a given quality goal. The implemented a-priori knowledge techniques are based on the total variation penalisation and a new recently found convex functional which is based on overlapping patches.

We give details of the different methods and their implementations while the code is distributed under free license.

We provide methods for estimating, in the absence of ground-truth data, the optimal parameters values for a-priori techniques.

PyHST2 is available here at: http://forge.epn-campus.eu/projects/pyhst2

I note three items that are bound to be part of our collective experience as we are surfing Moore's law. From this outstanding paper, one can read:  

• "....10 terabytes per experiment..." Memory is cheap, if people can record it, they will. 
• "...The total data volume is often larger than the available memory...." if one were to perform these experiment often, no make that very very often, then we would have to go into streaming algorithms. Right now, the science is such that performing these computation is a day's worth and a few of these computations are probably behind one of two thesis' work. In ten year's time, that experiment could be done every ten seconds. At that point, the algorithms will have to catch up and while memory will still be cheap, we will require data reconstruction at a faster pace.
• "...If the ground truth is not available, statistical methods such as the discrepancy principle [19] or generalized cross-validation [20] can be used to select the optimal regularization parameter. Such methods could be implemented in future versions of PyHST...." At some point, we will have to go to a grammar based exploratory approach. The choosing of parameters while worth it, is a reminder that we don't know very well the underlying structure of the signal.  

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.

Quantized Iterative Hard Thresholding: Bridging 1-bit and High-Resolution Quantized Compressed Sensing - implementation -

So yesterday, you saw the ability to approximate a data matrix through some sort of quantization of said matrix. But these data came from a sensor that quantized an analog data in the first place. Compressive sensing offers a new way to explore that trade-off that come with quantization.. In related news, Petros Boufounos tells us that "The page with resources on quantization has been updated to include the slides from the [ICASSP] tutorial. [ on Modern Quantization Strategies for Compressive Sensing and Acquisition Systems]"  . Today we have a paper making the bridge between 1-bit compressive sensing and your average run-of-the-mill quantization strategy. This is timely in light of all the discussions currently going on about the internet of things and related wireless communication protocols like SigFox. To come back to the original argument above, one wonders when data matrix will exploit the quantization found either here or in matrix sampling. Without further due, here is the paper:

Quantized Iterative Hard Thresholding: Bridging 1-bit and High-Resolution Quantized Compressed Sensing by Laurent Jacques, Kévin Degraux, Christophe De Vleeschouwer

In this work, we show that reconstructing a sparse signal from quantized compressive measurement can be achieved in an unified formalism whatever the (scalar) quantization resolution, i.e., from 1-bit to high resolution assumption. This is achieved by generalizing the iterative hard thresholding (IHT) algorithm and its binary variant (BIHT) introduced in previous works to enforce the consistency of the reconstructed signal with respect to the quantization model. The performance of this algorithm, simply called quantized IHT (QIHT), is evaluated in comparison with other approaches (e.g., IHT, basis pursuit denoise) for several quantization scenarios.

The implementation for the QIHT demo can be found here.

The quantization page is part of the Highly Technical Reference Pages

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.

Simple and Deterministic Matrix Sketches and Near-optimal Distributions for Data Matrix Sampling

Let us continue this week with some exciting streaming/sketching algorithms:

Simple and Deterministic Matrix Sketches by Edo Liberty (See experimental results in json format)

A sketch of a matrix A is another matrix B which is significantly smaller than A but still approximates it well. Finding such sketches effi ciently is an important building block in modern algorithms for approximating, for example, the PCA of massive matrices. This task is made more challenging in the streaming model, where each row of the input matrix can only be processed once and storage is severely limited. In this paper we adapt a well known streaming algorithm for approximating item frequencies to the matrix sketching setting. The algorithm receives n rows of a large matrix A 2 R n m one after the other in a streaming fashion. It maintains a sketch B 2 R` m containing only ` n rows but still guarantees that ATA B TB. More accurately,

8x;kxk = 1 0 kAxk2  kBxk2 2kAk2f=`

Or

BTB A TA and kA TABTBk 2kAk2f=` :This gives a streaming algorithm whose error decays proportional to 1=` using O(m`) space. For comparison, random-projection, hashing or sampling based algorithms produce convergence bounds proportional to 1=p`. Sketch updates per row in A require amortized O(m`) operations and the algorithm is perfectly parallelizable. Our experiments corroborate the algorithm's scalability and improved convergence rate. The presented algorithm also stands out in that it is deterministic, simple to implement and elementary to prove.

Near-optimal Distributions for Data Matrix Sampling by Dimitris Achlioptas, Zohar Karnin, Edo Liberty 

We give near-optimal distributions for the sparsification of large m x n matrices,where m much less than n, for example representing n observations over m attributes. Our algorithms can be applied when the non-zero entries are only available as a stream, i.e., in arbitrary order, and result in matrices which are not only sparse, but whose values are also highly compressible. In particular, algebraic operations with the resulting matrices can be implemented as (ultra-efficient) operations over indices.

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.