Paper Perusal System

Click title in table of contents to view paper's abstract. To view the paper, click its title in the abstract (assumes availability of a PostScript viewer). To download the paper and any companion files in compressed format, click the ">Z<" symbol appearing before the abstract's title.

Table of Contents.

>Z< Minimax risk over l_p-balls for l_q-error David L. Donoho and Iain M. Johnstone

Consider estimating the mean vector $\theta$ from data $N_n(\theta, \sigma^2 I )$ with $l_q$ norm loss, $q \geq 1$, when $\theta$ is known to lie in an $n$-dimensional $l_p$ ball, $p \in (0, \infty )$. For large $n$, the ratio of minimax \sl linear \rm risk to minimax risk can be arbitrarily large if $p < q$. Obvious exceptions aside, the limiting ratio equals 1 only if $p=q=2$. Our arguments are mostly indirect, involving a reduction to a univariate Bayes minimax problem. When $p< q$, simple non-linear co-ordinatewise threshold rules are asymptotically minimax at small signal-to-noise ratios, and within a bounded factor of asymptotic minimaxity in general. Our results are basic to a theory of estimation in Besov spaces using wavelet bases (to appear elsewhere).

>Z< Ideal Spatial Adaptation via Wavelet Shrinkage David L. Donoho and Iain M. Johnstone

With ideal spatial adaptation, an oracle furnishes information about how best to adapt a spatially variable estimator -- piecewise constant, piecewise polynomial, variable knot spline, or variable bandwidth kernel -- to the unknown function. Estimation with the aid of an oracle offers dramatic advantages over traditional linear estimation by nonadaptive kernels; however, it is a priori unclear whether such performance can be obtained by a procedure relying on the data alone. We describe a new principle for spatially-adaptive estimation--- selective wavelet reconstruction. We show that variable-bandwidth kernels, variable-knot spline fits and piecewise-polynomial fits, when equipped with an oracle to select the knots, are not dramatically more powerful than selective wavelet reconstruction with an oracle. We develop a practical spatially adaptive method, RiskShrink, which works by shrinkage of empirical wavelet coefficients. RiskShrink mimics the performance of an oracle for selective wavelet reconstruction as well as it is possible to do so. A new inequality in multivariate normal decision theory which we call the oracle inequality shows that attained performance differs from ideal performance by at most a factor $ \sim 2 \log(n)$, where $n$ is the sample size. Moreover no estimator can give a better guarantee than this. Within the class of spatially adaptive procedures, RiskShrink is essentially optimal. Relying only on the data, it comes within a factor $\log^2(n)$ of the performance of piecewise polynomial and variable-knot spline methods equipped with an oracle. In contrast, it is unknown how or if piecewise polynomial methods could be made to function this well when denied access to an oracle and forced to rely on data alone.

>Z< Minimax Estimation via Wavelet Shrinkage David L. Donoho and Iain M. Johnstone

We attempt to recover an unknown function from noisy, sampled data. Using orthonormal bases of compactly supported wavelets we develop a nonlinear method which works in the wavelet domain by simple nonlinear shrinkage of the empirical wavelet coefficients. The shrinkage can be tuned to be nearly minimax over any member of a wide range of Triebel- and Besov-type smoothness constraints, and asymptotically minimax over Besov bodies with $p \leq q$. Linear estimates cannot achieve even the minimax rates over Triebel and Besov classes with $p < 2$, so our method can significantly outperform every linear method (kernel, smoothing spline, sieve, \dots) in a minimax sense. Variants of our method based on simple threshold nonlinearities are nearly minimax. Our method possesses the interpretation of spatial adaptivity: it reconstructs using a kernel which may vary in shape and bandwidth from point to point, depending on the data. Least favorable distributions for certain of the Triebel and Besov scales generate objects with sparse wavelet transforms. Many real objects have similarly sparse transforms, which suggests that these minimax results are relevant for practical problems. Sequels to this paper discuss practical implementation, spatial adaptation properties and applications to inverse problems.

Back to Table of Contents.

>Z< Nonlinear Solution of Linear Inverse Problems by Wavelet-Vaguelette Decomposition David L. Donoho

We describe the Wavelet-Vaguelette Decomposition (WVD) of a linear inverse problem. It is a substitute for the singular value decomposition (SVD) of an inverse problem, and it exists for a class of special inverse problems of homogeneous type -- such as numericaldifferentiation, inversion of Abel-type transforms, certain convolution transforms, and the Radon Transform. We propose to solve ill-posed linear inverse problems by nonlinearly ``shrinking'' the WVD coefficients of the noisy, indirect data. Our approach offers significant advantages over traditional SVD inversion in the case of recovering spatially inhomogeneous objects. We suppose that observations are contaminated by white noise and that the object is an unknown element of a Besov space. We prove that nonlinear WVD shrinkage can be tuned to attain the minimax rate of convergence, for $L^2$ loss, over the entire Besov scale. The important case of Besov spaces $\Bspq$, $p <2$, which model spatial inhomogeneity, is included. In comparison, linear procedures -- SVD included -- cannot attain optimal rates of convergence over such classes in the case $p<2$. For example, our methods achieve faster rates of convergence, for objects known to lie in the Bump Algebra or in Bounded Variation, than any linear procedure.

>Z< De-Noising by Soft-Thresholding David L. Donoho

Donoho and Johnstone (1992a) proposed a method for reconstructing an unknown function $f$ on $[0,1]$ from noisy data $d_i =f(t_i ) + \sigma z_i$, $\1in$, $t_i = i/n$, $z_i \stackrel{iid}{\sim} N(0,1)$. The reconstruction $\fn^*$ is defined in the wavelet domain by translating all the empirical wavelet coefficients of $d$ towards 0 by an amount $\sqrt{2 \log (n)} \cdot \sa / \sqrt{n}$. We prove two results about that estimator. [Smooth]: With high probability $\fn^*$ is at least as smooth as $f$, in any of a wide variety of smoothness measures. [Adapt]: The estimator comes nearly as close in mean square to $f$ as any measurable estimator can come, uniformly over balls in each of two broad scales of smoothness classes. These two properties are unprecedented in several ways. Our proof of these results develops new facts about abstract statistical inference and its connection with an optimal recovery model.

>Z< Density estimation by wavelet thresholding David L. Donoho, Iain M. Johnstone, Gerard Kerkyacharian, Dominique Picard

Density estimation is a commonly used test case for non-parametric estimation methods. We explore the asymptotic properties of estimators based on thresholding of empirical wavelet coefficients. Minimax rates of convergence are studied over a large range of Besov function classes $B_{s,p,q}$ and for a range of global $L_p' $ error measures, $1 \leq p' < \infty$. A single wavelet threshold estimator is asymptotically minimax within logarithmic terms simultaneously over a range of spaces and error measures. In particular, when $p' > p$, some form of non-linearity is essential, since the minimax linear estimators are suboptimal by polynomial powers of $n$. A second approach, using an approximation of a Gaussian white noise model in a Mallows metric, is used to attain exactly optimal rates of convergence for quadratic error ($p' = 2$).

Back to Table of Contents.

>Z< Wavelet Shrinkage: Asymptopia? David L. Donoho, Iain M. Johnstone, Gerard Kerkyacharian, and Dominique Picard

Considerable effort has been directed recently to develop asymptotically minimax methods in problems of recovering infinite-dimensional objects (curves, densities, spectral densities, images) from noisy data. A rich and complex body of work has evolved, with nearly- or exactly- minimax estimators being obtained for a variety of interesting problems. Unfortunately, the results have often not been translated into practice, for a variety of reasons -- sometimes, similarity to known methods, sometimes, computational intractability, and sometimes, lack of spatial adaptivity.
We discuss a method for curve estimation based on $n$ noisy data; one translates the empirical wavelet coefficients towards the origin by an amount $\sqrt{2 \log(n)} \sa /\sqrt{n}$. The method is different from methods in common use today, is computationally practical, and is spatially adaptive; thus it avoids a number of previous objections to minimax estimators. At the same time, the method is nearly minimax for a wide variety of loss functions -- e.g. pointwise error, global error measured in $L^p$ norms, pointwise and global error in estimation of derivatives -- and for a wide range of smoothness classes, including standard Holder classes, Sobolev classes, and Bounded Variation. This is a much broader near-optimality than anything previously proposed in the minimax literature. Finally, the theory underlying the method is interesting, as it exploits a correspondence between statistical questions and questions of optimal recovery and information-based complexity.

>Z< Unconditional Bases are Optimal Bases for Data Compression and for Statistical Estimation David L. Donoho

An orthogonal basis of $L^2$ which is also an unconditional basis of a functional space $\cal F$ is a kind of optimal basis for compressing, estimating, and recovering functions in $\cal F$. Simple thresholding operations, applied in the unconditional basis, work essentially better for compressing, estimating, and recovering than they do in any other orthogonal basis. In fact, simple thresholding in an unconditional basis works essentially better for recovery and estimation than other methods, period. (Performance is measured in an asymptotic minimax sense.) As an application, we formalize and prove Mallat's Heuristic, which says that wavelet bases are optimal for representing functions containing singularities, when there may be an arbitrary number of singularities, arbitrarily distributed.

>Z< Adapting to Unknown Smoothness via Wavelet Shrinkage David L. Donoho and Iain M. Johnstone

We attempt to recover a function of unknown smoothness from noisy, sampled data. We introduce a procedure, SureShrink, which suppresses noise by thresholding the empirical wavelet coefficients. The thresholding is adaptive: a threshold level is assigned to each dyadic resolution level by the principle of minimizing the Stein Unbiased Estimate of Risk (Sure) for threshold estimates. The computational effort of the overall procedure is order $N \cdot \log(N)$ as a function of the sample size $N$.
SureShrink is smoothness-adaptive: if the unknown function contains jumps, the reconstruction (essentially) does also; if the unknown function has a smooth piece, the reconstruction is (essentially) as smooth as the mother wavelet will allow. The procedure is in a sense optimally smoothness-adaptive: it is near-minimax simultaneously over a whole interval of the Besov scale; the size of this interval depends on the choice of mother wavelet. We know from a previous paper by the authors that traditional smoothing methods -- kernels, splines, and orthogonal series estimates -- even with optimal choices of the smoothing parameter, would be unable to perform in a near-minimax way over many spaces in the Besov scale.
Examples of SureShrink are given: the advantages of the method are particularly evident when the underlying function has jump discontinuities on a smooth background.

Back to Table of Contents.

>Z< Factorization Approach to Unitary Time-Varying Filter Banks Ramesh A. Gopinath and C. Sidney Burrus, Rice University

A complete factorization of all optimal (in terms of quick transition) time-varying FIR unitary filter bank tree topologies is obtained. This has applications in adaptive subband coding, tiling of the time-frequency plane and the construction of orthonormal wavelet bases for the half-line and interval. A simple efficient implementation algorithm also comes with the factorization ensuring that even the most complex tree topology can be adapted with minimal overhead. Explicit formulas for entry/exit filters are given for arbitrary tree transitions. The results are independent of the number of channels and the length of the filters (as long as they are FIR), implying that some of the efficiency reasons for considering only binary time-varying trees is not valid any more. Time-varying wavelet bases (different bases for different segments of the real line) are also constructed.

>Z< Optimal wavelet representation of signals and the wavlet sampling theorem R.A. Gopinath, J.E. Odegard, and C.S. Burrus

The wavelet representation using orthonormal wavelet bases has received widespread attention. Recently M-band orthonormal wavelet bases have been constructed and compactly supported M-band wavelets have been parameterized. This paper gives the theory and algorithms for obtaining the optimal wavelet multiresolution analysis for the representation of a given signal at a predetermined scale in a veriety of error norms. Moreover, for classes of signals, this paper gives the theory and algorithms for designing robust wavelet multiresolution analysis that minimizes the worst case approximation error among all signals in the class. All results are derived for the general M-band multiresolution analysis. An efficient numerical scheme is also described for the design of the optimal wavelet multiresolution analysis when the least-squared error criterion is used. Wavelet theory introduces the concept of scale which is analogous to the concept of frequency in Fourier analysis. This paper introduces essentially scalelimited signals and shows that bandlimited signals are essentially scalelimited, and gives the wavelet sampling theorem, which states that the scaling function expansion coefficients of a function with respect to the M-band wavelet basis, at a certain scale (and above) completely specify a bandlimited signal (i.e., behave like Nyquist (or higher) rate samples).

>Z< Unitary Equivalence: A New Twist on Signal Processing Richard G. Baraniuk and Douglas L. Jones

Unitary similarity transformations furnish a powerful vehicle for generating inf inite generic classes of signal analysis and processing tools based on concepts different from time, frequency, and scale. Implementation of these new tools involves simply preprocessing the signal by a unitary transformation, performing standard processing techniques on the transformed signal, and then (in some cases) transforming the resulting output. The resulting unitarily equivalent systems focus on the critical signal characteristics in large classes of signals and, hence, prove useful for representing and proces sing signals that are not well matched by current techniques. As specific examples of this procedure, we generalize linear time-invariant systems, orthonormal basis and frame decompositions, and joint time-frequency and time-scale distributions, illustrating the utility of the unitary equivalence concept for uniting seemingly disparate approaches proposed in the literature.

Back to Table of Contents.

>Z< Magnitude Squared Design of Recursive Filters with the Chebyshev Norm Using a Constrained Rational Remez Algorithm Ivan W. Selesnick, Markus Lang, and C. Sidney Burrus

We describe a Remez type exchange algorithm for the design of stable recursive filters for which the Chebyshev norm of H(w)-F(w) is minimized, where H(w) and F(w) are the realized and desired magnitude squared frequency responses. The number of poles and zeros can be chosen arbitrarily and the zeros do not have to lie on the unit circle. The algorithm allows us to design filters with non-conventional frequency responses with arbitrary weighting functions. It also gives optimal minimum phase FIR filters and Elliptic recursive filters as special cases. We discuss three main difficulties in the use of the Remez algorithm for recursive filter design and give ways to overcome them.

>Z< Automatic Generation of Prime Length FFT Programs Ivan W. Selesnick and C. Sidney Burrus

We describe a set of programs for circular convolution and prime length FFTs that are short, possess great structure, share many computational procedures, and cover a large variety of lengths. The programs make clear the structure of the algorithms and clearly enumerate independent computational branches that can be performed in parallel. Moreover, each of these independent operations is made up of a sequence of sub-operations which can be implemented as vector/parallel operations. This is in contrast with previously existing programs for prime length FFTs: they consist of straight line code, no code is shared between them, and they can not be easily adapted for vector/parallel implementations. We have also developed a program that automatically generates these programs for prime length FFTs. This code generating program requires information only about a set of modules for computing cyclotomic convolutions.

>Z< Efficient Low Delay Filter Banks Gerald Schuller and Mark J. T. Smith

This paper treats the problem of designing efficient FIR analysis-synthesis filter banks with system delays that can be pre-specified. A framework is introduced that is comprised of the cascade of several distinctive matrices with invertibility properties. The explicit form of the matrices guarantees computational efficiency and exact reconstruction, and allows for control over the system delay.

Back to Table of Contents.

>Z< A New Algorithm for Efficient Low Delay Filter Bank Design Gerald Schuller and Mark J. T. Smith

Historically, exact reconstruction FIR filter banks have had system delays of $L-1$, where $L$ is the length of the analysis and synthesis filters. Recently it was shown that the system delay could be made less than $L-1$, which is attractive in applications like speech coding where excessive delays are annoying. In this paper, a formulation and new design algorithm are introduced for two-band low-delay filter banks. The formulation is related to that of two-band lattice filter banks and provides a broad range of design flexibility within a compact framework. Both exact reconstruction and specified system delay are guaranteed by the structure of the framework.

>Z< A General Formulation for Modulated Perfect Reconstruction Filter Banks with Variable System Delay Gerald Schuller and Mark J. T. Smith

This paper introduces a new formulation for analysis and design of modulated filter banks. A unique feature of the formulation is that it provides explicit control of the input-to-output system delay. The paper discusses minimum delay filter banks and demonstrates that truly exact reconstruction is possible in this context. The formulation provides a broad range of design flexibility within a compact framework and allows for the design of a variety of computationally efficient modulated filter banks with different numbers of bands and virtually arbitrary lengths.

>Z< Diagonalizing the Gabor Frame Operator H. Boelcskei, H.G. Feichtinger, and F. Hlawatsch

The Gabor expansion is a signal decomposition into time-frequency shifted version of a window function. Computation of the expansion coefficients requires a "dual" window. This paper discusses fast algorithms for calculating the dual window. We consider situations where the Gabor frame operator can be expressed--either directly or in a transform domain--as a multiplication operator, and hence the dual window can be calculated by pointwise division. In the cases of critical sampling and integer oversampling, the Zak transform allows this procedure independently of the original window. In the general case (including the case of rational oversampling), one has to make restrictions on the window's temporal or spectral support. We furthermore obtain expressions for the eigenfunctions, eigenvalues, and frame bounds of the Gabor frame operator, and we derive an efficient algorithm for the construction of tight Gabor-type (Weyl-Heisenberg) frames.

Back to Table of Contents.

>Z< Equivalence of DFT Filter Banks and Gabor Expansions H. Boelcskei and F. Hlawatsch

Recently, connections between the wavelet transform and filter banks have been established. We show that similar relations exist between the Gabor expansion and DFT filter banks. We introduce the "z-Zak transform" by suitably extending the discrete-time Zak transform and show its equivalence to the polyphase representation. A systematic discussion of parallels between DFT filter banks and Weyl-Heisenberg frames (Gabor expansion theory) is then given. Among other results, it is shown that tight Weyl-Heisenberg frames correspond to paraunitary DFT filter banks.

Back to Table of Contents.