We summarize the main results of a recent theory—developed by the authors—establishing fundamental lower bounds on the connectivity and memory requirements of deep neural networks as a function of the complexity of the function class to be approximated by the network. These bounds are shown to be achievable. Specifically, all function classes that are optimally approximated by a general class of representation systems—so-called affine systems—can be approximated by deep neural networks with minimal connectivity and memory requirements. Affine systems encompass a wealth of representation systems from applied harmonic analysis such as wavelets, shearlets, ridgelets, α-shearlets, and more generally α-molecules. This result elucidates a remarkable universality property of deep neural networks and shows that they achieve the optimum approximation properties of all affine systems combined. Finally, we present numerical experiments demonstrating that the standard stochastic gradient descent algorithm generates deep neural networks which provide close-to-optimal approximation rates at minimal connectivity. Moreover, stochastic gradient descent is found to actually learn approximations that are sparse in the representation system optimally sparsifying the function class the network is trained on.
The need of reconstructing discrete-valued sparse signals from few measurements, that is solving an undetermined system of linear equations, appears frequently in science and engineering. Those signals appear, for example, in error correcting codes as well as massive Multiple-Input Multiple-Output (MIMO) channel and wideband spectrum sensing. A particular example is given by wireless communications, where the transmitted signals are sequences of bits, i.e., with entries in f0; 1g. Whereas classical compressed sensing algorithms do not incorporate the additional knowledge of the discrete nature of the signal, classical lattice decoding approaches do not utilize sparsity constraints. In this talk, we present an approach that incorporates a discrete values prior into basis pursuit. In particular, we address finite-valued sparse signals, i.e., sparse signals with entries in a finite alphabet. We will introduce an equivalent null space characterization and show that phase transition takes place earlier than when using the classical basis pursuit approach. We will further discuss robustness of the algorithm and show that the nonnegative case is very different from the bipolar one. One of our findings is that the positioning of the zero in the alphabet - i.e., whether it is a boundary element or not - is crucial.
Measurements in real world applications are often corrupted by noise due to exterior influences. It is therefore convenient to investigate perturbations of the utilized measurement systems. In the present paper, we consider small perturbations of fusion frames in Hilbert spaces and study the effect on the canonical duals of original and perturbed fusion frame. It turns out that the duals are stable under these perturbations.
We study the exact recovery of signals from quantized frame coefficients. Here, the basis of the quantization is hard thresholding, and we present a simple algorithm for the recovery of reconstructable signals. The set of non-reconstructable signals is shown to be star-shaped and symmetric with respect to the origin. Moreover, we provide a criterion on the frame for the boundedness of this set. In this case, we also give a priori bounds.
KEYWORDS: Radon, Mathematics, Matrices, Condition numbers, Vector spaces, Signal processing, Linear algebra, Wavelets, Current controlled current source
The recently introduced and characterized scalable frames can be considered as those frames which allow for perfect preconditioning in the sense that the frame vectors can be rescaled to yield a tight frame. In this paper we define m−scalability, a refinement of scalability based on the number of non-zero weights used in the rescaling process. We enlighten a close connection between this notion and elements from convex geometry. Another focus lies in the topology of scalable frames. In particular, we prove that the set of scalable frames with “usual” redundancy is nowhere dense in the set of frames.
The novel framework of parabolic molecules provides for the first time a unifying framework for (sparse) approximation properties of directional representation systems by, in particular, including curvelets and shearlets.
However, the considered common bracket is parabolic scaling, which excludes systems such as ridgelets and wavelets. In this paper, we therefore provide a generalization of this framework, which we coin α-molecules, by introducing an additional parameter α, which specifies the extent of anisotropy in the scaling. We show that, for instance, both ridgelets and wavelets are in fact α-molecules. As an application of the concept, we then analyze the sparse approximation behavior of α-molecules. Utilizing the idea of sparsity equivalence, it is possible to identify large classes of α-molecules providing the same sparse approximation behavior.
An issue in data analysis is that of incomplete data, for example a photograph with scratches or seismic data collected with fewer than necessary sensors. There exists a unified approach to solving this problem and that of data separation: namely, minimizing the norm of the analysis (rather than synthesis) coefficients with respect to particular frame(s).There have been a number of successful applications of this method recently.
Analyzing this method using the concept of clustered sparsity leads to theoretical bounds and results, which will be presented. Furthermore, necessary conditions for the frames to lead to sufficiently good solutions will be shown, and this theoretical framework will be use to show that shearlets are able to inpaint larger gaps than wavelets. Finally, the results of numerical experiments comparing this approach to inpainting to numerous others will be presented.
Data often have two or more fundamental components, like cartoon-like and textured elements in
images; point, filament, and sheet clusters in astronomical data; and tonal and transient layers in
audio signals. For many applications, separating these components is of interest. Another issue in
data analysis is that of incomplete data, for example a photograph with scratches or seismic data
collected with fewer than necessary sensors. There exists a unified approach to solving these problems
which is minimizing the ℓ1 norm of the analysis coefficients with respect to particular frame(s). This
approach using the concept of clustered sparsity leads to similar theoretical bounds and results, which
are presented here. Furthermore, necessary conditions for the frames to lead to sufficiently good
solutions are also shown.
The fast digital shearlet transform (FDST) was recently introduced as a means to analyze natural images
efficiently, owing to the fact that those are typically governed by cartoon-like structures. In this paper, we
introduce and discuss a first-order hybrid sigma-delta quantization algorithm for coarsely quantizing the shearlet
coefficients generated by the FDST. Radial oversampling in the frequency domain together with our choice for
the quantization helps suppress the reconstruction error in a similar way as first-order sigma-delta quantization
for finite frames. We provide a theoretical bound for the reconstruction error and confirm numerically that the
error is in accordance with this theoretical decay.
A fusion frame is a frame-like collection of subspaces in a Hilbert space. It generalizes the concept of a frame
system for signal representation. In this paper, we study the existence and construction of fusion frames. We first
introduce two general methods, namely the spatial complement and the Naimark complement, for constructing a
new fusion frame from a given fusion frame. We then establish existence conditions for fusion frames with desired
properties. In particular, we address the following question: Given M, N, m ∈ N and {λj}Mj
=1, does there exist
a fusion frame in RM with N subspaces of dimension m for which {λj}Mj
=1 are the eigenvalues of the associated
fusion frame operator? We address this problem by providing an algorithm which computes such a fusion frame
for almost any collection of parameters M, N, m ∈ N and {λj}Mj
=1. Moreover, we show how this procedure can
be applied, if subspaces are to be added to a given fusion frame to force it to become tight.
KEYWORDS: Fourier transforms, Image processing, Digital image processing, Wavelets, Monte Carlo methods, Image compression, Mathematics, MATLAB, Precision measurement, Transform theory
Shearlab is a Matlab toolbox for digital shearlet transformation of two-D (image) data we developed following
a rational design process. The Pseudo-Polar FFT fits very naturally with the continuum theory of the Shearlet
transform and allows us to translate Shearlet ideas naturally into a digital framework. However, there are
still windows and weights which must be chosen. We developed more than a dozen performance measures
quantifying precision of the reconstruction, tightness of the frame, directional and spatial localization and other
properties. Such quantitative performance metrics allow us to: (a) tune parameters and objectively improve our
implementation; and (b) compare different directional transform implementations. We present and interpret the
most important performance measures for our current implementation.
In this paper we analyze the use of frames for the transmission and error-correction of analog signals via a
memoryless erasure-channel. We measure performance in terms of the mean-square error remaining after error
correction and reconstruction. Our results continue earlier works on frames as codes which were mostly concerned
with the smallest number of erased coefficients. To extend these works we borrow some ideas from binary coding
theory and realize them with a novel class of frames, which carry a particular fusion frame architecture. We show
that a family of frames from this class achieves a mean-square reconstruction error remaining after corrections
which decays faster than any inverse power in the number of frame coefficients.
Compressed Sensing (CS) is a new signal acquisition technique that allows sampling of sparse signals using
significantly fewer measurements than previously thought possible. On the other hand, a fusion frame is a new
signal representation method that uses collections of subspaces instead of vectors to represent signals. This work
combines these exciting new fields to introduce a new sparsity model for fusion frames. Signals that are sparse
under the new model can be compressively sampled and uniquely reconstructed in ways similar to sparse signals
using standard CS. The combination provides a promising new set of mathematical tools and signal models useful
in a variety of applications.
With the new model, a sparse signal has energy in very few of the subspaces of the fusion frame, although it
needs not be sparse within each of the subspaces it occupies. We define a mixed ℓ1/ℓ2 norm for fusion frames.
A signal sparse in the subspaces of the fusion frame can thus be sampled using very few random projections
and exactly reconstructed using a convex optimization that minimizes this mixed ℓ1/ℓ2 norm. The sampling
conditions we derive are very similar to the coherence and RIP conditions used in standard CS theory.
One key property of frames is their resilience against erasures due to the possibility of generating stable, yet
over-complete expansions. Blind reconstruction is one common methodology to reconstruct a signal when frame
coefficients have been erased. In this paper we introduce several novel low complexity replacement schemes which
can be applied to the set of faulty frame coefficients before blind reconstruction is performed, thus serving as a
preconditioning of the received set of frame coefficients. One main idea is that frame coefficients associated with
frame vectors close to the one erased should have approximately the same value as the lost one. It is shown that
injecting such low complexity replacement schemes into blind reconstruction significantly reduce the worst-case
reconstruction error. We then apply our results to the circle frames. If we allow linear combinations of different
neighboring coefficients for the reconstruction of missing coefficients, we can even obtain perfect reconstruction
for the circle frames under certain weak conditions on the set of erasures.
The new notion of fusion frames will be presented in this article. Fusion frames provide an extensive framework
not only to model sensor networks, but also to serve as a means to improve robustness or develop efficient and
feasible reconstruction algorithms. Fusion frames can be regarded as sets of redundant subspaces each of which
contains a spanning set of local frame vectors, where the subspaces have to satisfy special overlapping properties.
Main aspects of the theory of fusion frames will be presented with a particular focus on the design of sensor
networks. New results on the construction of Parseval fusion frames will also be discussed.
We analyze a fundamental question in Hilbert space frame theory: What is the optimal decomposition of a Parseval frame? We will see that this question impacts several famous unsolved problems in different areas of mathematics. As a step towards the solution of this question, we give a new identity which holds for all Parseval frames.
In this paper we describe a new class of multidimensional
representation systems, called shearlets. They are obtained by
applying the actions of dilation, shear transformation and
translation to a fixed function, and exhibit the geometric and
mathematical properties, e.g., directionality, elongated shapes,
scales, oscillations, recently advocated by many authors for
sparse image processing applications. These systems can be studied
within the framework of a generalized multiresolution analysis.
This approach leads to a recursive algorithm for the
implementation of these systems, that generalizes the classical
cascade algorithm.
The theory of localized frames is a recently introduced concept with
broad implications to frame theory in general, as well as to the
special cases of Gabor and wavelet frames. Using the new notion of a
R-dual sequence associated with a Bessel sequence, we derive
several duality principles concerning localization in abstract frame
theory. As applications of our results we prove a duality principle
of localization of Gabor systems in the spirit of the Ron-Shen
duality principle, and obtain a Janssen representation for general
frame operators.
In this paper we study a notion of density for subsets of R2 called accumulative density, which is similar to the density for sequences in the unit disc developed by Seip. Along the way we derive some new properties of Beurling density. Finally, we prove that the accumulative density and the Beurling density coincide.
Density conditions have turned out to be a powerful tool for deriving
necessary conditions for weighted wavelet systems to possess an upper or lower frame bound. In this paper we study different definitions
of density and compare them with respect to their appropriateness
and practicality.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.