30343

Download the full version of the ebook at
https://ebookultra.com
Beyond Wavelets 1st Edition Grant Welland
https://ebookultra.com/download/beyond-
wavelets-1st-edition-grant-welland/
Explore and download more ebook at https://ebookultra.com

Recommended digital products (PDF, EPUB, MOBI) that
you can download immediately if you are interested.
Wavelets and Multiwavelets 1st Edition Fritz Keinert
https://ebookultra.com/download/wavelets-and-multiwavelets-1st-
edition-fritz-keinert/
ebookultra.com
A Friendly Guide to Wavelets 1st Edition Gerald Kaiser

(Auth.)
https://ebookultra.com/download/a-friendly-guide-to-wavelets-1st-
edition-gerald-kaiser-auth/
ebookultra.com
Discrete Fourier analysis and wavelets 2ed. Edition

Broughton S.A.
https://ebookultra.com/download/discrete-fourier-analysis-and-
wavelets-2ed-edition-broughton-s-a/
ebookultra.com
Square³ Mira Grant
https://ebookultra.com/download/square%c2%b3-mira-grant/
ebookultra.com
Plant Speciation Verne Grant
https://ebookultra.com/download/plant-speciation-verne-grant/
ebookultra.com
Parry and Grant Encyclopaedic Dictionary of International

Law 3rd Edition John P Grant
https://ebookultra.com/download/parry-and-grant-encyclopaedic-
dictionary-of-international-law-3rd-edition-john-p-grant/
ebookultra.com
Fundamentals of wavelets Theory algorithms and

applications 2ed Edition Goswami J.
https://ebookultra.com/download/fundamentals-of-wavelets-theory-
algorithms-and-applications-2ed-edition-goswami-j/
ebookultra.com
Mapping the Posthuman 1st Edition Grant Hamilton
https://ebookultra.com/download/mapping-the-posthuman-1st-edition-
grant-hamilton/
ebookultra.com
World War II Reg Grant
https://ebookultra.com/download/world-war-ii-reg-grant/
ebookultra.com
Beyond Wavelets 1st Edition Grant Welland Digital
Instant Download
Author(s): Grant Welland
ISBN(s): 9781435631991, 1435631994
Edition: 1
File Details: PDF, 14.30 MB
Year: 2003
Language: english
BEYOND WAVELETS
BEYOND WAVELETS
Gran t V. WELLAND
University of Missouri - St. Louis
Department of Mathematicsand Computer Science
St.Louis, USA
ACADEMIC PRESS
An imprint of Elsevier Science
2003
Amsterdam - Boston - Heidelberg - London - New York - Oxford - Paris
San Diego - San Francisco - Singapore - Sydney - Tokyo
STUDIES IN
COMPUTATIONA
L MATHEMATIC
S 10
Editors:
C.K. CHUI
StanfordUniversity
Stanford, CA,USA
P. MONK
University of Delaware
Newark. DE. USA
L. WUYTACK
University of Antwerp
Antwerp, Belgium
ACADEMI
C PRESS
An imprint of Elsevier Science
2003
Amsterdam - Boston - Heidelberg - London - New York - Oxford - Paris
San Diego - San Francisco - Singapore - Sydney - Tokyo
ELSEVIER SCIENCE Inc.
360 Park Avenu e South
New York, NY 10010-1710. USA
' 2003 Elsevier Science Inc. Allrightsreserved.
This work is protecte d unde r copyrigh t by Elsevier Science, and the followin g terms and condition s appl y to its use:
Photocopyin g
Single photocopie s of single chapter s may be made for persona l use as allowed by national copyrigh t laws. Permission
of the Publishe r and paymen t of a fee is require d for all other photocopying , includin g multipl e or systematic copying ,
copyin g for advertisin g or promotiona l purposes , resale, and all forms of documen t delivery . Special rates are availabl e
for educationa l institution s that wish to make photocopie s for non-profi t educationa l classroom use.
Permission s may be sough t directl y from Elsevier’ s Science & Technolog y Rights Departmen t in Oxford, UK: phone :
(+44) 1865 843830, fax: (+44) 1865 853333, e-mail: [email protected] . You may also complet e your reques t
on-lin e via the Elsevier Science homepag e (http://www.elsevier.com) , by selecting ’Custome r Support ’ and then
’Obtainin g Permissions’ .
In the USA, users may clear permission s and make payment s throug h the Copyrigh t Clearanc e Center , Inc., 222
Rosewood Drive, Danvers , MA 01923, USA; phone : (978) 7508400, fax: (978) 7504744, and in the UK throug h the
Copyrigh t Licensin g Agency Rapid Clearanc e Service (CLARCS), 90 Tottenham Court Road, London WIP OLP, UK;
phone : (+44) 207 631 5555; fax: (+44) 207 631 5500. Other countrie s may hav e a local reprographi c rights agency for
payments .
Derivativ e Works
Tables of content s may be reproduce d for interna l circulation , but permissio n of Elsevier Science is require d for external
resale or distributio n of such material .
Permission of the Publishe r is require d for all other derivativ e works , includin g compilation s and translations .
Electroni c Storage or Usage

Permission of the Publishe r is require d to store or use electronicall y any materia l containe d in this work, includin g any
chapter or part of a chapter .
Except as outline d above , no part of this work may be reproduced , stored in aretrieval system or transmitte d in any form
or by any means , electronic , mechanical , photocopying , recordin g or otherwise , withou t prior written permissio n of the
Publisher .
Addres s permission s request s to: Elsevier’ s Science & Technolog y Rights Department , at the phone , fax and e-mail
addresse s noted above .
Notice
No responsibility is assume d by the Publishe r for any injur y and/or damage to person s or propert y as a matter of
product s liability, negligenc e or otherwise , or from any use or operatio n of any methods , products , instruction s or ideas
containe d in the material herein . Because of rapid advance s in the medica l sciences , in particular , independen t
verificatio n of diagnose s and dru g dosages shoul d be made.
First edition 2003
Librar y of Congres s Cataloging in Publication Data

A catalog record from the Librar y of Congres s has been applie d for.
British Librar y Cataloguin g in Publication Data

A catalogue record from the British Librar y has been applie d for.
Academi c Press
An Elsevier Science Imprint
525 B Street, Suite 1900, San Diego, CaHfomia 92101-4495, USA
http://www.academicpress.co m
ISBN: 0 1 2 743273 6
ISSN: 1570 579 X (Series)
Typeset by Alden Press, Oxford

Printed in Great Britain by MPG Books Ltd, Bodmin , Cornwal l
' The paper used in this publicatio n meets the requirement s of ANSI/NISO Z3 9.48-1992 (Permanenc e of Paper).
Printed in The Netherlands .
PREFACE
The themes of classical wavelets include terms such as compression and effi›
cient representation. Important features which play a role in analysis of functions
in two variables are dilation, translation, spatial and frequency localization and
singularity orientation. Singularities of functions in more than one variable vary in
dimensionality. Important singularities in one dimension are simply points. In two
dimensions zero and one dimensional singularities are important. A smooth singu›
larity in two dimensions may be a one dimensional smooth manifold. Smooth sin›
gularities in two dimensional images often occur as boundaries of physical objects.
Efficient representation in two dimensions is a hard problem and is addressed in
the first six chapters. The next two chapters return to problems of one dimen›
sion where new important results are given. The final two chapters represent a
transition from harmonic analysis to statistical methods and filtering theory but
the goals remain consistent with those of earlier chapters. We have chosen to
title "Beyond Wavelets". We could have used the title, "Pursuing the Promise of
Wavelets". We briefly describe each chapter.
The lead chapter, "Digital Ridgelet Transform based on True Ridge Functions"
by David Donoho and Georgina Flesia addresses the problem of analyzing the
structure of a function of two real variables. It extends work of Donoho and an
associated group of co-workers. Special credit is due to Emmanuel Candes. Donoho
and Candes have constructed a system called curvelets which gives high-quality
asymptotic approximation of singularities. Passage from their continuum study
to one appropriate for applications requires development of digital algorithms to
implement concepts of the continuum study faithfully. A less obvious proposal
than a standard tensor product basis was made earlier by Donoho emphasizing
"wide-sense" ridgelets with localization properties in radial and angular frequency
domains. Wide-sense ridgelets are no longer of strict ridge form but allow the
possibility of an orthonormal set of elements. The theory is related to that of
the Radon transform and to rotation and scaling of images. At the continuum
level these are natural but for digital data issues are problematic. In this chapter a
definiton of digital ridgelet transform is given. The digital transform has structural
relationships strongly analogous to those of the continuum case. The transform
takes a n-by-n array of data in Cartesian coordinates and expands it by a factor
of 4 in creating a coefficient array. This leaves room for further improvements.
VI
Chapter 2 is a companion chapter to Chapter 1 and continues the study of digi›

tal implementation of ridgelets with ridgelet packets. The two principal approaches
given are the frequency-domain approach and the Radon approach. In the first
approach a recursive dyadic partition of the polar Fourier domain produces a col›
lection of rectangular tiles followed by a tensor basis of windowed sinusoids in
the angular and radial variables for each tile. In the Radon approach transforma›
tion to the Radon domain is followed by using wavelets in the angular variable and
wavelet packets in the second Radon variable. The Radon isometry is important in
this case. The notion of pseudopolar Fast Fourier Transform and a pseudo Radon
isometry called the normalized Slant Stack are discussed and used. In both cases
analysis of image data relies on directionally oriented waveforms. The wavelet
packet and the local sinusoidal packet bases are generalizations of the original
wavelet systems of elements. Ridgelet packets which follow in the spirit of these
systems are highly orientation selective and bear much the same relationship to
ridgelets as do wavelet packets to wavelets.
In Chapter 3, Frangois Meyer and Raphy Coifman create brushlets to address
the problem of describing an image with a library of steerable wavelet packets.
By careful design of the window of the local Fourier basis, brushlets with very
fast decay are obtained. They note that other directionally oriented filter banks
have been constructed which a redundancy factor of 2 or 4. This presents a major
hurdle to computing a sparse image representation. By use of a construction in the
Fourier domain they create wavelet packets which are complex valued functions
with a phase. A key ingredient of the construction is a window used for local
Fourier analysis. The window is required to have very fast decay.
Do and Vetterli study image representation in Chapter 4. An observation that
the curvelet transform is defined in the frequency domain leads to the question: "Is
there as spatial domain scheme for refinement which at each generation, doubles
the spatial resolution as well as the angular resolution?" They propose a filter
bank construction that effectively deals with piecewise smooth images with smooth
contours. The resulting image expansion is a frame composed of contour segments,
which are named contourlets. Their work leads to an effective method to implement
the discrete curvelet transform.
Chan and Zhou open discussion of the ENO-wavelet construction in Chapter 5,
by discussing oscillations which emulate the classical Gibbs’ phenomenon. It has
be discovered that the wavelet Gibbs’ phenomenon is generated by using differ›
ence filters across boundaries of discontinuity. ENO is the acronym for the phrase
essential non-oscillatory which represents an approach for suppression of unwanted
oscillations encountered at discontinuities. Rigorous approximation error bounds
are found to depend on the smoothness of function away from discontinuities when
the ENO approach is used. Several applications of the ENO method are given which
include function approximation, image compression and signal denoising.
An explicit model for Bayesian reconstruction of tomographic data is given by
S. Zhao and H. Cai in Chapter 6. Their approach to image analysis is based on an
interesting analogy to classical mechanics. The intensity of each pixel of an image
is modelled by a transverse motion of a "pixtron". The energy for Bayesian tomo-
VII
graphic reconstruction is interpreted as the total kinetic energy of the collection

of pixtrons and log-likelihood is interpreted as potential energy restricting motion
of pixtrons. Finally, the use of the minimization of a log-posterior is analogous to
the principle of least action of classical mechanics. The analogy allows them to
show that a Gaussian Markov random field prior can viewed as the kinetic energy
of free motion of pixtrons. The analogy leads to a novel image prior for Bayesian
tomographic reconstruction based on level-set evolution of an image driven by the
mean curvature motion. Their methods are accompanied by applications to brain
slice images which demonstrate algorithms produced by the model.
Chui and Stockier give extensive description of recent developments of spline
wavelets and frames in Chapter 7. Splines have many of the natural features
required in the original design of I. Daubechies for wavelets which result in beauti›
ful formulas. Vanishing moments reflect smoothness. Design of wavelet frames with
vanishing moments requires a series of new ideas. The authors explain why early
design approaches fail to create wavelets with higher orders of vanishing moments
and then provide steps to recover vanishing moments. The method involves the
notion of vanishing moment recover functions. The theory is extended in the direc›
tion of tight spline-wavelet frames with arbitrary knot sequences that allow stacked
knots. Knot Stacking provides local increase in smoothness and can be applied at
the boundaries of bounded intervals and half line segments. This gives greater
flexibility overcoming standard rigid design features of classical wavelets in which
supports are closely tied to the dilation factor of wavelet families. Multi-wavelets
represent a special case of this more general construction.
Chapter 8, "Afl^ne, Quasi-afl[ine and Co-affine Wavelets", by Washington Uni›
versity the group of researchers, is devoted to fully understanding results of Ron
and Shen. Dilations and translation are two characteristic operators used to define
the wavelet pyramid. The question studied asks whether the order in which dila›
tion and translation are applied is important. A subset of the affine group, used in
the wavelet definition, is the set translations followed by dilation. A second subset
of the aflfine group is the set for which dilation is applied first which is followed
by translation. The effects are dramatically diflferent. Ron and Shen found that by
reversing the order of these operators at a ’half-way’ point in the wavelet pyramid
results in a diflferent set of functions and yet they are sufficient to solve the rep)-
resentation problem. This chapter is devoted to understanding this phenomenon
and it is discovered that the choice of Ron and Shen is essentially optimal.
Benichou and Saito search for relations between the related criteria in Chap›
ter 9. Two studies motivate them. Olshausen and Field pioneered an approach
to imaging which investigates representation of natural images emphasizing spar-
sity of representation using a large library of photographs of natural images and
computer experiments to derive a set of basis elements for eflficient representation.
Bell and Sejnowski conducted similar studies in which statistical independence
was the major criterion. The pair of studies suggests both the basis derived for
sparse representation and the basis derived under the independence criterion pro›
duce elements eflficient for capture of edges, orientation and location; all features
prominently studied by image researchers. Their study is based on a modest goal
Vilf
that begin s with an artificial stochastic process , the spike process , from which
they obtain theorem s which give precis e condition s on the sparsit y and statistical
independenc e criteri a to select the same basis for the spike process .
S. Akkarakaran and P.P. Vaidyanatha n provid e a new directio n from previou s
work in Chapter 10. Standard filter banks fall unde r the theor y of design and uni›
form filter banks. A nonunifor m filter bank is one whose channe l decimatio n rates
need not all be equal . Most nonunifor m filter bank design s resul t in approximatio n
or near-perfec t reconstructio n which leaves open theoretica l issues for nonunifor m
filter banks. Their stud y is restricte d to filter banks with integer decimatio n rates.
A set, S, of integer s satisfies maximal decimatio n if the reciprocal s of the inte›
gers sum to unity. They only stud y filter banks with integer decimatio n rates.
Their stud y searche s for necessar y and sufficien t condition s on S for existence of
a perfect-reconstructio n filter bank belongin g to some class which uses S as its set
of decimators . They presen t examples with condition s which are either sufficien t
or necessar y but unfortunatel y different . They focus on rational filter banks and
strengthe n known necessar y condition s providin g an importan t step to solvin g the
problem . However , the basic proble m remain s unresolved . Necessary and sufficien t
condition s remai n unknown . Thus they open an importan t proble m and provid e
insigh t toward solvin g it.
This volum e is a produc t which was conceive d durin g a conferenc e funde d
by the National Science Foundatio n and the Conferenc e Board of Mathematical
Sciences at which David Donoho was the principa l speaker in May of 2000 at the
Universit y of Missouri - St. Louis. The title "Beyond Wavelets" is due to David
Donoho. I thank the NSF and the Universit y of Missouri - St. Louis and the suppor t
staff of the Mathematics Departmen t there . A very special thank s is extended to
David Donoho for his continue d suppor t and understanding .
Many contribute d to the success of that conferenc e and to the origina l idea to
develo p "Beyond Wavelets". I give thanks to Charles Chui, Raphy Coiftnan, Ingrid
Daubechies , and Joachim Stockier and Shiying Zhao. I thank the contributor s to
the volum e both for their efforts and understanding . I take responsibilit y for the
delays encountere d and beg your forgiveness . Many more deserv e to be mentione d
to whom I extend my thank s anonymously .
Grant Welland
St. Louis, MO
February , 2003.
CONTENTS
V Preface v
1 Digital Ridgele t TVansfor m
base d on Tru e Ridg e Function s
D.L. Donoho and A.G. Flesia 1

1.1 Introduction 2
1.1.1 Ridgelets on the Continuum 2
1.1.2 Discretization of Ridgelets 3
1.2 Digital Ridgelets 4
1.3 Relation to Fast Slant Stack 10
1.4 Structural Analogies 13
1.4.1 Two Continuum Radon Transforms 13
1.4.2 Analogies between Polar and Pseudopolar Fourier
Domains 14
1.4.3 Analogies between Radon Isometrics 15
1.4.4 Analogies between Ortho-Ridgelet Analyses 16
1.4.5 Analogies Between Frequency-Domai n Tilings 16
1.5 Example: HalfDome 17
1.6 Sparsity of the Frame Kernel 19
1.6.1 Analysis of a Coarse-scale ridgelet 20
1.6.2 Remarks on Decay 20
1.6.3 Edge Effects 21
1.7 Comparisons 21
1.7.1 Comparison with Zp-ridgelets 21
1.7.2 Comparison with earlier ridgelets 23
1.8 Discussion 26
Reference s 29
2 Digital Implementatio n of Ridgele t Packets
A.G. Flesia, H. Hel-Or,

A. Averbuch , E.J. Candes ,
R.R. Coifman and D.L. Donoho 31
2.1 Introduction 32
2.2 Fourier Preliminaries 36
IX
X CONTENTS
2.3 Radon Preliminaries 39

2.4 The Ridgelet Construction, and its Properties 40
2.5 Ridgelet Packet Construction 42
2.5.1 General Procedure 42
2.5.2 Bases of Ridgelet Packets 43
2.5.3 Radon Approach: Wavelets in both Ridge and Angular
Directions 43
2.5.4 Radon Approach: Wavelet Packets in the Ridge Direc›
tion 45
2.5.5 Polar Fourier Approach: Wavelet (g) Cosine Packet 47
2.6 Implementation on Digital Data 48
2.6.1 Fast Slant Stack 48
2.6.2 Pseudopolar F FT 48
2.6.3 Digital Radon Domain 49
2.6.4 Strategy for Digital Implementation 50
2.6.5 Digital Ridgelet Packets 50
2.6.6 Digital Implementation 51
2.6.7 Examples of Digital Implementation 52
2.6.8 Synthesis from Tiles 52
2.6.9 Analysis 53
2.7 Adaptation 55
2.7.1 Background on Best Basis 55
2.7.2 Application to Ridgelet Packets 56
2.8 Discussion 57
2.8.1 Improvements in the Digital Implementation 57
2.8.2 Limitations on the Ridgelet Packet Scheme 58
Reference s 59
3 B r u s h l e t s : S t e e r a b l e Wavele t P a c k e ts
Francoi s G. Meyer an d Ronal d R. Coifma n 61

3.1 Introduction 61
3.2 Biorthogonal windowed Fourier bases 65
3.2.1 Implementation by folding 67
3.3 Choice of the bell function 69
3.3.1 The orthonormal bell of Wickerhauser 69
3.3.2 Optimized bell of Matviyenko 69
3.3.3 Modulated Lapped Biorthogonal Transform (MLBT) 71
3.4 Biorthogonal brushlet bases 72
3.4.1 One dimensional case 72
3.4.2 Discrete implementation of the brushlet expansion 74
3.4.3 Two-dimensional case 75
3.5 Conclusion 81
Reference s 82
CONTENTS XI
4 Contourlet s
M. N. Do and M. Vetterli 83
4.1 Introduction and Motivation 83
4.2 Representing 2-D Piecewise Smooth Functions 85
4.2.1 Curvelet construction 85
4.2.2 Non-linear approximation behaviors 85
4.2.3 A filter bank approach for sparse image expansions 87
4.3 Pyramidal Directional Filter Bank 89
4.3.1 Multiscale decomposition 89
4.3.2 Directional decomposition 90
4.3.3 Multiscale and directional decomposition 91
4.3.4 PDFB for curvelets 93
4.4 Multiresolution Analysis 93
4.4.1 Multiscale 94
4.4.2 Multiple Directions 95
4.4.3 Multiscale and multidirection 98
4.5 Numerical Experiments 100
4.6 Conclusion 104
Reference s 104
5 ENO-wavelet Transform s
£Uid Some Application s
Tony F. Chan and Hao-Min Zhou 107

5.1 Introduction 107
5.2 The ENO-Wavelet Algorithm HI
5.2.1 ENO-wavelet at Discontinuities 111
5.2.2 Locating the Discontinuities 116
5.2.3 A Simple Example 118
5.3 Theory: Error Bound and Stability 119
5.4 Application 121
5.4.1 Function Approximation 121
5.4.2 Image Compression 125
5.4.3 Signal Denoising 130
Reference s 131
6 A Mechanica l Imag e Model for
Bayesian Tomographi c Reconstructio n
Shiying Zhao and Haiyan Cai 135

6.1 Introduction and Background 136
6.1.1 Introduction 136
6.1.2 Positron Emission Tomography 137
6.1.3 Bayesian Tomographic Reconstruction Method 138
xii CONTENTS
6.2 Materials and Methods 140

6.2.1 A Mechanical Image Model 140
6.2.2 Kinetic Energy Induced from Level-Set Evolution 142
6.2.3 Numerical Implementations 143
6.3 Results and Discussion 145
6.3.1 Simulation Results 145
6.3.2 Discussion 146
6.3.3 Conclusion 149
Reference s 149
7 Recen t Developmen t of Splin e
Wavele t Frame s wit h Compac t Suppor t
Charle s Chu i and Joachim Stockier 151

7.2 Characterization of Wavelet Spline Frames 155
7.2.1 Tight frames with dilation factor 2 158
7.2.2 Non-tight sibling frames with dilation factor 2 166
7.2.3 Frames with integer dilation factor 171
7.3 Wavelet Frames of Splines with Multiple Knots 175
7.4 The Common Link: Approximate Duals 184
7.4.1 Background on univariate 5-splines 186
7.4.2 A particular polynomial 190
7.4.3 Explicit form of an approximate dual 191
7.5 Tight Spline Frames with Non-uniform Knots 199
7.5.1 Piecewise linear tight frames 203
7.5.2 Piecewise cubic tight frames with equidistant simple
knots 205
7.5.3 Tight frames of cubic splines with equidistant knots of
multiplicity 2 208
Reference s 212
8 Afiine , Quasi-Affin e an d Co-Affine Wavelet s
Philip Gressman , Demetri o Labate, Guid e Weiss and Edwar d

N. Wilson 215
8.1 Introduction _ 215
8.2 Frames and the three systems X{ip),X*{ip), and X{ip) 219
Reference s 222
9 Sparsit y vs . Statistical
Independenc e in Adaptiv e
Signal Representations :
A Case Stud y of th e Spike Process
CONTENTS xiii
Bertran d Benicho u and Naoki Saito 225

9.2 Notation and Terminology 227
9.3 Sparsity vs. Statistical Independence 228
9.3.1 Sparsity 228
9.3.2 Statistical Independence 229
9.4 Two-Dimensional Counterexample 230
9.5 The Spike Process 230
9.5.1 The Karhunen-Loev e Basis 231
9.5.2 The Best Sparsifying Basis 232
9.5.3 Statistical Dependence and Entropy of the Spike Process 232
9.5.4 The LSDB among 0(n) 233
9.5.5 The LSDB among GL(n,R) 233
9.6 Proofs of Propositions and Theorems 236
9.6.1 Proof of Proposition 236
9.6.2 Proof of Theorem 9.5.1 237
9.6.3 Coordinate-wise Entropy of the Spike Process 239
9.6.6 Proof of Proposition 9.5.2 247
9.6.7 Proof of Corollary 9.5.5 247
9.7 Discussion 248
9.8 Appendices 250
9.8.1 Appendix A: Proof of Lemma 9.6.1 250
9.8.2 Appendix B: Proof of Lemma 9.6.3 252
9.8.3 Appendix C: Proof of Lemma 9.6.5 253
Reference s 255
10 Nonunifor m Filter Banks :
New Result s and Open Problem s
Sony Akkarakara n and P.P. Vaidyanathan 259

10.1.1 Relevant earlier work 261
10.1.2 Outline 263
10.1.3 Notations, definitions and assumptions 263
10.2 Background: Equivalent Uniform FBs; PR Equations 264
10.2.1 PR for uniform FBs, and the nonuniform to uniform
transform 265
10.2.2 The general PR conditions for nonuniform FBs 266
10.2.3 Relation between the nonuniform and uniform PR
designs 268
10.3 Problem Statement, and Unconstrained FBs 269
10.3.1 Problem statement 269
xiv CONTENTS
10.3.2 FBs with unconstrained complex and real coefficient fil›

ters 270
10.4 Tree Structures 271
10.4.1 Basics and terminology 271
10.4.2 Uniform-trees: An incomplete PR theory for nonuniform
FBs 273
10.4.3 Using trees to improve PR conditions on the decimators 275
10.5 Delay-chains 276
10.5.1 PR condition on the set of decimators 277
10.5.2 Testing the PR condition 277
10.5.3 Delay-chains vs. uniform-trees 278
10.6 The Class of Rational FBs 280
10.6.1 Previously known necessary conditions on decimators 280
10.6.2 The pairwise gcd test 281
10.6.3 Tree version of strong compatibility 281
10.6.4 The AC-matrix test 282
10.7 Conditions Based on Reductions to Tree Structures 285
10.8 Summary and Comparison of Necessary Conditions 289
10.9 Concluding Remarks 290
10.10 Appendices 291
lO.lO.lAppendix A: Proof of Nonuniform Biorthogonality Con›
dition (2.3) 291
10.10.2Appendix B: Derivability of Decimator-sets from a
Uniform-tree 292
10.10.3Appendix C: Proof of Fact 3 293
10.10.4Appendix D: Proof of Fact 4 294
10.10.5Appendix E: Testing Tree Version of Strong Compati›
bility 296
10.10.6Appendix F: Algorithm for the AC Matrix Test 297
10.10.7Appendix G: Proofs of Theorems 6,7 297
10.10.8Appendix H: Proof of Theorem 8 300
Reference s 301
Inde x 303
Beyond Wavelets
G. V. Welland (Editor)
' 2003 Elsevier Science (USA) All rights reserved
DIGITAL RIDGELET TRANSFORM

BASED ON TRUE RIDGE FUNCTIONS
D.L. DONOHO AND A.G. FLESIA
Department of Statistics, Stanford University
Sequoia Hall, 390 Serra Mall, Stanford, CA 94305-4065
[email protected], edu [email protected], edu
A b s t r a ct
We study a notion of ridgelet transform for arrays of digital data in which
the analysis operator uses true ridge functions, as does the synthesis oper›
ator. There are fast algorithms for analysis, for synthesis, and for partial
reconstruction. Associated with this is a transform which is a digital analog
of the orthonormal ridgelet transform (but not orthonormal for finite n). In
either approach, we get an overcomplete frame; the result of ridgelet trans›
forming an n X n array is a 2n x 2n array. The analysis operator is invertible
on its range; the appropriately preconditioned operator has a tightly con›
trolled spread of singular values. There is a near-parseval relationship.
Our construction exploits the recent development by Averbuch et al.
(2001) of the Fast Slant Stack, a Radon transform for digital image data;
it may be viewed as following a Fast Slant Stack with fast 2-d wavelet
transform. A consequence of this construction is that it offers discrete
objects (discrete ridgelets, discrete Radon transform, discrete Pseudopo-
lar Fourier domain) which obey inter-relationships paralleling those in the
continuum ridgelet theory (between ridgelets. Radon transform, and polar
Fourier domain).
We make comparisons with other notions of ridgelet transform, and we
investigate what we view as the key issue: the summability of the kernel
underlying the constructed frame. The sparsity observed in our current
implementation is not nearly as good as the sparsity of the underlying
continuum theory, so there is room for substantial progress in future imple›
mentations.
2 DIGITAL RIDGELET TRANSFORM
1.1 INTRODUCTION
1.1.1 Ridgelets on the Continuum
Recently, several theoretical papers have called attention to the potential benefits
of analyzing continuum objects /(x, y) with (x, y) R^ using new bases/frames
called ridgelets [3], [4] and [12]
A ridge function p(x,y) = r{ax -f- by), that is to say, it is a function of two
variables which is obtained as a scalar function r{t) of a synthetic scalar variable
t = ax+hy [20]. Geometrically, the level sets of such a function are lines ax-i-by = t
and so the graph of such a function, viewed as a topographic surface, exhibits
ridges. The function r{t) is the profile of the ridge function as one traverses the
ridge orthogonally to its level sets.
In Candes’ thesis [3], a ridgelet is a function pa,h,e{x,y) xjj{{cos{9)x-f
sin(^)y - b)/a)/a^/’^ where V’(t) is a wavelet - an oscillatory function obeying
certain moment conditions and smoothness conditions. The continuous Ridgelet
transform Rf{a,b,0) = {f,Pa,b,9)is defined on functions / in L^ and extends by
density to L^. This transform obeys a parseval relation and an exact reconstruc›
tion formula. Candes also showed that discrete decompositions were possible, so
that for L^ spaces of compactly supported functions one could develop a frame
of ridgelets - a discrete family (ân,6n,^n(^)) serving the role of an approximating
system.
The "classic ridgelets" of Candes are not in L^(R^), being constant on lines
t = xi cos 9 -h X2sin^ in the plane. This fact seems responsible for certain tech›
nical difficulties in the deployment and interpretation of discrete systems based
on Candes’ notion of ridgelet. In [12] Donoho proposed to broaden the concept of
ridgelet somewhat, allowing ’Svide-sense" ridgelets to be functions obeying certain
localization properties in a radial frequency x angular frequency domain. Under
this broader conception, ridgelets no longer are of strict ridge the form pa,b,u{^)y
so the elegant simplicity of formulation is lost. However, in exchange, it becomes
possible to have an orthonormal set of "wide-sense" ridgelets. These orthonormal
ridgelets are believed to be appropriate L^-substitutes for ridge functions, and to
fulfill the goal of a constructive and stable system which although not based on true
ridge functions are believed to play operationally the same role as ridge functions,
compare [12, 13].
For either classic ridgelets or orthonormal ridgelets, the central issue is that
such systems should behave very well at representing functions with linear singu›
larities. As a prototype, consider the mutilated Gaussian :
9{xuX2) = l(,,>o}e-^?-^’, X R2 . (1.1.1)
See Figure 1.1. This is discontinuous along the line X2 = 0 and smooth away
from that line. Due to the singularity along the line, this function has coefficients
of relatively slow decay in both wavelet and Fourier domains, so it requires large
numbers of wavelets or sinusoids to represent accurately. The rate of convergence of
best iV-term superpositions of wavelets or sinusoids cannot be faster than 0{N~^).
On the other hand, g can be represented by relatively few ridgelets: the rate of
INTRODUCTION
Figure 1.1. 'Half Dome'- a Mutilated Gaussian
convergence of appropriate AT-term superpositions of ridgelets or ortho-ridgelets

can be faster than 0{N~’^) for any m > 0. And the situation is the same for
any rotation or translation of p so that the line 0:2 = 0 becomes a Une cos(^)a: -f-
sin{0)y = t.
While perfectly straight singularities are rare, many two-dimensional objects
concern imagery with edges, which may be regarded as curved singularities.
While ridgelets per se do not provide the right tool for such curved singu›
larities, Candes and Donoho have used ridgelets to construct a system called
curvelets which gives high-quality asymptotic approximations to such singulari›
ties. Curvelets are ridgelets that have been dilated and translated and subjected
to a special space/frequency localization explained in [6]. The rate of convergence
of an appropriate AT-term superpositions of curvelets is nearly 0(iV~^) in squared
error, whereas the comparable behavior for classical systems would by 0{N~^) or
worse.
1.1.2 Discretization of Ridgelets

The conceptual attractiveness of this theoretical work drives us to consider the
problem of translating it (if possible) from continuum concepts, useful in theo›
retical discussion, to algorithmic concepts capable of widespread application. It is
initially by no means obvious how to do this or whether it can really be done.
The theory of ridgelets is closely related to the theories of Radon transformation ,
and of rotation and scaling of images, all of which seem natural and simple on the
continuum, and for which it is widely believed that there is no simple, inevitable
definition for digital data.
A number of prior attempts at defining a digital ridgelet transform have been
made; these will be discussed in detail further below.
In this paper, we propose a definition of digital ridgelet transform with several
desirable properties. We believe that this definition is based on a clear understand›
ing of the fundamental opportunities and limitations posed by data on a Cartesian
grid, and has clear superiority over some other notions of discrete ridge let trans›
form which are, in our view, false starts.
Our definition offers:
Analysis and synthesis by true ridge functions. The underlying analysis and
synthesis functions depend on (u, v) as p{u + bv) or p{v + bu). This means that
the transform is geometrically faithful, and avoids wrap-around artifacts.
Exact reconstruction formula. There is an iterative algorithm which in the limit
gives exact reconstruction from the ridgelet transform.
Near-Parseval Relationship. There is a variant of the DRT, which we call the
(pseudo-) Ortho-Ridgelet Transform, in which the energy in coefficient space is
equal to the energy in original space, to within a few percent.
Fast algorithm. There is a fast algorithm requiring only 0{N \og{N))flops for
data sampled in an n by n grid, where N = ’n? \s the total number of data.
Continuum analogies. The transform and related objects have structural rela›
tionships bearing a strong analogy with all the principal relationships that exist
in the continuum case, between ridgelet transform. Radon transform, and Polar
Fourier transform.
Cartesian data structures. The transform takes data on a Cartesian grid and
creates a rectangular coefficient array indexed according to a semi-direct product
of simple integer indices measuring scale, location, and orientation.
Overcompleteness. The transform takes an n-by-n array and expands it by a
factor of 4 in creating the coefficient array.
We also compare properties of this DRT with its continuum counterpart, and
with other discrete counterparts, particularly as regards sparse representation of
objects with discontinuities along lines. We point out certain conceptual and practi›
cal advantages of the new transform, over, for example, the Z^ transform proposed
by Do and Vetterli [8], and certain advantages over straightforward discretizations
of the Fourier plane proposed by Donoho [9] and Starck et al. [22].
Our current implementation provides a frame whose kernel does not have,
in our view, sufficient sparsity to provide in the digital setting all the quantita›
tive advantages offered by the continuum theory, leaving ample room for further
improvements.
1.2 DIGITAL RIDGELETS

Let ipj,k{t) = V^j,fc(^;^) be the periodic discrete Meyer wavelet for the m-point
discrete circle m/ 2 < t < m/2 with indices JQ < j < log2(m), and 0 < A; < 2^;
this is studied in, for example, Kolaczyk’s thesis [18]. This is actually defined as
the discrete inverse Fourier transform
m / 2 -l
’^jAt)= Yl 4;’’exp((i27r/m)ti;0
w=-m/2
of a certain complex sequence (cj;’^) which can be derived, e.g. using arguments in
[1]. Since the formula makes sense for all t and not only for integers in the range
DIGITAL RIDGELETS 5
m/ 2 < t < m/2, the periodic discrete Meyer wavelet is unambiguously defined
not just at integral t, hut in fact for all real t. Figure 1.2 displays a Meyer Wavelet
of degree 2.
We will also have use for fractionally-differentiated Meyer wavelets, defined as
follows. For a certain sequence {6^})
r _ j y/2w/m w ^ 0
" " \ y/Tjt^ W = 0
we apply this as a multiplier to the Fourier coefficients of ipj^k, getting
m / 2 -l
V^j,fc(0 = Yl ^^’^w^ ’ exp((227r/m)ti;t).
w= m/2
(Equivalently, we could define ’ipj^k = ^-^’^j,k, where denotes m-point circular

convolution and A is the inverse discrete Fourier transform of (6)).This is equally
well viewed as a trigonometric polynomial defined at all t. Figure 1.2 displays a
fractionally-differentiate
d Meyer wavelet. For reasons that will be clear later, we
also call the ipj^k normalized wavelets. In this paper we consider images as n by
1.
0.5
i ^V ^ (
^
' ^V i j 0 f^v-
^ M i! i
1
ll -0.5
y i
Figure 1.2. Left side: Meyer Wavelet of degree 2. Right side: Fractionally differenciated
Meyer wavelet of degree 2
n arrays indexed by coordinates (u, v) ranging in the square n/ 2 < u,v < n/2
centered at (0,0). Let 6^^ be defined so that
tan(^]. ) = 2£/n, -n/2 <£< n/2; cotan(^|.^) = 2£/n, n/2 < £ < n/2.
The lines v = ta.n{6j.^)u-ht we speak of as ’basically horizontal lines’ and the lines
u = cota.n{6f,^)v-{-twe speak of as ’basically vertical lines’. Each family of lines is
equispaced in slope, rather than angle. Figure 1.3 illustrates this family of angles.
Definition 1.2.1 Let n be given. A digital ridgelet Pj,k,s/ is an n by n array built

as ridge functions from Meyer wavelets by the formula
Pj,k,sA’^^’^)= ’^jA’^ -^ tan(^l)t’). s=h

and
DIGITAL RIDGELET TRANSFORM
Figure 1.3. Lines in frequency space corresponding to pseudopolar angles
p3,k,s,t{u,v) = ’0j,fc(v + cotan(^l)u), 5 = 2,

where the parameter m underlying the definition obeys m = 2n. We also call digital
ridgelet any function built as ridge functions from fractionally-differentiate
d Meyer
wavelets by the formula
Pj,k,s,t{u,v) = i)j^k{u+ tan(^|)i;), s = 1,
and
Pj,k,sA’^y^) = ’^jA’^ + cotan(^l)u), s = 2.
These definitions in fact guarantee that the resulting objects pj^k^s^ti’^-,’^)and

P3,k,s,i{u,v)are digital samplings of true continuum ridge functions. We note that
there are m = 2n wavelets and 2 x n angles ^|^. For future use, we write A =
(j, k, s, tj for quads occurring in this definition, and A for the set of all 4n^ quads.
Figure 1.4 gives a few examples of such ridgelets.
Figure 1.4. Digital Ridgelets
Definition 1.2.2 The digital ridgelet analysis operator applied to an n x n image

(/(li, v) : n/ 2 <u,v< n/2) is the array with 4n^ entries
DIGITAL RIDGELETS 7
RI={{I,px):X£A)
We also call digital ridgelet analysis the corresponding normalized operator
Rl = {{irpx):XeA)
In either case, we conventionally think of the DRT as a 2n by 2n array, as

in Figure 1.5, which shows the analysis of an object with linear singularity. Fig›
ure 1.6(a) gives a map of the coefficient space.
Figure 1.5. Ridgelet analysis of an object with a linear singularity: Left sideiAmplitude Map
of Ridgelet coefficients. Right side: Amplitude Map of Ridgelet coefficients on a square root
scale
1 = 3 4 5 6 7 3 4 5 6 7
Figure 1.6. Map of coefficient space: Left side: Ridgelets, Right side: Ortho-Ridgelets
Definition 1.2.3 The digital ridgelet synthesis operator takes a 2n by 2n coeffi›

cient array {ax : A G A) into an n x n array
R*a = Yâxpx.
We also call digital ridgelet synthesis the corresponding normalized operator

The notation J?* is meant to suggest the adjoint operation, and in fact /?* is
precisely the formal adjoint of R.
The first main result is that these transforms are in a sense invertible, and so
exact reconstruction is possible in principle.
Theore m 1.2.4 The operators R and R are one-one and so invertible on their
range.
The second main result is that these transforms are rapidly computable.
Theore m 1.2.5 The operators R, R, R* and R* can all be computed exactly in

order 0{N\og{N)) exact arithmetic operations, where N = n^ is the number of
entries in the n by n image.
The next ’result’ is really a distillation of computational experience.

Empirica l Fact. The normalized transforms R, and R* have their^ nonzero
singular values within about 10% of each other. The generalized inverse can be
computed to seven digits accuracy in 4 iterations of a conjugate gradient solver.
As a corollary of this empirical result, we have that the system p\ makes a
frameJ with the ratio of frame bounds empirically smaller than 1.10 . Thus the
system (px)behaves nearly as well as would a tight frame or ortho basis.
It will also be important to consider a discrete analog of orthonormal ridgelets.
Let Wi^£{u)denote a discrete orthonormal Cohen-Daubechies-Feauveau-Jawert h
boundary adjusted wavelet for the discrete interval n/ 2 < tx < n/2. There are n
of these wavelets, with indices 0 < z < log2(n) and 0 < ^ < 2*. For real sequences
(Wu)and (V;,) indexed by -n/2 <u< n/2, let {W, V} denote the inner product
Definition 1.2.6 Given the normalized discrete Ridgelet transform array RI, we
define the (pseudo-) Ortho Ridgelet transform array UI by taking the wavelet
transform along the angular variable of RI:
Figure 1.7 shows the ortho-ridgelet transform of the same Halfdome object as
in Figure 1.5. It will be evident that the display is more sparse; the transform in 6
has compressed the laterally elongated features in Figure 1.5 into more point-like
features. Figure 1.6(b) gives a map of the coefficient space M for this transform.
There is, of course, a Riesz representer for each coefficient of UI. For later
use, let fjL = {j,k\i,£) denote the tuple indexing UI, and let u^ denote the Riesz
representer of {UI)^, i.e. the vector obeying
{UI)^ = {I,u^).
DIGITAL RIDGELETS
WT "TT"
Figure 1.7. Ortho-Ridgelet analysis of an object with a linear singularity: Left side:Amplitude
map of Ortho-Ridgelet Coefficients. Right side.Ortho-Ridgelet Coefficients on a square root
scale
Figure 1.8 gives an example of such a representer, which we will call a (pseudo-)
ortho ridgelet. Just like the ortho ridgelets for the continuum, these are no longer
true ridge functions; they crudely behave like fragments of ridgelets windowed by
circular windows depending on i. Now U and R are related by an ort honormal
Figure 1.8. Some (pseudo-) Ortho-Ridgelets
transformation of the space of 2n by 2n arrays, so it follows that all the injectivity

and frame bounds properties obeyed by R follow for U as well.
Corollar y 1.2.7 The An? elements {u^ : /i G M) make a frame with frame bounds
empirically within about 10% of each other.
1.3 RELATION T O FAST SLANT STACK

The article [2] defined the notion of Fast Slant Stack a certain kind of discrete
Radon transform which is intimately connected to our notion of Ridgelet trans›
form.
Given an array /(w, v), a slope a with |a| < 1, and an offset z, we initially define
the Radon transform associated with the basically horizontal line t/ = ax -h 6 via
Radon({y = ax-\- b}, /) = ^ /^ (u, au + b).

u
Thus, we are summing at n values (w, au H- 6) along the line y = ax -\-b. Since a
is not integral, the ordinates at which we are summing do not in general lie in the
original pixel grid on integer pairs. Therefore, the values we are summing come not
from the original image /, but instead an interpolant /^(u,y), which takes integer
values in the first argument, and real values in the second argument.
The interpolation "in y only", is performed as follows. Letting m = 2n, we
define the Dirichlet kernel of order m by
Dm{t) = cotan(7r^/m) sin(7ri)/m -f-1 sin(7rt)/m.
We then set
n/2- l
v=-n/2
We note that Dm is an interpolating kernel, so that
I{u,v) = i^{u,v), - n /2 <u,v < n/2.
(b)
Lglpri
Figure 1.9. Left: Half Dome. Right: Slant Stack of Half Dome
In the case of basically vertical lines, we define the Radon transform similarly,
interchanging roles of x and y:
Radon({x = ay + 6}, /) = ^ P{av -\-b,v),

RELATIO
N TO FAST SLANT STACK 11
with the interpolant defined analogously:

n/2- l
P{X,V)= Yl I{u.v)Dm{x-u).
u=-n/2
It is convenient to also have 0 to represent the angle associated to the slope s.
Definition 1.3.1 The Slant Stack operator 5 is defined by

(57) (t, e) = Radon({y = tan(^)x +1}, / ) ,
and, for^G [7r/4,37r,4),
{SI){t,9) = Radon({x = cotan(6>)y -f t}, I).
where the intercept ranges through -n < t < n, and the angles vary through
$1^ = arctan(2^/n), - n / 2 < £ < n/2 and Oj^ = n/A + arctan(2Vn).
We note that while 7 is n by n, 57 may be regarded as a 2n by 2n array.

Figure 1.9 depicts the slant stack of the Half Dome image. Recall the fractional
Figure 1.10. The Slant Stack of a point is a broken line. First row: Images with nonzero
entry at a single point. Second row corresponding Radon Transform, with break in slope at
n corresponding to ^ = n/4.
differentiation operator introduced in Section 2. We can apply this to t-slices of 5

to produce a normalized Slant Stack operator:
5 7 ( ; 5 , 0 = A * 5 7 ( ; 5 , /)
The following properties of the Slant Stack operator have been established in [2].
Theorem 1.3.2 The operator 5 is one-one and hence invertible on its range.
Theorem 1.3.3 The operators 5 and 5* can each he computed in order

0{N\og{N)) flops.
T h e o r e m 1.3.4 The operator S has r? nonzero singular values; the ratio of the
largest to smallest is hounded independently of n.
The next ’result’ summarizes the computational experience in [2] .

Empirica l Fact. The normalized transform S, and adjoint S* have all their
nonzero singular values within about 10% of each other. The generalized inverse
can he computed to seven digits accuracy in 4 iterations of a conjugate gradient
solver.
We can now exhibit the relevance of the Slant Stack to our notion of Ridgelet
transform. To do so, we let ((,}) denote the inner product purely in the ^-variable.
T h e o r e m 1.3.5 The Digital Ridgelet Transform is the 1-dimensional Meyer-

wavelet transform, in t, of the Slant Stack Radon Transform:
{RI){j,k,s,l) = {{SI{-,s,l),^j,ki-))).
The normalized Digital Ridgelet Transform is the 1-dimensional Meyer-wavelet

transform, in t, of the normalized Slant Stack Radon Transform:
(^/)0-,A:,5,/) = ({57(-;5,0,V^,-,fc(-))).
With this equivalence established, it is clear that all the results of the last
section follow immediately from the results quoted here. Since the Meyer wavelet
transform is an isometry, we have
||5/||2 = ||fl/||2, ||5/|l2 = \\RIh-
All the norm bounds and norm ratios for the ridgelet transform and for the normal›
ized Slant Stack transform are identical. Since the 1-dimensional Meyer transform
costs 0 ( n l o g ( n )) flops, and we perform this once for each column of S the con›
version from the 2n x 2n slant stack domain to ridgelet domain costs a total of
0 ( n 2 l o g ( n )) or 0{N\og{N)) flops.
It remains to prove Theorem 1.3.5. Let [, ] denote the inner product in the
2n X 2n slant domain, and let lso,io denote the Kronecker sequence indexed by
{s,£) which has a 1 in position s = SQ, I = IQ and is zero elsewhere. Then
{{SI{-;sJ),^j,k{-))) = [SI.^j,k^ls,i]-
Now, by the definition of adjoint,
[57 , t/;,-fc ^ U,i] = (/, 5*(V^,-fc 0 1,,0).
Finally, we arrive at the key observation:
a digital ridgelet is the (slant-) Radon hackprojection of a wavelet living in a single

6-slice. In turn, this follows because trigonometric interpolation is exact on Meyer
wavelets,
STRUCTURAL ANALOGIES 13
n- l
t=-n
Indeed, S* involves application of the trigonometric interpolation operator to
each column of ipj^k <8> !«,/ and this gives exactly the same result at a given
{v = tan(^)u -f z) as applying the formula for ijjj^k directly at that point. The›
orem 3.5 is established.
1.4 STRUCTURAL ANALOGIES

There are several analogies between the discrete ridgelet analysis proposed here
and continuum ridgelet analysis. We believe that these analogies further support
the correctness of our notion of digital Ridgelet analysis.
1.4.1 Two Continuum Radon Transforms

To understand our analogies it is important to introduce an important variant of
the traditional continuum Radon transform - the continuum slant stack.
It is convenient in this paper to denote the Radon transform operator using
the letter "X", as R has already been taken by ridgelet transform, and X suggests
X-ray. Set
{Xf){t,e)= f f{x)6{xicose + X2sme-t) dx , (1.4.1)
where 9 e [0,27r) and t e H.
Suppose we define, for 9 G [ 7r/4,7r/4 )
Y’f{t,9) = f f{x,y)S{t-x~-ytM^))dxdy, (1.4.2)
and for 9 [7r/4,37r/4)
Y’^f{t,9) = f f{x,y)6{t - cotan(<9)x - y)dxdy (1.4.3)
and encapsulate these in a single object Yf defined by

y . / , m _ / > ^ V ( ^ , ^ ) ^ e [ - 7 r / 4 , 7 r / 4)
^ J ^^^^)-\Y^f(t,9) 9 e[7r/^,37r/A) ’
Then, if / is a small pointlike ’bump’, a display of Yf will look like a broken line,
with a break at the transition angle 9 = 7r/4.
The continuum Slant stack transform originated in seismics [7, 23]. Another
field in which this continuum transform has been (independently) developed is
medical tomography, where Yf is called the Linogram [14, 15], in reference to
the fact that points map under Y into broken lines, whereas in the usual Radon
transform, points map into sinusoids; because of this in medical tomography, the
usual Radon transform is sometimes called the sinogram.
We remark that the continuum Slant stack and the continuum Radon transform
contain the same information: for 0 G [-7r/4,7r/4),
(X/)(t.cos(^),^) = (y/)(t,^);
a similar relationship holds for 9 e [7r/4,37r/4).
It should be evident that the continuum slant stack has a close relationship
to the discrete slant stack; hence, the above relationship between the continuum
slant stack and the continuum Radon transform, provides a connection between
the discrete slant stack and the continuum Radon, albeit with a certain amount
of relabelling.
This observation is responsible for the several analogies described in this sec›
tion.
1.4.2 Analogies between Polar and Pseudopolar Fourier Domains

To understand still better the underlying relationships, note that there are actu›
ally three important domains associated with traditional ridgelet analysis in the
continuum case: the ridgelet domain, the Radon domain, and the so-called polar
Fourier domain. To complete our understanding of the situation, we need to know
about all three.
The polar Fourier transform is defined in terms of the usual Fourier transform
by simple cartesian-to-polar transformation :
F(u;, 9) = f{Lj ’ cos{9),uj sm{9))
Through the well-known projection-slice theorem [7], many facts about -the
Radon domain can be translated isometrically into facts about the polar Fourier
domain, and vice versa. The projection-slice theorem says that the one-dimensional
Fourier transform in t of a fixed ^-slice of the Radon transform yields precisely a
slice of the Polar Fourier transform at the same 9. So, if f{x,y) is a function in
L ^ ( R 2) with Radon transform Xf{t,9) and polar Fourier transform F{uj,9) and
if Fi denotes 1-dimensional Fourier transform in the first variable
{F,xf){uj,e) = F{w,e). (1.4.4)
The digital ridgelet transform obeys comparable relationships, between ridgelet
domain, (slant-) Radon domain, and pseudopolar Fourier domain. The pseudopolar
domain is discussed in detail in [2]. It offers a notion of polar Fourier domain
better adapted to digital data. The digital Fourier domain is viewed as a sequence
of squares, not circles, and the "radial shells" picked out by the (pseudo-) "radial"
variable are squares.
Define the ordinary 2-d Fourier transform of / by
/(Ci,6) = ^ / ( x i , t ; ) e x p { - i ( u 6 + ^ 6 ) } -
The discrete pseudopolar Fourier transform P of the digital image / is defined for
n<k<n and - n /2 < i < n/2 by sampling the 2-D Fourier transform at the
collection of pseudopolar grid points illustrated Figure 1.11. Formally,
STRUCTURAL ANALOGIES 15
Figure 1.11. Pseudopolar grid points
(I{7rk/nta.n{0l),7rk/n) s=l
{PI){Ks,£)
\ /(TT/C/TI, cotan(^|)7rA:/n) s = 2
The frequencies of evaluation in this relation do not lie in a Cartesian grid.

A discrete projection-slice theorem exists relating the (slant-) Radon transform
and the pseudopolar Fourier transform. The discrete projection-slice theorem [2]
says that if we take the 1-dimensional Fourier transform in t of the slant-Radon
data SI{t,9), we get samples of the two-dimensional Fourier transform of /.
(Fi5/)(a;,^) = P(a;,^), (1.4.5)
where now Fi denotes discrete Fourier transform of length 2n in the first variable
and u = nk/n, n<k<n and 6 = O^^. It follows that the (slant-) transform
of digital data is isometric to the pseudopolar Fourier Transform. We remark that
this situa,tion parallels a similar relationship for the continuum-domain Slant stack
transform Yf introduced above.
1.4.3 Analogies between Radon Isometries

An important consequence of (1.4.4) and (1.4.5): a simple postprocessing of the
Radon transform creates an isometry. Indeed, as the Fourier transform is an isom-
etry, we have that the norm of / is conveniently measured in the polar Fourier
domain by
-| /"oo /»27r
^ J-ooJo
Indeed,
oo /»27r /"Oo /»27r
/
/ \F{w, e)\^\ij\dwd9 = 2 / / | / ( r cos(6l), r sm(e))\’^rdrde
-oo Jo 2\\ff2
Jo Jo
= nf\\i
It follows that the object
F(uj,e) = \uj\F{uj,e)
is isometric with / , and equally that the new object
is a Radon-like object isometric with / , which we call the Radon isometry. Now
this object has an alternate definition. Let A denote the convolution operator on
smooth Z/^(R) functions g defined on the Fourier side by the multiplier relation
(Kicg){u;) = \uj\g{oj), u; € R.
It follows that
xf{;e)= A*xf{;e)
so that simple postprocessing of X by the Fourier multiplier |u;| creates an isometry.
SinceA*A = - ( ^ ) 2 , A is in an obvious sense a fractional differentiation operator.
The Radon isometry X bears a strong analogy with the normalized Slant Stack
S. Indeed, the fact that X is an isometry of L^, makes it comparable to a matrix
operator having all its singular values equal to one, while S has all its_singular
values within a reasonable percentage of each other. Moreover, X = {A (S)I)X
- i.e. a fractional differential operator is applied to the Radon transform; while
S = (A (g) / ) 5 - a discrete analog of fractional operator is applied to the Slant
stack.
1.4.4 Analogies between Ortho-Ridgelet Analyses

In the continuum case, the ridgelet orthobasis is built essentially as follows: we
create an orthobasis of wavelets {W\(t,0)) living in the Radon domain {t,6)
R X [0, 27r). We then apply the inverse Radon Isometry X~^ to the wavelet basis,
getting px = X~^Wx. In words, (ortho-) ridgelet analysis is wavelet analysis com›
posed with radon isometry.
In the discrete case, we do something entirely similar. We create an orthobasis
of wavelets living in the (slant-) Radon domain -n < t < n, 6}.^ = tan(2^/n),
ê;n cotan(2^/n), by taking the direct product ijjj^k <8) wfi. We then apply the
normalized (slant-) operator S^ to this, getting (pseudo-) ortho-ridgelets Tj^kî.i-
In the digital ridgelet case, we have something similar, but based on concentric
squares rather than concentric circles, see Figure 1.12(b).
1.4.5 Analogies Between Frequency-Domain Tilings

For additional insights, we can consider the ortho-ridgelets in the frequency domain
rather than the Radon domain. The typical member p\{x\,X2) of the ortho-
ridgelets basis for L^(R^) can be defined in the frequency domain by
EXAMPLE: HALFDOME 17
Figure 1.12. Ridgelet tiling and Digital Ridgelet tiling
Piio = ier*(v^;,fc(ieiK,w+V';fc(-ieiK,(^+7r))/2 (1.4.6)
Here {ipj,k{t): j G Z ,k Z) denotes an orthonormal basis of Meyer wavelets

for L2(IR), and {wl^{e), ^ = 0 , . . ., 2^ - 1; w}/e), i > IQ, ^ = 0 , . . ., 2^ - 1) an
orthonormal basis for L^[0,27r) made of periodized Lemarie scaling functions w^^^,
at level io and periodized Meyer wavelets w\^ at levels z > ZQ.
Now the 1-dimensional Fourier transform of a wavelet ipj,kW is a windowed
sinusoid, with window supported in A [|7r2^, f 7r2^]. Hence, the Fourier transform
of this ridgelet lives in a dyadic annulus of radius ^ 2K The wavelet w\^^{0)is
mostly concentrated to a window near Oiê = 27r^/2*. Hence, the Fourier transform
of the ortho ridgelet lives in an angular wedge. Combining these remarks, we have
the pattern illustrated in Figure 1.12(a), which we call the ridgelet tihng of the
frequency plane.
1.5 EXAMPLE: HALFDOME

We now use the HalfDome object to illustrate the relationships we have just dis›
cussed, and to underline the plausibility of ridgelet analysis. Figure 1.13 shows
the HalfDome object in Fourier space both with and without the Ridgelet tiling
superposed. It is evident that the energy in the object is concentrated near a
highly elongated sausage-shaped feature oriented at 90 to the orientation of the
discontinuity in the HalfDome object in original space. We of course hope that the
ridgelet tiling is well-adapted to the underlying distribution of energy in the object
under study - i.e. that only a few tiles are required to cover the bulk of the energy
in the object and that only a few coefficients per tile are needed to represent the
part of the object overlapping that tile. It is evident from the distribution of the
energy in frequency space that there is a strong possibility that things will work
out as hoped.
(a) (b)
Figure 1.13. Fourier Transform of Halfdome on log scale, (a) without (b) with ridgelet tiling
We now conside r the situation in the Radon domain . Figur e 1.14 reveal s that
the Slant Stack of the HalfDome objec t is smooth away from a singularit y at a
single (5, /, t) value . Now, the ridgele t coefficients of HalfDome are roughl y speak›
ing such wavele t coefficients of the Slant Stack. It makes sense that a 2 d wavele t
transfor m of this objec t will have sparse coefficients, with the large coefficients con›
centrate d at indice s associated with spatial position s near the singularity . Hence,
we expect the ridgele t transfor m to be sparse . However , to be rigorousl y correct ,
we must remembe r that the ridgele t coefficients arise from the wavele t transfor m
of the normalize d Slant Stack, which is portraye d in Figur e 1.14.
(b)
Figure 1.14. a) Normalized Slant Stack of HalfDome and b) Wavelet Transform of it
The normalize d Slant Stack exhibits - like the unnormalize d Slant Stack -
smoothnes s away from a singularit y at a single point . Consequently , it is clear that
we shoul d indee d have sparsit y of the 2-D wavele t transfor m and henc e sparsit y
SPARSITY OF THE FRAME KERNEL 19
in the ridgelet domain, as indeed we observe in Figure 1.5. For extra clarity, we
show the wavelet transform with nonlinear transformation .
(a)
^^11^^^
Figure 1.15. Left: Half Dome, Right:Pseudopolar FT of HalfDome
Continuing in our chain of equivalences, suppose we now take the discrete

Fourier transform in t of each i-slice of the normalized Slant Stack. Then we are
viewing the (normalized) pseudopolar Fourier transform of HalfDome; this is dis›
played below. In this pseudo-polar coordinate system, the object of interest is
well-concentrated in a few tiles. Again, we see reason to expect a sparse represen›
tation.
1.6 SPARSITY OF THE FRAME KERNEL

Both ridgelet transforms defined here are expansive: they transform an n by n array
into a 2n by 2n coefficient array. Equivalently, each set of analysis and synthesis
functions, having 4n^ elements for representing objects with n^, is overcomplete.
As a result, it becomes important to study the frame kernel G(/x, v) = {p^, pu),
particularly as regards the sparsity of its rows kernel. If the ridgelet system were
orthonormal, each row would have a single nonzero element on the diagonal, and
hence be extremely sparse. In the overcomplete case, what we can hope for is
that the nonzero elements in each row, once rearranged in order of decreasing
amplitude, decay rapidly.
Owing to the obviously high inner products of true ridge functions oriented in
neighboring directions, we should not expect rapid decay of the coefficients if we
work in the ridgelet system, but should look instead to the ortho-ridgelet system.
To check the sparsity condition, we consider the following computational exper›
iment: we synthesize a single ortho-ridgelet and then analyze that ridgelet, inspect›
ing the resulting transform coefficients for rapid decay.
We give examples here in two caês.
Figure 1.16. Ortho-Ridgelet Synthesis and Analysis Planes: Left side: OrthoRidgelet Synthe-
sis. Right side:OrthoRidgelet Analysis on a square root scale
1.6.1 Analysis of a Coarse-scale ridgelet

Figure 1.16 shows the ortho-ridgelet synthesis plane - evidently a delta sequence
peaking at the appropriate place in coefficient space -, and the ort ho-ridgelet anal›
ysis plane. The analysis plane is considerably more spread out than the synthesis
plane. Figure 1.17 presents a close-up of the principal subband.The delta in the
synthesis plane is replaced by a blob in the analysis plane. Another display of
Figure 1.17. Close-up of principal subband of Ridgelet Analysis Plane
behavior in the analysis plane simply plots the sizes of coefficients in decreasing
order, as shown in Figure 1.18. Evidently, there are few "big" coefficients, followed
by a decaying tail.
1.6.2 Remarks on Decay

While the analysis plane is visually quite sparse, in fact the degree of sparsity
exhibited by the transform is disappointing. This is caused by the fact - seen in
Figure 1.18- that, after the initial quite rapid drop-off of coefficient amplitudes,
there is a rather slow decay in the tail region. This sort of phenomenon is well
known in the harmonic analysis of nonperiodic signals, and it is an interesting
open question whether some variant on the procedure could repair this slow decay.
COMPARISONS 21
Figure 1.18. Decreasing Rearrangement of Ridgelet Analysis Plane
1.6.3 Edge Effects

It seems important to note that the kernel decay becomes worse the more the
ridgelet in question is concentrated near the edges of the image. We consider a
ridgelet at a fine scale that happens to live near the corner of the image domain,
and again show its ten-term reconstruction, see Figure 1.19. We again show the
Figure 1.19. Left, Corner Ridgelet, and right, 10-term Reconstruction
analysis and synthesis planes. The analysis plane is dramatically more spread out
than before, exhibiting long stripes, see Figure 1.20. Figure 1.21 presents a close-up
of the principal subband.
1.7 COMPARISONS
1.7.1 Comparison with Zp-ridgelets
Do and Vetterli [8] have proposed a method of ridgelet analysis based on the
use of the Radon transform for Zp, the cartesian product of two copies of the
integers mod p, where p is a prime. At a formal level, this has much to recommend
it, including orthogonality. Essentially, one applies the Z^ Radon transform, and
then take the wavelet transform in the T direction.
Figure 1.20. Corner Ridgelet: Synthesis and Analysis Planes
Figure 1.21. Corner Ridgelet: Principal subband of Ridgelet Analysis Plane
Unfortunately, the Z’^ Radon transform integrates over ’lines’ which are defined
algebraically rather than geometrically, and so the points in a ’line’ can be rather
arbitrarily and randomly spread out over the spatial domain. In consequence, the
Zp ridgelets that are defined in this way have a rather strange apppearance. Tyj)-
ical examples are shown on Figure 1.22. Such ’ridge functions’ have their support
i ' ' ' : ' ' ;
Figure 1.22. Examples of Zp Ridgelets
scattered haphazardly throughout the image plane, and resemble neither a a tra-
COMPARISONS 23
ditional ridge function, nor any spatially coherent object. As a consequence of this
behavior, partial reconstructions in the Zp system have errors which look very
much like textured random noise. Figure 1.23 compares reconstruction of Half-
Dome by 50 Zp ridgelet coefficients with reconstruction by 50 ridgelets based on
the transform developed here. The additional noisiness is clear. Figure 1.24 con-
(a) (b)
4gP
(c) (d)
Figure 1.23. Reconstruction of HalfDome by Zp ridgelets, and digital ridgelets. (a) Recon-
struction by 50 Zp coefficients, (b) Reconstruction by 50 DR coefficients, (c) Reconstruction
by 100 Zl coefficients, (d) Reconstruction by 100 DR coefficients
siders an object used by Do and Vetterli [8] in their paper on Z’^ ridgelets, and
compares reconstruction by 50 Z^ ridgelet coefficients with reconstruction by 50
ridgelets based on the transform developed here. Again, the additional noisiness
in Z^ reconstruction is clear.
In summary, the Z’^ approach simply is not based on a geometrically faithful
notion of ridgelet, and suffers from textural artifacts.
1.7.2 Comparison with earlier ridgelets

We briefly mention three other notions of ridgelet transform we know about.
In [9] , an initial attempt was made to construct a discrete ridgelet transform
operating in order N\og{N) flops, where N = ’n? is the image size. The idea
was based on approximate cartesian-to-polar resampling. One would overlay a
true polar grid on the discrete Fourier transform, and approximately evaluate
the discrete Fourier transform at polar grid points by interpolation from nearby
cartesian grid points. It was shown that by this device one could obtain a Frame,
provided the polar grid were sufficiently dense. However, this approach had three
seeming drawbacks. First, it might be that it would require a very high degree
of oversampling to obtain the Frame property. Second, the kind of interpolation
required would involve considerable arithmetic for each desired polar grid point,
with frequent accesses to data in a near a corresponding pixel location, which, on
(a) (b)
# ^ ^ ^ ^ ^ ^
d d
(c) (d)
Figure 1.24. Reconstruction by Zp ridgelets, and digital ridgelets. (a) Reconstruction by 128
Zp coefficients, (b) Reconstruction by 256 Zp coefficients, (c) Reconstruction by 128 DR
coefficients, (d) Reconstruction by 256 DR coefficients
modern hierarchical memory computers might cause frequent cache misses, and
correspondingly slow operations. Third, the method was inelegant to program, for
example, because of attempting to ’fit a round polar grid in a square cartesian
box’ the were annoying special cases arose at the corners of the grid.
In [10], the strategy described in this paper, based on the pseudo-polar grid,
was described and implemented, only with m n in the definition rather than
the choice vn ln used here. A key advantage of this approach is that the under›
lying pseudopolar FFT requires only one-dimensional FFT’s and so is completely
vectorizable; this is an advantage on modern hierarchical memory machines and
machines with 1-dimensional FFT’s as built-in operations. The difference between
the m n and m = 2n versions comes in boundary behavior. The m = n approach
has ridgelets which wrap around at the border, while the m = 2n approach does
not suffer from the wrap-around artifacts (seeFigure 1.28).
(a) (b)
Figure 1.25. Wrap around artifact of earlier ridgelets

COMPARISONS 25
(a) (b)
(c) (d)
A
Figure 1.26. Comparison between Wavelet reconstructions, earlier Ridgelet reconstruction
and OrthoRidgelet reconstruction of (a) Half Dome using, (b) 16 Wavelet coefficients, (c)
16 Earlier Ridgelet coefficinets, (d) 16 Ridgelet coefficients
(a) (b)
(d)
Figure 1.27. (a) Half Dome, (b)BandPassed HalfDome, (c) FT of Half Dome on square root
scale, (d) Windowed FT of Half Dome on a square root scale.
The above cited papers were not released at the time they were written because
of Stanford University’s patent fiUng in this area.
The paper [22], follows part of the strategy described in this paper, based on
the pseudo-polar grid. However, instead of exact evaluation of the trigonometric
polynomial / on the pseudo-polar grid, it uses a simple nearest-neighbor interpo›
lation scheme to evaluate pseudo-polar grid points in terms of nearby Cartesian
grid points. The frame bounds available by this approach are considerably broader
than those obtained by the exact interpolation used in this paper, although for
Figure 1.28. Ridgelet Analysis of BandPassed HalfDome. Left side:Amplitude Map of

Ridgelet coefficients. Right side:Amplitude Map of Ridgelet coefficients on a square root
scale
(a) (b)
Rank order, m Number of Terms, m
Figure 1.29. Left side: Decreasing Rearrangement of Ridgelet Analysis Plane, Right side:
m-term aproximation errors
the image de-noising application described there, this factor does not seem to be
very important.
Yoel Shkolnisky has pointed out another possible variation on our approach,
discussed in [2] and forthcoming work. In extending the image we zero pad out to
length m = 2n-j- I rather than 2n, obtaining a corresponding expression for Dm
which is purely real, namely
m sin[7rt/m)
This fixes a slightly inelegant property of the choice m = 2n, namely that the
ridgelets with the highest radial index j are not purely real - they have a small
imaginary component, owing to the small imaginary component of the kernel D2n-
With m = 2n 4-1 this component goes away.
1.8 DISCUSSION
We have described a notion of ridgelet transform which is able to synthesize or
analyze using true ridge functions and which has various exact reconstruction
DISCUSSION 27
(a) (b)
Figure 1.30. Reconstructions from 16, 50 and 100 OR coefficients: (a) Band Passed Half
Dome, (b) Reconstructed by 16 coefficients, (c) reconstructed by 50 coefficients, (d) recon-
structed by 100 coefficients.
and frame properties. It also obeys a series of relationships with a notion of digital
Radon transform and a notion of digital polar Fourier transform which are precisely
analogous to corresponding relationships that exist in the frequency domain. At
its heart, the method is based on the use of pseudopolar F FT and Fast Slant Stack
described in [2] .
The principal disappointment of the existing implementation is the relatively
slow decay of the ortho-ridgelet coefficients of a ortho-ridgelet. Figure 19 shows
that, after an initially steep decline in coefficients, a kind of flat ’background’
sets in. The slow decay is reminiscent of the behavior one would see from Gibbs
phenomena in fourier analysis of discontinuities, or from critical sampling in Gabor
analysis. It is not hard to see why this behavior obtains, and to see that it is
intrinsically tied to our central assumption - the use of ridge functions in a digital
setting. Figure 1.31 illustrates the ridgelet analysis process; Figure 1.32 illustrates
its adjoint, the ridgelet synthesis process. The ridgelet analysis process works as
follows: an image is extended to twice its length, then sheared, then projected,
then wavelet analyzed. The ridgelet synthesis process works ’in reverse’: a delta
sequence in the wavelet coefficient domain is inverted into a wavelet, which is
then backprojected into a ridge function, which is then sheared into a tilted ridge
function, which is then mutilated.
This last step - mutilation - is the adjoint of extension by zero-padding, mean›
ing that digital ridgelets, when viewed as an array, amount to a series of columns
containing 1-d wavelets which have been brutally truncated from an n x 2n array
to fit in an n X n array. If the wavelets were not mutilated, their inner products
would decay rapidly with separation in index space; but the mutilation spoils the
Figure 1.31. Stages of Radon analysis: padding, shearing, projection
Figure 1.32. Stages of Radon synthesis (right to left): backprojection, shearing, mutilation
decay property. From this point of view, it is rather obvious what to try next. One
should develop analysis and synthesis transforms not based on ridge functions, but
instead based on windowed ridge functions. We have not explored this proposal
in detail here simply because although a straightforward and obvious extension, it
violates the initial assumption marking the origin of this project: the use of true
ridge functions.
ACKNOWLEDGEMENT
This work has been partially supported by AFOSR MURI 95-P49620-96-1-O028,
by National Science Foundation grant DMS 98-72890 (KDI), and by DARPA
ACMP BAA 98-04. The authors would like to thank Amir Averbuch, Emmanuel
Candes, Raphy Coifman, Jean-Luc Starck, Yoel Shkolnisky, and Martin Vetterli
for helpful comments, preprints, and references. AGF would like to thank the
Statistics Department at UC Berkeley for its hospitality.
REFERENCES 29
REFERENCES
[1] P. Auscher, G. Weiss and M.V. Wickerhauser, Local sine and cosine bases of
Coifman and Meyer and the construction of smooth wavelets. Wavelets: A
tutorial in Theory and Applications Academic Press: Boston, 237-256.
[2] A. Averbuch, R.R. Coifman, D.L. Donoho, M. Israeli and J. Walden Fast Slant
Stack: A notion of Radon Transform for Data in a Cartesian Grid which is
Rapidly Computible, Algebraically Exact, Geometrically Faithful and Invert-
ible, to Appear: SIAM J.Sci. Comp.
[3] E. Candes Ridgelets: Theory and Applications. Ph.D. Thesis, Department of
Statistics, Stanford University, 1998.
[4] E.J. Candes, and D. L. Donoho Ridgelets: The key to High-Dimensional Inter-
mittency? in Phil. Trans. R. Soc. Lond. A. 3 5 7 1999, 2495-2509.
[5] E. Candes and D. Donoho Curvelets and Curvilinear integrals (1999) Tech›
nical Report, Department of Statistics, Stanford University. http://www-
stat. Stanford, edu/’ donoho/Reports/2000/Curves- Curvelets.ps.
[6] E. Candes and D.L. Donoho. Curvelets: a surprisingly effective nonadaptive
representation of objects with edges. Curve and Surface Fitting: Saint-Malo
1999 Albert Cohen, Christophe Rabut, and Larry L. Schumaker (eds.) Van-
derbilt University Press, Nashville, TN. ISBN 0-8265-1357-3.
[7] S. R. Deans The Radon transform and some of its applications. New York:
Wiley & Sons.
[8] M. Do and M. Vetterli. Orthonormal finite Ridgelet transform for image com›
pression. To appear Proc. of IEEE International Conference on Image Pro›
cessing, ICIP-2000.
[9] D. L. Donoho. Fast Ridgelet Transform in Dimension 2. Available: http://www-
stat. Stanford. edu/^donoho/Reports/1997/FRT.pdf 1997.
[10] D.L.Donoho, Fast Ridgelet Transform via Digital Polar Coordinate Transform.
Available: http://www-st at. Stanford, edu/’donoho/Reports/ 1998/FRTvD-
PCT.pdf 1998.
[11] D.L. Donoho. Tight Frames of /c-Plane Ridgelets and the Problem of Repre›
senting c?-dimensional singularities in R"^. Proc. Nat. Acad. Sci. USA, 96
1998, 1828-1833.
[12] D.L. Donoho. Orthonormal Ridgelets and Linear Singularities. SIAM J. Math
Anal. 3 1 no 5 2000, 1062-1099.
[13] D.L. Donoho Ridge Functions and Orthonormal Ridgelets. Journ. Approx.
Thry. I l l 2001, 143-179.
[14] P. Edholm and G.T. Herman.Linogram s in image reconstruction from projec›
tions. IEEE Trans. Medical Imaging, M I - 6 ( 4) 1987, 301-307.
[15] P. Edholm, G.T. Herman, and D.A. Roberts. Image reconstruction from lino-
grams: Implementation and evaluation. IEEE Trans. Medical Imaging, M I-
7(3)1988, 239-246.
[16] I.M. Gel’fand and G.E. Shilov Generalized Functions: Properties and Opera›
tions. Academic Press, 1964.
[17] S. Helgason, Groups and Geometric analysis: integral geometry, invariant dif›
ferential operators, and spherical functions. Series title: Pure and applied
30 REFERENCES
mathematics. Orlando: Academic Press,1984.

[18] E. Kolaczyk Wavelet-Vaguelette Decomposition of certain Homogeneous Linear
Inverse problems. Ph.D. Thesis, Department of Statistics, Stanford Univer›
sity, 1994.
[19] P. G. Lemarie Y. and Meyer. Ondelettes et bases Hilbertiennes, Revista Matem-
atica Iberoamericana 2 1986, 1-18.
[20] B.F. Logan L.A. and Shepp Optimal reconstruction of a function from its
projections. Duke Math. J. 42 1975, no. 4,645-659 .
[21] F. Matus and J. Flusser. Image representations via a Finite Radon Transform.
IEEE Trans. Pattern Ana. Machine Intell. 15 1993, 996-1006.
[22] J.L. Starck, E. Candes and D.L. Donoho The Curvelet Transform for Image
Denoising, to appear IEEE Transactions on Image Processing.
[23] Oz Yilmaz, Seismic Data Processing (SEG Investigations in Geophysics N 2.)
2000.
Exploring the Variety of Random
Documents with Different Content
Guardian.
The Secret of the Australian Desert. By Ernest Favenc.
“We recommend the book most heartily; it is certain to
please boys and girls, and even some grown-ups.”—
Guardian.
My Friend Kathleen. By Jennie Chappell.
A Girl’s Kingdom. By M. Corbet-Seymour.
“The story is bright, well told, and thoroughly healthy and
good.”—Ch. Bells.
Laugh and Learn: The Easiest Book of Nursery Lessons and
Nursery Games. By Jennett Humphreys.
“One of the best books of the kind imaginable, full of
practical teaching in word and picture, and helping the
little ones pleasantly along a right royal road to
learning.”—Graphic.
Reefer and Rifleman: A Tale of the Two Services. By Lieut.-Col.
Percy-Groves.
A Musical Genius. By the Author of the “Two Dorothys”.
“It is brightly written, well illustrated, and daintily bound,
and can be strongly recommended as a really good prize-
book.”—Teachers’ Aid.
For the Sake of a Friend: A Story of School Life. By Margaret
Parker.
“An excellent school-girls’ story.”—Athenæum.
Things Will take a Turn. By Beatrice Harraden. With 44 Illustrations
by John H. Bacon.
“Perhaps the most brilliant is Things Will Take a Turn.... It
is a delightful blending of comedy and tragedy, with an
excellent plot.”—The Times.
From “Things will Take a Turn”. (Reduced.)
Under the Black Eagle. By Andrew Hilliard.

“The rapid movement of the story, and the strange scenes
through which it passes, give it a full interest of surprise
and adventure.”—Scotsman.
A Golden Age. By Ismay Thorn. Illustrated by Gordon Browne.
“Ought to have a place of honour on the nursery shelf.”—
The Athenæum.
Hal Hungerford. By J. R. Hutchinson, b.a.
“Altogether, Hal Hungerford is a distinct literary success.”—
Spectator.
The Secret of the Old House. By E. Everett-Green.
“Tim, the little Jacobite, is a charming creation.”—
Academy.
White Lilac: or, The Queen of the May. By Amy Walton.
“Every rural parish ought to add White Lilac to its
library.”—Academy.
The Whispering Winds, and the Tales that they Told. By Mary H.
Debenham. With 25 Illustrations by Paul Hardy.
Miriam’s Ambition. By Evelyn Everett-Green.
“Miss Green’s children are real British boys and girls.”—
Liverpool Mercury.
The Brig “Audacious”. By Alan Cole.
“Fresh and wholesome as a breath of sea air.”—Court
Journal.
Jasper’s Conquest. By Elizabeth J. Lysaght.
“One of the best boys’ books of the season.”—
Schoolmaster.
Little Lady Clare. By Evelyn Everett-Green.
“Reminds us in its quaintness of Mrs. Ewing’s delightful
tales.”—Liter. World.
The Eversley Secrets. By Evelyn Everett-Green.
“Roy Eversley is a very touching picture of high
principle.”—Guardian.
The Hermit Hunter of the Wilds. By G. Stables, r.n.
“Will gladden the heart of many a bright boy.”—Methodist
Recorder.
Sturdy and Strong. By G. A. Henty.
“A hero who stands as a good instance of chivalry in
domestic life.”—The Empire.
Gutta-Percha Willie. By George Mac Donald.
“Get it for your boys and girls to read for themselves.”—
Practical Teacher.
The War of the Axe: or, Adventures in South Africa. By J. Percy-
Groves.
“The story is well and brilliantly told.”—Literary World.
The Lads of Little Clayton. By R. Stead.
“A capital book for boys.”—Schoolmaster.
Ten Boys. By Jane Andrews. With 20 Illustrations.
“The idea is a very happy one, and admirably carried
out.”—Practical Teacher.
A Waif of the Sea: or, The Lost Found. By Kate Wood.
“Written with tenderness and grace.”—Morning Advertiser.
Winnie’s Secret. By Kate Wood.
“One of the best story-books we have read.”—
Schoolmaster.
Miss Willowburn’s Offer. By Sarah Doudney.
“Patience Willowburn is one of Miss Doudney’s best
creations.”—Spectator.
A Garland for Girls. By Louisa M. Alcott.
“These little tales are the beau ideal of girls’ stories.”—
Christian World.
Hetty Gray: or, Nobody’s Bairn. By Rosa Mulholland.
“Hetty is a delightful creature—piquant, tender, and
true.”—World.
Brothers in Arms. By F. Bayford Harrison.
“Sure to prove interesting to young people of both
sexes.”—Guardian.
Stimson’s Reef: A Tale of Adventure. By C. J. Hyne.
Miss Fenwick’s Failures. By Esmé Stuart.
“A girl true to real life, who will put no nonsense into
young heads.”—Graphic.
Gytha’s Message. By Emma Leslie.
“This is the sort of book that all girls like.”—Journal of
Education.
A Little Handful. By Harriet J. Scripps.
“He is a real type of a boy.”—The Schoolmaster.
Hammond’s Hard Lines. By Skelton Kuppord.
“It is just what a boy would choose if the selection of a
story-book is left in his own hand.”—School Guardian.
Dulcie King: A Story for Girls. By M. Corbet-Seymour.
Nicola: The Career of a Girl Musician. By M. Corbet-Seymour.
Hugh Herbert’s Inheritance. By Caroline Austin.
Jack o’ Lanthorn: A Tale of Adventure. By Henry Frith.
A Rough Road: or, How the Boy Made a Man of Himself. By Mrs. G.
Linnæus Banks.
The Two Dorothys. By Mrs. Herbert Martin.
“A book that will interest and please all girls.”—The Lady.
Reduced Illustration from, “A Girl in Spring-time”.
My Mistress the Queen. By M. A. Paull.

The Stories of Wasa and Menzikoff.
Stories of the Sea in Former Days.
Tales of Captivity and Exile.
Famous Discoveries by Sea and Land.
Stirring Events of History.
Adventures in Field, Flood, and Forest.
A Cruise in Cloudland. By Henry Frith.
Marian and Dorothy. By Annie E. Armstrong.
Gladys Anstruther. By Louisa Thompson.
BLACKIE’S TWO-SHILLING SERIES.
Illustrated by eminent Artists. Crown 8vo, cloth elegant.

Tommy the Adventurous. By S. E. Cartwright.
Some Other Children. By H. F. Gethen.
That Merry Crew. By Florence Coombe.
Sir Wilfrid’s Grandson. By Geraldine Mockler.
Sydney’s Chums: A Story of East and West London. By H. F.
Gethen.
Daddy Samuels’ Darling. By the Author of “The Two Dorothys”.
May, Guy, and Jim. By Ellinor Davenport Adams.
A Girl in Spring-time. By Mrs. Mansergh.
In the Days of Drake. Being the Adventures of Humphrey Salkeld.
By J. S. Fletcher.
Wilful Joyce. By W. L. Rooper.
Proud Miss Sydney. By Geraldine Mockler.
Queen of the Daffodils. By Leslie Laing.
The Girleen. By Edith Johnstone.
The Organist’s Baby. By Kathleen Knox.
School Days in France. By An Old Girl.
The Ravensworth Scholarship. By Mrs. Henry Clarke.
Sir Walter’s Ward: A Tale of the Crusades. By William Everard.
Raff’s Ranche: A Story of Adventure among Cow-boys and Indians.
By F. M. Holmes.
The Joyous Story of Toto. By Laura E. Richards.
Our Dolly: Her Words and Ways. By Mrs. R. H. Read.
Fairy Fancy: What she Heard and Saw. By Mrs. Read.
New Light through Old Windows. By Gregson Gow.
Little Tottie, and Two Other Stories. By Thomas Archer.
Naughty Miss Bunny. By Clara Mulholland.
Adventures of Mrs. Wishing-to-be. By Alice Corkran.
An Unexpected Hero. By Eliz. J. Lysaght.
The Bushranger’s Secret. By Mrs. Henry Clarke, m.a.
The White Squall. By John C. Hutcheson.
The Wreck of the “Nancy Bell”. By J. C. Hutcheson.
The Lonely Pyramid. By J. H. Yoxall.
Bab: or, The Triumph of Unselfishness. By Ismay Thorn.
Brave and True, and other Stories. By Gregson Gow.
The Light Princess. By George Mac Donald.
Nutbrown Roger and I. By J. H. Yoxall.
Sam Silvan’s Sacrifice. By Jesse Colman.
Insect Ways on Summer Days in Garden, Forest, Field, and
Stream. By Jennett Humphreys. With 70 Illustrations.
Susan. By Amy Walton.
A Pair of Clogs. By Amy Walton.
The Hawthorns. By Amy Walton.
Dorothy’s Dilemma. By Caroline Austin.
Marie’s Home. By Caroline Austin.
A Warrior King. By J. Evelyn.
Aboard the “Atalanta”. By Henry Frith.
The Penang Pirate. By John C. Hutcheson.
Teddy: The Story of a “Little Pickle”. By John C. Hutcheson.
A Rash Promise. By Cecilia Selby Lowndes.
Linda and the Boys. By Cecilia Selby Lowndes.
Swiss Stories for Children. From the German of Madam Johanna
Spyri. By Lucy Wheelock.
The Squire’s Grandson. By J. M. Callwell.
Magna Charta Stories. Edited by Arthur Gilman, a.m.
The Wings of Courage; and The Cloud-Spinner. Translated from the
French of George Sand, by Mrs. Corkran.
Chirp and Chatter: Or, Lessons from Field and Tree. By Alice Banks.
With 54 Illustrations by Gordon Browne.
Four Little Mischiefs. By Rosa Mulholland.
LIBRARY OF FAMOUS BOOKS FOR BOYS AND
GIRLS.
Illustrated. Crown 8vo, cloth extra, 1s. 6d. each.
The Rifle Rangers. By Captain Mayne Reid.

Macaulay’s Essays on English History.
Autobiographies of Boyhood.
Holiday House. By Catherine Sinclair.
Log-book of a Midshipman.
Parry’s Third Voyage.
Passages in the Life of a Galley-Slave.
The Downfall of Napoleon. By Sir Walter Scott.
What Katy Did. By Susan Coolidge.
What Katy Did at School.
Wreck of the “Wager”.
Miss Austen’s Northanger Abbey.
Miss Edgeworth’s The Good Governess.
Martineau’s Feats on the Fiord.
Marryat’s Poor Jack.
The Snowstorm. By Mrs. Gore.
Life of Dampier.
The Cruise of the Midge. M. Scott.
Lives and Voyages of Drake and Cavendish.
Edgeworth’s Moral Tales.
Marryat’s The Settlers in Canada.
Michael Scott’s Tom Cringle’s Log.
Natural History of Selborne.
Waterton’s Wanderings in S. America.
Anson’s Voyage Round the World.
Autobiography of Franklin.
Lamb’s Tales from Shakspeare.
Southey’s Life of Nelson.
Miss Mitford’s Our Village.
Two Years Before the Mast.
Children of the New Forest.
Scott’s The Talisman.
The Basket of Flowers.
Marryat’s Masterman Ready.
Alcott’s Little Women.
Cooper’s Deerslayer.
The Lamplighter. By Miss Cummins.
Cooper’s Pathfinder.
The Vicar of Wakefield.
Plutarch’s Lives of Greek Heroes.
Poe’s Tales of Romance and Fantasy.
BLACKIE’S EIGHTEENPENNY SERIES.
Illustrated. Crown 8vo, cloth elegant.
Holidays at Sandy Bay. By E. S. Buchheim.

Best of Intentions. By Geraldine Mockler.
An Africander Trio. By Jane H. Spettigue.
A Chum Worth Having. By Florence Coombe.
Penelope and the Others. By Amy Walton.
The “Saucy May”. By Henry Frith.
The Little Girl from Next Door. By Geraldine Mockler.
Uncle Jem’s Stella. By Mrs. Martin.
The Ball of Fortune. By C. Pearse.
The Family Failing. By D. Dale.
Warner’s Chase. By Annie S. Swan.
Climbing the Hill. By Annie S. Swan.
Into the Haven. By Annie S. Swan.
Down and Up Again. By Gregson Gow.
Madge’s Mistake. By Annie E. Armstrong.
The Troubles and Triumphs of Little Tim. By Gregson Gow.
The Happy Lad. By B. Björnson.
A Box of Stories. By H. Happyman.
The Patriot Martyr, and other Narratives of Female Heroism.
Olive and Robin. By Mrs. Martin.
Mona’s Trust. By P. Leslie.
With Illustrations. In crown 8vo, cloth elegant.

Reduced Illustration From “A Chum Worth Having”.
Little Jimmy: A Story of Adventure. By Rev. D. Rice-Jones, m.a.

Pleasures and Pranks. By Isabella Pearson.
In a Stranger’s Garden. By Constance Cuming.
Yarns on the Beach. By G. A. Henty.
A Soldier’s Son. By Annette Lyster.
Mischief and Merry-making. By Isabella Pearson.
Tom Finch’s Monkey. By J. C. Hutcheson.
Miss Grantley’s Girls. By Thos. Archer.
The Pedlar and his Dog. By Mary C. Rowsell.
Littlebourne Lock. By F. Bayford Harrison.
Wild Meg and Wee Dickie. By Mary E. Ropes.
Grannie. By Elizabeth J. Lysaght.
The Seed She Sowed. By Emma Leslie.
Unlucky: A Fragment of a Girl’s Life. By Caroline Austin.
Everybody’s Business. By Ismay Thorn.
Tales of Daring and Danger. By G. A. Henty.
The Seven Golden Keys. By James E. Arnold.
The Story of a Queen. By Mary C. Rowsell.
Edwy: or, Was he a Coward? By Annette Lyster.
The Battlefield Treasure. By F. Bayford Harrison.
Joan’s Adventures at the North Pole. By Alice Corkran.
Filled with Gold. By J. Perrett.
Our General. By Elizabeth J. Lysaght.
Aunt Hesba’s Charge. By Elizabeth J. Lysaght.
By Order of Queen Maude. By Louisa Crow.
The Late Miss Hollingford. By Rosa Mulholland.
Our Frank. By Amy Walton.
A Terrible Coward. By G. Manville Fenn.
Town Mice in the Country. By M. E. Francis.
Phil and his Father. By Ismay Thorn.
Prim’s Story. By L. E. Tiddeman.
⁂ Also a large selection of Rewards at 1s., 9d., 6d., 3d., 2d., and 1d.
A complete list will be sent post free on application.
BLACKIE’S
SCHOOL AND HOME LIBRARY.
Under the above title the publishers have arranged to issue, for
School Libraries and the Home Circle, a selection of the best and
most interesting books in the English language. The Library includes
lives of heroes, ancient and modern, records of travel and adventure
by sea and land, fiction of the highest class, historical romances,
books of natural history, and tales of domestic life.
The greatest care has been devoted to the get-up of the Library. The
volumes are clearly printed on good paper, and the binding made
specially durable, to withstand the wear and tear to which well-
circulated books are necessarily subjected.
In crown 8vo volumes. Strongly bound in cloth. Price 1s. 4d.
each.
Dana’s Two Years before the Mast.

Southey’s Life of Nelson.
Waterton’s Wanderings in S. America.
Anson’s Voyage Round the World.
Lamb’s Tales from Shakspeare.
Autobiography of Benjamin Franklin.
Marryat’s Children of the New Forest.
Miss Mitford’s Our Village.
Scott’s Talisman.
The Basket of Flowers.
Marryat’s Masterman Ready.
Alcott’s Little Women.
Cooper’s Deerslayer.
Parry’s Third Voyage.
Dickens’ Old Curiosity Shop. 2 vols.
Plutarch’s Lives of Greek Heroes.
The Lamplighter.
Cooper’s Pathfinder.
The Vicar of Wakefield.
White’s Natural History of Selborne.
Scott’s Ivanhoe. 2 vols.
Michael Scott’s Tom Cringle’s Log.
Irving’s Conquest of Granada. 2 vols.
Lives of Drake and Cavendish.
Michael Scott’s Cruise of the Midge.
Edgeworth’s Moral Tales.
Passages in the Life of a Galley-Slave.
The Snowstorm. By Mrs. Gore.
Life of Dampier.
Marryat’s The Settlers in Canada.
Martineau’s Feats on the Fiord.
Marryat’s Poor Jack.
The Good Governess. By Maria Edgeworth.
Northanger Abbey. By Jane Austen.
The Log Book of a Midshipman.
Autobiographies of Boyhood.
Holiday House. By Catherine Sinclair.
Wreck of the “Wager”.
What Katy Did. By Miss Coolidge.
What Katy Did at School. By Do.
Scott’s Life of Napoleon.
Essays on English History. By Lord Macaulay.
The Rifle Rangers. By Captain Mayne Reid.
Detailed Prospectus and Press Opinions will be sent post free on

Application.
“The Library is one of the most intelligent enterprises in connection

with juvenile literature of recent years.... A glance at the list proves
that the editing is in the hands of some one who understands the
likings of healthy boys and girls.... One of the healthiest juvenile
libraries in existence.”—Bookman.
LONDON:
BLACKIE & SON, Limited, 50 OLD BAILEY, E.C.
Transcriber's Notes
A number of typographical errors were corrected silently.
Cover image is in the public domain.
Caption for illustration "The figure moved, rose, came forward with the painful caution of
dreary suspense" was incorrect in original image and was changed to match the text.
*** END OF THE PROJECT GUTENBERG EBOOK A GIRL OF TO-DAY
***
Updated editions will replace the previous one—the old editions

will be renamed.
Creating the works from print editions not protected by U.S.

copyright law means that no one owns a United States
copyright in these works, so the Foundation (and you!) can copy
and distribute it in the United States without permission and
without paying copyright royalties. Special rules, set forth in the
General Terms of Use part of this license, apply to copying and
distributing Project Gutenberg™ electronic works to protect the
PROJECT GUTENBERG™ concept and trademark. Project
Gutenberg is a registered trademark, and may not be used if
you charge for an eBook, except by following the terms of the
trademark license, including paying royalties for use of the
Project Gutenberg trademark. If you do not charge anything for
copies of this eBook, complying with the trademark license is
very easy. You may use this eBook for nearly any purpose such
as creation of derivative works, reports, performances and
research. Project Gutenberg eBooks may be modified and
printed and given away—you may do practically ANYTHING in
the United States with eBooks not protected by U.S. copyright
law. Redistribution is subject to the trademark license, especially
commercial redistribution.
START: FULL LICENSE

THE FULL PROJECT GUTENBERG LICENSE
PLEASE READ THIS BEFORE YOU DISTRIBUTE OR USE THIS WORK
To protect the Project Gutenberg™ mission of promoting the

free distribution of electronic works, by using or distributing this
work (or any other work associated in any way with the phrase
“Project Gutenberg”), you agree to comply with all the terms of
the Full Project Gutenberg™ License available with this file or
online at www.gutenberg.org/license.
Section 1. General Terms of Use and

Redistributing Project Gutenberg™
electronic works
1.A. By reading or using any part of this Project Gutenberg™
electronic work, you indicate that you have read, understand,
agree to and accept all the terms of this license and intellectual
property (trademark/copyright) agreement. If you do not agree
to abide by all the terms of this agreement, you must cease
using and return or destroy all copies of Project Gutenberg™
electronic works in your possession. If you paid a fee for
obtaining a copy of or access to a Project Gutenberg™
electronic work and you do not agree to be bound by the terms
of this agreement, you may obtain a refund from the person or
entity to whom you paid the fee as set forth in paragraph 1.E.8.
1.B. “Project Gutenberg” is a registered trademark. It may only

be used on or associated in any way with an electronic work by
people who agree to be bound by the terms of this agreement.
There are a few things that you can do with most Project
Gutenberg™ electronic works even without complying with the
full terms of this agreement. See paragraph 1.C below. There
are a lot of things you can do with Project Gutenberg™
electronic works if you follow the terms of this agreement and
help preserve free future access to Project Gutenberg™
electronic works. See paragraph 1.E below.
1.C. The Project Gutenberg Literary Archive Foundation (“the
Foundation” or PGLAF), owns a compilation copyright in the
collection of Project Gutenberg™ electronic works. Nearly all the
individual works in the collection are in the public domain in the
United States. If an individual work is unprotected by copyright
law in the United States and you are located in the United
States, we do not claim a right to prevent you from copying,
distributing, performing, displaying or creating derivative works
based on the work as long as all references to Project
Gutenberg are removed. Of course, we hope that you will
support the Project Gutenberg™ mission of promoting free
access to electronic works by freely sharing Project Gutenberg™
works in compliance with the terms of this agreement for
keeping the Project Gutenberg™ name associated with the
work. You can easily comply with the terms of this agreement
by keeping this work in the same format with its attached full
Project Gutenberg™ License when you share it without charge
with others.
1.D. The copyright laws of the place where you are located also
govern what you can do with this work. Copyright laws in most
countries are in a constant state of change. If you are outside
the United States, check the laws of your country in addition to
the terms of this agreement before downloading, copying,
displaying, performing, distributing or creating derivative works
based on this work or any other Project Gutenberg™ work. The
Foundation makes no representations concerning the copyright
status of any work in any country other than the United States.
1.E. Unless you have removed all references to Project

Gutenberg:
1.E.1. The following sentence, with active links to, or other

immediate access to, the full Project Gutenberg™ License must
appear prominently whenever any copy of a Project
Gutenberg™ work (any work on which the phrase “Project
Gutenberg” appears, or with which the phrase “Project
Gutenberg” is associated) is accessed, displayed, performed,
viewed, copied or distributed:
This eBook is for the use of anyone anywhere in the United

States and most other parts of the world at no cost and
with almost no restrictions whatsoever. You may copy it,
give it away or re-use it under the terms of the Project
Gutenberg License included with this eBook or online at
www.gutenberg.org. If you are not located in the United
States, you will have to check the laws of the country
where you are located before using this eBook.
1.E.2. If an individual Project Gutenberg™ electronic work is

derived from texts not protected by U.S. copyright law (does not
contain a notice indicating that it is posted with permission of
the copyright holder), the work can be copied and distributed to
anyone in the United States without paying any fees or charges.
If you are redistributing or providing access to a work with the
phrase “Project Gutenberg” associated with or appearing on the
work, you must comply either with the requirements of
paragraphs 1.E.1 through 1.E.7 or obtain permission for the use
of the work and the Project Gutenberg™ trademark as set forth
in paragraphs 1.E.8 or 1.E.9.
1.E.3. If an individual Project Gutenberg™ electronic work is

posted with the permission of the copyright holder, your use and
distribution must comply with both paragraphs 1.E.1 through
1.E.7 and any additional terms imposed by the copyright holder.
Additional terms will be linked to the Project Gutenberg™
License for all works posted with the permission of the copyright
holder found at the beginning of this work.
1.E.4. Do not unlink or detach or remove the full Project

Gutenberg™ License terms from this work, or any files
containing a part of this work or any other work associated with
Project Gutenberg™.
1.E.5. Do not copy, display, perform, distribute or redistribute

this electronic work, or any part of this electronic work, without
prominently displaying the sentence set forth in paragraph 1.E.1
with active links or immediate access to the full terms of the
Project Gutenberg™ License.
1.E.6. You may convert to and distribute this work in any binary,
compressed, marked up, nonproprietary or proprietary form,
including any word processing or hypertext form. However, if
you provide access to or distribute copies of a Project
Gutenberg™ work in a format other than “Plain Vanilla ASCII” or
other format used in the official version posted on the official
Project Gutenberg™ website (www.gutenberg.org), you must,
at no additional cost, fee or expense to the user, provide a copy,
a means of exporting a copy, or a means of obtaining a copy
upon request, of the work in its original “Plain Vanilla ASCII” or
other form. Any alternate format must include the full Project
Gutenberg™ License as specified in paragraph 1.E.1.
1.E.7. Do not charge a fee for access to, viewing, displaying,

performing, copying or distributing any Project Gutenberg™
works unless you comply with paragraph 1.E.8 or 1.E.9.
1.E.8. You may charge a reasonable fee for copies of or

providing access to or distributing Project Gutenberg™
electronic works provided that:
• You pay a royalty fee of 20% of the gross profits you derive
from the use of Project Gutenberg™ works calculated using the
method you already use to calculate your applicable taxes. The
fee is owed to the owner of the Project Gutenberg™ trademark,
but he has agreed to donate royalties under this paragraph to
the Project Gutenberg Literary Archive Foundation. Royalty
payments must be paid within 60 days following each date on
which you prepare (or are legally required to prepare) your
periodic tax returns. Royalty payments should be clearly marked
as such and sent to the Project Gutenberg Literary Archive
Foundation at the address specified in Section 4, “Information
about donations to the Project Gutenberg Literary Archive
Foundation.”
• You provide a full refund of any money paid by a user who

notifies you in writing (or by e-mail) within 30 days of receipt
that s/he does not agree to the terms of the full Project
Gutenberg™ License. You must require such a user to return or
destroy all copies of the works possessed in a physical medium
and discontinue all use of and all access to other copies of
Project Gutenberg™ works.
• You provide, in accordance with paragraph 1.F.3, a full refund of

any money paid for a work or a replacement copy, if a defect in
the electronic work is discovered and reported to you within 90
days of receipt of the work.
• You comply with all other terms of this agreement for free
distribution of Project Gutenberg™ works.
1.E.9. If you wish to charge a fee or distribute a Project

Gutenberg™ electronic work or group of works on different
terms than are set forth in this agreement, you must obtain
permission in writing from the Project Gutenberg Literary
Archive Foundation, the manager of the Project Gutenberg™
trademark. Contact the Foundation as set forth in Section 3
below.
1.F.
1.F.1. Project Gutenberg volunteers and employees expend

considerable effort to identify, do copyright research on,
transcribe and proofread works not protected by U.S. copyright
law in creating the Project Gutenberg™ collection. Despite these
efforts, Project Gutenberg™ electronic works, and the medium
on which they may be stored, may contain “Defects,” such as,
but not limited to, incomplete, inaccurate or corrupt data,
transcription errors, a copyright or other intellectual property
infringement, a defective or damaged disk or other medium, a
computer virus, or computer codes that damage or cannot be
read by your equipment.
1.F.2. LIMITED WARRANTY, DISCLAIMER OF DAMAGES - Except

for the “Right of Replacement or Refund” described in
paragraph 1.F.3, the Project Gutenberg Literary Archive
Foundation, the owner of the Project Gutenberg™ trademark,
and any other party distributing a Project Gutenberg™ electronic
work under this agreement, disclaim all liability to you for
damages, costs and expenses, including legal fees. YOU AGREE
THAT YOU HAVE NO REMEDIES FOR NEGLIGENCE, STRICT
LIABILITY, BREACH OF WARRANTY OR BREACH OF CONTRACT
EXCEPT THOSE PROVIDED IN PARAGRAPH 1.F.3. YOU AGREE
THAT THE FOUNDATION, THE TRADEMARK OWNER, AND ANY
DISTRIBUTOR UNDER THIS AGREEMENT WILL NOT BE LIABLE
TO YOU FOR ACTUAL, DIRECT, INDIRECT, CONSEQUENTIAL,
PUNITIVE OR INCIDENTAL DAMAGES EVEN IF YOU GIVE
NOTICE OF THE POSSIBILITY OF SUCH DAMAGE.
1.F.3. LIMITED RIGHT OF REPLACEMENT OR REFUND - If you

discover a defect in this electronic work within 90 days of
receiving it, you can receive a refund of the money (if any) you
paid for it by sending a written explanation to the person you
received the work from. If you received the work on a physical
medium, you must return the medium with your written
explanation. The person or entity that provided you with the
defective work may elect to provide a replacement copy in lieu
of a refund. If you received the work electronically, the person
or entity providing it to you may choose to give you a second
opportunity to receive the work electronically in lieu of a refund.
If the second copy is also defective, you may demand a refund
in writing without further opportunities to fix the problem.
1.F.4. Except for the limited right of replacement or refund set

forth in paragraph 1.F.3, this work is provided to you ‘AS-IS’,
WITH NO OTHER WARRANTIES OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR ANY PURPOSE.
1.F.5. Some states do not allow disclaimers of certain implied

warranties or the exclusion or limitation of certain types of
damages. If any disclaimer or limitation set forth in this
agreement violates the law of the state applicable to this
agreement, the agreement shall be interpreted to make the
maximum disclaimer or limitation permitted by the applicable
state law. The invalidity or unenforceability of any provision of
this agreement shall not void the remaining provisions.
1.F.6. INDEMNITY - You agree to indemnify and hold the

Foundation, the trademark owner, any agent or employee of the
Foundation, anyone providing copies of Project Gutenberg™
electronic works in accordance with this agreement, and any
volunteers associated with the production, promotion and
distribution of Project Gutenberg™ electronic works, harmless
from all liability, costs and expenses, including legal fees, that
arise directly or indirectly from any of the following which you
do or cause to occur: (a) distribution of this or any Project
Gutenberg™ work, (b) alteration, modification, or additions or
deletions to any Project Gutenberg™ work, and (c) any Defect
you cause.
Section 2. Information about the Mission

of Project Gutenberg™
Project Gutenberg™ is synonymous with the free distribution of
electronic works in formats readable by the widest variety of
computers including obsolete, old, middle-aged and new
computers. It exists because of the efforts of hundreds of
volunteers and donations from people in all walks of life.
Volunteers and financial support to provide volunteers with the

assistance they need are critical to reaching Project
Gutenberg™’s goals and ensuring that the Project Gutenberg™
collection will remain freely available for generations to come. In
2001, the Project Gutenberg Literary Archive Foundation was
created to provide a secure and permanent future for Project
Gutenberg™ and future generations. To learn more about the
Project Gutenberg Literary Archive Foundation and how your
efforts and donations can help, see Sections 3 and 4 and the
Foundation information page at www.gutenberg.org.
Section 3. Information about the Project

Gutenberg Literary Archive Foundation
The Project Gutenberg Literary Archive Foundation is a non-
profit 501(c)(3) educational corporation organized under the
laws of the state of Mississippi and granted tax exempt status
by the Internal Revenue Service. The Foundation’s EIN or
federal tax identification number is 64-6221541. Contributions
to the Project Gutenberg Literary Archive Foundation are tax
deductible to the full extent permitted by U.S. federal laws and
your state’s laws.
The Foundation’s business office is located at 809 North 1500

West, Salt Lake City, UT 84116, (801) 596-1887. Email contact
links and up to date contact information can be found at the
Foundation’s website and official page at
www.gutenberg.org/contact

30343

Uploaded by

Copyright:

Available Formats

30343

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

30343

Uploaded by

Copyright:

Available Formats

Download the full version of the ebook at

Beyond Wavelets 1st Edition Grant Welland

Explore and download more ebook at https://ebookultra.com

Wavelets and Multiwavelets 1st Edition Fritz Keinert

A Friendly Guide to Wavelets 1st Edition Gerald Kaiser

Discrete Fourier analysis and wavelets 2ed. Edition

Square³ Mira Grant

Parry and Grant Encyclopaedic Dictionary of International

Fundamentals of wavelets Theory algorithms and

Mapping the Posthuman 1st Edition Grant Hamilton

World War II Reg Grant

' 2003 Elsevier Science Inc. Allrightsreserved.

Electroni c Storage or Usage

First edition 2003

Librar y of Congres s Cataloging in Publication Data

British Librar y Cataloguin g in Publication Data

Typeset by Alden Press, Oxford

Chapter 2 is a companion chapter to Chapter 1 and continues the study of digi›

graphic reconstruction is interpreted as the total kinetic energy of the collection

D.L. Donoho and A.G. Flesia 1

A.G. Flesia, H. Hel-Or,

2.3 Radon Preliminaries 39

Francoi s G. Meyer an d Ronal d R. Coifma n 61

Tony F. Chan and Hao-Min Zhou 107

Shiying Zhao and Haiyan Cai 135

6.2 Materials and Methods 140

Charle s Chu i and Joachim Stockier 151

Philip Gressman , Demetri o Labate, Guid e Weiss and Edwar d

Bertran d Benicho u and Naoki Saito 225

Sony Akkarakara n and P.P. Vaidyanathan 259

10.3.2 FBs with unconstrained complex and real coefficient fil›

DIGITAL RIDGELET TRANSFORM

9{xuX2) = l(,,>o}e-^?-^’, X R2 . (1.1.1)

Figure 1.1. 'Half Dome'- a Mutilated Gaussian

convergence of appropriate AT-term superpositions of ridgelets or ortho-ridgelets

1.1.2 Discretization of Ridgelets

1.2 DIGITAL RIDGELETS

(Equivalently, we could define ’ipj^k = ^-^’^j,k, where denotes m-point circular

Definition 1.2.1 Let n be given. A digital ridgelet Pj,k,s/ is an n by n array built

Pj,k,sA’^^’^)= ’^jA’^ -^ tan(^l)t’). s=h

Figure 1.3. Lines in frequency space corresponding to pseudopolar angles

p3,k,s,t{u,v) = ’0j,fc(v + cotan(^l)u), 5 = 2,

Pj,k,s,t{u,v) = i)j^k{u+ tan(^|)i;), s = 1,

These definitions in fact guarantee that the resulting objects pj^k^s^ti’^-,’^)and

Figure 1.4. Digital Ridgelets

Definition 1.2.2 The digital ridgelet analysis operator applied to an n x n image

We also call digital ridgelet analysis the corresponding normalized operator

In either case, we conventionally think of the DRT as a 2n by 2n array, as

Definition 1.2.3 The digital ridgelet synthesis operator takes a 2n by 2n coeffi›

We also call digital ridgelet synthesis the corresponding normalized operator

Theore m 1.2.5 The operators R, R, R* and R* can all be computed exactly in

The next ’result’ is really a distillation of computational experience.

Figure 1.8. Some (pseudo-) Ortho-Ridgelets

transformation of the space of 2n by 2n arrays, so it follows that all the injectivity

1.3 RELATION T O FAST SLANT STACK

Radon({y = ax-\- b}, /) = ^ /^ (u, au + b).

Dm{t) = cotan(7r^/m) sin(7ri)/m -f-1 sin(7rt)/m.

Radon({x = ay + 6}, /) = ^ P{av -\-b,v),

with the interpolant defined analogously:

It is convenient to also have 0 to represent the angle associated to the slope s.