Nuit Blanche

Tuesday, February 07, 2012

Randomized Items [updated]

Petros Boufounos has two internships related to compressive sensing at MERL.

If you have a need for an intern who understands compressive sensing, there is a probability she or he reads Nuit Blanche.

Yesterday, on the Twitter, two of you pointed me to some other instances of nonlinear compressive sensing. Alejandro pointed to FROG, while Laurent pointed to phase retrieval from partial Fourier measurements since the solver has to deal with intensities rather than amplitudes. For FROG, I am a little more reserved as indeed one seems to need to use nonlinear measurements but right now I know of no paper that has solved this problem with an explicit sparsity constraint. I recall that it is mentioned in a recent paper, but I have not seen the solver used for that purpose. Maybe I should put out a list of problems I have not seen solved so far.

A reader asks when a conference with an emphasis on Compressive Sensing will take place in the U.S. The next best thing I can think of is look up the SIVA list of conferences. as I am not aware of a specifically dedicated meeting on the subject within the next 12 months. Maybe some of the readers can help.

Next I want to write an entry on the issue of calibration. This is not a sexy subject, but as in many cases with compressive sensing, we need to revisit it and go back to the basics. I recall that calibration was something you would do in high school and relied on least squares apporaches. Well since we are revisiting the least square approach in the form of the l_2 minimization, what about doing the same on this very old subject. It will at least be some sort of compilation of these entries. Let me know if there is an aspect of that that I have not covered yet.

The LinkedIn Compressive Sensing group has more than 1299 members right now, while the Matrix Factroization one has about 176 members. I find it very interesting that there is not much overlap between the two groups.

Finally, as Zhilin pointed out, The ITA meeting is currently taking place in San Diego, you may want to take a look at the presentation abstracts here.

Image Credit: NASA/JPL/Space Science Institute Full-Res: N00181197.jpg
N00181197.jpg was taken on February 05, 2012 and received on Earth February 05, 2012. The camera was pointing toward TITAN at approximately 2,933,044 kilometers away, and the image was taken using the CL1 and CB3 filters.

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, February 06, 2012

Nonlinear Compressive Sensing

There are subjects that are less covered than others. Mostly because it is less convenient to deal with them or maybe because they are islands of knowledge, i.e. a small set of people live in them untouched by the rest of the community because the waters have not receded yet (see What Island is Next ?). I made a request on LinkedIn for any references related to nonlinear compressive sensing without much explanation as to I meant by nonlinear. I look forward to more (just add them in the comment section) but here is what we have so far:

The whole field of 1bit Compressive Sensing and low quantization CS with their attendant solvers,
Compressed Sensing with Nonlinear Observations by Thomas Blumensath (Sparsify solver)
Some Algorithmic Problems and Results in Compressed Sensing by Muthu Muthukrishnan
Poisson Compressed Sensing and Performance Bounds on Compressed Sensing with Poisson Noise by Rebecca Willett and Maxim Raginsky
An Iteratively Reweighted Algorithm for Sparse Reconstruction of Subsurface Flow Properties from Nonlinear Dynamic Data by Lianlin Li and Jafarpour
Sparse Interactions: Identifying High-Dimensional Multilinear Systems via Compressed Sensing by Nazer and Nowack
Using the Kernel Trick in Compressive Sensing: Accurate Signal Recovery from Fewer Measurements by Qi and Hughes
Sparse Volterra and Polynomial Regression Models: Recoverability and Estimation by Kekatos and Giannakis
Highly nonlinear approximations for sparse signals representations project: http://www.nonlinear-approx.info/overview/index.html
Sundeep Rangan's generalized AMP algorithm supports arbitrary probabilistic output channels that, in effect, model output linearities such as quantization. (an implementation of GAMP is here)
Optimized measurements for kernel compressive sensing by K. N. Ramamurthy and A. Spanias,
Boolean solvers involved in Group Testing and Sudoku solving
Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing by Yoav Shechtman, Yonina C. Eldar, Alexander Szameit, Mordechai Segev

Thanks to Matthieu Puigt, Phil Schniter and Karthikeyan Natesan Ramamurthy for responding to the query:

Sunday, February 05, 2012

EE/CS Dept Head search, RFP for Special issue on Relaxation Methods in Identification and Estimation Problems

Mike Wakin sent me the following:

Dear Igor,

After a recent reorganization at the Colorado School of Mines, our EE and CS programs have been joined into a brand new EECS department. We are now in the process of searching for our first Department Head.

More details about this search are available here:

http://inside.mines.edu/UserFiles/File/hr/Job%20Openings/Academic%20Faculty/12-081010DepartmentHeadEECS.pdf

This person will undoubtedly play an important role in shaping the future of our program.

If you happen to know anyone who would be interested in and qualified for this position, I would greatly appreciate you passing along this information. Anyone is welcome to contact me at mwakin at mines.edu for further information.

Thanks and best regards,

-Mike

Borhan Sanandaji also sent me the following:

Dear Igor,

I would like to bring your attention to the attached announcement of the special issue of the IEEE Transactions on Automatic Control (TAC) on "Relaxation Methods in Identification and Estimation Problems". The corresponding guest editor of this special issue, Prof. Diego Regruto asked me to advertise the special issue in the signal processing/compressive sensing community and I could not think of any other places better than your great blog, the Nuit Blanche, for doing that. Would you please post the announcement of this special issue of TAC on Nuit Blanche? More details of the special issue can be found in the attached announcement and also here http://www.nd.edu/%7Eieeetac/special.html

The topics relevant to this session include (but are not limited to) the following approaches:

Convex relaxation techniques

LMI/SDP-based relaxation techniques (Sum of squares decompositions, moment-based approaches, etc.)

l1-minimization approaches

Probabilistic/randomized methods

Rank/nuclear norm minimization techniques

Compressive sensing

I really appreciate your help in advance and please let me know if you any questions.

Cheers,

Borhan

Sure Borhan.

Friday, February 03, 2012

Calibrating a Compressive Sensing System

As I was reading this presentation from Andrew Waters, I was reminded of the calibration issue I keep on mentioning every once in a while. Dynamic range is a known issue in compressive sensing because every measurement is the linear combination of many several "normal" measurements. In other words, compressive measurements are larger while requiring a similar resolution as "normal" measurements. All the quantization work generated around compressive sensing stems from needing to understand in the interplay between quantization and dynamic range issues. As it turns out, the example used here is the single pixel camera (see how it works here) which is used as a spectral imager. The concern is that the pixel may not be deep enough or have enough resolution in its A/D system.

What's important is really to note that saturation is in fact an issue and one wonders how one can recover from it or be able to live with it.

and it looks like in order to not pollute your system, one rather want to reject saturated measurements.

As Mark Davenport mentioned in Google + thread, the blue curve is the recovery if one uses the conventional approach a rescale the signals so that they fit into the depth of the dynamic range (at the expense of the quantization of the sample) whereas the red one is the one shows a system where saturated measurements are discarded so that the rest of the sample that fit can have better discretization. In the attendant paper [1], another method enforces consistency:whereby the saturated measurements are included in the optimization steps and reconstructed with SC-CoSAMP, From [1]

1) the conventional approach, scaling the signal so that the saturation rate is zero and reconstructing with the program (3);

2) the rejection approach, discarding saturated measurements before reconstruction with (4); and

3) the consistent approach, incorporating saturated measurements as a constraint in the program (6).

As one can see, the consistent approach does not help much besides increasing the complexity of the solver. However, I wonder if something could not be done using the fact that most calibrating images could come from a low dimensional manifold or use the recent matrix completion or low rank solvers in some way. There is more information on this Google+ thread.

[1] Democracy in Action: Quantization, Saturation, and Compressive Sensing, Jason N. Laska, Petros T. Boufounos, Mark A. Davenport, and Richard G. Baraniuk

It never was noise; Just a different convolution

One of the difficulties working with video material is that suddenly everything gets bigger and computations go slower fast. This is the reason we had to crop the scene in the Fukushima endoscopic videos. The scene analyzed was essentially a cropped version of the next 12 seconds of the following video

(at one minute into the video)

That yielded this result :

Obviously, random projections as implemented in SpaRCS would be helpful. A compressive sensing of the dynamical scenes of this video might also give us a way to think of the type of important parameters a compressive sensing system were to use in this type of situation. One of the interesting feature of these shots is that the "noise" or blips observed on the focal plane array, are not unlike what one would see in a hyperspectral video a la CASSI where a third dimension (spectral information) is embedded in each 2D shot through a hardware based convolution. Here, the hardware based convolution is the interaction between the radiation field and the hardware instance of the focal plane array which result in these "noisy" or more exactly radiation modulated images.

Thursday, February 02, 2012

Robust Denoising Fukushima Endoscopic Videos

[ このビデオは東京電力によって公開された、福島第一原発の第5核融合炉の内部を映したものです。
我々は新しく考案したRobust PCA等を用いた新しいアルゴリズムを用いて、水滴や放射線等によるノイズを除去しました。

http://nuclear.tamu.edu/~kurwitz/

The following videos were released by TEPCO. They show the inside of reactor 5 at Fukushima Daiichi. We processed these videos using new techniques such as Robust PCA to evaluate the algorithm's capabilities to separate background information from more dynamic information such as water droplets and radiation hits on the focal plane array. Thank you Julien, Yasuda-san and Tsuji-san for the translation. ].

In Robust Denoise This! I wondered if there was a way to denoise the videos coming out of endoscopic visualization of the containment vessel of reactor 5 at Fukushima Daiichii. One of the impediment of videos being inserted in this area is clearly related to the radiation field and water droplets that render the video very noisy. We are here well outside the comfortable academic benchmarks used to figure out the quality of denoising algorithms. However, I am of the opinion that any of the Robust PCA or other advanced Matrix Factorization techniques can only be field tested with actual footages that have not been carefully prepared like these endoscopic shots.

For this reason, Cable Kurwitz and I were thinking about what could be obtained from this sort of shots. Let us first realize that these endoscopic shots were performed on one of the least damaged reactor and so radiation issue for this survey would be more like what could be expected from a reactor that has gone through a normal cold shutdown operation

The GoDec solver was used for this preliminary trial. It performs a low rank decomposition added with a sparse and noisy component. We were wondering if the radiation field (mostly bleeps occurring at every frame at different locations) would be caught by the noisy component. By the way, they are not truly blips because the videos themselves seem to have been transform coded with MPEG: i.e every hit has become more like small crosses. We hypotethized that the droplets would mostly be in the sparse component so that the noisy component would provide a proxy for the radiation level seen by the endoscopic Focal Place Array. In other words, we could use the video also as radiation detector.. Here is the result so far from about 800 frames at 1 minutes into video 2:

Here is what we can see:

The low rank component (1) is pretty nice and steady and seems to be able to catch different illuminations
The noisy component (3) does indeed catch most of the the radiation hits but
it also catches some of the droplet component (so the noisy component cannot be used right away as a proxy to the radiation level).
The sparse components (2) picks up most of the droplets

Additional processing would need to be performed on the noisy component to catch only the radiation hit component.

TFOCS version 1.1 is out with demos (RPCA, SVM, Matrix Completion)

Stephen Becker sent me the following:

Hi Igor,

I'm happy to announce that we have an updated version of TFOCS (version 1.1). It has more building-block functions, more examples, and some bug fixes. We have demos for compressed sensing, image denoising, sparse SVM, matrix completion, and robust PCA, as well as examples for solving arbitrary LP, QP and SDP.

The speed is usually competitive with other state-of-the-art first-order methods, and always faster than interior-point methods on large-scale problems.

We hope the software will be used like a large-scale CVX (cvxr.com) for people who need to prototype new algorithms.

The website is http://tfocs.stanford.edu/. Most of the demos are in the code package, but four of them are also in html format at: http://tfocs.stanford.edu/demos/

Best,

Stephen

From the current demo page:

Demos
RPCA demo (from SIAM OPT 11 conference). This shows how to use TFOCS to perform Robust Principal Component Analysis. For a background on RPCA, see Robust Principal Component Analysis? by J. Candès, X. Li, Y. Ma, and J. Wright, in Journal of ACM 58(1), 1-37.
Support Vector Machine (SVM) demo. This covers basic SVM as well as a type of sparse-SVM. For a background in SVM, there are many online resources; a good introduction is chapter 8.6 of the free online textbook Convex Optimization by Stephen Boyd and Lieven Vandenberghe (2004).
Matrix completion demo. This demonstrates recovering a low-rank matrix from partially observed entries via nuclear norm minimization. For a background on nuclear norm minimization, see Exact matrix completion via convex optimization by E. J. Candès and B. Recht, in Found. of Comput. Math., 9 717-772.

I'll be adding TFOCS to the Matrix Factorization Jungle page as well. Thanks Stephen.

Wednesday, February 01, 2012

On Wondering Star today: Imaging Volcanoes with Atmospheric Muons

I just wrote an entry on Imaging Volcanoes with Atmospheric Muons on Wondering Star, the blog where sensors are the size of a planet...

Enjoy!

Compressive Sensing of Dynamical Scenes with demo code

Aswin Sankaranarayanan just let me know that the Compressive Acquisition of Dynamical Scenes page is up with an attendant demo. Aswin also mentions that:

The code is a bit specialized for normal purposes since it involves a special measurement process. The file demo.m is set to automatically run, simulate compressive measurements and then the video recovery process. The code is also a bit on the slower side --- as is almost the case when we deal with videos.

The attendant paper is: Compressive Acquisition of Dynamical Scenes by Aswin C. Sankaranarayanan , Pavan Turaga, Rama Chellappa, Richard Baraniuk. The abstract reads:

Abstract. Compressive sensing (CS) is a new approach for the acquisition and recovery of sparse signals and images that enables sampling rates signifi cantly below the classical Nyquist rate. Despite signifi cant progress in the theory and methods of CS, little headway has been made in compressive video acquisition and recovery. Video CS is complicated by the ephemeral nature of dynamic events, which makes direct extensions of standard CS imaging architectures and signal models di cult. In this paper, we develop a new framework for video CS for dynamic textured scenes that models the evolution of the scene as a linear dynamical system (LDS). This reduces the video recovery problem to first estimating the model parameters of the LDS from compressive measurements, and then reconstructing the image frames. We exploit the low-dimensional dynamic parameters (the state sequence) and high-dimensional static parameters (the observation matrix) of the LDS to devise a novel compressive measurement strategy that measures only the dynamic part of the scene at each instant and accumulates measurements over time to estimate the static parameters. This enables us to lower the compressive measurement rate considerably. We validate our approach with a range of experiments involving both video recovery, sensing hyper-spectral data, and classi cation of dynamic scenes from compressive data. Together, these applications demonstrate the eff ectiveness of the approach.

Thanks Aswin.

The Cost of Knowledge is Too Damn High Party

Echoing the The rent is too damn high party, here is the cost of knowledge is too damn high party geared toward Elsevier, will you be part of it ?

http://thecostofknowledge.com/