Imaging and Computing Seminar — Spring 2012
-
Aria Abubakar, Schlumberger-Doll Research, Cambridge, MA
Compression approaches for nonlinear inversions
Abstract: The rigorous interpretation of geophysical seismic and electromagnetic data requires the use of full nonlinear inversion methods. This is an ill-posed problem. Furthermore, it is also a large-scale computational problem because we have to deal with a large number of data points as well as unknown model parameters. We attempt to cope with the ill-posedness by using regularization approaches and constraints. In this talk we focus on the use of compression approaches for reducing the computational time and memory requirement of nonlinear inversion algorithms. To deal with a large number of sources and receivers, we employ the so-called source-receiver compression scheme. By detecting and quantifying the extent of redundancy in the data, we assemble a reduced set of simultaneous sources and receivers that are weighted sums of the physical sources and receivers used in the survey. Because the number of these simultaneous sources and receivers can be significantly less than those of the physical sources and receivers, the computational time and memory usage of any gradient-type inversion method such as Gauss-Newton, nonlinear conjugate gradient, or contrast source inversion methods can be tremendously reduced. The scheme is based on decomposing the data into their principal components using a singular value decomposition approach and the data compression is done through the elimination of the small eigenvalues. One of bottlenecks of the Gauss-Newton method is the Jacobian matrix storage and the computational cost of calculating the Gauss-Newton step (the inner-loop calculation). We reduce the memory usage by calculating the Jacobian matrix on the fly in each inner-loop iteration. By doing so the computational cost of calculating the Gauss-Newton step increases; however, this overhead is mitigated by compressing the field matrices (which contain redundancy) using the Adaptive Cross Approximation scheme. For some cases, this compressed implicit Jacobian scheme may even speed-up the Gauss-Newton step calculation and further regularizes the Gauss-Newton method. As for the large-number of unknown model parameters (such as P-wave velocity, S-wave velocity, mass-density, or resistivity), we employ the so-called model compression scheme. In this scheme the unknown model parameters are represented in terms of a basis such as Fourier, cosine, or wavelet. By applying a proper truncation criterion, the model may then be approximated by a reduced number of basis functions, which is usually much less than the number of the model parameters. Furthermore, for applications such as the controlled-source electromagnetic measurements, which have low-resolution, we will show that for inversion it is sufficient to only keep the low-spatial frequency part of the image. This model compression scheme accelerates the computational time as well as reduces the memory usage of the Gauss-Newton method. As demonstrations of these approaches, we show various inversion results of well-known benchmark seismic models such as Marmousi, BP/EAGE Salt, and 3D SEG/EAGE Salt models as well as controlled-source electromagnetic synthetic and field data.
-
David Nicholls , Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago
A Boundary Perturbation Method for Interface Reconstruction via Constrained Quadratic Optimization
Abstract: Grating scattering is a fundamental model in acoustics, electromagnetics, nanoscience, and the geosciences. In this talk we examine the problem of detecting the geometric properties of gratings in a two-dimensional acoustic medium where the fields are governed by the Helmholtz equation. Building upon the success of our previous Boundary Perturbation approach (implemented with the Operator Expansions formalism) we derive a new approach which augments this with a new "smoothing" mechanism. With numerous numerical experiments we demonstrate the enhanced stability and accuracy of our new approach which further suggests not only a rigorous proof of convergence, but also a path to generalizing the algorithm to multiple layers, three dimensions, and the full equations of linear elasticity and Maxwell's equations.
-
Felix Krahmer , Institute for Numerical and Applied Mathematics, Georg-August-Universität Göttingen, Germany
Compressed sensing bounds via improved estimates for Rademacher chaos
Abstract: The theory of compressed sensing considers the following problem: Let A be a m x n matrix and let x be a vector of length n that is s-sparse, i.e., all but s of its entries vanish. One seeks to recover x uniquely and efficiently from linear measurements y = Ax, although m is much smaller than n. A sufficient condition to ensure that this is possible is the Restricted Isometry Property (RIP). A is said to have the RIP, if its restriction to any small subset of the columns acts almost like an isometry. In this talk, we study two classes of matrices with respect to the RIP: First, we consider matrices A which represent the convolution with a random vector followed by a restriction to an arbitrary fixed set of entries. For the random vector, we focus on Rademacher vectors, i.e., vectors whose entries are independent random signs. Second, we study Gabor synthesis matrices, that is, matrices consisting of time-frequency shifts of a Rademacher vector. In both cases, this question can be reduced to estimating random variables of the form D_B:=sup_(A\in B) | || A \epsilon\|^2 - \E ||A \epsilon||^2| where the supremum is taken over an arbitrary set of matrices. Random variables of this type are closely related to suprema of chaos processes. Using generic chaining techniques, we derive a bound for the expectation of such variables in terms of the Talagrand γ2-functional. As a consequence, we obtain that matrices from both classes under consideration have the RIP with high probability if the embedding dimension satisfies m > Cs log(n)4 . This bound exhibits optimal dependence on s, while previous works had only obtained a suboptimal scaling of s^3/2 . This is joint work with Shahar Mendelson and Holger Rauhut.
-
Ramesh Raskar, Media Lab, MIT
Looking around Corners with Trillion Frames Per Second Imaging
Abstract: The talk will describe a range of new and challenging inverse problems in ultra-fast imaging.
Can we look around corners beyond the line of sight? Our goal is to exploit the finite speed of light to improve image capture and scene understanding. New theoretical analysis coupled with emerging ultra-high-speed imaging techniques can lead to a new source of computational visual perception. We are developing the theoretical foundation for sensing and reasoning using Femto-photography and transient light transport, and experimenting with scenarios in which transient reasoning exposes scene properties that are beyond the reach of traditional computational imaging.
The key idea is to time-resolve the multiple diffuse bounces of light. In addition to the ability to image hidden objects, the analysis also allows us to recover reflectance properties and sub-surface scattering. Visualization of the propagation of light provides a fascinating intuitive insight into the complex light transport.
We are making the existing datasets from our unique ultra-fast device available and invite researchers to send proposals for new capture configurations or applications. (Joint work with a large team, please see http://raskar.info/femto and http://raskar.info/trillionfps)
Bio
Ramesh Raskar is an Associate Professor at MIT Media Lab and heads the Lab's Camera Culture research group. He joined MIT from Mitsubishi Electric Research Laboratories (MERL) in 2008.
His research interests span the fields of computational light transport, computational photography, inverse problems in imaging and human-computer interaction. Recent projects and inventions include transient imaging to look around a corner, a next generation CAT-Scan machine, imperceptible markers for motion capture (Prakash), long distance barcodes (Bokode), touch+hover 3D interaction displays (BiDi screen), low-cost eye care devices (Netra,Catra), new theoretical models to augment light fields (ALF) to represent wave phenomena and algebraic rank constraints for 3D displays(HR3D).
He is a recipient of TR100 award from Technology Review, 2004, Global Indus Technovator Award, top 20 Indian technology innovators worldwide, 2003, Alfred P. Sloan Research Fellowship award, 2009 and Darpa Young Faculty award, 2010. Other awards include Marr Prize honorable mention 2009, LAUNCH Health Innovation Award, presented by NASA, USAID, US State Dept and NIKE, 2010, Vodafone Wireless Innovation Award (first place), 2011. He holds over 40 US patents and has received four Mitsubishi Electric Invention Awards. He is currently co-authoring a book on Computational Photography. [Personal webpage http://raskar.info]