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: http://people.engr.ncsu.edu/dzbaron/pdf/ita2011a.pdf
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!.
Dror

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 Sharma, Ronald 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)







Sunday, July 17, 2011

The Flashed Face Distortion Effect



More information here.

The answer is No.

After some offline discussions, the inventors of the PFCA seem to have a very good handle on getting a better looking Mona Lisa. This is outstanding as we all look forward to better images from this device. It also looks like some of the readership of Nuit Blanche is growing and somehow changing :-) A commenter said recently:
From what i understand, the blurred image is the result not much of the processing, but from the hardware limitation
I initially responded with: "No" but eventually felt this answer was too terse, let me re-frame it:

Compressive sensing has the potential to improve on the current approach for calibrating this imager. The physical limitations of this device are, in my view, not even reached.

Compressive sensing is not about getting into fashionable papers to get new grants and fame, etc..... It's about making sure that new detectors are the embodiments of our understanding that Nature is governed by power laws and that, finally, terabytes of data will actually mean something..

Friday, July 15, 2011

Compressive Sensing: Around the blogs in 80 hours and some papers

Dirk Lorenz has two entries on his blog that of interest:

Bob Sturm comments on An Improvement to CoSaMP but not to Supspace Pursuit?



This paper develops new theory and algorithms to recover signals that are approximately sparse in some general (i.e., basis, frame, over-complete, or incomplete) dictionary but corrupted by a combination of measurement noise and interference having a sparse representation in a second general dictionary. Particular applications covered by our framework include the restoration of signals impaired by impulse noise, narrowband interference, or saturation, as well as image in-painting, super-resolution, and signal separation. We develop efficient recovery algorithms and deterministic conditions that guarantee stable restoration and separation. Two application examples demonstrate the efficacy of our approach.
Rich has more on his blog.

We present an imaging method, dSLIM, that combines a novel deconvolution algorithm with spatial light interference microscopy (SLIM), to achieve 2.3x resolution enhancement with respect to the diffraction limit. By exploiting the sparsity of the phase images, which is prominent in many biological imaging applications, and modeling of the image formation via complex fields, the very fine structures can be recovered which were blurred by the optics. With experiments on SLIM images, we demonstrate that significant improvements in spatial resolution can be obtained by the proposed approach. Moreover, the resolution improvement leads to higher accuracy in monitoring dynamic activity over time. Experiments with primary brain cells, i.e. neurons and glial cells, reveal new subdiffraction structures and motions. This new information can be used for studying vesicle transport in neurons, which may shed light on dynamic cell functioning. Finally, the method is flexible to incorporate a wide range of image models for different applications and can be utilized for all imaging modalities acquiring complex field images
.
While Laurent Duval let me know of this one: Sparse approximation property and stable recovery of sparse signals from noisy measurements by Qiyu Sun
In this paper, we introduce a sparse approximation property of order s for a measurement matrix A:kxsk2 DkAxk2 + s(x) p s for all x; where xs is the best s-sparse approximation of the vector x in `2, s(x) is the s-sparse approximation error of the vector x in `1, and D and are positive constants. The sparse approximation property for a measurement matrix can be thought of as a weaker version of its restricted isometry property and a stronger version of its null space property. In this paper, we show that the sparse approximation property is an appropriate condition on a measurement matrix to consider stable recovery of any compressible signal from its noisy measurements. In particular, we show that any compressible signal can be stably recovered from its noisy measurements via solving an `1-minimization problem if the measurement matrix has the sparse approximation property with 2 (0; 1), and conversely the measurement matrix has the sparse approximation property with 2 (0; 1) if any compressible signal can be stably recovered from its noisy measurements via solving an `1-minimization problem.
Finally, this one showed up on my radar screen:

Convergence and Rate Analysis of Neural Networks for Sparse Approximation by Aurele Balavoine, Justin Romberg, and Christopher J. Rozell. The abstract reads:
We present an analysis of the Locally Competitive Algorithm (LCA), a Hopfield-style neural network that solves sparse approximation problems (e.g., approximating a vector from a dictionary using just a few non-zero coefficients). This class of problems plays a significant role in both theories of neural coding and applications in signal processing, but traditional analysis approaches are difficult because the objective functions are non-smooth. Specifically, we characterize the convergence properties of this system by showing that the LCA is globally
convergent to a fixed point corresponding to the exact solution of the objective function, and (under some mild conditions) this solution is reached in finite time. Furthermore, we characterize
the convergence rate of the system by showing that the LCA converges exponentially fast with an analytically bounded convergence rate (that depends on the specifics of a given problem).
We support our analysis with several illustrative simulations.
In other news, the ICCV 2011 papers on the web are here. A working list of people who contribute on the topics of statistics, machine learning and data analysis on Quora lists me as Others/ Bloggers/ Not Sure: this is good. Pierre Vandergheynst has a profile on the Montreux Jazz Festival that reminds me when I was asked to provide a speaker on MEMS for SXSW back in 1999.

Image Credit: NASA/JPL/Space Science Institute, W00068470.jpg was taken on July 12, 2011 and received on Earth July 13, 2011. The camera was pointing toward SATURN at approximately 1,317,905 kilometers away, and the image was taken using the CL1 and IR1 filters. 

Thursday, July 14, 2011

Calibrating and Enhancing the Planar Fourier Capture Array ?

Laurent Duval sent me a link to the paper on the tiny camera we mentioned earlier, it's called the Planar Fourier Capture Array (PFCA). The article is: A Micro-Scale Camera Using Direct Fourier-Domain Scene Capture by  Patrick Gill, Changhyuk Lee, Dhon-Gue Lee, Albert Wang, and Alyosha Molnar. The abstract reads:
We demonstrate chip-scale (< 1 mm2) sensor, the Planar Fourier Capture Array (PFCA), capable of imaging the far field without any off-chip optics. The PFCA consists of an array of angle-sensitive pixels manufactured in a standard semiconductor process, each of which reports one component of a spatial 2D Fourier transform of the local light field. Thus, the sensor directly captures 2D Fourier transforms of scenes. The effective resolution of our prototype is approximately 400 pixels.



From the text of the paper:

To characterize the array, we presented a series of random calibration images to the sensor using a square CRT area 20 cm on a side, 22.86cm from the PFCA for an h of 31.7 at the square's corners.... We then use linear system identification tools [12] to reconstruct the kernel of each ASP (Fig. 6C). Afterwards, we presented various test images with an accumulation time of 15.7ms and  successfully reconstructed the images (Fig. 7B) up to the Nyquist Limit of our sensor, set by the highest-b design in our array....

Clearly, in light of what we now know about Compressive Sensing, some improvements could be entertained:



  • If I understand correctly, the colored tiles above show photodiodes with different spatial frequencies responses. The sampling is ordered so that the whole Fourier domain is covered up to the Nyquist limit. The use of Compressive Sensing could allow more of these pixels packed in the same space under the condition that the fewer pixels with a random set of frequencies were to be set on this plane. This could be done at the hardware level. In the meantime, however, given the data already gathered:
  • The calibration step could be improved as the transfer function for each pixel (ASP) is sparse in the Fourier domain. Sensing random patterns as trial function should yield good transfer functions using L_1 solvers.. 
  • Given the transfer functions of every ASP computed already, and as mentioned earlier, using an L_1 minimization solver could probably give a better looking Mona Lisa. 


Thanks Laurent, Dan and Alain for alerting me and pointing me to the paper.

Wednesday, July 13, 2011

Nuit Blanche Reader's Mailbag

Bob Sturm provided a new correction to his implementation of CoSaMP and Subspace Pursuit algorithms. If this is not a huge justification for having written Nobody cares about you and your algorithm, I don't know what is. Currently I am playing with some of the sparse PCA and Low Rank codes around and keep on getting mex errors for a few of them. So even when this is written in Matlab, you're not communicating with your target audience if your algorithm cannot be instantiated on the users' computer.

Some anonymous commenters mentionned about Facing Mona Lisa:

The discussion on this blog is very "scientific" and I havent started to read up on it yet. I was imagining that it would be possible to use these methods to create a new compression-algorithm for images, like a new JPEG or ECW or MrSID- format. What is your idea on this?
Thanks for a nice blog and I will try to read up on compressed sensing!

To what I responded with:
Compressive sensing provides a simple way of compressing data however, it is also known that a naive approach to it yield schemes that are not as optimal compared to jpeg or wavelet based compression encodings. Less naive schemes include adaptive compressive sampling and/or structured sparsity based decoders and are likely to yield better results than the naive approach. However, if one looks at the semi-success of jpeg2000, a wavelet based encoding system, it looks like the era of better compression systems does not have bright future.

In the case of this sensor however, a jpeg or jpeg2000 encoding system would not make sense as the compressed data is already gathered through the readings of the voltage of the chip. What is needed is a better reconstruction solvers that takes these readings from voltages to an images. The point I made in this entry is that there are better reconstructions solvers than the least square solution (which seems to have been used by the authors of the paper) especially for a system that looks like it is underdetermined such as happens in compressive sensing....

Laurent Duval added:

You said "Compressive sensing provides a simple way of compressing data however, it is also known that a naive approach". I would not be in complete accordance with that. Compressive is (still IMHO) somehow an adjective to sensing, as (seemingly) pointed out by Bob Sturm here: "I agree that compressed sensing is much more a method of acquisition than it is a method for compression.", more than a way to compress stuff. Actual compression generally needs some amount of engineering wizardy than goes far beyond any "sparsity" assumptions. In a word: Fourier+Huffman < local Fourier (DCT)+ Huffman but local (8x8) wavelet + Huffamn < local Fourier (DCT)+ Huffman. Yet Wavelet + Zerotree > local Fourier (DCT)+ Huffman. Again, Wavelet + Zerotree ~ DCT + zerotree, both < to Windowed Fourier (GenLOT like) + treillis. And the story may not be over yet. There is some intertwining between sparsity yielded by transform and coding, AND expectation. Poor sparsity + black magic coding may perform better than highest sparsity and 2nd order entropy. As for: "However, if one looks at the semi-success of jpeg2000, a wavelet based encoding system, it looks like the era of better compression systems does not have bright future." I believe this assertion deserves some further historical, time-to-market and corporate weighting and a reference to Sentience is indescribable by Daniel Lemire. When we can describe the forest... but  progress on NP or PCP are needed first.


Eric Tramel replied with

WRT the "next era" of coding methods, I think we're still on the look out for the next wave. Currently, advanced coders, like Laurent mentioned, are mostly completely hyper-engineered, 100-mode contraptions that can squeeze compression out of rocks. H.264 for video is a hairy beast of corner cases, but it is my understanding that H.265 makes it look simple by comparison, all for ~30% rate-distortion performance gain.

CS is attractive for its simplicity, and that despite its simplicity it has passable performance in practice (in some applications). In order for CS to become the next thing in coding, measurement quantization will need to be fully understood and we'll need more accurate solvers (i.e. ones that make the most out of signal models & priors). I don't see this happening at a rate that would put CS on par with anything but last-gen traditional coding techniques. But of course, CS isn't intended for these purposes :P

TL;DR: Still looking for something elegant for the next gen of coders..

and then added

nother comment that is more on the topic of what you talked about in the post, Igor:

You'd be surprised what you can recover from. Well, maybe you wouldn't be, but others might. We talk a lot about making sure that the projector, \Phi, A, etc, matches bounds to ensure performance. But, legibility can be achieved with even really, really, really crappy & poorly conditioned projectors and a handful of measurements. This is potentially useful for some very simple vision applications.

So, it is very possible that, as you are suggesting, an L1 solver approach could provide some kind of performance gain. They just have to make sure that they characterize the effective projection accurately :P Also remember that they are dealing with a single, non-reconfigurable, shot. So, they are also limited by the number of sensors on the chip. It is possible that for a low sensor resolution and a single capture, a maximum liklihood approach might make more sense than an L1 solution.

But, I'm having the same problem you stated at the beginning of the article. I can't find the paper! I went to look for it right after reading the press release but came up empty. It could be that they are waiting for some kind of patent application to go through...

No paper makes it hard to tell what they're doing exactly for recovery or what kind of trade-offs they're making in design :'(

As I have said before, i have been here before. The main difficulty for another paper to be a compressive sensing paper based on this detector design would be to have a good characterization of its transfer function and see if it fits the Donoho-Tanner phase transition. Also I think I made my views clear that indeed in some circumstances, we really are performing sparsity sensing as opposed to compressive sensing.For the rest I am bit more optimistic than Laurent because for examples such as image processing, we have mostly six billion entities on earth with a capable processor even through none of them grew in the same fashion as the others.

Finally, Stephen Becker sent me the following:


Hi Igor, I found a bad link for Regularized OMP (ROMP) on your list of solvers (section 4.1 of http://sites.google.com/site/igorcarron2/cs )
The bad link is: http://www.math.ucdavis.edu/%7Edneedell/romp.m(also, http://www.math.ucdavis.edu/~dneedell/ is bad)
an updated link is:
http://www-stat.stanford.edu/~dneedell/romp.m
While I was thinking about this, I realized there are caltech links that need to be updated.  We merged departments, so the "acm" website is permanently down, and hence our solver NESTA
http://www.acm.caltech.edu/~nesta/
has moved to a new home:http://www-stat.stanford.edu/~candes/nesta/

Also, my website (formerly http://www.acm.caltech.edu/~srbecker) is now http://ugcs.caltech.edu/~srbecker).  Our TFOCS solver URL remains the same.  On a related note, I leave Caltech soon, and have written a thesis that you or your readers may find interesting:http://resolver.caltech.edu/CaltechTHESIS:06022011-152525054"Practical compressed sensing: modern data acquisition and signal processing".
And some old websites of (former) caltech folks are being removed, so I've listed them below, along with the new links:
http://www.eecs.umich.edu/~wakin/( now http://www.mines.edu/~mwakin )http://www.acm.caltech.edu/~jrom/( now http://users.ece.gatech.edu/justin )http://www.acm.caltech.edu/~emmanuel/ (2 locations)( now http://www-stat.stanford.edu/~candes/ )
While I was at it, I checked other links on this site (http://sites.google.com/site/igorcarron2/cs) using a validator (http://validator.w3.org/checklink ) since I'd noticed that other links were old as well.  Turns out a lot of them are old! Here's a list:
-- Missing targets --http://homepages.cae.wisc.edu/~jhaupt/http://sites.google.com/site/igorcarron2/tr_1231851202623http://sites.google.com/site/igorcarron2/tr_1267470689827http://sites.google.com/site/igorcarron2/goog_2029081109http://sites.google.com/site/igorcarron2/tr_1267456797996http://www.mit.edu/~texel/http://www.ece.rice.edu/~drorb/CSBP/http://www-personal.umich.edu/~markiwen/http://www.math.lsa.umich.edu/~cvspenc/http://www.bu.edu/systems/people/students.htmlhttp://www.academie-sciences.fr/membres/M/Meyer_Yves.htmhttp://www.stanford.edu/~idrorihttp://www.csl.uiuc.edu/directory/detail_dir1.asp?NetID=weidaihttp://www.math.univ-paris13.fr/~malgouy/software/bpdn_web.zipftp://ftp.math.ucla.edu/~tao/preprints/sparse.html (meant to be http not ftp???)http://www.ceremade.dauphine.fr/~peyre/upload/cs-tv/html/content.htmlhttp://ee.sharif.ir/~ghmohimani/http://www.stanford.edu/~singerhttp://www.stanford.edu/~tsaighttp://www.math.uchicago.edu/faculty.htmlhttp://www.math.ucla.edu/~tagoldst/FLASH_c.ziphttp://web.mit.edu/texel/www/http://www.tele.ucl.ac.be/~jacques/ (twice; "forbidden". link to index.html instead?)http://www.stanford.edu/~sjkim/http://www.stanford.edu/~deneb1/http://www.caam.rice.edu/~eth3881/http://math.berkeley.edu/~shamgar/http://www.public.asu.edu/~jliu86/http://www.its.caltech.edu/~amin/weighted_l1_codes/http://www.ece.osu.edu/~schniter
-- other links (permanently gone, or servers temporarily down?) --
http://www.columbia.edu/~zw2109/http://www.math.utah.edu/~tanner/ ("forbidden". link to index.html instead?)http://www.ece.osu.edu/~zinielj/fbmp/index.html  ("forbidden")http://www.ece.osu.edu/~zinielj  ("forbidden")http://www.ece.osu.edu/~zinielj/fbmp/download.html  ("forbidden")http://www.ece.osu.edu/~potter   ("forbidden")http://www.stanford.edu/~hllee/softwares/nips06-sparsecoding.htm("forbidden")http://www.cs.washington.edu/homes/venkat/   ("forbidden")
http://sina2jp.googlepages.com/sinajafarpour'shomepage (the apostrophe is probably not right)
http://www.math.sfu.ca/~zhaosong/Codes/Compressed_Sensing(redirected to) http://people.math.sfu.ca/~zhaosong/Codes/Compressed_Sensing, (which isn't found either)
http://www.math.yale.edu/~sl349/demos_data/demos.htm(redirected to) http://users.math.yale.edu/~sl349/demos_data/demos.htm, (which isn't found)
http://www.convexoptimization.com/wikimization/index.php/Matlab_for_Convex_Optimization_%26_Euclidean_Distance_Geometry(broken due to some punctuation in the link)

http://www.emmanuel-ravelli.com/downloads   (can't find host)http://jbobin.shje.org/  (can't find host -- this site is gone)http://www-math.univ-fcomte.fr/pp_Annu/SCHRETIEN/   (can't connect)

Thanks for all your work indexing these pages and the almost daily updates! We appreciate it.
-Stephen

Thanks Stephen, I needed work :-) I'll try to focus on the big ones, other sites may become permanently silent as a result of this audit though.

Image Credit: NASA/JPL/Space Science Institute
W00067992.jpg was taken on July 10, 2011 and received on Earth July 11, 2011. The camera was pointing toward SATURN at approximately 291,728 kilometers away, and the image was taken using the CB2 and CL2 filters. 


Tuesday, July 12, 2011

Facing Mona Lisa

I cannot seem to find the paper anywhere of this lens free tiny imager, but I have gone through this route several times already. It looks like we are witnessing a typical Compressive Sensing problem but the designers are probably not aware of it. It is understandable as it takes a lot of effort to design hardware and sometimes the deconvolution is just, if not an afterthought, something that is considered known . If I go to Alyosha Molnar's group and go to his research page, one can see some of the drawing/figures of what this sensor is doing.


In short, the response of the chip is angle dependent because for each ray of light (that one could consider a dirac) striking it at a specific angle, the chip records three different voltages. These voltages are different enough over the range of the field of view to permit some discretization thanks to probably the dynamic range of the chip (this is not unlike the Anger camera scheme)

In this example, we have a ray of light that is providing three measurements in parallel. Remember this is a one-to-many set up similar to the analog-to-digital converters work being undertaken by several groups. For one pixel, several rays of light of different intensities (figure 3) will strike the chip. This operation is similar to a typical multiplexing operation.  In order to obtain the image back from the chip measurement, one is facing a deconvolution problem with a transfer function that looks like the second figure above. What do we get out of this if we naively take the results from the chip and deconvolute these using, I am making a guess, a least square solver? Well, from the press release, we get this pretty bad Mona Lisa (on the right).


Why ? Most probably because an L_1 reconstruction solver was not used to deconvolute this image. There are many solutions to deconvoluting this multiplexing process since there are not that many sensors (it is very likely underdetermined). The L_1 solvers have the particularity that they will "search" for the sparsest decomposition that fits the measurements provided by the chip as opposed to search for a solution with the  smallest error. It turns out, in most cases, the L_1 solution is also the one with the least error among all the ones with small reconstruction error (including the Least Squares solution)..

After having spent so many hours devising this ingenious piece of hardware, how can we make this Mona Lisa look better ... fast ?  L_1 reconstruction solvers can be used like any other Least Squares solvers. If one were interested in getting a better looking Mona Lisa, easy to use and efficient implementations can be used such as: SPGL1, GPSR or SL0. Instead of performing y = A\x in Matlab, one just needs to perform y = SPGL1(A,x,..) or y = GPSR_BB(A, x,..) or y = SL0(A, x,..) after having downloaded any of these packages. Please note that the "...." replace the arguments generally used in the examples provided in these packages. There should not be a need for tuning these parameters to get a better Mona Lisa. Let us also note that for an optimal result, one should certainly add a wavelet dictionary in the reconstruction process, i.e. use A*W as opposed to just A with W representing a wavelet basis (see Sparco's problems for an easy to use implementation).

Monday, July 11, 2011

Call for Host of SPARS'13 and Compressive Sensing Literature This Week

Remi Gribonval sent me the following:

Dear Igor,

In the follow-up of the workshop SPARS'11 on Signal Processing with Adaptive/Sparse Representations, the SPARS Steering Committee is looking for hosts for the following SPARS meeting.

Would you mind relaying this on your blog ?

All the best,
Remi.

Absolutely, here is the call for hosts of the next SPARS meeting:


Dear colleagues,

In the follow-up of the workshop SPARS'11 on Signal Processing with Adaptive/Sparse Representations, the SPARS Steering Committee is looking for hosts for the following SPARS meeting.
The SPARS workshop is expected to run about each 24 months, so the next workshop would most likely be held in end of June/beginning of July 2013.
For more about SPARS11 and previous workshops, see http://ecos.maths.ed.ac.uk/SPARS11/ , http://spars09.inria.fr/ and http://spars05.irisa.fr

(As a past host myself, I know that this is an exciting and rewarding opportunity to make a major contribution to the community!)

If you and/or colleagues would like to host the next workshop, or think this sounds interesting and would like to know more, please send me a brief email as an "Expression of Interest".

Full details are not required at this stage, but as much of the following information (if known) would be helpful:

* Proposed location / venue

* Names of organizers

* Suggested dates

* Funding strategy

* Other information if available (accommodation options, travel, costs, other special features)

Please send any initial "expressions of interest" by email to me (remi.gribonval@inria.fr) by August 30.

The SPARS Steering Committee will then discuss these expressions of interest and we will get back to you.

In the meantime, if you have any queries, please let me know.

Best wishes,

Rémi Gribonval.

---
Note: the Steering Committee will take the following elements into particular consideration when assessing propositions:

* Format: SPARS is aimed to be a "human size" workshop: not more than 200 participants, one or at most two parallel tracks, and ample time for discussions.

* Student-friendliness: support to students, e.g., through reduced fee and/or travel grants, is expected.

* Abstract 'only': SPARS is primarily intended to be a forum for exchanges at the frontier between applied math and electrical engineering. To accommodate the different publishing cultures of these communities,
SPARS11 only requested a mandatory 1-page abstract, but full papers were not required. The organizers of SPARS13 are free to consider optional proceedings for authors who would wish to provide an extended paper.

* Funding: Bidders should show that they can provide / have applied for a grant to support the organization of the event.

* Accessibility & affordability: ease of access and affordability may be preferred to fancy locations.

* Timing: time conflicts with other sparsity related workshops such as SaMPTA, SPIE Wavelets&Sparsity, etc. should be avoided if possible.


Thanks Remi 

You're in the Edinburgh area and want to make your body available for some Compressive sensing testing, Mike Davies is performing CS MRI studies on 10 healthy subjects. Please note all the exclusion criteria.


While we are on the subject of Edinburgh, here are the presentations slides for SPARS11 for Analysis Operator Learning for Overcomplete Co-sparse Representations by Mehrdad Yaghoobi, Sangnam Nam, Remi Gribonval, and Mike E. Davies

also found on the interwebs:



Signal and Image Processing in Astrophysics by Sandrine Pires



Group Testing with Probabilistic Tests: Theory, Design and Application by Mahdi Cheraghchi, Ali Hormati, Amin Karbasi, and Martin Vetterli. The abstract reads:
Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of test results obtained for each pool. In a classical noiseless group testing setup, it is assumed that the sampling procedure is fully known to the reconstruction algorithm, in the sense that the existence of a defective member in a pool results in the test outcome of that pool to be positive. However, this may not be always a valid assumption in some cases of interest. In particular, we consider the case where the defective items in a pool can become independently inactive with a certain probability. Hence, one may obtain a negative test result in a pool despite containing some defective items. As a result, any sampling and reconstruction method should be able to cope with two different types of uncertainty, i.e., the unknown set of defective items and the partially unknown, probabilistic testing procedure. In this work, motivated by the application of detecting infected people in viral epidemics, we design non-adaptive sampling procedures that allow successful identification of the defective items through a set of probabilistic tests. Our design requires only a small number of tests to single out the defective items. In particular, for a population of size N and at most K defective items with activation probability p, our results show that M = O(K2log (N/K)/p3) tests is sufficient if the sampling procedure should work for all possible sets of defective items, while M = O(K log (N)/p3) tests is enough to be successful.



Compressed sensing (CS) samples signals at a much lower rate than the Nyquist rate if they are sparse in some basis. In this paper, the CS methodology is applied to sinusoidally modeled audio signals. As this model is sparse by definition in the frequency domain (being equal to the sum of a small number of sinusoids), we investigate whether CS can be used to encode audio signals at low bitrates. In contrast to encoding the sinusoidal parameters (amplitude, frequency, phase) as current state-of-the-art methods do, we propose encoding few randomly selected samples of the time-domain description of the sinusoidal component (per signal segment). The potential of applying compressed sensing both to single-channel and multi-channel audio coding is examined. The listening test results are encouraging, indicating that the proposed approach can achieve comparable performance to that of state-ofthe-art methods. Given that CS can lead to novel coding systems where the sampling and compression operations are combined into
one low-complexity step, the proposed methodology can be considered as an important step towards applying the CS framework to audio coding applications.


ANALYSIS OPERATOR LEARNING FOR OVERCOMPLETE COSPARSE REPRESENTATIONS by
Mehrdad Yaghoobi, Sangnam Nam, Remi Gribonval, and Mike E. Davies. The abstract reads:
We consider the problem of learning a low-dimensional signal model from a collection of training samples. The mainstream approach would be to learn an overcomplete dictionary to provide good approximations of the training samples using sparse synthesis coefficients. This famous sparse model has a less well known counterpart, in analysis form, called the cosparse analysis model. In this new model, signals are characterized by their parsimony in a transformed domain using an overcomplete analysis operator. We propose to learn an analysis operator from a training corpus using a constrained optimization program based on L1 optimization. We derive a practical learning algorithm, based on projected subgradients, and demonstrate its ability to robustly recover a ground truth analysis operator, provided the training set is of sufficient size. A local optimality condition is derived, providing preliminary theoretical support for the well-posedness of the learning problem under appropriate conditions.


Estimation of Sparse MIMO Channels with Common Support by Yann Barbotin, Ali Hormati, Sundeep Rangan, Martin Vetterli. The anstract reads:
We consider the problem of estimating sparse communication channels in the MIMO context. In small to medium bandwidth communications, as in the current standards for OFDM and CDMA communication systems (with bandwidth up to 20 MHz), such channels are individually sparse and at the same time share a common support set. Since the underlying physical channels are inherently continuous-time, we propose a parametric sparse estimation technique based on finite rate of innovation (FRI) principles. Parametric estimation is especially relevant to MIMO communications as it allows for a robust estimation and concise description of the channels. The core of the algorithm is a generalization of conventional spectral estimation methods to multiple input signals with common support. We show the application of our technique for channel estimation in OFDM (uniformly/contiguous DFT pilots) and CDMA downlink (Walsh-Hadamard coded schemes). In the presence of additive white Gaussian noise, theoretical lower bounds on the estimation of SCS channel parameters in Rayleigh fading conditions are derived. Finally, an analytical spatial channel model is derived, and simulations on this model in the OFDM setting show the symbol error rate (SER) is reduced by a factor 2 (0 dB of SNR) to 5 (high SNR) compared to standard non-parametric methods - e.g. lowpass interpolation.


Weighted algorithms for compressed sensing and matrix completion by Stéphane Gaïffas, Guillaume Lecué. Thye abstract reads:
This paper is about iteratively reweighted basis-pursuit algorithms and matrix completion problems. In a first part, we give a theoretical explanation of the fact that reweighted basis pursuit can improve a lot upon basis pursuit for exact recovery in compressed sensing. We exhibit a condition that links the accuracy of the weights to the RIP and incoherency constants, which ensures exact recovery. In a second part, we introduce a new algorithm for matrix completion, based on the idea of iterative reweighting. Since a weighted nuclear "norm" is typically non-convex, it cannot be used easily as an objective function. So, we define a new estimator based on a fixed-point equation. We give empirical evidences of the fact that this new algorithm leads to strong improvements over nuclear norm minimization on simulated and real matrix completion problems.


For comparison purposes, it would have been great if figure 1 could have been compared to the figure and variables of the Donoho-Tanner phase transition curve. I am just saying.

Sunday, July 10, 2011

The Last Rendez Vous Pitch Maneuver

With Atlantis now docked on the International Space Station, this maneuver was the last one

Saturday, July 09, 2011

About that 3D lens free imager

After reading more about the lensless 3d "Fourier Imager" from the Cornell group mentioned earlier this week by Dan Reetz, I could not but recall a similar set up used in the Anger camera and it obviously would be conducive to an efficient compressive implementation.

Printfriendly