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.