Title: L1 minimization without amplitude information
Abstract: In many practical situations, we need to reconstruct sparse signals
from measurements that eliminate amplitude information of the acquired
signal. This talk discusses two specific acquisition scenarios. In the
first scenario the sparse signal is acquired by recording the timing of
its zero crossings. Signal reconstruction from zero crossings is well
know to be unstable. The sparsity prior and L1 regularization
stabilizes the reconstruction and allows us to recover the signal. In
the second scenario we only acquire the signs of linear measurements of
a sparse signal. This introduces significant reconstruction ambiguity
which the sparsity prior allows us to resolve.
In both cases, the measurements eliminate amplitude information on the signal, resulting to a fundamental ambiguity. To resolve this ambiguity we impose the constraint that the signal lies on the unit L2 sphere. This constraint significantly reduces the search space and improves reconstruction results. We demonstrate a variation of the Fixed Point Continuation algorithm that runs on the unit sphere and, despite the nonconvexity of the problems, produces very good results.
Tony Chan
Title: TVL1 models for imaging: global optimization and geometric properties: Part I
Abstract: Rudin, Osher, and Fatemi's total variation based image
denoising model has been very popular. We describe properties of a variant
in which the fidelity term is replaced by the L1 norm. This seemingly modest
modification has important consequences, in terms of contrast invariance,
multiscale image decompositions, and geometric properties of solutions. In
addition, it has connections to convex formulations of certain important
shape optimization problems from computer vision, such as shape denoising
and piecewise constant segmentation. In particular, we show that it leads to
algorithms based on convex optimization techniques that are guaranteed to
find the global minimizer of certain non-convex shape optimization problems.
Ronald DeVore
Title: Decoders for Compressed Sensing
Abstract: In
compressed sensing, we encode a discrete signal $x\in \R^N$ by the
vector $y=\Phi x$ where $\Phi$ is a suitably chosen $n\times N$
matrix with $n<<N$. The vector $x$ is underdetermined by
$y$ and so decoding $y$ is a typical inverse problem. We shall
discuss various ways of decoding $y$ including $\ell_1$ minimization
and greedy algorithms. We shall discuss the
performance of encoder-decoder pairs in terms of accuracy for
a given computational
budget.
Selim Esedoglu
Title: TVL1 models for imaging: global optimization and geometric properties: Part II
Abstract: We first discuss how the convex formulation of two-phase,
piecewise constant image segmentation motivated by the L1 fidelity version
of the ROF model allows adapting the convex duality based optimization
methods developed originally for the standard ROF model to the context of
image segmentation. We also briefly indicate recent work on applying these
ideas to other related shape optimization problems. Then, we shift focus and
discuss the correct way to generalize L1 regularization to the context of
geometry denoising, which is a standard problem (also called surface
fairing) in computer graphics.
Anna Gilbert (joint work with R. Berinde, P. Indyk, H. Karloff, and M. Strauss)
Title: Combining geometry and combinatorics: a unified approach to sparse
Abstract: There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix Phi and then uses linear programming to decode information about x from Phi x. The combinatorial approach constructs Phi and a combinatorial decoding algorithm to match. We present a unified approach to these two classes of sparse signal recovery algorithms. The unifying elements are the adjacency matrices of high-quality unbalanced expanders. We generalize the notion of Restricted Isometry Property (RIP), crucial to compressed sensing results for signal recovery, from the Euclidean norm to the l_p norm for p >= 1, and then show that unbalanced expanders are essentially equivalent to RIP-p matrices. From known deterministic constructions for such matrices, we obtain new deterministic measurement matrix constructions and algorithms for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.
Jean-Luc Guermond/Bojan Popov
Title: Approximating PDEs in L1
Abstract: In this talk we will consider L_1-based minimization methods for three different
problems:
(1) Ill-posed transport equations;
(2) Stationary Hamilton-Jacobi equations;
(3) Digital elevation maps for natural and urban terrain.
We will describe each of the three problems. In the case of stationary
Hamilton-Jacobi equations a convergence theory will be presented. We construct
approximate solutions in all cases using a special type of l1-based
minimization. The main features of our methods are that they are of arbitrary
polynomial order and the numerical solutions are oscillation free even when the
underlying data/solution has singularities.
Title: Numerical Methods for Modern Traffic Flow Models
Abstract: I will describe two different traffic flow models. The first model is a scalar conservation law with Arrhenius look-ahead dynamics. It is a modification of the classical fluid dynamics model by Lighthill and Whitham. The modification is based on an assumption that unlike the fluid particles, drivers can see the traffic dynamics ahead of their cars and adjust the speeds of their cars correspondingly. This factor results in a global dependence of the flux on the solution, which makes it challenging to develop numerical methods for the studied scalar conservation law.
The second
model is a modification of the Aw-Rascle system, designed to describe
the formation and dynamics of traffic jams. The model consists of a
constrained pressureless gas dynamics system, which is extremely
stiff. The stiffness makes it difficult to develop robust and
accurate explicit numerical schemes for this model.
I will present several numerical methods for the
above two models and demonstrate their superb performance on a number
of numerical examples.
Gitta Kutyniok (joint work with David
Donoho, Stanford University)
Title: l1-Minimization and
the Geometric Separation Problem
Abstract: Modern data
are often composed of two (or more) geometrically distinct
constituents -- for instance, pointlike and curvelike structures in
astronomical imaging of galaxies. Although it seems impossible to
extract those components -- as there are two unknowns for every datum
-- suggestive empirical results have already been obtained.
In
this talk we develop a theoretical approach to this Geometric
Separation Problem in which a deliberately overcomplete
representation is chosen made of two frames. One is suited to
pointlike structures (wavelets) and the other suited to curvelike
structures (curvelets or shearlets). The decomposition principle is
to minimize the $\ell_1$ norm of the analysis (rather than
synthesis) frame coefficients. Our theoretical results show that at
all sufficiently fine scales, nearly-perfect separation is indeed
achieved.
Our analysis has three interesting features.
Firstly, we use a viewpoint deriving from microlocal analysis to
understand heuristically why separation might be possible and to
organize a rigorous analysis. Secondly, we introduce some novel
technical tools: cluster coherence, rather than the now-traditional
singleton coherence and $\ell_1$-minimization in frame settings,
including those where singleton coherence within one frame may be
high. Thirdly, our approach to exploiting $\ell_1$ minimization by
using the geometry of the problem as the driving force reaches
conclusions reminiscent of those which have been obtained previously
using randomness of the sparsity pattern to be recovered; however
here, the pattern is not random but highly organized.
Title: Fast Bregman Iteration for Compressive Sensing and Sparse Denoising
Abstract: We propose, analyze and show
results of extremely fast, efficient and simple methods for solving
the convex optimization problem:min_u{|u|
_L1 /Au=f, u in
R^n, A mXn, m<n}. The linearized method was first devised with J.
Darbon, then the realization that it is relevant to this problem was
done in more generality and with theoretical and computational
results with W. Yin, D. Goldfarb and J. Darbon, convergence
results for the linearized method with J. Cai and Z. Shen, and an
improvement with Y. Mao, B.Dong and W. Yin, with sparse denoising
added. Bregman iteration, introduced to image science with M. Burger,
D. Goldfarb, J-J Xu, and W. Yin, is the key idea.
Alexander Petoukhov (joint work with Inna Kozlov)
Title: l^1 greedy algorithm for finding solutions of underdetermined linear systems
Abstract: Finding sparse solutions of undedetermined systems Ax=b is a hot topic of the last years. Many problems of information theory (data compression, error correcting codes, compressed sensing, etc) can be reformulated in terms of this problem.
We are gointg to discuss different apprlications of this problem and to present a new algorithm solving the problem for wider range of the input data. The known algorithms are represent two competing classes: l^1 minimization and orthogonal greedy methods. Our new algorithm, essentially based on reweighted l^1 minimization (by E.Candes, M.Wakin and S.Boyd), may serve as "a peace agreement" between the two competing approaches. The algorithm outperporms the reweighted l^1 optimization by about 10%.
Justin
Romberg
Title: Architectures for Compressive Sampling
Abstract: Several recent results in Compressive Sampling show that a sparse signal (i.e. one which can be compressed in a known orthobasis) can be efficiently acquired by taking linear measurements against random test functions. In practice, however, it is difficult to build sensing devices which take these types of measurements. In this presentation, we will show how to extend some of the results in Compressive Sampling to measurement systems which are more amenable to real-world implementation. We will discuss applications to radar imaging, coherent optical imaging, and next-generation analog-to-digital converters.
Panagiotis Souganidis
Title: Rates of convergence for monotone approximations of viscosity solutions
Abstract: In this talk I will review a general theory yielding the convergence of
monotone approximations to visocisty solutions of first and second order
pde. I will also present new results about error estimates.
Eitan Tadmor
Title: L1 Techniques for Three Problems in Nonlinear PDEs, Signal and Image Processing
Abstract: We address three different questions using L1 techniques.
(i) The vanishing viscosity limit of two-dimensional nonlinear
convection:L1 convergence follows from spectral dynamics (a joint work
with D. Wei).
(ii) Detection of edges in spectral information of
piecewise smooth data (a joint work with S. Engelberg and J. Zou); and
(iii) Recent results on image processing using (BV, L1)
multi-scale hierarchical decompositions (joint work with P. Athavale).
Jared Tanner (joint work with David Donoho, Stanford
University)
Title: The surprising structure of
Gaussian point clouds and its implications for signal
processing
Abstract: We will explore connections
between the structure of high-dimensional convex polytopes and
information acquisition for compressible signals. A classical result
in the field of convex polytopes is that if N points are distributed
Gaussian i.i.d. at random in dimension n<<N, then only order
(log N)^n of the points are vertices of their convex hull.
Recent results show that provided n grows slowly with N, then with
high probability all of the points are vertices of its convex hull.
More surprisingly, a rich "neighborliness" structure
emerges in the faces of the convex hull. One implication of
this phenomenon is that an N-vector with k non-zeros can be recovered
computationally efficiently from only n random projections with n=2e
k log(N/n). Alternatively, the best k-term approximation of a signal
in any basis can be recovered from 2e k log(N/n) non-adaptive
measurements, which is within a log factor of the optimal rate
achievable for adaptive sampling.
Richard Tsai
Title: Exploratory path planning and target detection
Abstract: I
will present a recent work on planning a path through an unknown
environment under various settings. In this talk, a robot is placed in
an unknown environment and is supposed to map out the environment using
what can be seen from its current and previous locations. When an
unknown diffusive source is present, the robot, equipped with the
appropriate sensor, is to move to a location so that the unknown source
can be determined from the collected sensor data, and is under visual
surveillance from the robot.
Title: Enhanced Compressive Sensing and More
Abstract: We consider the equivalence between finding the sparsest vector in a set
and continuous optimization on the same set. This approach enables
remarkably simple proofs to unify and extend some compressive sensing
recoverability and stability results, and reveals potential benefits of
doing enhanced compressive sensing (ECS) where prior information could
allow recovery of much less sparse signals.
We will also introduce some recent algorithmic work done by our CAAM group
at Rice University.