Justin Romberg, School of Electrical and Computer Engineering. Georgia Tech.
An Introduction to Compressive Sensing and its Applications

From decades of research in signal processing, we have learned that having a good signal representation is key for tasks including compression, denoising, and restoration. The new theory of Compressed Sensing (CS) shows us how a good representation can fundamentally aid us in the acquisition (or sampling) process as well. In this first talk, we will outline the main theoretical results in CS and discuss how the ideas have started to appear in next-generation imaging and acquisition systems.
[back]

Justin Romberg, School of Electrical and Computer Engineering. Georgia Tech.
The Mathematics of Compressive Sensing

In the second talk, we will delve more deeply into the mathematics of compressive sensing. We will show how random projections can be used to stably embed the set of sparse signals into low dimensional subspaces, and how to "invert" this projection using convex optimization. We will also discuss reconstruction guarantees for systems with structured randomness (e.g. sampling using random convolution or random modulation) and recent progress on sampling ensembles of correlated signals using low-rank recovery algorithms.
[back]

Per Christian Hansen, Technical University of Denmark
Image Deblurring with Krylov Subspace Methods

Image deblurring, i.e., reconstruction of a sharper image from a blurred and noisy one, involves the solution of a large and very ill-conditioned system of linear equations, and regularization is needed in order to compute a stable solution. Krylov subspace methods are often ideally suited for this task: their iterative nature is a natural way to handle such large-scale problems, and the underlying Krylov subspace provides a convenient mechanism to regularized the problem by projecting it onto a low-dimensional "signal subspace" adapted to the particular problem. In this talk we consider the three Krylov subspace methods CGLS, MINRES, and GMRES. We describe their regularizing properties, and we discuss some computational aspects such as preconditioning and stopping criteria. [back]

Per Christian Hansen, Technical University of Denmark
Total Variation and Tomographic Imaging from Projections

Total Variation (TV) regularization is a powerful technique for image reconstruction tasks such as denoising, in-painting, and deblurring, because of its ability to produce sharp edges in the images. In this talk we discuss the use of TV regularization for tomographic imaging, where we compute a 2D or 3D reconstruction from noisy projections. We demonstrate that for a small signal-to-noise ratio, this new approach allows us to compute better (i.e., more reliable) reconstructions than those obtained by classical methods. This is possible due to the use of the TV reconstruction model, which incorporates our prior information about the solution and thus compensates for the loss of accuracy in the data. A consequence is that smaller data acquisition times can be used, thus reducing a patients exposure to X-rays in medical scanning and speeding up non-destructive measurements in materials science. [back]

Irad Yavneh, Technion - Israel Institute of Technology
Coarse to Fine and Back Again

Multi-level techniques of various forms have become more and more prevalent over recent years in the framework of computational image processing. Typically, a hierarchy of representations of the problem under consideration is defined, consisting of the target problem and a collection of less detailed versions of this problem. Usually, the "coarser" versions are employed in order to obtain a good initial approximation of the sought detailed solution, in an effort to reduce computation time and/or to avoid locally optimal solutions that are significantly inferior to the global optimum. Sometimes this works well. And yet, it is often recognized that the coarse versions may be of limited utility, and might even lead us astray, due to the fact that they lack some vital information that is encoded in the fine scales.

To make good use of the coarse versions we must therefore somehow embed in them the influence of the fine-scale information on the coarse scales. This approach has been formalized and brought to efficient use in the framework of multigrid methods for partial differential equations since the 1970's, but it has not been found easy to incorporate in many other settings. The first talk will introduce the fundamental ideas underlying multi-level computational methods, and the second will describe several algorithms that contain such two-way flow of information across scales, and their successful implementation in imaging problems. [back]

Alain Bossavit, Laboratoire de Génie Électrique de Paris, Université Paris Sud
Geometric structures underlying mimetic approaches

Mimetic methods, in Electromagnetics, replace 3D-space by a finite element mesh and classical differential operators such as grad, rot, div, by matrices that describe the topology of the mesh, in a consistent way (mobilizing some notions of cohomology and differential geometry). They neatly separate ``pre-metric" features of the theory from constitutive laws (expressed as Hodge operators, which encapsulate metric properties). The end result of this process is a system of two interlocked networks, one electric, one magnetic, talking to each other, respectively based on the primal mesh and on its dual. [back]

Alain Bossavit, Laboratoire de Génie Électrique de Paris, Université Paris Sud
Consistent extensions of mimetic techniques to coupled problems

Mimetic methods appear as a systematic way to discretize electromagnetic dynamicalsystems, so it's only natural to try and extend such approaches to other compartmentsof physics. My purpose in this second talk is to suggest how similar methods can be developed forcoupled problems in elasto-electro-dynamics, by exploiting formal analogies betweenelectromagnetics and elasticity. This solves in a satisfactory way the old problem of forces in electrodynamic computations. [back]

Pavel Bochev, Sandia National Laboratory ¹ ²
Part 1: Mimetic discretizations and what they can do for you

Recent advances in compatible discretizations have enabled impressive gains in computational science and affirmed the key role of homological principles in numerical PDEs. Thanks to homological ideas and tools, we now have a much better understanding of why some discretization methods work so well and why other methods fail spectacularly. More importantly, homological ideas can be used to develop stable and physically consistent discretizations, such as mimetic methods, which translate PDEs to algebraic equations that inherit their fundamental structural properties.

In Part 1 we provide a common framework for mimetic methods using algebraic topology to guide our analysis. The key concept in our approach is the natural inner product on co-chains. This inner product is sufficient to generate a combinatorial Hodge theory on co-chains but avoids complications attendant in the construction of a robust discrete Hodge-star operators. In particular, using a reduction and a reconstruction maps between differential forms and co-chains we define mutually consistent sets of natural and derived discrete operations that preserve the invariants of the De Rham homology groups and obey a discrete Stokes theorem. By choosing a specific reconstruction operator we obtain well-known mixed FE, mimetic FD and covolume methods and explain when they are equivalent.

To illustrate the potential of compatible discretizations we use the mimetic framework to reformulate the discrete Maxwells equations into a system that is dominated by discrete Hodge-Laplace operators and has much improved scaling for highly heterogeneous conductors - a setting that arises the modeling and simulation of Z-pinch at Sandia. Using properties of mimetic operators we show that the kernel of the mimetic Hodge-Laplace operator has the same dimension as the kernel of the analytic Hodge-Laplacian. Together with the improved scaling, this means that the discrete Laplacian is equivalent to a standard vector Laplace operator. As a result, the reformulated system can be used with standard "black-box" AMG solvers for the Poisson equation.

We will close with a brief summary of the INTREPID project at Sandia. INTREPID is a software package that represents a radical departure from conventional discretization libraries that are designed to support a single discretization paradigm. In contrast, INTREPID provides a flexible software infrastructure that can support a mixture of FE, FV and FD discretizations, defined on different types of cells, including general polyhedral cells. The core toolset of INTREPID represents a software realization of our mimetic framework and offers intuitive API for restriction and reconstruction operators and the natural and derived discrete operations in the framework. INTREPID follows the successful "package" design principle of Trilinos and leverages specialized tools such as STK to provide production level support for mesh management.

¹ Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed-Martin Company, for the United States Department of Energy's National Nuclear Security Administration under contract DEAC- 94AL85000.

² This work was partially funded by the ASCR Program, U.S. Department of Energy, Office of Science

[back]

Pavel Bochev, Sandia National Laboratory ¹ ²
Part 2: Mimetic Discrete Models with Weak Material Laws, or Least Squares Methods Revisited

To a casual observer, compatible (or mimetic) methods and least squares methods for PDEs are polar opposites. Mimetic methods inherit key conservation properties of the PDE, can be related to a naturally occurring optimization problem, and require specially selected, dispersed degrees of freedom. The conventional wisdom about least squares is that they rely on artificial energy principles, are only approximately conservative, but can work with standard C⁰ nodal (or collocated) degrees of freedom. The latter is considered to be among the chief reasons to use least squares methods.
In this talk we demonstrate that exactly the opposite is true about least-squares methods. First, we will argue that nodal elements, while admissible in least squares, do not allow them to realize their full potential, should be avoided and are, perhaps, the least important reason to use least squares! Second, we will show that for an important class of problems least squares and compatible methods are close relatives that share a common ancestor. In fact, we will prove that in some circumstances, least squares and compatible methods compute identical answers. The price paid for gaining favorable conservation properties is that one has to give up what is arguably the least important advantage attributed to least squares methods: one can no longer use C⁰ nodal elements for all variables.
To this end, we will use the mimetic framework from Part 1 to develop a new interpretation of a certain class of compatible least-squares methods, as discrete realizations of a Hodge-star operator, obtained from weakly enforced material laws. We reformulate the governing PDEs into a constrained optimization problem in which material laws are enforced weakly. We then consider three possible mimetic discretizations of the optimization problem. Two of them give familiar Galerkin and/or mixed type methods. The third one reduces the optimization problem to a mimetic least squares principle whose minimizers are, under certain conditions, identical with the solutions of the other two mimetic discretizations. We conclude by a series of numerical examples that confirm our findings

¹ Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed-Martin Company, for the United States Department of Energy's National Nuclear Security Administration under contract DEAC- 94AL85000.

² This work was partially funded by the ASCR Program, U.S. Department of Energy, Office of Science

[back]

Blair Perot, University of Massachusetts Amherst
Discrete Calculus Methods and Their Application in Fluid Dynamics

The mathematical concepts of: order of accuracy, stability, and consistency/convergence are core pillars in the design of numerical methods for the solution of partial differential equations (PDEs). It turns out that these criteria are necessary to capture the mathematical essence of PDEs but not sufficient to ensure the proper representation of the important physics that most PDEs are intended to represent. Recently, there has been a significant effort to formulate additional criteria that allow numerical methods to capture physics well. Discretization approaches that result in algebraic systems which mimic the physics of the continuous PDE, are often referred to as mimetic numerical methods. The Discrete Calculus methodology is one possible approach to formulating mimetic numerical methods for PDEs.

There are two core ideas behind the Discrete Calculus approach to producing mimetic methods. The first idea is that PDEs need to be split into their fundamental parts, in order to isolate physical and mathematical identities from material constitutive equations. The other important concept is that discretization (defined as the transformation from a continuous PDE problem to a discrete algebraic system) needs to be performed exactly. While conceding that exact discretization is a counter-intuitive idea to many current practitioners, it will be shown to actually be very straightforward. The attractive part of the formalism is that exact discretization always results in a 'discrete calculus' that has no option but to be mimetic. It will then be shown that solution (rather than discretization) of the algebraic system requires some sort of approximation/interpolation, and that this approximation is best placed in the problem's material constitutive equations, rather than within the exact discrete calculus.

The Discrete Calculus approach to generating mimetic numerical methods is potentially attractive because it uses terminology and mathematical concepts familiar to every engineer and scientist. The basic ideas are illustrated in this talk on the simple problem of unsteady diffusion. But the discrete calculus approach can be applied very generally. To show the versatility of the method, results are also presented for mimetic calculations of the unsteady incompressible Navier-Stokes equations on moving and adaptive unstructured meshes in three-dimensions. [back]

Blair Perot, University of Massachusetts Amherst
The Relationship between Discrete Calculus Methods and other Numerical Methods that Capture Physics Well

An interesting aspect of the Discrete Calculus approach to generating mimetic numerical methods is that it can be used to generate different kinds of numerical methods. Subsets of finite volume, staggered mesh, finite element, discontinuous Galerkin, and finite difference methods, can all be generated via the Discrete Calculus approach. This allows the methods and various analysis tools developed for mimetic approaches to be related to each other.
It will be briefly described how the Discrete Calculus approach can be used to derive existing mimetic numerical methods. In particular, the relationship to mimetic finite element methods (such as Nedeléc elements or Raviart-Thomas elements) will be considered. These types of FE methods have analysis techniques rooted in algebraic topology and a discrete de Rham complex. We will also consider the relationship with Support Operator Methods which originally coined the term 'mimetic'. Finally, staggered mesh methods are perhaps the oldest mimetic methods, and were the progenitor of the Discrete Calculus approach. It will be demonstrated that the Discrete Calculus approach allows one to relate all these superficially very different methods (and some others) to each other. Ultimately, this may allow a crossover of analysis tools. The hope is to provide an analysis framework where any existing mimetic method can collectively analyzed and from which new mimetic methods can be easily generated. [back]