Thursday, December 22, 2011

Everyone knows this is impossible: Is Ankylography an instance of Compressive Sensing ?

It's a tale we have heard before, reviewers tell us in their infinite wisdom that "everyone knows this is impossible". You can always doubt some paper, but in this particular case, the authors gave access to their codes. If it is impossible, it really means then maybe you're lazy. The ever outstanding ArXiv blog points us to the particular story of Ankylography In short, the authors propose an algorithm that can perform a 3D reconstruction of an object based on the diffraction pattern observed on a spherical shell. Examples and the attendant code are available here..I learned very quickly about the intricacies of the system by reading this well done REU report, where we get to see that the algorithm fills a 3D volume based on data gathered from a CCD or a CMOS from which some linear curve interpolation has been performed.. At some point, somebody is going to make the connection with sparsity and low rank systems I am sure, wink wink...

The algorithm

All the images I have seen from these papers could be construed as sparse or low rank. What would be interesting is provide this group with some sense at to how the phase transition like that of Donoho-Tanner will make their solvers unable to perform the reconstruction. 

The newest paper is:  Potential and Challenge of Ankylography by Jianwei Miao, Chien-Chun Chen, Yu Mao, Leigh S. Martin, Henry C. Kapteyn. The abstract is here:
The concept of ankylography, which under certain circumstances enables 3D structure determination from a single view[1], had ignited a lively debate even before its publication[2,3]. Since then, a number of readers requested the ankylographic reconstruction codes from us. To facilitate a better understanding of ankylography, we posted the source codes of the ankylographic reconstruction on a public website and encouraged interested readers to download the codes and test the method[4]. Those who have tested our codes confirm that the principle of ankylography works. Furthermore, our mathematical analysis and numerical simulations suggest that, for a continuous object with array size of 14x14x14 voxels, its 3D structure can usually be reconstructed from the diffraction intensities sampled on a spherical shell of 1 voxel thick[4]. In some cases where the object does not have very dense structure, ankylography can be applied to reconstruct its 3D image with array size of 25x25x25 voxels[4]. What remains to be elucidated is how to extend ankylography to the reconstruction of larger objects, and what further theoretical, experimental and algorithm developments will be necessary to make ankylography a practical and useful imaging tool. Here we present our up-to-date understanding of the potential and challenge of ankylography. Further, we clarify some misconceptions on ankylography, and respond to technical comments raised by Wei[5] and Wang et al.[6] Finally, it is worthwhile to point out that the potential for recovering 3D information from the Fourier coefficients within a spherical shell may also find application in other fields.
The original paper is: Three-dimensional structure determination from a single view by Kevin S. Raines, Sara Salha, Richard L. Sandberg, Huaidong Jiang, Jose A. Rodriguez, Benjamin P. Fahimian, Henry C. Kapteyn, Jincheng Du, Jianwei Miao. The abstract reads:
The ability to determine the structure of matter in three dimensions has profoundly advanced our understanding of nature. Traditionally, the most widely used schemes for 3D structure determination of an object are implemented by acquiring multiple measurements over various sample orientations, as in the case of crystallography and tomography (1,2), or by scanning a series of thin sections through the sample, as in confocal microscopy (3). Here we present a 3D imaging modality, termed ankylography (derived from the Greek words ankylos meaning 'curved' and graphein meaning 'writing'), which enables complete 3D structure determination from a single exposure using a monochromatic incident beam. We demonstrate that when the diffraction pattern of a finite object is sampled at a sufficiently fine scale on the Ewald sphere, the 3D structure of the object is determined by the 2D spherical pattern. We confirm the theoretical analysis by performing 3D numerical reconstructions of a sodium silicate glass structure at 2 Angstrom resolution and a single poliovirus at 2 - 3 nm resolution from 2D spherical diffraction patterns alone. Using diffraction data from a soft X-ray laser, we demonstrate that ankylography is experimentally feasible by obtaining a 3D image of a test object from a single 2D diffraction pattern. This approach of obtaining complete 3D structure information from a single view is anticipated to find broad applications in the physical and life sciences. As X-ray free electron lasers (X-FEL) and other coherent X-ray sources are under rapid development worldwide, ankylography potentially opens a door to determining the 3D structure of a biological specimen in a single pulse and allowing for time-resolved 3D structure determination of disordered materials.
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.


Anonymous said...

see also:

and comments below

Anonymous said...

Am I the only one to suspect that an inverse crime has been committed in their numerical simulations?

Igor said...

Maybe there is something else at play:

Igor said...

Either way, whether it is an "inverse crime" or some sparsity based inpainting, it is easily checkable.

Anonymous said...

To rule out an inverse crime one would need the source of the program which produced the .mat files.