Workshop on
Sparse Tomographic Reconstruction: Theoretical and Numerical Aspects
March 19-20 2015
Abstract:
The goal of this workshop is to present state of the art
results, on both theoretical guarantees and numerical algorithms, for
tomographic reconstruction regularized by co-/sparsity, total variation
etc.
We aim to pinpoint the gap between the practical efficiency of recent
regularization methods, and our mathematical understanding of low complexity models
in tomographic inversion. While many theoretical guarantees rely on
uniform analysis with random measurements, tomographic reconstruction
requires more customized mathematical tools and algorithms to capture
the geometry of signals and images that can be stably recovered. This
includes for instance total variation minimization from tomographic
measurements and the development of novel recovery algorithms that
can cope with huge problem sizes like occuring e.g. in 3D tomography.
The workshop will gather talks by leading experts in the fields of
compressive sensing and large-scale numerical optimization.
Location
Heidelberg Collaboratory for Image Processing (HCI)
University of Heidelberg
Speyerer Strasse 6
69115 Heidelberg (Germany)
Programme
pdf
Confirmed Speakers
-
Joost K. Batenburg, Centrum Wiskunde & Informatica (CWI)
[abstract]
Large-scale Tomographic Reconstruction from Limited Projection Data:
some advances and some great challenges
In recent years, significant advances have been made in the ability to reconstruct
large 3D tomography volumes from highly limited projection data, by exploiting various types of sparsity-related priors. Despite these advances,
the practical use of such reconstruction approaches still remains limited compared to classical methods. In this talk I will discuss the various challenges
that must be overcome to apply various sparsity-based reconstruction methods to large-scale, real-world datasets. I will also present some cases of success,
where new scientific discoveries could actually be made due to substantial improvements in the employed reconstruction algorithm.
-
Yair Censor, University of Haifa
[abstract]
Strict Fejér monotonicity by superiorization of feasibility-seeking projection methods
The superiorization methodology works by taking an iterative algorithm, investigating its perturbation resilience, and then using proactively such perturbations
in order to “force” the perturbed algorithm to do in addition to its original task something useful. The perturbed
algorithm is called the “superiorized version” of the original unperturbed algorithm. If the original algorithm is computationally efficient
and useful in terms of the application at hand, and if the perturbations are
simple and not expensive to calculate, then the advantage of this method is that, for essentially the computational cost of the
original algorithm, we are able to get something more by steering its iterates according to the perturbations.
This is a very general principle, which has been successfully used in some important practical applications such as image reconstruction
from projections, intensity-modulated radiation therapy and nondestructive testing, and awaits to be implemented and tested in additional
fields. An important case is when the original algorithm is a feasibility-seeking algorithm, or one that strives to find constraint-compatible
points for a family of constraints, and the perturbations that are interlaced into the original algorithm aim at reducing (not
necessarily minimizing) a given merit function.
Joint work with Alexander J. Zaslavski
Jürgen Frikel, Helmholtz Zentrum München
[abstract]
Characterization and reduction of artifacts in limited angle x-ray tomography
In this talk we consider the reconstruction problem of limited angle x-ray tomography. Such problems appear naturally in many
applications, such as digital breast tomosynthesis, dental tomography or electron microscopy. Many of these modalities still employ the filtered
backprojection algorithm (FBP) for practical reconstructions. However, since the FBP algorithm implements an inversion formula for the Radon
transform, an essential requirement for its application is the completeness of the tomographic data. Consequently, the application of FBP
is not justified in the case of limited angle tomography. As a result, only specific features of the original object can be reconstructed reliably and
additional artifacts can be created by the FBP algorithm. In this talk, we present a characterization of the FBP reconstructions for a limited angular
range. In particular, we give a characterization of visible singularities (i.e. those features that can be reconstructed reliably) from limited angle data.
The main part of this talk is devoted to the characterization of artifacts that may appear in limited angle reconstructions. Moreover, we derive an
artifact reduction strategy for the filtered backprojection algorithm and illustrate its performance in some numerical experiments.
Jakob S. Jørgensen, DTU
[abstract]
Phase-transition behavior in X-ray CT matches that of Gaussian sensing matrices
Sparsity regularization in X-ray computed tomography (CT) has shown large promise for accurate reconstruction from reduced data.
Compressed sensing (CS) has motivated these developments by offering guarantees of accurate reconstruction of sparse images from reduced
data under suitable assumptions on the sampling matrix. However, existing CS guarantees, e.g., based on the restricted isometry property,
do not apply to structured and sparse sampling matrices in X-ray CT. Using empirical phase diagrams we study image recoverability from
X-ray CT data as function of image sparsity and undersampling level. We consider sparsity in the image and gradient domains and
reconstruction by 1-norm and TV regularization. We demonstrate empirically that X-ray CT exhibits a pronounced relation between image
sparsity and the possible undersampling level as well as sharp phase transitions for certain image classes. We demonstrate that the
observed phase-transition behavior of X-ray CT is comparable with theoretical results for Gaussian sensing matrices. However, we also
highlight an important difference between X-ray CT and Gaussian sensing, namely that structure in nonzero locations and not just sparsity
level affects recoverability in X-ray CT.
Christian Kruschel, University Göttingen
[abstract]
Constructions and Interpretations of Dual Certificates for Unique Solutions in Compressed Sensing
For an real-valued, underdetermined matrix, the existence of an element w such that A^Tw
is a subgradient of the l1-norm at a given vector x^* is crucial for identifying x^* as a
minimizer of Basis Pursuit. Such an element w is called dual certificate. In this talk,
three different geometrical interpretations of dual certificates will be presented. The
focus will be laid on questions concerning which properties must be satisfied by the
considered geometrical objects such that one can guarantee that all k-sparse vectors are
unique minimizers or all minimizer are unique. Further, these interpretations give an
intuitive insight on how to construct or identify unique minimizers with high sparsity.
In the second part of the talk, the construction and identification of unique minimizers
will be generalized to other problems in compressed sensing, i.e. analysis l1
minimization and isotropic total variation.
To that end generalized dual certificates will be identified by optimality conditions
which will be used to state methods for constructing and identifying unique minimizers of
both compressed sensing problems.
Martin Kleinsteuber, TUM
[abstract]
Bimodal Sparse Image Priors
The success of many computer vision tasks lies in the ability to exploit the interdependency between different image modalities. Fusing corresponding information
can be achieved on several levels, and one promising approach is the integration at a low level. Moreover, sparse signal models have successfully been used in many
vision applications and serve amongst others as prior for regularizing inverse problems. Within this area of research, the so called co-sparse analysis model has attracted
considerably less attention than its well-known counterpart, the sparse synthesis model, although it has been proven to be very useful in various image processing applications.
In this talk, I propose a co-sparse analysis model that is able to capture the interdependency of two image modalities. It is based on the assumption that a pair of
analysis operators exists, so that the co-supports of the corresponding bimodal image structures are correlated. I propose an algorithm that is able to learn such a
coupled pair of operators from registered and noise-free training data. Furthermore, it is explained how this model can be applied to solve linear inverse problems in
image processing and how it can be used for image registration tasks.
Deanna Needell, Claremont McKenna College
[abstract]
Recovering Overcomplete Sparse Representations from Structured Sensing
In many signal processing applications, one wishes to acquire images
that are approximately sparse in transform domains such as wavelets
using frequency domain samples. Often the quality of the sparsity
based model significantly improves when one considers redundant
representation systems such as wavelet frames. To date, compressed
sensing with redundant representation systems has, however, only been
studied for measurement systems that have certain concentration
properties, which is not the case for frequency domain samples. In
this talk, we close this gap, providing more general reconstruction
guarantees for signals that are sparse with respect to redundant systems.
Marc Nicodème, University of Bordeaux
[abstract]
Optimal Dual Certificate for Noise Robustness Bounds
In this talk, we deal with optimizing Lipschitz bounds relating locally the reconstruction error to the measurement error in the RIPless compressive sensing
framework. Most recent theoretical papers in the field parametrize such bounds relatively to certain families of vectors called dual certificates, which are fundamental to several reconstruction criteria. We show that such a family of bounds admits a unique minimizer that has a deep geometric meaning and can be explicitly constructed via a convex projection algorithm that we describe. We also give a faster greedy algorithm that provides
approximate solutions.
Constantin Popa, University of Constanta
[abstract]
Strategies for Selecting the Projection Hyperplane in Kaczmarz-Type Algorithms
The Kaczmarz algorithm is a standard row-action method that can be applied to large systems of equations. Two main versions of it have been considered and analysed. One uses in each iteration a complete set of projections onto the hyperplanes associated to the equations of the system (Tanabe, 1971), whereas the other uses only one projection on a hyperplane selected in an appropriate manner (cyclic, almost cyclic, maximal residual, randomly; e.g. Censor & Zenios, 1997). According to the first version Kaczmarz algorithm has been extended for solving inconsistent linear systems in a least squares sense (Kaczmarz Extended (KE); Popa, 1995, 1998). For the second version, KE was adapted and theoretically analysed in the random choice case for the projection hyperplanes (Needell, 2010; Zouzias & Freris, 2013). In this talk we will adapt and theoretically analyse the KE algorithm in the almost cyclic and maximal residual choice cases for the projection hyperplanes.
Ioana Pomparau, University of Constanta
[abstract]
Adaptive Constraining Strategy for Projection-Based Iterations
When solving image reconstruction problems, previous knowledge concerning the original image
may lead to various constraining strategies. Typically, general iterative projection-based methods employ a
single strictly nonexpansive idempotent constraining operator with a closed image. In this talk we consider a
family of such constraining operators in order to use the a priori information adaptively in every calculated
iteration. We design a particular family of box-constraining operators which satisfies our general assumptions
for convergence. This results in an iteration-dependent family of constraining operators, which is used for
reconstructing sparse images as occurring in Tomographic Particle Image Velocimetry.
Paul Swoboda, University of Heidelberg
[abstract]
Convergent Message Passing for Structured Linear Programs
Message passing solvers belong for many applications (e.g. MAP-MRF, linear assignment, b-matching, perfect matching) to the state-of-the-art, due to them being fast, having low memory footprint and being easy to implement. In the field of MAP-MRF variants of message passing (SRMP, MPLP, TRWS) have been developed in recent years, which are monotonically convergent and guaranteedly converge to a fixpoint, which is usually very good in practice. Our message passing algorithm transfers these desirable characteristics to a more general class of structured linear programs. Experiments on graph matching problems confirm the benefits of our approach.
Andreas Weinmann, Helmholtz Zentrum München
[abstract]
Signals with Jump Discontinuities - Partitioning and Reconstruction
In recent years there is increasing interest in nonsmooth and nonconvex methods in various branches of applied mathematics.
In this talk, we primarily consider so-called (nonsmooth and nonconvex) Potts functionals. They were originally considered in statistics
and are, in the meantime, applied in signal and image processing, in sparse approximation/compressed sensing,
as well as in inverse problems. We report on analytic and algorithmic results and show application to real data. In particular, we
consider the inverse problem setup and, especially, the reconstruction of classical Radon and spherical Radon data. As outlook, we briefly
discuss other types of functionals as well as manifold-valued data.
Eric W. Tramel, Ecole Normale Superieure
[abstract]
Belief Propagation and Approximations for Discrete Tomography
Discrete tomography, or the reconstruction of binary images from a set of limited angular
measurements, has applications within many practical and theoretical fields. The binary
limitation on pixel values should allow for exact reconstruction from very few measurements,
however, developing algorithms to deliver on this theoretical promise is challenging. The field
of statistical physics has long been interested in the properties of correlated binary models, e.g. the
well-known Ising model, which can be used to capture the intricacies of local correlations within
an image. Using these well-known models and approaches can deliver accurate and efficient
tomographic reconstruction without yielding to greedy or convex-ified algorithms by instead
operating on a grounded statistical interpretation of the problem via the factorized estimation of the
a posteriori probability of pixel values.
In this talk we will discuss recently published work in applying Belief Propagation (BP) to estimate
this factorization, its exact nature in 1D line reconstruction, its advantages over convex techniques such
as Total Variation (TV), and the challenges in its application to 2D image models. Next,
we will discuss new results which improve on the BP approach both in terms of computational
efficiency and accuracy by moving to a 2D model and applying a mean-field approximation with 2nd order
corrections (à la Thouless-Anderson-Palmer). Finally, we will discuss some future promising work in
the application of these techniques to multi-color discrete tomography problems via the Potts model and
its applications to angle-limited electron tomography.
Andreas Tillmann, TU Darmstadt
[abstract]
Computational Aspects of Sparse Recovery
We discuss a selection of aspects from the sparse recovery context, with a focus on computational matters: Firstly, we investigate heuristic optimality checks for several noise-aware L1-minimization models (synthesis- and analysis-based) and provide preliminary numerical results that demonstrate the potential effectiveness of such schemes for early solver termination. Furthermore, we show that every linear program can be transformed into a (noise-free) basis pursuit problem via a polynomial reduction and sketch possible applications and complexity-theoretical implications. Finally, the fact that verifying whether a relaxation or heuristic such as basis pursuit actually yields the sparsest solution is NP-hard itself gives rise to two questions: On the one hand, can we find other polynomially solvable special cases of sparse recovery besides those identified by the known recovery conditions? On the other hand, it motivates tackling the search for sparse solutions directly, by exact methods from discrete and/or combinatorial optimization. We investigate branch-and-cut methods for binary set-covering integer program reformulations of the sparse recovery task.
Andreas Weinmann, Helmholtz Zentrum München
[abstract]
Signals with Jump Discontinuities - Partitioning and Reconstruction
In recent years there is increasing interest in nonsmooth and nonconvex methods in various branches of applied mathematics.
In this talk, we primarily consider so-called (nonsmooth and nonconvex) Potts functionals. They were originally considered in statistics
and are, in the meantime, applied in signal and image processing, in sparse approximation/compressed sensing,
as well as in inverse problems. We report on analytic and algorithmic results and show application to real data. In particular, we
consider the inverse problem setup and, especially, the reconstruction of classical Radon and spherical Radon data. As outlook, we briefly
discuss other types of functionals as well as manifold-valued data.
Scientific Organization
Registration
... please register yourself here ...
Sponsors
|