Monday, July 18, 2011

Sparse Fault Identification Software

Before we can get on today's entry, I can see the need for a repository of software that are not strictly Compressive sensing per se but use most of its machinery to make a different point than the traditional acquisitiion and reocnstruction steps. We have an example today as sent by Dror Baron:

Hi Igor, 
Danny, Alex, and I have released software for fault identification, which is related to compressed sensing:
Ordinarily I would request that you add it to your software links webpage
However..... this is not a new reconstruction algorithm. Instead, we have two things:
(1) an *application* of our old belief propagation CS algorithm to the algorithmic problem of fault identification. Our paper has extensive simulations, and the code that was run for the simulations is online.
(2) a *computation* of the exact information theoretic performance limit for the problem that we studied. Our simulations match very nicely with the theory, for example see slide 14 in this talk I gave in February:
Seeing that we already had a "discussion" of the belief propagation on your blog (in early 2009), it would add zero intellectual information. At the same time, the plot showing the correspondence of theory and simulations is nice, and the true message is that the theoretical limits are really good. Sundeep Rangan has also advocated this view, but some might be unaware that belief propagation is more powerful than ell1.... Not sure how to link this into your blog, we will be delighted to provide any additional info of course!.

The code is in support of  this paper we mentioned earlier:  Fault Identification via Non-parametric Belief Propagation by Danny Bickson, Dror Baron, Alexander Ihler, Harel Avissar, Danny Dolev. The abstract reads:

We consider the problem of identifying a pattern of faults from a set of noisy linear measurements. Unfortunately, maximum a posteriori probability estimation of the fault pattern is computationally intractable. To solve the fault identification problem, we propose a non-parametric belief propagation approach. We show empirically that our belief propagation solver is more accurate than recent state-of-the-art algorithms including interior point methods and semidefinite programming. Our superior performance is explained by the fact that we take into account both the binary nature of the individual faults and the sparsity of the fault pattern arising from their rarity.

Fault identification has been featured on Nuit Blanche before, let me list some of the work I can recall (I am absolutely sure I am missing some, please let me know what they are):

Wiring Diagnostics via ℓ1-Regularized Least Squares by Stefan Schuet.
Self-Healing Reconfigurable Logic using Autonomous Group Testing by Carthik SharmaRonald Demara and Alizera Sarvi.

Compressed Sensing and Time-Parallel Reduced-Order Modeling for Structural Health Monitoring using a DDDAS by Julien Cortial, Charbel Farhat,Leonidas Guibas and Manjunath Rajashekhar (see here Compressed Sensing: On-Line Structural Damage Detection )

If you recall this is an unfeasible fault detection test that is at the origin of the Rendez-Vous Pitch Maneuver performed on all Shuttles docking to the International Space Station since 2003. The maneuver is there to visually inspect the belly and sides of the shuttles. Columbia's accident uncovered, among other things, that for fifteen days none of the readings on the shuttle internal thermal network gave a clue that Columbia had a big hole in its wings (as shown in the Southwest Research Institute Tests)

No comments: