Nuit Blanche: Search results for "Stefano Marchesini"

Showing posts sorted by relevance for query "Stefano Marchesini". Sort by date Show all posts

Friday, February 04, 2011

Compressive auto-indexing in femtosecond nanocrystallography

Stefano Marchesini sent me the following:

Hi Igor,
there is a recent paper in Nature that might be of interest to you:
http://www.nature.com/nature/journal/v470/n7332/full/nature09750.html

several terabytes of data were processed using fairly standard crystallographic software, but we are investigating better ways. The connection with compressive sensing is made here:
http://arxiv.org/abs/1011.3072
The model was very simple and needs work, I include the code used for the figures of that paper, in case you are interested, (it takes too much paperwork to publish it myself).

Cheers,
Stefano

The Nature paper is :Femtosecond X-ray protein nanocrystallography by Henry N. Chapman, Petra Fromme, Anton Barty, Thomas A. White, Richard A. Kirian, Andrew Aquila, Mark S. Hunter, Joachim Schulz, Daniel P. DePonte, Uwe Weierstall, R. Bruce Doak, Filipe R. N. C. Maia, Andrew V. Martin, Ilme Schlichting, Lukas Lomb, Nicola Coppola, Robert L. Shoeman, Sascha W. Epp, Robert Hartmann, Daniel Rolles, Artem Rudenko, Lutz Foucar, Nils Kimmel, Georg Weidenspointner, Peter Holl, Mengning Liang, Miriam Barthelmess, Carl Caleman, Sébastien Boutet, Michael J. Bogan, Jacek Krzywinski, Christoph Bostedt, Saša Bajt, Lars Gumprecht, Benedikt Rudek, Benjamin Erk, Carlo Schmidt, André Hömke, Christian Reich, Daniel Pietschner, Lothar Strüder, Günter Hauser, Hubert Gorke, Joachim Ullrich, Sven Herrmann, Gerhard Schaller, Florian Schopper, Heike Soltau, Kai-Uwe Kühnel, Marc Messerschmidt, John D. Bozek, Stefan P. Hau-Riege, Matthias Frank, Christina Y. Hampton, Raymond G. Sierra, Dmitri Starodub, Garth J. Williams, Janos Hajdu, Nicusor Timneanu, M. Marvin Seibert, Jakob Andreasson, Andrea Rocker, Olof Jönsson, Martin Svenda, Stephan Stern, Karol Nass, Robert Andritschke, Claus-Dieter Schröter, Faton Krasniqi, Mario Bott, Kevin E. Schmidt, Xiaoyu Wang, Ingo Grotjohann, James M. Holton, Thomas R. M. Barends, Richard Neutze, Stefano Marchesini, Raimund Fromme, Sebastian Schorb, Daniela Rupp, Marcus Adolph, Tais Gorkhover, Inger Andersson, Helmut Hirsemann, Guillaume Potdevin,Heinz Graafsma,Björn Nilsson; John C. H. Spence et al. the abstract reads:

X-ray crystallography provides the vast majority of macromolecular structures, but the success of the method relies on growing crystals of sufficient size. In conventional measurements, the necessary increase in X-ray dose to record data from crystals that are too small leads to extensive damage before a diffraction signal can be recorded1, 2, 3. It is particularly challenging to obtain large, well-diffracting crystals of membrane proteins, for which fewer than 300 unique structures have been determined despite their importance in all living cells. Here we present a method for structure determination where single-crystal X-ray diffraction ‘snapshots’ are collected from a fully hydrated stream of nanocrystals using femtosecond pulses from a hard-X-ray free-electron laser, the Linac Coherent Light Source4. We prove this concept with nanocrystals of photosystem I, one of the largest membrane protein complexes5. More than 3,000,000 diffraction patterns were collected in this study, and a three-dimensional data set was assembled from individual photosystem I nanocrystals (~200 nm to 2 μm in size). We mitigate the problem of radiation damage in crystallography by using pulses briefer than the timescale of most damage processes6. This offers a new approach to structure determination of macromolecules that do not yield crystals of sufficient size for studies using conventional radiation sources or are particularly sensitive to radiation damage.

The connecting paper (to compressive sensing) is: Compressive auto-indexing in femtosecond nanocrystallography by Filipe R. N. C. Maia, Chao Yang, Stefano Marchesini. The abstract reads:

Ultrafast nanocrystallography has the potential to revolutionize biology by enabling structural elucidation of proteins for which it is possible to grow crystals with 10 or fewer unit cells on the side. The success of nanocrystallography depends on robust orientation-determination procedures that allow us to average diffraction data from multiple nanocrystals to produce a three dimensional (3D) diffraction data volume with a high signal-to-noise ratio. Such a 3D diffraction volume can then be phased using standard crystallographic techniques. "Indexing" algorithms used in crystallography enable orientation determination of diffraction data from a single crystal when a relatively large number of reflections are recorded. Here we show that it is possible to obtain the exact lattice geometry from a smaller number of measurements than standard approaches using a basis pursuit solver.

And the code is here. Thanks Stefano !

Thursday, November 06, 2008

CS: Ab Initio Compressive Phase Retrieval

I was wondering when this subject would come up. Out of the many indirect sensing schemes, diffraction is a sensing scheme that most everybody has heard about. It is a lensless imaging process that requires a computational step to obtain an image.

On top of it, one can use a high luminosity source, as high as the sample allows. Stefano Marchesini has written on the subject with a particular view on how Compressive sensing could be used to alleviate some of the very large sampling required by the current direct methods. In some of the approaches, there is some consideration for using coded apertures.

An introduction on the subject can be found in this recent presentation entitled Large scale inverse problems in ultrafast x-ray imaging. A previous abstract of the presentation reads:

The Fourier inversion of coherent diffraction patterns offers diffraction-limited three dimensional images without the aberrations, inefficiencies and depth-of field limitations of lens-based tomographic systems. We report experimental images inverted using holographic and computational phase retrieval methods. Ultimately the resolution of X-ray diffraction imaging will be limited by radiation damage. This limit can be overcome using pulses faster than the damage process. The first experimental verification of the principle of flash diffraction imaging using a soft X-ray free-electron laser will be presented. Experiments aimed at the characterization of the dynamics of organic matter under intense radiation and validation of theoretical models will be discussed.

For a more in-depth introduction on the subject, one should check A unified evaluation of iterative projection algorithms for phase retrieval. The number of measurements becomes a burden when trying to invert the computational problem as shown in the following slide:

Hence Compressive Sensing is probably becoming an obvious solution to investigate. This is done in Ab initio compressive phase retrieval by Stefano Marchesini. The abstract reads:

Any object on earth has two fundamental properties: it is finite, and it is made of atoms. Structural information about an object can be obtained from diffraction amplitude measurements that account for either one of these traits. Nyquist-sampling of the Fourier amplitudes is sufficient to image single particles of finite size at any resolution. Atomic resolution data is routinely used to image molecules replicated in a crystal structure. Here we report an algorithm that requires neither information, but uses the fact that an image of a natural object is compressible. Intended applications include tomographic diffractive imaging, crystallography, powder diffraction, small angle x-ray scattering and random Fourier amplitude measurements.

I note the use of Sparco and SPGL-1. In Stefano Marchesini's presentation page, one can find additional mateiral such as a list of most experiments that could use CS here. There are also two other talks (here and here).

I am sure I'll come back to this later.

Thursday, September 27, 2012

Alternating Direction Methods for Classical and Ptychographic Phase Retrieval

Stefano just sent me the following:

Hi Igor,

I'd like to bring your attention to some references on phase retrieval, I hope you enjoy the links:

http://math.sjtu.edu.cn/faculty/zw2109/paper/PRADM.pdf

http://arxiv.org/abs/1209.4924

a presentation by Filipe Maia on Multi-GPU Real-Time Ptychographic X-ray Image Reconstruction at http://nvidia.fullviewmedia.com/gtc2012/0516-A8-S0131.html

some diffraction data is available here :http://cxidb.org/

see also this (By Filipe Maia):

http://www.nature.com/nmeth/journal/v9/n9/full/nmeth.2110.html

cheers,

Stefano

Thanks Stefano .Here are the two papers:

Alternating Direction Methods for Classical and Ptychographic Phase Retrieval by Zaiwen Wen, Chao Yang, Xin Liu, Stefano Marchesini

Abstract. In this paper, we show how augmented Lagrangian alternating direction method (ADM) can be used to solve both the classical and ptychographic phase retrieval problems. We point out the connection between ADM and projection algorithms such as the hybrid input-output (HIO) algorithm, and compare its performance against standard algorithms for phase retrieval on a number of test images. Our computational experiments show that ADM appears to be less sensitive to the choice of relaxation parameters, and it usually outperforms the existing techniques for both the classical and ptychographic phase retrieval problems.

Augmented projections for ptychographic imaging by Stefano Marchesini, Andre Schirotzek, Filipe Maia, Chao Yang. The abstract reads:

Ptychography is a popular technique to achieve diffraction limited resolution images of a two or three dimensional sample using high frame rate detectors. We introduce a relaxation of common projection algorithms to account for instabilities given by intensity and background fluctuations, position errors, or poor calibration using multiplexing illumination. This relaxation introduces an additional phasing optimization at every step that enhances the convergence rate of common projection algorithms. Numerical tests exhibit the exact recovery of the object and the noise when there is high redundancy in the data.

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.

Thursday, September 24, 2015

Jobs: Center for Advanced Mathematics for Energy Research Applications (CAMERA)

Stefano Marchesini just sent me the following:

Dear Igor,

We had some good news from DOE office of Science to support and expand the Center for Advanced Mathematics for Energy Research Applications (CAMERA):http://newscenter.lbl.gov/2015/09/22/new-support-for-camera-to-develop-computational-mathematics-for-experimental-facilities-research/

I refer to the news release and our website camera.lbl.gov for a detailed description of all the projects. CAMERA’s mission is to develop fundamental mathematics and algorithms, delivered as data analysis software that can accelerate scientific discovery at the advanced scientific user facilities of DOE office of science.

I was hoping you could point to your vast and skilled readership that CAMERA has positions and visiting opportunities available across a collection of disciplines to meet data analysis challenges. Particularly valuable are cross-disciplinary skills blending combinations of such fields as-Applied mathematics, including statistics and machine learning.

Computational science.

Signal and image processing.

Scientific research at experimental facilities and laboratories.

Software engineering.

Further information about CAMERA, current projects, future expansion, and engagement opportunities may be found at camera.lbl.gov. contact information camera@math.lbl.gov

I'd be happy to answer questions about some of these opportunities as well, though not in all areas, primarily phase retrieval, inverse problems, parallel computing, x-ray science and technology, my contact below.

--

Lawrence Berkeley National Laboratory addresses the world’s most urgent scientific challenges by advancing sustainable energy, protecting human health, creating new materials, and revealing the origin and fate of the universe. Founded in 1931, Berkeley Lab’s scientific expertise has been recognized with 13 Nobel prizes. The University of California manages Berkeley Lab for the U.S. Department of Energy’s Office of Science. For more, visit www.lbl.gov.
DOE’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States, and is working to address some of the most pressing challenges of our time. For more information about DOE’s Office of Science please visit science.energy.gov.

--

Best, Stefano

|^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-^-
Stefano Marchesini http://smarchesini.lbl.gov
CAMERA, Advanced Light Source, MS 2-400
Lawrence Berkeley National Laboratory
1 Cyclotron Rd. Berkeley, CA 94720-8199, USA

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

Friday, December 31, 2010

Thank You !

[ I am still looking for the most interesting paper on Compressive Sensing you read in 2010 ? You can remain anonymous, just the title is enough, no need for full references.]

After the 2008 version, the 2009 version, here is the 2010 version of the Thank You Post. All of you listed below have one thing in common, you know about Nuit Blanche and had some sorts of a conversation on it this past year. Make no mistake, these conversation may have been short, but they helped somebody else. I am done with the introduction bit, now talk amongst yourselves :-). Sorry for the ones I missed, but here is the list in no particular order:

This past year has also seen a rise of websites linking to the blog, I have bestowed the honor of having Good Taste in All Manners to all the following blogs/websites:

Thank you, y'all.

Credit: NASA, JPL, Cornell, Texas A&M University. Sunset on Mars.

Friday, May 07, 2010

CS: SPIE meeting, Lensless wide-field fluorescent imaging, Compressive sensor networks, Multichannel Sampling RI, ECME Thresholding Methods.

You'd thought you'd go home with nothing to read. Fear not, it's not happening this week-end:

Stefano Marchesini let me know of the following SPIE meeting with several compressive sensing papers in them.

Hi Igor,
there are a few talks on compressive sensing in the following spie conference:
http://spie.org//app/program/index.cfm?fuseaction=conferencedetail&conference=7800

Thanks Stefano.

Today, we have some new hardware: Lensless wide-field fluorescent imaging on a chip using compressive decoding of sparse objects by Ahmet F. Coskun, Ikbal Sencan, Ting-Wei Su, and Aydogan Ozcan. The abstract reads:

We demonstrate the use of a compressive sampling algorithm for on-chip fluorescent imaging of sparse objects over an ultra-large field-of-view (>8 cm2) without the need for any lenses or mechanical scanning. In this lensfree imaging technique, fluorescent samples placed on a chip are excited through a prism interface, where the pump light is filtered out by total internal reflection after exciting the entire sample volume. The emitted fluorescent light from the specimen is collected through an on-chip fiber-optic faceplate and is delivered to a wide field-of-view opto-electronic sensor array for lensless recording of fluorescent spots corresponding to the samples. A compressive sampling based optimization algorithm is then used to rapidly reconstruct the sparse distribution of fluorescent sources to achieve ~10 µm spatial resolution over the entire active region of the sensor-array, i.e., over an imaging field-of-view of >8 cm2. Such a wide-field lensless fluorescent imaging platform could especially be significant for high-throughput imaging cytometry, rare cell analysis, as well as for micro-array research.

I'll add it shortly to the compressive sensing hardware page.

John Zheng Sun's thesis at MIT entitled: Compressive sensor networks : fundamental limits and algorithms is out. The abstract reads:

Compressed sensing is a non-adaptive compression method that takes advantage of natural sparsity at the input and is fast gaining relevance to both researchers and engineers for its universality and applicability. First developed by Candis et al., the subject has seen a surge of high-quality results both in its theory and applications. This thesis extends compressed sensing ideas to sensor networks and other bandwidth-constrained communication systems. In particular, we explore the limits of performance of compressive sensor networks in relation to fundamental operations such as quantization and parameter estimation. Since compressed sensing is originally formulated as a real-valued problem, quantization of the measurements is a very natural extension. Although several researchers have proposed modified reconstruction methods that mitigate quantization noise for a fixed quantizer, the optimal design of such quantizers is still unknown. We propose to find the optimal quantizer in terms of minimizing quantization error by using recent results in functional scalar quantization. The best quantizer in this case is not the optimal design for the measurements themselves but rather is reweighted by a factor we call the sensitivity. Numerical results demonstrate a constant-factor improvement in the fixed-rate case. Parameter estimation is an important goal of many sensing systems since users often care about some function of the data rather than the data itself. Thus, it is of interest to see how efficiently nodes using compressed sensing can estimate a parameter, and if the measurements scalings can be less restrictive than the bounds in the literature. We explore this problem for time difference and angle of arrival, two common methods for source geolocation. We first derive Cramer-Rao lower bounds for both parameters and show that a practical block-OMP estimator can be relatively efficient for signal reconstruction. However, there is a large gap between theory and practice for time difference or angle of arrival estimation, which demonstrates the CRB to be an optimistic lower bound for nonlinear estimation. We also find scaling laws 'for time difference estimation in the discrete case. This is strongly related to partial support recovery, and we derive some new sufficient conditions that show a very simple reconstruction algorithm can achieve substantially better scaling than full support recovery suggests is possible.

Multichannel Sampling of Pulse Streams at the Rate of Innovation by Kfir Gedalyahu, Ronen Tur, Yonina Eldar. The abstract reads:

We consider minimal-rate sampling schemes for streams of delayed and weighted versions of a known pulse shape. Such signals belong to the class of finite rate of innovation (FRI) models. The minimal sampling rate for these parametric signals, is the number of degrees of freedom per unit of time, referred to as the rate of innovation. Although sampling of pulse streams was treated in previous works, either the rate of innovation was not achieved, or the pulse shape was limited to diracs and the method was instable for high rates of innovation. In this work we propose a multichannel framework for pulse streams with arbitrary shape, operating at the rate of innovation. Our approach is based on modulating the input signal with a set of properly chosen waveforms, followed by a bank of integrators. We show that the pulse stream can be recovered from the proposed minimal-rate samples using standard tools taken from spectral estimation in a stable way even at high rates of innovation. In addition, we address practical implementation issues, such as reduction of hardware complexity and immunity to failure in the sampling channels. The resulting scheme is flexible and exhibits better noise robustness than previous approaches.

ECME Thresholding Methods for Sparse Signal Reconstruction by Kun Qiu, Aleksandar Dogandzic. The abstract reads:

We propose a probabilistic framework for interpreting and developing hard thresholding sparse signal reconstruction methods and present several new algorithms based on this framework. The measurements follow an underdetermined linear model, where the regression-coefficient vector is the sum of an unknown deterministic sparse signal component and a zero-mean white Gaussian component with an unknown variance. We first derive an expectation-conditional maximization either (ECME) iteration that guarantees convergence to a local maximum of the likelihood function of the unknown parameters for a given signal sparsity level. To analyze the reconstruction accuracy, we introduce the minimum sparse subspace quotient (SSQ), a more flexible measure of the sampling operator than the well-established restricted isometry property (RIP). We prove that, if the minimum SSQ is sufficiently large, ECME achieves perfect or near-optimal recovery of sparse or approximately sparse signals, respectively. We also propose a double overrelaxation (DORE) thresholding scheme for accelerating the ECME iteration. If the signal sparsity level is unknown, we introduce an unconstrained sparsity selection (USS) criterion for its selection and show that, under certain conditions, applying this criterion is equivalent to finding the sparsest solution of the underlying underdetermined linear system. Finally, we present our automatic double overrelaxation (ADORE) thresholding method that utilizes the USS criterion to select the signal sparsity level. We apply the proposed schemes to reconstruct sparse and approximately sparse signals from tomographic projections and compressive samples.

Friday, August 21, 2009

CS: Post-Doc at Lawrence Berkeley Labs.

Stefano Marchesini wants to let y'all know about this Post-Doc fellowship opportunity at Lawrence Berkeley labs:

Physicist Postdoc Fellow (X-ray Coherent Imaging and Scattering)
Req Number:

The Advanced Light Source Division (ALS) at Lawrence Berkeley National Laboratory (Berkeley Lab) offers an exciting postdoctoral fellow opportunity to conduct experiments at the ALS and develop experimental and theoretical methods for x-ray coherent imaging and scattering. This position reports to the Coherent Imaging lead scientist within the Experimental Systems Group.

Key responsibilities include:

Develop experimental and theoretical methods for x-ray coherent imaging, holography and general scattering.
Communicate work results via reports and oral presentations, including participation in meetings, reviews, conferences, and publications in refereed journals.

Qualifications include:

Ph.D. in Optics, Physics or Engineering within the last 2 years
Experience with complex experimental apparatuses such as synchrotron beamlines and/or optical measurements
Familiarity with signal processing (phase retrieval, compressive sensing) and/or familiarity with experimental techniques of synchrotron radiation research is advantageous.

Note : This is a one-year term appointment with the possibility of renewal after one year based on demonstrated performance and availability of funds.

Thanks Stefano !
I'll add it to the Compressive Sensing Jobs page later.

Wednesday, December 03, 2008

CS: GPUCamp, 2 comments, large scale version of the SaMP package, CS with Sequential Observations, Instance Optimal Decoding by Thresholding in CS

Stefano Marchesini has just put up a presentation shown at the UTK Colloquium. This is a 39 MB movie of the slides. If y'all are not reading the comments, Stefano kindly mentioned the following aftter being featured here:

For fairness, the CS part was inspired by Matthew Moravec et al. "Compressive Phase Retrieval", Wavelets XII, SPIE 6701, No. 1. (2007)

It's funny, I did not see it listed on the Rice Repository. The closest I can find is this one.

Thong Do just released a large scale version of the Sparsity Adaptive Matching Pursuit package. More information can be found here. The link is also in the big picture reconstruction section.

Ramesh Raskar has updated his Camera Culture site. One can read more about his fascinating hardware development projects here. He is also recruiting.

Also found two new additions on the Rice Repository:

Compressed Sensing with Sequential Observations by Dmitry Malioutov, Sujay Sanghavi, Alan Willsky. The abstract reads:

Compressed sensing allows perfect recovery of a signal that is known to be sparse in some basis using only a small number of measurements. The results in the literature have focused on the asymptotics of how many samples are required and the probability of making an error for a fixed batch of samples. We investigate an alternative scenario where observations are available in sequence and can be stopped as soon as there is reasonable certainty of correct reconstruction. For the random Gaussian ensemble we show that a simple stopping rule gives the absolute minimum number of observations required for exact recovery, with probability one. However, for other ensembles like Bernoulli or Fourier, this is no longer true, and the rule is modified to trade off delay in stopping and probability of error. We also describe a stopping rule for the nearsparse case which tells when enough observations are made to reach a desired tolerance in reconstruction. Sequential approach to compressed sensing involves the solution of a sequence of linear programs, and we outline how this sequence can be solved efficiently.

and Instance Optimal Decoding by Thresholding in Compressed Sensing by Albert Cohen, Wolfgang Dahmen, and Ronald DeVore. The abstract reads:

Compressed Sensing seeks to capture a discrete signal x element of R^N with a small number n of linear measurements. The information captured about x from such measurements is given by the vector y = \phi x element of R^n where is an n x N matrix. The best matrices, from the viewpoint of capturing sparse or compressible signals, are generated by random processes, e.g. their entries are given by i.i.d. Bernoulli or Gaussian random variables. The information y holds about x is extracted by a decoder mapping R^n into R^N. Typical decoders are based on l1-minimization and greedy pursuit. The present paper studies the performance of decoders based on thresholding. For quite general random families of matrices , decoders are constructed which are instance-optimal in probability by which we mean the following. If x is any vector in R^N, then with high probability applying \delta to y = \phi x gives a vector x :=\Delta (y) such that ||x-x^-|| less than C_0 \sigma_k(x)_l2 for all k less than a n / logN provided a is suciently small (depending on the probability of failure). Here \sigma_k(x)_l2 is the error that results when x is approximated by the k sparse vector which equals x in its k largest coordinates and is otherwise zero. It is also shown that results of this type continue to hold even if the measurement vector y is corrupted by additive noise: y = \phi x + e where e is some noise vector. In this case \sigma_k(x)_l2 is replaced by \sigma_k(x)_l2 + ||e||_l2 .

Finally, found on ArXiv,

L1Packv2: A Mathematica package for minimizing an $\ell_1$-penalized functional by Ignace Loris. The abstract reads:

L1Packv2 is a Mathematica package that contains a number of algorithms that can be used for the minimization of an $\ell_1$-penalized least squares functional. The algorithms can handle a mix of penalized and unpenalized variables. Several instructive examples are given. Also, an implementation that yields an exact output whenever exact data are given is provided.

The Mathematica package is here.

Saturday, December 31, 2011

Thank You and Happy New Year

In particular, let me thank the following people who made these "nuit blanches" in 2011 more entertaining:

Yves Wiaux, Stephen Becker, Jong Chul Ye , Sergey Ten, Sylvain Gigan, Tom Kaye, Art Anderson, Justin Ziniel, Jerome Gilles, Son Hua, Bo Zhang, Mateusz Malinowski, Patrick Gill, Henrik Ohlsson, Jason T. Parker, Volkan Cevher, Philip Schniter, Jason Laska, Mark Davenport, Florent Krzakala, Lenka Zdeborova , Marc Mézard, François Sausset,Yifan Sun , Thong Do, Gael Varoquaux, Matthieu Puigt, Ming Yan, Laurent Duval. Peter Gerstoft, Kiryung Lee, Yoram Bresler, Aswin C. Sankaranarayanan, Daniel Reetz, Dror Baron, Olivier Grisel, Hervé Jégou, Danny Bickson, Joel Tropp, Piotr Indyk, Gongguo Tang, Silvio Ventres, Marco Duarte, Vicente Malave, Zeno Ganter, Tianyi David Zhou, Ulugbeck Kamilov, Mark Tygert, Jared Tanner, Bob Sturm, Henry Pfister, Andreas Tillman, Mike Wakin, Mark Davenport, Genevera Allen, Xiaobo Qu, Jake Hofman, Rebecca Willett, Martin Jaggi, Nematollah K. Batmanghelich, Ori Katz, Zai Yang, Ivan Papusha, Hyrum Anderson, Greg Charvat, David San Segundo, Tibault Reveyrand, Laurent Jacques, Eric Tramel, Daniel Reetz, Alain K., Dick Gordon, Cable Kurwitz, Emily Allstot, Remi Gribonval, Max Little, Angshul Majumdar, Dirk Lorenz, Julien Mairal, Jort Gemmeke, Krzysztof, Ilan, Andrew McGregor, Piotr Indyk, Laurent Daudet, Namrata Vaswani, Jim Fowler, Rishi Gupta, Thomas, Ramesh Raskar, Zhilin Zhang, Petros Boufounos, Thomas Arildsen, R. H. Sri Hari, Ravi Kiran B., Pierre Vandergheynst, Emmanuel Candes, Gabriel Peyre, Gilles Chardon, Sebastien Popoff, Geoffroy Lerosey, Borhan Sannadaji, Steven Vandeput, Maria Jafari, Stefano Marchesini, Alessandro Foi, Kun Qiu, Vladimir Kofman, Ori Shental, Emil Sidky, Varun AV, Tim Lin , Mohammadreza (Reza) Mahmudimanesh and Alejandro Weinstein

Monday, November 15, 2010

CS: Threshold-ISD, Weak Compressed Sensing, Deterministic Matrices, Compressive auto-indexing in femtosecond nanocrystallography, randomized Hadamard transform, Compressive Sensing Microscope and more...

Yilun Wang sent me the following:

Dear Igor,

Wotao and I have developed an algorithm called ``Threshold-ISD'', which was once mentioned in a Nuit Blanche post.

The algorithm was published at SIAM Journal on Imaging Sciences, 2010, and the code was available online at http://www.caam.rice.edu/~optimization/L1/ISD/

Could you please put it on the your page of reconstruction technologies at http://sites.google.com/site/igorcarron2/cs#reconstruction?

We are expecting that more people can be aware of it, test it and give us more feedback in order to further improve it.

Thanks you very much.

Yilun

Thanks Yilun. I have added Threshold-ISD to the reconstruction section of the big picture as I should have done a long time ago. Since the last version was released in June 2010, I hope more people will look at it as it solves the interesting problem of performing the better reconstruction with the measurements you already have.

In a different direction, Do you recall the entry about weak compressive sensing ? Well it looks like I was borrowing the idea from different people to a certain extent. In particular from here: and here:

They both look at [A I] which seem to suggest that they follow the analysis of the Donoho-Tanner phase transition. Now an analysis needs to be performed on how \epsilon changes all that in [\epsilon*A I].

There is a new version of Kronecker Compressive Sensing by Marco Duarte, and Richard Baraniuk.

I also found this new presentation entitled Large-Scale Structured Sparse Learning by Jieping Ye

Compressive auto-indexing in femtosecond nanocrystallography by Filipe R.N.C. Mai, Chao Yang and Stefano Marchesini. The abstract reads:

Ultrafast nanocrystallography has the potential to revolutionize biology by enabling structural elucidation of proteins for which it is possible to grow crystals with 10 or fewer unit cells on the side. The success of nanocrystallography depends on robust orientation-determination procedures that allow us to average diffraction data from multiple nanocrystals to produce a three-dimensional (3D) diffraction data volume with a high signal-to-noise ratio. Such a 3D diffraction volume can then be phased using standard crystallographic techniques. “Indexing” algorithms used in crystallography enable orientation determination of diffraction data from a single crystal when a relatively large number of reflections are recorded. Here we show that it is possible to obtain the exact lattice geometry from a smaller number of measurements than standard approaches using a basis pursuit solver.

Improved analysis of the subsampled randomized Hadamard transform by Joel Tropp. The abstract reads:

This paper presents an improved analysis of a structured dimension-reduction map called the subsampled randomized Hadamard transform. This argument demonstrates that the map preserves the Euclidean geometry of an entire subspace of vectors. The new proof is much simpler than previous approaches, and it offers---for the first time---optimal constants in the estimate on the number of dimensions required for the embedding.

I mentioned that paper before and had some people comment it on the blog while Bob explained the paper a day later, but there is now a new version of it with an added author, here it is again: Compressed Sensing with Coherent and Redundant Dictionaries by Emmanuel Candes, Yonina Eldar, Deanna Needell, and Paige Randall. The abstract reads:

This article presents novel results concerning the recovery of signals from undersampled data in the common situation where such signals are not sparse in an orthonormal basis or incoherent dictionary, but in a truly redundant dictionary. This work thus bridges a gap in the literature and shows not only that compressed sensing is viable in this context, but also that accurate recovery is possible via an `1-analysis optimization problem. We introduce a condition on the measurement/sensing matrix, which is a natural generalization of the now well-known restricted isometry property, and which guarantees accurate recovery of signals that are nearly sparse in (possibly) highly overcomplete and coherent dictionaries. This condition imposes no incoherence restriction on the dictionary and our results may be the rst of this kind. We discuss practical examples and the implications of our results on those applications, and complement our study by demonstrating the potential of `1-analysis for such problems.

Practical Large-Scale Optimization for Max-Norm Regularization by Jason Lee, Benjamin Recht, Ruslan Salakhutdinov, Nathan Srebro, Joel A. Tropp. The abstract reads:

The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.

Low-Rank Matrix recovery Via Iteratively Reweighted Least Square Minimization by Massimo Fornasier, Holger Rauhut and Rachel Ward. The abstract reads:

Abstract. We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal nuclear norm and an approximatively low-rank solution. Under the assumption that the linear measurements ful ll a suitable generalization of the Null Space Property known in the context of compressed sensing, the algorithm is guaranteed to recover iteratively any matrix with an error of the order of the best k-rank approximation. In certain relevant cases, for instance for the matrix completion problem, our version of this algorithm can take advantage of the Woodbury matrix identity, which allows to expedite the solution of the least squares problems required at each iteration. We present numerical experiments which con rm the robustness of the algorithm for the solution of matrix completion problems, and demonstrate its competitiveness with respect to other techniques proposed recently in the literature.

I have put together a list of preprints and papers on deterministic measurement matrices for compressed sensing. It is here in the Deterministic Compressed Sensing page. There is a new contribution in this area: Deterministic Compressed Sensing Matrices from Multiplicative Character Sequences by Nam Yul Yu. The abstract reads:

Compressed sensing is a novel technique where one can recover sparse signals from the undersampled measurements. In this paper, a $K imes N$ measurement matrix for compressed sensing is deterministically constructed via multiplicative character sequences. Precisely, a constant multiple of a cyclic shift of an $M$-ary power residue or Sidelnikov sequence is arranged as a column vector of the matrix, through modulating a primitive $M$-th root of unity. The Weil bound is then used to show that the matrix has asymptotically optimal coherence for large $K$ and $M$, and to present a sufficient condition on the sparsity level for unique sparse solution. Also, the restricted isometry property (RIP) is statistically studied for the deterministic matrix. Numerical results show that the deterministic compressed sensing matrix guarantees reliable matching pursuit recovery performance for both noiseless and noisy measurements.

In the Matlab Central library, here is a new benchmark for MRI :Compressed Sensing Phantom (v1.0) by David Smith:

Description

CSPHANTOM is a test phantom tailored to compressed sensing MRI algorithm development. It is designed to be non-sparse under a gradient transform and to contain features difficult to reproduce with partial Fourier sampling. We hope that this phantom can be used to evaluate the quality and accuracy of compressed sensing MRI reconstruction algorithms in the noise-free domain so that real-world applications of CS MRI may be improved.

Here is another hardware instance that I am going to add to the Compressive Sensing Hardware page: Experimental demonstration of an Optical-Sectioning Compressive Sensing Microscope (CSM) by Yuehao Wu, Peng Ye, Iftekhar O. Mirza, Gonzalo Arce, and Dennis Prathe. The abstract reads:

In this paper we present the design and implementation of a Compressive Sensing Microscopy (CSM) imaging system, which uses the Compressive Sensing (CS) method to realize optical-sectioning imaging. The theoretical aspect of the proposed system is investigated using the mathematical model of the CS method and an experimental prototype is constructed to verify the CSM design. Compared to conventional optical-sectioning microscopes (such as Laser Scanning Confocal Microscopes (LSCMs) or Programmable Array Microscopes (PAMs)), the CSM system realizes optical-sectioning imaging using a single-pixel photo detector and without any mechanical scanning process. The complete information of the imaging scene is reconstructed from the CS measurements numerically.

Compressive sensing principles and iterative sparse recovery for inverse and ill-posed problems by Evelyn Herrholz and Gerd Teschke. The abstract reads:

In this paper, we are concerned with compressive sampling strategies and sparse recovery principles for linear inverse and ill-posed problems. As the main result, we provide compressed measurement models for ill-posed problems and recovery accuracy estimates for sparse approximations of the solution of the underlying inverse problem. The main ingredients are variational formulations that allow the treatment of ill-posed operator equations in the context of compressively sampled data. In particular, we rely on Tikhonov variational and constrained optimization formulations. One essential difference to the classical compressed sensing framework is the incorporation of joint sparsity measures allowing the treatment of infinite-dimensional reconstruction spaces. The theoretical results are furnished with a number of numerical experiments.

I just found the following on an extensive search on arxiv, CS is mentioned: An inverse problem for the wave equation with one measurement and the pseudorandom noise by Tapio Helin, Matti Lassas, Lauri Oksanen. The abstract reads:

We consider the wave equation $(\p_t^2-\Delta_g)u(t,x)=f(t,x)$, in $\R^n$, $u|_{\R_-\times \R^n}=0$, where the metric $g=(g_{jk}(x))_{j,k=1}^n$ is known outside an open and bounded set $M\subset \R^n$ with smooth boundary $\p M$. We define a deterministic source $f(t,x)$ called the pseudorandom noise as a sum of point sources, $f(t,x)=\sum_{j=1}^\infty a_j\delta_{x_j}(x)\delta(t)$, where the points $x_j,\ j\in\Z_+$, form a dense set on $\p M$. We show that when the weights $a_j$ are chosen appropriately, $u|_{\R\times \p M}$ determines the scattering relation on $\p M$, that is, it determines for all geodesics which pass through $M$ the travel times together with the entering and exit points and directions. The wave $u(t,x)$ contains the singularities produced by all point sources, but when $a_j=\lambda^{-\lambda^{j}}$ for some $\lambda>1$, we can trace back the point source that produced a given singularity in the data. This gives us the distance in $(\R^n, g)$ between a source point $x_j$ and an arbitrary point $y \in \p M$. In particular, if $(\bar M,g)$ is a simple Riemannian manifold and $g$ is conformally Euclidian in $\bar M$, these distances are known to determine the metric $g$ in $M$. In the case when $(\bar M,g)$ is non-simple we present a more detailed analysis of the wave fronts yielding the scattering relation on $\p M$.

Monday, February 02, 2009

CS: Twitter, Several news and findings, A Non-Iterative Procedure for Undetermined Systems, Molecular imaging, Super-resolution X-ray

For those of who know what this is, I am on Twitter.

Thomas Blumensath sent me a kind e-mail :

As an avid reader of your blog, I thought I clarify the following points raised in one of your previous entries regarding the OLS algorithm.

Firstly, we did not propose the method in our paper. This method has been around with many names and in many guises. Our paper actually gives a good historical overview (which was its main purpose). A better reference for the OLS algorithm would be:

S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification.,” International Journal of Control, vol. 50, no. 5, pp. 1873–1896, 1989.

Secondly, I would like to point out that ols is also available in my Sparsify toolbox (greed_ols).

Thanks Thomas for the clarification.

Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. I'll add it to the Compressive Sensing Videos page.

Jort Gemmeke let me know that the schedule and list of presentation of the Compressive Sensing Workshop is now available here. Lots of goodies.

Andryian Suksmono has just released a draft e-book on Compressive Sensing. The mild caveat is that it is in Indonesian. No worry, Google Translate now has Indonesian to English translation services.

Felix J. Herrmann, Yogi Erlangga, Tim Lin have released a new version of Compressive simultaneous full-waveform simulation.

A passing thought: when you hear about an imaging system that is diffraction-limited, you are really hearing that the analog way of combining light rays together to form an image has limits. If you have read the previous entry on compressive phase retrieval featuring Ab Initio Compressive Sensing Phase retrieval by Stefano Marchesini and Compressed Sensing Phase Retrieval by Matthew Moravec, Justin Romberg and Richard Baraniuk, you know by now that every time you hear about an indirect measurement system or have the ability to engineer the PSF (Point Spread Function), it is likely you should be able to use the strength of compressive sensing to perform measurements.

Here are three papers that I think are interesting in different respect:

Sparse image reconstruction for molecular imaging by Michael Ting, Raviv Raichand, Alfred O. Hero III. The abstract reads:

The application that motivates this paper is molecular imaging at the atomic level. When discretized at subatomic distances, the volume is inherently sparse. Noiseless measurements from an imaging technology can be modeled by convolution of the image with the system point spread function (psf). Such is the case with magnetic resonance force microscopy (MRFM), an emerging technology where imaging of an individual tobacco mosaic virus was recently demonstrated with nanometer resolution. We also consider additive white Gaussian noise (AWGN) in the measurements. Many prior works of sparse estimators have focused on the case when H has low coherence; however, the system matrix H in our application is the convolution matrix for the system psf. A typical convolution matrix has high coherence. The paper therefore does not assume a low coherence H. A discrete-continuous form of the Laplacian and atom at zero (LAZE) p.d.f. used by Johnstone and Silverman is formulated, and two sparse estimators derived by maximizing the joint p.d.f. of the observation and image conditioned on the hyperparameters. A thresholding rule that generalizes the hard and soft thresholding rule appears in the course of the derivation. This so-called hybrid thresholding rule, when used in the iterative thresholding framework, gives rise to the hybrid estimator, a generalization of the lasso. Unbiased estimates of the hyperparameters for the lasso and hybrid estimator are obtained via Stein’s unbiased risk estimate (SURE). A numerical study with a Gaussian psf and two sparse images shows that the hybrid estimator outperforms the lasso.

a related (older) presentation can be found in A. O. Hero, R. Raich, and M. Ting, Finding dust in space: localizing atoms from noisy projections.

Here is another interesting and somewhat surprising paper: A Non-Iterative Procedure for Computing Sparse and Sparsifiable Solutions to Slightly Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

We consider the problem of reconstructing a sparse image from a few of its 2-D DFT frequency values. A sparse image has pixel values that are mostly zero, with a few non-zero values at unknown locations. The number of known 2-D DFT values must exceed four times the number of non-zero pixel values. We unwrap the 2-D problem to a 1-D problem using the Good-Thomas FFT, and apply Prony's method to compute the non-zero pixel value locations. Thus we reformulate the problem as a dual 2-D harmonic retrieval problem. Our solution has three advantages over direct application of 2-D ESPRIT: (1) Instead of solving a huge generalized eigenvalue problem, we compute the roots on the unit circle of a huge polynomial; (2) the locations of the known 2-D DFT values need not form a centrosymmetric region; and (3) there are no matching issues. Our algorithm is also applicable to 2-D beamforming.

and New Atomicity-Exploiting Algorithms for Super-Resolution X-Ray Crystallography by Andrew Yagle. The abstract reads:

The X-ray crystallography problem is to reconstruct a crystalline structure from the Fourier magnitude of its diffracted scattering data. This has three major difficulties: (1) Only Fourier magnitude (not phase) data are known; (2) There is no support constraint (since the crystal is periodic); and (3) only low-wavenumber scattering data are available. But it also has two major advantages: (1) the crystal is sparse (atomicity) since it consists of isolated atoms; and (2) the crystal structure often has even symmetry. We exploit atomicity to show that the crystal can be reconstructed easily from only low wavenumber Fourier data. We also propose new algorithms for reconstruction of crystals with even or no symmetry from low-wavenumber Fourier magnitude data using two or one isomorphic replacements (4 algorithms). Small numerical examples illustrate the algorithms.

Sparse Imputation for Noise Robust Speech Recognition Using Soft Masks by Jort Gemmeke, Bert Cranen. The abstract reads:

In previous work we introduced a new missing data imputation method for ASR, dubbed sparse imputation. We showed that the method is capable of maintaining good recognition accuracies even at very low SNRs provided the number of mask estimation errors is sufficiently low. Especially at low SNRs, however, mask estimation is difficult and errors are unavoidable. In this paper, we try to reduce the impact of mask estimation errors by making soft decisions, i.e., estimating the probability that a feature is reliable. Using an isolated digit recognition task (using the AURORA-2 database), we demonstrate that using soft masks in our sparse imputation approach yields a substantial increase in recognition accuracy, most notably at low SNRs.

Credit: NASA/JPL/Space Science Institute, Photo of Saturn's rings taken by Cassini the day before yesterday.