Main navigation | Main content
HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program
Joint IDR-IMA Workshop
Akram Aldroubi (Department of Mathematics, Vanderbilt University) http://atlas.math.vanderbilt.edu/~aldroubi aldroubi@math.Vanderbilt.Edu
Non-Uniform Sampling and Reconstruction in Shift-Invariant and Wavelet Spaces
We will discuss modern techniques for non-uniform sampling and reconstruction of functions in shift-invariant spaces, and we will present a unified framework for uniform and non-uniform sampling and reconstruction in shift-invariant spaces. This is accomplished by bringing together wavelet theory, frame theory, reproducing kernel Hilbert spaces, approximation theory, amalgam spaces, and sampling. This combination simplifies some parts of the literature on sampling, and we hope will provide the ground for more interactions between mathematicians and other researchers interested in sampling, reconstruction and related areas of research and applications.The theory will be motivated by applications from communication, astronomy and medicine, and the following aspects will be emphesized: (a) The sampling problem is well-defined within the setting of shift-invariant spaces; (b) The general theory works in arbitrary dimension and for a broad class of generators; (c) The reconstruction of a function from any sufficiently dense non-uniform sampling set is obtained by efficient iterative algorithms. These algorithms converge geometrically and are robust in the presence of noise; (d) To model the natural decay conditions of real signals and images, the sampling theory is developedin weighted Lp-spaces.
Richard G. Baraniuk (Department of Electrical and Computer
Engineering, Rice University) richb@ece.rice.edu
Besov, Bayes, and Plato in Multiscale Image Modeling
There currently exist two distinct paradigms for modeling
images. In the first, images are regarded as functions from
a deterministic function space, such as a Besov smoothness class.
In the second, images are treated statistically as realizations
of a random process. This talk with review and indicate the
links between the leading deterministic and statistical image
models, with an emphasis on multiresolution techniques and wavelets.
To overcome the major shortcomings of the Besov smoothness characterization,
we will develop new statistical models based on mixtures on
graphs. To illustrate, we will discuss applications in image
estimation and segmentation.
Ronald DeVore
(Director of Industrial Mathematical Institute, University of
South Carolina-Columbia), devore@math.sc.edu
Harmonic Analysis of BV
The space BV of functions of bounded variation occurs naturally
in PDEs, image processing, and differential geometry. Its structure
is complicated in part by the fact that it does not admit an
unconditional basis. In this joint work with Albert Cohen, Ingrid
Daubechies, and Wolfgang Dahmen, we shall show that BV is almost
characterized by wavelet decompositions. We prove various properties
of the wavelet coefficients of BV functions and use these to
prove theorems on denoising and PDE embeddings such as the Poincare
and Gagliardo-Nirenberg inequalities.
Konstantinos Drakakis (Princeton University)
drakakis@Princeton.EDU
A Scale-Oriented Study of the Internet Traffic
There is a lot of effort nowadays put into trying to understand
and analyze the Internet traffic. In this work, evidence will
be provided towards the fact that traffic seems to behave differently
in different time scales, and that this scaling property along
with non-negligible autocorrelation and certain protocol characteristics
suffice to give a good initial understanding of the traffic
as a stochastic process. The scaling of traffic allows for wavelets
to be used in some of our analysis tools.
Nira
Dyn (School of Mathematical Sciences, Tel Aviv University)
niradyn@post.tau.ac.il
Poly-Scale
Refinability and Subdivision
A subdivision scheme is a two-scale process, which repeatedly
computes discrete values at the next refinement level from the
discrete values at the current refinement level, using a single
given mask. If this process defines in the limit a continous
function, for all initial data, the subdivision scheme is termed
convergent. With each convergent subdivision scheme there is
associated a unique continuous function which is two-scale refinable.
This framework is generalized here to the poly-scale setting.
On the one hand properties of solutions of poly-scale refinement
equations are discussed. On the other hand poly-scale subdivision
schemes are introduced. Such schemes compute the next refinement
level from several coarser levels, using several masks. A relation
between poly-scale refinable functions and convergent poly-scale
subdivision schemes, similar to the one in the two-scale case,
is presented. Also, some aspects of the theory of subdivision
schemes are reviewd together with their generalizations to the
poly-scale case. This discussion includes issues of convergence
of schemes and of the smoothness properties of functions generated
by subdivision schemes. The relation of poly-scale subdivision
schemes to matrix subdivision schemes is mentioned, and several
examples of interesting poly-scale refinable functions and poly-scale
subdivision schemes are presented.
This is a joint work with S. Dekel from Tel-Aviv University.
Jeff Geronimo
(Georgia Tech) geronimo@math.gatech.edu
On Causal solutions to Certain 2D Autoregressive Models
Autoregressive Models play an important role in one dimensional
filtering and prediction theory. In two dimensions such models
have been used in texture analysis and synthesis. We will present
results that indicate when such a model will have a causal solution.
The results presented will also give a solution to a weak form
of the two variable Riesz-Fejer factorization lemma.
Anna Gilbert (AT&T Labs - Research) agilbert@research.att.com http://www.research.att.com/~agilbert
Summary Statistics for Database Range Queries
Joint work with Yannis Kotidis, S.
Muthukrishnan, and Martin J. Strauss, all of AT&T Labs.
Given an input signal of length N, we wish to construct a
concise representation to answer queries of the form: sum signal
values from a to b. These are range queries. We present two
sets of results for range queries, which are amongst the most
common queries. Our results give summary representations that
provide the optimal approximate answers to range queries. Approximate
range queries are useful not only directly but also for query
optimization in database systems.
First, we focus on a histogram as summary statistics. A histogram
includes bucket boundaries and bucket averages. We present an
algorithm to compute the optimal histogram that takes time polynomial
in the L^1 norm of the signal. Ideally, we would like an algorithm
that is polynomial in the number of signal points. We give polynomial
time algorithms for finding the best bucket boundaries and bucket
summary statistics for a representation that generalizes the
histogram representation.
Second, we focus on wavelet(packet)-based representations.
We present a fast algorithm that finds the optimal wavelet(packet)
representation for range queries. We ostensibly code the 1D
signal into a 2D square of range queries but our algorithm takes
time O(N polynomial(log(N))).
Christopher Heil
heil@math.gatech.edu and Radu
Balan
Excesses
of Frames
An overcomplete frame has the property that at least one element
can be removed yet leave a complete set, and in fact the remaining
set must itself be a frame. The excess of a frame is the greatest
number of elements that can be removed yet leave a complete
set. This provides a crude measure of the redundancy of a frame.
A frame with finite excess is a Riesz basis with finitely many
extra elements. We present several related results on frames
with infinite excess, including an explicit characterization
of those frames for which infinitely many elements can be deleted
yet leave a frame, and we apply these results to the case of
Gabor and wavelet multiframes (multiple generators). For these
systems, the case of irrationally related parameters requires
special care and leaves some open questions.
Palle
Jorgensen http://www.math.uiowa,edu/~jorgen/
pjorgen@blue.weeg.uiowa.edu
Connected
components of the Variety of Wavelet Filters, and Chaos Features
of the Corresponding Wavelets
We identify a variety of wavelet filters corresponding to compactly
supported L2(R) wavelets. Much of the theory will
also apply to the L(Rd) situation. The variety is
defined by inequalities, and the orthogonal wavelets correspond
to the "boundary" in the sense that the inequalities will be
identities. The case of the biorthogonal wavelets, or equivalently,
the dual wavelet bases, then is the full variety. The full variety
may be realized as matrix functions defined on a torus and taking
values in the invertible N by N matrices where N is the scaling
of the wavelet at hand. In this representation, the orthogonal
wavelets correspond to the matrix functions taking values in
U(N,C). We give factorizations of the U(N,C) matrix functions
which produce q-bit algorithms, with the factors of the U(N,C)
functions corresponding to the spin-vectors of the quantum algorithm.
Varying the spin vectors we are then able to trace the corresponding
wavelets and study their L2(R) properties. It is
this dependence of the L2(R) theory on the spin vectors
which exhibits chaos features, in the sense that a small variation
of the spin vector configurations will produce "large swings"
in the wavelet generators. We will apply a statistical approach
in trying to take an average of the unpredictable chaos in the
cascades of wavelets.
David
R. Larson (Department of Mathematics, Texas A&M
University) David.Larson@math.tamu.edu
Wavelets,
Frames and Operator Theory
Orthonormal wavelets can be regarded as complete wandering vectors
for a system of bilateral shifts acting on a separable infinite
dimensional Hilbert space. We describe in detail a method of
constructing new wavelets by interpolating between known pairs
of wavelets, and more generally interpolating over finite families
of wavelets, using Hilbert space operator techniques. These
considerations lead naturally to some basic global results for
orthonormal wavelets, Riesz wavelets and frame wavelets, that
can tend to be surprising from a purely function-theoretic point
of view. Included is the concept of a super wavelet (a wavelet
for a super-space), which has potential applications to multiplexing
problems, and we give some new examples of superwavelets. These
considerations also yield alternate derivations of some well-known
function-theoretic results. Similar techniques can be applied
to the windowed Fourier transforms found in Gabor Theory, or
Weyl-Heisenberg Frame Theory, and we obtain some global density
and connectivity results for these classes.
Bradley
J. Lucier (Department of Mathematics, Purdue University)
lucier@math.purdue.edu
Smoothing
Functional Magnetic Resonance Images: A Little Bit of Theory
and a Lot of Practice
Functional (time-dependent) Magnetic Resonance Imaging is an
important way of measuring certain types of brain function.
We believe that anisotropic wavelet decompositions, as introduced
by Christopher Leisner in his thesis, can help to model more
precisely fMRI data. We give a brief summary of Leisner's technique,
and then review a number of practical questions: What is the
relative smoothness in time and space of these images? Is it
better to model in the Fourier domain or the image domain? What
techniques should one use to perform the wavelet shrinkage?
Olof C. Runborg (Princeton University) orunborg@math.princeton.edu
Multiresolution Approximation of Curves with Normal Polylines
Normal meshes is a type of multiresolution meshes recently
proposed for the efficient description of curves and surfaces
in e.g. computer graphics applications. We analyse some of their
mathematical properties (e.g. regularity) in the one-dimensional
Martin J. Strauss (AT&T Labs-Research) mstrauss@research.att.com
Efficient Stream Computation of Approximate Wavelet Representations
Joint work with Anna Gilbert, Yannis
Kotidis, S. Muthukrishnan,
all of AT&T Labs.
We consider the algorithmic problem of finding a good and
short wavelet representation of a signal of N sample points,
presented in a stream. We allow the sample points to arrive
in any order; furthermore, we allow arbitrary updates to the
signal values of the form "add 5 to the current value of sample
number 3." Our main result is that, if there exists a few-term
representation with small L2 error, we can efficiently find
one that is almost as good; otherwise, we can efficiently detect
this fact. Here "efficiently" means using total space and per-item
time at most polylogarithmic in N. Our randomized algorithm
succeeds with high probability over its random choices, but
it works on any signal with a good representation--we make no
probabilistic assumption about the small coefficients. On the
other hand, we show that finding even an approximation to the
single largest wavelet coefficient requires space almost sufficient
to store the whole signal, in general (i.e., in case the signal
does not have a good few-term representation).
We discuss future directions and open problems, including
implications for redundant dictionaries.
Vladimir
N. Temlyakov (Department of Mathematics, University
of South Carolina) temlyak@math.sc.edu
Greedy Algorithms in Nonlinear Approximation
Our main interest in this talk is nonlinear approximation. The
basic idea behind nonlinear approximation is that the elements
used in the approximation do not come from a fixed linear space
but are allowed to depend on the function being approximated.
We note that this form of approximation appears in many numerical
applications such as adaptive PDE solvers, compression of images
and signals, statistical classification, and so on. The standard
problem in this regard is the problem of m-term approximation
where one fixes a basis and looks to approximate a target function
by a linear combination of $m$ terms of the basis. When the
basis is a wavelet basis or a basis of other waveforms, then
this type of approximation is the starting point for compression
algorithms. We will discuss the quantitative aspects of this
type of approximation. We will also discuss stable algorithms
for finding good or near best approximations using m terms.
These algorithms are representatives of a family of greedy algorithms.
More recently, there has emerged another more complicated form
of nonlinear approximation which we call highly nonlinear approximation.
It takes many forms but has the basic ingredient that a basis
is replaced by a larger system of functions that is usually
redundant. Some types of approximation that fall into this general
category are mathematical frames, adaptive pursuit (or greedy
algorithms) and adaptive basis selection. Redundancy on the
one hand offers much promise for greater efficiency in terms
of approximation rate, but on the other hand gives rise to highly
nontrivial theoretical and practical problems. We will discuss
some of these theoretical problems in the talk.
pdf
(540 KB) postscript
(760KB)
Michael
Unser (Biomedical Imaging Group/IOA/DMT Swiss Federal
Institute of Technology Lausanne EPFL) http://bigwww.epfl.ch/ michael.unser@epfl.ch
Fractional
Splines and Wavelets: From Theory to Applications
Joint work with T. Blu.
In the first part, we present the theory of fractional splines;
an extension of the polynomial splines for non-integer degrees.
Their basic constituents are piecewise power functions of degree
alpha. The corresponding B-splines are obtained through a localization
process similar to the classical one, replacing finite differences
by fractional differences. We show that the fractional B-splines
share virtually all the properties of the classical B-splines,
including the two-scale relation, and can therefore be used
to define new wavelet bases with a continuously-varying order
parameter. We discuss some of their remarkable properties; in
particular, the fact that the fractional spline wavelets behave
like fractional derivatives of order alpha + 1.
In the second part, we turn to applications. We first describe
a fast implementation of the fractional wavelet transform, which
is essential to make the method practical. We then present an
application of fractional splines to tomographic reconstruction
where we take advantage of explicit formulas for computing the
fractional derivatives of splines. We also make the connection
with ridgelets. Finally, we consider the use of fractional wavelets
for the detection and localization of brain activation in fMRI
sequences. Here, we take advantage of the continuously-varying
order parameter which allows us to fine-tune the localization
properties of the basis functions.
Ozgur Yilmaz (PACM, Princeton University) oyilmaz@Math.Princeton.EDU
Stability and Robustness Analysis for Several Sigma-Delta
Methods of Coarse Quantization of Band-Limited Functions
We investigate stability and robustness properties of a family
of algorithms used to "coarsely quantize" band-limited functions.
The algorithms we will consider are one-bit second-order sigma-delta
quantization schemes and some modified versions of these. We
prove that there exists a bounded region that remains invariant
under the two-dimensional piecewise-affine discrete dynamical
system associated with each of these quantizers. Moreover, this
bounded region can be constructed so that it is robust under
small changes in the quantizer.
Thomas Yu (Department of Mathematical Sciences, Rensselaer
Polytechnic Institute) yut@rpi.edu
Divide-and-Conquer, Minimum-Time Rendering and Isoperimetric
Inequalities
Divide-and-conquer and recursive dyadic partitioning are prevailing
ideas in both adaptive signal processing and theoretical computer
science. In this talk I will discuss a so-called minimum-time
rendering (MTR) problem in computer graphics which can be solved
by a marriage of divide-and-conquer and the celebrated graph
separation work of Lipton and Tarjan. While this method yields
sound theoretical results, it occurs to suffer from a certain
inefficiency inherent to divide-and-conquer. Based on a close
relationship between the MTR problem and isoperimetric problems,
we present a result which addresses this inefficiency. We present
also a new non-recursive algorithms for the MTR problem (inspired
by the idea of 'fast marching') which bypass the above-mentioned
inefficiency.
setting of curves in R^2.
|
|
|
|
|