CS: SpiralTap code, Single exposure super-resolution compressive imaging, IMP, three talks.

Zac Harmany just sent me the following:

Hi Igor,
Thanks for kindly featuring our work on Nuit Blanche today! Just wanted to let you know that I have our ISBI paper on my page if you wanted to link to it:

http://people.ee.duke.edu/~zth/publications/

There's also one other ICIP paper listed there: "Poisson Image Reconstruction with Total Variation Regularization." Also we have released a MATLAB toolbox for SPIRAL which solves inverse problems in the presence of Poisson noise. This is the code that was used in the experiments in the above papers, and the paper you had featured earlier this summer that we had submitted to Transactions on Image Processing. Feel free to pass along that anyone can try out our code (with feedback welcome and appreciated), available here:

http://people.ee.duke.edu/~zth/software/

Hope all is well and keep up the great work on Nuit Blanche,

-Zac Harmany
Graduate Student
Electrical and Computer Engineering
Duke University

Here is the paper he is mentioning: Poisson Image Reconstruction with Total Variation Regularization, by Rebecca Willett. Zachary Harmany and Roummel Marcia. The abstract reads:

This paper describes an optimization framework for reconstructing nonnegative image intensities from linear projections contaminated with Poisson noise. Such Poisson inverse problems arise in a variety of applications, ranging from medical imaging to astronomy. A total variation regularization term is used to counter the ill-posedness of the inverse problem and results in reconstructions that are piecewise smooth. The proposed algorithm sequentially approximates the objective function with a regularized quadratic surrogate which can easily be minimized. Unlike alternative methods, this approach ensures that the natural nonnegativity constraints are satisfied without placing prohibitive restrictions on the nature of the linear projections to ensure computational tractability. The resulting algorithm is computationally efficient and outperforms similar methods using wavelet-sparsity or partition-based regularization.

From the software website:

Overview The Sparse Poisson Intensity Reconstruction ALgrotihms (SPIRAL) toolbox, SPIRALTAP.m, is MATLAB code for recovering sparse signals from Poisson observations. SPIRAL minimizes a regularized negative log-likelihood objective function with various penalty choices for the regularization terms:

• Sparsity (l1 norm) of the coefficients in an orthonormal basis [SPIRAL-ONB],
• Total variation seminorm of the image [SPIRAL-TV],
• Penalty based on Recursive Dyadic Partitions (RDPs) [SPIRAL-RDP], and
• Penalty based on translationally-invariant (cycle-spun) RDPs [SPIRAL-RDPTI].

For more details, see: Zachary T. Harmany, Roummel F. Marcia, Rebecca M. Willett, “This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms – Theory and Practice,” Submitted to IEEE Transactions on Image Processing. [PDF (arXiv.org)]

Thanks Zac !

also found on the web and on arxiv:

Single exposure super-resolution compressive imaging by double phase encoding by Yair Rivenson, Adrian Stern, and Bahram Javidi. The abstract reads:

Super-resolution is an important goal of many image acquisition systems. Here we demonstrate the possibility of achieving super-resolution with a single exposure by combining the well known optical scheme of double random phase encoding which has been traditionally used for encryption with results from the relatively new and emerging field of compressive sensing. It is shown that the proposed model can be applied for recovering images from a general image degrading model caused by both diffraction and geometrical limited resolution.

IMP: A Message-Passing Algorithm for Matrix Completion by Byung-Hak Kim, Arvind Yedla, Henry Pfister. The abstract reads:

A new message-passing (MP) method is considered for the matrix completion problem associated with recommender systems. We attack the problem using a (generative) factor graph model that is related to a probabilistic low-rank matrix factorization. Based on the model, we propose a new algorithm, termed IMP, for the recovery of a data matrix from incomplete observations. The algorithm is based on a clustering followed by inference via MP (IMP). The algorithm is compared with a number of other matrix completion algorithms on real collaborative filtering (e.g., Netflix) data matrices. Our results show that, while many methods perform similarly with a large number of revealed entries, the IMP algorithm outperforms all others when the fraction of observed entries is small. This is helpful because it reduces the well-known cold-start problem associated with collaborative filtering (CF) systems in practice.

Things to come generally can be seen firsthand in informal presentations, here are three that are about to take place and took place in Israel, Germany and China:

Pixel Club Seminar: Compressed Sensing for Hyperspectral Imaging

Speaker:
Udi Pfeffer (CS, Technion)
Date:
Wednesday, 14.7.2010, 11:30
Place:
Room 337-8 Taub Bld.


We introduce a system for hyperspectral imaging based on micro-mirror array, that projects subsets of image pixels onto a prism (or diffraction grating), followed by a CCD-type sensor. This system allows generalized sampling schemes including compressed sensing. We acquire only a fraction of the samples that are required to obtain the full-resolution signal (hyperspectral cube in our case), and by means of non-linear optimization recover the underlying signal. We use a prior knowledge about the signal sparsity in some dictionary, and its limited total variation. We also introduce additional measurements of full-resolution image using small number of filters similar to RGB. As a result, we obtain a feasible system for hyperspectral imaging that enables faster acquisition compared to traditional sampling systems. We present sensitivity analysis of our system to dark and shot noise.

*M.Sc thesis seminar under the supervision of Prof. Ehud Rivlin and Dr. Michael Zibulevsky.

An ALPS’ view of Compressive Sensing

Volkan Cevher, Assistant Professor
Ecole Polytechnique Fédérale de Lausanne

Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for acquisition of sparse or compressible signals that can be well approximated by just K much less than N elements from an N-dimensional basis. Instead of taking periodic samples, we measure inner products with M less than N random vectors and then recover the signal via a sparsity-seeking optimization or greedy algorithm. The standard CS theory dictates that robust signal recovery is possible from M=O(K log(N/K)) measurements. The implications are promising for many applications and enable the design of new kinds of analog-to-digital converters, cameras and imaging systems, and sensor networks. In this talk, we introduce three first-order, iterative CS recovery algorithms, collectively dubbed algebraic pursuits (ALPS), and derive their theoretical convergence and estimation guarantees. We empirically demonstrate that ALPS outperforms the Donoho-Tanner phase transition bounds for sparse recovery using Gaussian, Fourier, and sparse measurement matrices. We then describe how to use ALPS for CS recovery in redundant dictionaries. Finally, we discuss how ALPS can also incorporate union-of-subspaces-based sparsity models in recovery with provable guarantees to make CS better, stronger, and faster.

New RIP and MIP Bounds in Compressed Sensing

Guangwu Xu University of Wisconsin--Milwaukee
July 6, Tuesday 9:00

The exciting new field of compressed sensing concerns efficient recovery of sparse signals from considerably fewer (linear) measurements. This technique of information processing has numerous potential applications in areas including statistics, medical imaging, decoding and encryption.
In this talk, we shall describe a family of RIP conditions that ensure the reconstruction of sparse data via convex minimization, for compressed sensing matrices. Some simple conditions which are of theoretical and practical interest can be deduced from this family. The main ingredients of our approach include the norm inequality and the square-root lifting inequality. The improvement on the conditions shows that signals with larger support can be recovered accurately. Issues on compressed sensing matrix design and our complete solution of sparse recovery in the mutual incoherence framework will also be touched on.
(Joint work with Tony Cai and Lie Wang.)

Credit: NASA / JPL / SSI / color composite by Gordan Ugarkovic. Via the planetary society blog.
Cassini captured the frames for this approximately true color view of the moon Daphnis and the wakes it excites at the edge of the Keeler gap in Saturn's A ring on July 5, 2010 from a distance of about 73,000 kilometers.