HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Talk Abstracts
Joint IDR-IMA Workshop

Material from Talks

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
setting of curves in R^2.

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.

Material from Talks

Joint IDR-IMA Workshop: Ideal Data Representation

2000-2001 Program: Mathematics in Multimedia