CS: Random Projections and a talk.

Laurent Jacques pointed out that I messed up in the previous entry. I have changed that and now want to mention two papers/preprints focused on random projections.

Graph Laplacian Tomography from Unknown Random Projections by Ronald Coifman,Yoel Shkolnisky, Fred Sigworth and Amit Singer.

The abstract reads:

We introduce a graph Laplacian-based algorithm for the tomographic reconstruction of a planar object from its projections taken at random unknown directions. A Laplace type operator is constructed on the data set of projections, and the eigenvectors of this operator reveal the projection orientations. The algorithm is shown to successfully reconstruct the Shepp-Logan phantom from its noisy projections. Such a reconstruction algorithm is desirable for the structuring of certain biological proteins using cryo-electron microscopy.

and a follow-up of that paper.

Cryo-EM Structure Determination through Eigenvectors of Sparse Matrices by Ronald Coifman,Yoel Shkolnisky, Fred Sigworth and Amit Singer. The abstract reads:

Recovering the three-dimensional structure of proteins is important for understanding their functionality. We describe a spectral graph algorithm for reconstructing the three-dimensional structure of molecules from their cryo-electron microscopy images taken at random unknown orientations. The key idea of the algorithm is designing a sparse operator defined on the projection images, whose eigenvectors reveal their orientations. The special geometry of the problem rendered by the Fourier projection-slice theorem is incorporated into the construction of a weighted graph whose vertices are the radial Fourier lines and whose edges are linked with the common line property. The radial lines are associated with points on the sphere and are networked through spider like connections. The graph organizes the radial lines on the sphere in a global manner that reveals the projection directions. This organization is derived from a global computation of a few eigenvectors of the graph’s adjacency matrix. Once the directions are obtained, the molecule can be reconstructed using classical tomography methods. The presented algorithm is direct (as opposed to iterative refinement schemes), does not require any prior model for the reconstructed object, and shown to have favorable computational and numerical properties. Moreover, the algorithm does not impose any assumption on the distribution of the projection orientations. Physically, this means that the algorithm successfully reconstructs molecules that have unknown spatial preference. We also introduce extensions of the algorithm, based on the spectral properties of the operator, which significantly improve its applicability to realistic data sets. These extensions include: particle selection, to filter corrupted projections; center determination to estimate the relative shift of each projection; and, a method to resolve the heterogeneity problem, in cases where a mix of different molecules is being imaged concurrently.

Petar Maynoukov has a summary on a presentation by one of the authors.
Unrelated, Dror Baron will give a talk tomorrow at the Technion CS department at the Pixel Club Seminar. The title is Compressed Sensing Meets Information Theory,

Date: Thursday, 18.9.2008, 11:30, Place:Room 337-8 Taub Bld.

Abstract of the talk:

Sensors, signal processing hardware, and algorithms are under increasing pressure to accommodate ever larger data sets; ever faster sampling and processing rates; ever lower power consumption; and radically new sensing modalities. Fortunately, there have been enormous increases in computational power. This progress has motivated Compressed Sensing (CS), an emerging field based on the revelation that a sparse signal can be reconstructed from a small number of linear measurements. The implications of CS are promising, and enable the design of new kinds of cameras and analog-to-digital converters. Information theory has numerous insights to offer CS; I will describe several investigations along these lines. First, unavoidable analog measurement noise dictates the minimum number of measurements required to reconstruct the signal. Second, we leverage the remarkable success of LDPC channel codes to design low-complexity CS reconstruction algorithms. Third, distributed compressed sensing (DCS) provides new distributed signal acquisition algorithms that exploit both intra- and inter-signal correlation structures in multi-signal ensembles. DCS is immediately applicable in sensor networks.

Linear measurements play a crucial role not only in compressed sensing but in disciplines such as finance, where numerous noisy measurements are needed to estimate various statistical characteristics. Indeed, many areas of science and engineering seek to extract information from linearly derived measurements in a computationally feasible manner. Advances toward a unified theory of linear measurement systems will enable us to effectively process the vast amounts of data being generated in our dynamic world.

Credit Photo: Pool Photo AP, also one can check the slide show from ABC on the devastation of Hurricane Ike.