BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Gitta Kutyniok

Gitta Kutyniok appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.FAmath.NAInformation Theorymath.ITMachine LearningNumerical AnalysisArtificial Intelligenceeess.IVeess.SPmath.APmath.OCComputer Visionmath.HOmath.PRmath.STMathematical SoftwareNetworking and Internet ArchitectureNeural and Evolutionary ComputingStatistics Theory

Catalog footprint

What is connected

50works
19topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

50 published item(s)

preprint2023arXiv

Computability of Optimizers

Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Analyzing Finite Neural Networks: Can We Trust Neural Tangent Kernel Theory?

Neural Tangent Kernel (NTK) theory is widely used to study the dynamics of infinitely-wide deep neural networks (DNNs) under gradient descent. But do the results for infinitely-wide networks give us hints about the behavior of real finite-width ones? In this paper, we study empirically when NTK theory is valid in practice for fully-connected ReLU and sigmoid DNNs. We find out that whether a network is in the NTK regime depends on the hyperparameters of random initialization and the network's depth. In particular, NTK theory does not explain the behavior of sufficiently deep networks initialized so that their gradients explode as they propagate through the network's layers: the kernel is random at initialization and changes significantly during training in this case, contrary to NTK theory. On the other hand, in the case of vanishing gradients, DNNs are in the the NTK regime but become untrainable rapidly with depth. We also describe a framework to study generalization properties of DNNs, in particular the variance of network's output function, by means of NTK theory and discuss its limits.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Generalization Analysis of Message Passing Neural Networks on Large Random Graphs

Message passing neural networks (MPNN) have seen a steep rise in popularity since their introduction as generalizations of convolutional neural networks to graph-structured data, and are now considered state-of-the-art tools for solving a large variety of graph-focused problems. We study the generalization error of MPNNs in graph classification and regression. We assume that graphs of different classes are sampled from different random graph models. We show that, when training a MPNN on a dataset sampled from such a distribution, the generalization gap increases in the complexity of the MPNN, and decreases, not only with respect to the number of training samples, but also with the average number of nodes in the graphs. This shows how a MPNN with high complexity can generalize from a small dataset of graphs, as long as the graphs are large. The generalization bound is derived from a uniform convergence result, that shows that any MPNN, applied on a graph, approximates the MPNN applied on the geometric model that the graph discretizes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

LocUNet: Fast Urban Positioning Using Radio Maps and Deep Learning

This paper deals with the problem of localization in a cellular network in a dense urban scenario. Global Navigation Satellite Systems (GNSS) typically perform poorly in urban environments, where the likelihood of line-of-sight conditions is low, and thus alternative localization methods are required for good accuracy. We present LocUNet: A deep learning method for localization, based merely on Received Signal Strength (RSS) from Base Stations (BSs), which does not require any increase in computation complexity at the user devices with respect to the device standard operations, unlike methods that rely on time of arrival or angle of arrival information. In the proposed method, the user to be localized reports the RSS from BSs to a Central Processing Unit (CPU), which may be located in the cloud. Alternatively, the localization can be performed locally at the user. Using estimated pathloss radio maps of the BSs, LocUNet can localize users with state-of-the-art accuracy and enjoys high robustness to inaccuracies in the radio maps. The proposed method does not require pre-sampling of the environment; and is suitable for real-time applications, thanks to the RadioUNet, a neural network-based radio map estimator. We also introduce two datasets that allow numerical comparisons of RSS and Time of Arrival (ToA) methods in realistic urban environments.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Neural Tangent Kernel Beyond the Infinite-Width Limit: Effects of Depth and Initialization

Neural Tangent Kernel (NTK) is widely used to analyze overparametrized neural networks due to the famous result by Jacot et al. (2018): in the infinite-width limit, the NTK is deterministic and constant during training. However, this result cannot explain the behavior of deep networks, since it generally does not hold if depth and width tend to infinity simultaneously. In this paper, we study the NTK of fully-connected ReLU networks with depth comparable to width. We prove that the NTK properties depend significantly on the depth-to-width ratio and the distribution of parameters at initialization. In fact, our results indicate the importance of the three phases in the hyperparameter space identified in Poole et al. (2016): ordered, chaotic and the edge of chaos (EOC). We derive exact expressions for the NTK dispersion in the infinite-depth-and-width limit in all three phases and conclude that the NTK variability grows exponentially with depth at the EOC and in the chaotic phase but not in the ordered phase. We also show that the NTK of deep networks may stay constant during training only in the ordered phase and discuss how the structure of the NTK matrix changes during training.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Mathematics of Artificial Intelligence

We currently witness the spectacular success of artificial intelligence in both science and public life. However, the development of a rigorous mathematical foundation is still at an early stage. In this survey article, which is based on an invited lecture at the International Congress of Mathematicians 2022, we will in particular focus on the current "workhorse" of artificial intelligence, namely deep neural networks. We will present the main theoretical directions along with several exemplary results and discuss key open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Transferability of Graph Neural Networks: an Extended Graphon Approach

We study spectral graph convolutional neural networks (GCNNs), where filters are defined as continuous functions of the graph shift operator (GSO) through functional calculus. A spectral GCNN is not tailored to one specific graph and can be transferred between different graphs. It is hence important to study the GCNN transferability: the capacity of the network to have approximately the same repercussion on different graphs that represent the same phenomenon. Transferability ensures that GCNNs trained on certain graphs generalize if the graphs in the test set represent the same phenomena as the graphs in the training set. In this paper, we consider a model of transferability based on graphon analysis. Graphons are limit objects of graphs, and, in the graph paradigm, two graphs represent the same phenomenon if both approximate the same graphon. Our main contributions can be summarized as follows: 1) we prove that any fixed GCNN with continuous filters is transferable under graphs that approximate the same graphon, 2) we prove transferability for graphs that approximate unbounded graphon shift operators, which are defined in this paper, and, 3) we obtain non-asymptotic approximation results, proving linear stability of GCNNs. This extends current state-of-the-art results which show asymptotic transferability for polynomial filters under graphs that approximate bounded graphons.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

$\ell^1$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?

This paper investigates the problem of signal estimation from undersampled noisy sub-Gaussian measurements under the assumption of a cosparse model. Based on generalized notions of sparsity, we derive novel recovery guarantees for the $\ell^1$-analysis basis pursuit, enabling accurate predictions of its sample complexity. The corresponding bounds on the number of required measurements do explicitly depend on the Gram matrix of the analysis operator and therefore particularly account for its mutual coherence structure. Our findings defy conventional wisdom which promotes the sparsity of analysis coefficients as the crucial quantity to study. In fact, this common paradigm breaks down completely in many situations of practical interest, for instance, when applying a redundant (multilevel) frame as analysis prior. By extensive numerical experiments, we demonstrate that, in contrast, our theoretical sampling-rate bounds reliably capture the recovery capability of various examples, such as redundant wavelets systems, total variation, or random frames. The proofs of our main results build upon recent achievements in the convex geometry of data mining problems. More precisely, we establish a sophisticated upper bound on the conic Gaussian mean width that is associated with the underlying $\ell^1$-analysis polytope. Due to a novel localization argument, it turns out that the presented framework naturally extends to stable recovery, allowing us to incorporate compressible coefficient sequences as well.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Theoretical Analysis of Deep Neural Networks and Parametric PDEs

We derive upper bounds on the complexity of ReLU neural networks approximating the solution maps of parametric partial differential equations. In particular, without any knowledge of its concrete shape, we use the inherent low-dimensionality of the solution manifold to obtain approximation rates which are significantly superior to those provided by classical neural network approximation results. Concretely, we use the existence of a small reduced basis to construct, for a large variety of parametric partial differential equations, neural networks that yield approximations of the parametric solution maps in such a way that the sizes of these networks essentially only depend on the size of the reduced basis.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximation spaces of deep neural networks

We study the expressivity of deep neural networks. Measuring a network's complexity by its number of connections or by its number of neurons, we consider the class of functions for which the error of best approximation with networks of a given complexity decays at a certain rate when increasing the complexity budget. Using results from classical approximation theory, we show that this class can be endowed with a (quasi)-norm that makes it a linear function space, called approximation space. We establish that allowing the networks to have certain types of "skip connections" does not change the resulting approximation spaces. We also discuss the role of the network's nonlinearity (also known as activation function) on the resulting spaces, as well as the role of depth. For the popular ReLU nonlinearity and its powers, we relate the newly constructed spaces to classical Besov spaces. The established embeddings highlight that some functions of very low Besov smoothness can nevertheless be well approximated by neural networks, if these networks are sufficiently deep.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Expressivity of Deep Neural Networks

In this review paper, we give a comprehensive overview of the large variety of approximation results for neural networks. Approximation rates for classical function spaces as well as benefits of deep neural networks over shallow ones for specifically structured function classes are discussed. While the mainbody of existing results is for general feedforward architectures, we also depict approximation results for convolutional, residual and recurrent neural networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

In-Distribution Interpretability for Challenging Modalities

It is widely recognized that the predictions of deep neural networks are difficult to parse relative to simpler approaches. However, the development of methods to investigate the mode of operation of such models has advanced rapidly in the past few years. Recent work introduced an intuitive framework which utilizes generative models to improve on the meaningfulness of such explanations. In this work, we display the flexibility of this method to interpret diverse and challenging modalities: music and physical simulations of urban environments.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Interval Neural Networks: Uncertainty Scores

We propose a fast, non-Bayesian method for producing uncertainty scores in the output of pre-trained deep neural networks (DNNs) using a data-driven interval propagating network. This interval neural network (INN) has interval valued parameters and propagates its input using interval arithmetic. The INN produces sensible lower and upper bounds encompassing the ground truth. We provide theoretical justification for the validity of these bounds. Furthermore, its asymmetric uncertainty scores offer additional, directional information beyond what Gaussian-based, symmetric variance estimation can provide. We find that noise in the data is adequately captured by the intervals produced with our method. In numerical experiments on an image reconstruction task, we demonstrate the practical utility of INNs as a proxy for the prediction error in comparison to two state-of-the-art uncertainty quantification methods. In summary, INNs produce fast, theoretically justified uncertainty scores for DNNs that are easy to interpret, come with added information and pose as improved error proxies - features that may prove useful in advancing the usability of DNNs especially in sensitive applications such as health care.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Numerical Solution of the Parametric Diffusion Equation by Deep Neural Networks

We perform a comprehensive numerical study of the effect of approximation-theoretical results for neural networks on practical learning problems in the context of numerical analysis. As the underlying model, we study the machine-learning-based solution of parametric partial differential equations. Here, approximation theory predicts that the performance of the model should depend only very mildly on the dimension of the parameter space and is determined by the intrinsic dimension of the solution manifold of the parametric partial differential equation. We use various methods to establish comparability between test-cases by minimizing the effect of the choice of test-cases on the optimization and sampling aspects of the learning problem. We find strong support for the hypothesis that approximation-theoretical effects heavily influence the practical behavior of learning problems in numerical analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Real-time Localization Using Radio Maps

This paper deals with the problem of localization in a cellular network in a dense urban scenario. Global Navigation Satellite System typically performs poorly in urban environments when there is no line-of-sight between the devices and the satellites, and thus alternative localization methods are often required. We present a simple yet effective method for localization based on pathloss. In our approach, the user to be localized reports the received signal strength from a set of base stations with known locations. For each base station we have a good approximation of the pathloss at each location in the map, provided by RadioUNet, an efficient deep learning-based simulator of pathloss functions in urban environment, akin to ray-tracing. Using the approximations of the pathloss functions of all base stations and the reported signal strengths, we are able to extract a very accurate approximation of the location of the user.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

tfShearlab: The TensorFlow Digital Shearlet Transform for Deep Learning

The shearlet transform from applied harmonic analysis is currently the state of the art when analyzing multidimensional signals with anisotropic singularities. Its optimal sparse approximation properties and its faithful digitalization allow shearlets to be applied to different problems from imaging science, such as image denoising, image inpainting, and singularities detection. The shearlet transform has also be successfully utilized, for instance, as a feature extractor. As such it has been shown to be well suited for image preprocessing in combination with data-driven methods such as deep neural networks. This requires in particular an implementation of the shearlet transform in the current deep learning frameworks, such as TensorFlow. With this motivation we developed a tensor shearlet transform aiming to provide a faithful TensorFlow implementation. In addition to its usability in predictive models, we also observed an significant improvement in the performance of the transform, with a running time of almost 40 times the previous state-of-the-art implementation. In this paper, we will also present several numerical experiments such as image denoising and inpainting, where the TensorFlow version can be shown to outperform previous libraries as well as the learned primal-dual reconstruction method for low dose computed tomography in running time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Restricted Isometry of ReLU Networks: Generalization through Norm Concentration

While regression tasks aim at interpolating a relation on the entire input space, they often have to be solved with a limited amount of training data. Still, if the hypothesis functions can be sketched well with the data, one can hope for identifying a generalizing model. In this work, we introduce with the Neural Restricted Isometry Property (NeuRIP) a uniform concentration event, in which all shallow $\mathrm{ReLU}$ networks are sketched with the same quality. To derive the sample complexity for achieving NeuRIP, we bound the covering numbers of the networks in the Sub-Gaussian metric and apply chaining techniques. In case of the NeuRIP event, we then provide bounds on the expected risk, which hold for networks in any sublevel set of the empirical risk. We conclude that all networks with sufficiently small empirical risk generalize uniformly.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Mathematical Framework for Feature Selection from Real-World Data with Non-Linear Observations

In this paper, we study the challenge of feature selection based on a relatively small collection of sample pairs $\{(x_i, y_i)\}_{1 \leq i \leq m}$. The observations $y_i \in \mathbb{R}$ are thereby supposed to follow a noisy single-index model, depending on a certain set of signal variables. A major difficulty is that these variables usually cannot be observed directly, but rather arise as hidden factors in the actual data vectors $x_i \in \mathbb{R}^d$ (feature variables). We will prove that a successful variable selection is still possible in this setup, even when the applied estimator does not have any knowledge of the underlying model parameters and only takes the 'raw' samples $\{(x_i, y_i)\}_{1 \leq i \leq m}$ as input. The model assumptions of our results will be fairly general, allowing for non-linear observations, arbitrary convex signal structures as well as strictly convex loss functions. This is particularly appealing for practical purposes, since in many applications, already standard methods, e.g., the Lasso or logistic regression, yield surprisingly good outcomes. Apart from a general discussion of the practical scope of our theoretical findings, we will also derive a rigorous guarantee for a specific real-world problem, namely sparse feature extraction from (proteomics-based) mass spectrometry data.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Compressed Sensing for Finite-Valued Signals

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. Whereas classical compressed sensing algorithms do not incorporate the additional knowledge of the discrete nature of the signal, classical lattice decoding approaches such as the sphere decoder do not utilize sparsity constraints. In this work, we present an approach that incorporates a discrete values prior into basis pursuit. In particular, we address unipolar binary and bipolar ternary sparse signals, i.e., sparse signals with entries in $\{0,1\}$, respectively in $\{-1,0,1\}$. We will show that phase transition takes place earlier than when using the classical basis pursuit approach and that, independently of the sparsity of the signal, at most $N/2$, respectively $3N/4$, measurements are necessary to recover a unipolar binary, and a bipolar ternary signal uniquely, where $N$ is the dimension of the ambient space. We will further discuss robustness of the algorithm and generalizations to signals with entries in larger alphabets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Regularization and Numerical Solution of the Inverse Scattering Problem using Shearlet Frames

Regularization techniques for the numerical solution of inverse scattering problems in two space dimensions are discussed. Assuming that the boundary of a scatterer is its most prominent feature, we exploit as model the class of cartoon-like functions. Since functions in this class are asymptotically optimally sparsely approximated by shearlet frames, we consider shearlets as a means for regularization in a Tikhonov method. We analyze two approaches, namely solvers for the nonlinear problem and for the linearized problem obtained by the Born approximation technique. As example for the first class we study the acoustic inverse scattering problem, and for the second class, the inverse scattering problem of the Schrödinger equation. In both cases, we derive analytical results for our approaches. Whereas our emphasis for the linearized problem is more on the theoretical side due to the standardness of associated solvers, we provide numerical examples for the nonlinear problem that highlight the effectiveness of our algorithmic approach.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Effect of Perturbations of Operator-Valued Frame Sequences and Fusion Frames on Their Duals

Fusion frames, and, more generally, operator-valued frame sequences are generalizations of classical frames, which are today a standard notion when redundant, yet stable sequences are required. However, the question of stability of duals with respect to perturbations has not been satisfactorily answered. In this paper, we quantitatively measure this stability by considering the associated deviations of the canonical and alternate dual sequences from the original ones. It is proven that operator-valued frame sequences are indeed stable in this sense. Along the way, we also generalize existing definitions for fusion frame duals to the infinite-dimensional situation and analyze how they perform with respect to a list of desiderata which, to our minds, a fusion frame dual should satisfy. Finally, we prove a similar stability result as above for fusion frames and their canonical duals.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Classification of Edges Using Compactly Supported Shearlets

We analyze the detection and classification of singularities of functions $f = χ_B$, where $B \subset \mathbb{R}^d$ and $d = 2,3$. It will be shown how the set $\partial B$ can be extracted by a continuous shearlet transform associated with compactly supported shearlets. Furthermore, if $\partial S$ is a $d-1$ dimensional piecewise smooth manifold with $d=2$ or $3$, we will classify smooth and non-smooth components of $\partial S$. This improves previous results given for shearlet systems with a certain band-limited generator, since the estimates we derive are uniform. Moreover, we will show that our bounds are optimal. Along the way, we also obtain novel results on the characterization of wavefront sets in $3$ dimensions by compactly supported shearlets. Finally, geometric properties of $\partial S$ such as curvature are described in terms of the continuous shearlet transform of $f$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Compressive Imaging of Fourier Data

Applications such as Magnetic Resonance Tomography acquire imaging data by point samples of their Fourier transform. This raises the question of balancing the efficiency of the sampling strategies with the approximation accuracy of an associated reconstruction procedure. In this paper, we introduce a novel sampling-reconstruction scheme based on a random anisotropic sampling pattern and a compressed sensing type reconstruction strategy with a variant of dualizable shearlet frames as sparsifying representation system. For this scheme, we prove asymptotic optimality in an approximation theoretic sense for cartoon-like functions as a model class for the imaging data. Finally, we present numerical experiments showing the superiority of our scheme over other approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

$α$-Molecules

Within the area of applied harmonic analysis, various multiscale systems such as wavelets, ridgelets, curvelets, and shearlets have been introduced and successfully applied. The key property of each of those systems are their (optimal) approximation properties in terms of the decay of the $L^2$-error of the best $N$-term approximation for a certain class of functions. In this paper, we introduce the general framework of $α$-molecules, which encompasses most multiscale systems from applied harmonic analysis, in particular, wavelets, ridgelets, curvelets, and shearlets as well as extensions of such with $α$ being a parameter measuring the degree of anisotropy, as a means to allow a unified treatment of approximation results within this area. Based on an $α$-scaled index distance, we first prove that two systems of $α$-molecules are almost orthogonal. This leads to a general methodology to transfer approximation results within this framework, provided that certain consistency and time-frequency localization conditions of the involved systems of $α$-molecules are satisfied. We finally utilize these results to enable the derivation of optimal sparse approximation results \msch{for} a specific class of cartoon-like functions by sufficient conditions on the 'control' parameters of a system of $α$-molecules.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Asymptotic Analysis of Inpainting via Universal Shearlet Systems

Recently introduced inpainting algorithms using a combination of applied harmonic analysis and compressed sensing have turned out to be very successful. One key ingredient is a carefully chosen representation system which provides (optimally) sparse approximations of the original image. Due to the common assumption that images are typically governed by anisotropic features, directional representation systems have often been utilized. One prominent example of this class are shearlets, which have the additional benefitallowing faithful implementations. Numerical results show that shearlets significantly outperform wavelets in inpainting tasks. One of those software packages, www.shearlab.org, even offers the flexibility of usingdifferent parameter for each scale, which is not yet covered by shearlet theory. In this paper, we first introduce universal shearlet systems which are associated with an arbitrary scaling sequence, thereby modeling the previously mentioned flexibility. In addition, this novel construction allows for a smooth transition between wavelets and shearlets and therefore enables us to analyze them in a uniform fashion. For a large class of such scaling sequences, we first prove that the associated universal shearlet systems form band-limited Parseval frames for $L^2(\mathbb{R}^2)$ consisting of Schwartz functions. Secondly, we analyze the performance for inpainting of this class of universal shearlet systems within a distributional model situation using an $\ell^1$-analysis minimization algorithm for reconstruction. Our main result in this part states that, provided the scaling sequence is comparable to the size of the (scale-dependent) gap, nearly-perfect inpainting is achieved at sufficiently fine scales.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Cartoon Approximation with $α$-Curvelets

It is well-known that curvelets provide optimal approximations for so-called cartoon images which are defined as piecewise $C^2$-functions, separated by a $C^2$ singularity curve. In this paper, we consider the more general case of piecewise $C^β$-functions, separated by a $C^β$ singularity curve for $β\in (1,2]$. We first prove a benchmark result for the possibly achievable best $N$-term approximation rate for this more general signal model. Then we introduce what we call $α$-curvelets, which are systems that interpolate between wavelet systems on the one hand ($α= 1$) and curvelet systems on the other hand ($α= \frac12$). Our main result states that those frames achieve this optimal rate for $α= \frac{1}β$, up to $\log$-factors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dualizable Shearlet Frames and Sparse Approximation

Shearlet systems have been introduced as directional representation systems, which provide optimally sparse approximations of a certain model class of functions governed by anisotropic features while allowing faithful numerical realizations by a unified treatment of the continuum and digital realm. They are redundant systems, and their frame properties have been extensively studied. In contrast to certain band-limited shearlets, compactly supported shearlets provide high spatial localization, but do not constitute Parseval frames. Thus reconstruction of a signal from shearlet coefficients requires knowledge of a dual frame. However, no closed and easily computable form of any dual frame is known. In this paper, we introduce the class of dualizable shearlet systems, which consist of compactly supported elements and can be proven to form frames for $L^2(\mathbb{R}^2)$. For each such dualizable shearlet system, we then provide an explicit construction of an associated dual frame, which can be stated in closed form and efficiently computed. We also show that dualizable shearlet frames still provide optimally sparse approximations of anisotropic features.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient Resolution of Anisotropic Structures

We highlight some recent new delevelopments concerning the sparse representation of possibly high-dimensional functions exhibiting strong anisotropic features and low regularity in isotropic Sobolev or Besov scales. Specifically, we focus on the solution of transport equations which exhibit propagation of singularities where, additionally, high-dimensionality enters when the convection field, and hence the solutions, depend on parameters varying over some compact set. Important constituents of our approach are directionally adaptive discretization concepts motivated by compactly supported shearlet systems, and well-conditioned stable variational formulations that support trial spaces with anisotropic refinements with arbitrary directionalities. We prove that they provide tight error-residual relations which are used to contrive rigorously founded adaptive refinement schemes which converge in $L_2$. Moreover, in the context of parameter dependent problems we discuss two approaches serving different purposes and working under different regularity assumptions. For frequent query problems, making essential use of the novel well-conditioned variational formulations, a new Reduced Basis Method is outlined which exhibits a certain rate-optimal performance for indefinite, unsymmetric or singularly perturbed problems. For the radiative transfer problem with scattering a sparse tensor method is presented which mitigates or even overcomes the curse of dimensionality under suitable (so far still isotropic) regularity assumptions. Numerical examples for both methods illustrate the theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear Stable Sampling Rate: Optimality of 2D Wavelet Reconstructions from Fourier Measurements

In this paper we analyze two-dimensional wavelet reconstructions from Fourier samples within the framework of generalized sampling. For this, we consider both separable compactly-supported wavelets and boundary wavelets. We prove that the number of samples that must be acquired to ensure a stable and accurate reconstruction scales linearly with the number of reconstructing wavelet functions. We also provide numerical experiments that corroborate our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Measures of scalability

Scalable frames are frames with the property that the frame vectors can be rescaled resulting in tight frames. However, if a frame is not scalable, one has to aim for an approximate procedure. For this, in this paper we introduce three novel quantitative measures of the closeness to scalability for frames in finite dimensional real Euclidean spaces. Besides the natural measure of scalability given by the distance of a frame to the set of scalable frames, another measure is obtained by optimizing a quadratic functional, while the third is given by the volume of the ellipsoid of minimal volume containing the symmetrized frame. After proving that these measures are equivalent in a certain sense, we establish bounds on the probability of a randomly selected frame to be scalable. In the process, we also derive new necessary and sufficient conditions for a frame to be scalable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scalable Frames and Convex Geometry

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, and study the connection between this notion and elements from convex geometry. Finally, we provide results on the topology of scalable frames. In particular, we prove that the set of scalable frames with "small" redundancy is nowhere dense in the set of frames.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gabor Shearlets

In this paper, we introduce Gabor shearlets, a variant of shearlet systems, which are based on a different group representation than previous shearlet constructions: they combine elements from Gabor and wavelet frames in their construction. As a consequence, they can be implemented with standard filters from wavelet theory in combination with standard Gabor windows. Unlike the usual shearlets, the new construction can achieve a redundancy as close to one as desired. Our construction follows the general strategy for shearlets. First we define group-based Gabor shearlets and then modify them to a cone-adapted version. In combination with Meyer filters, the cone-adapted Gabor shearlets constitute a tight frame and provide low-redundancy sparse approximations of the common model class of anisotropic features which are cartoon-like functions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Analysis of Inpainting via Clustered Sparsity and Microlocal Analysis

Recently, compressed sensing techniques in combination with both wavelet and directional representation systems have been very effectively applied to the problem of image inpainting. However, a mathematical analysis of these techniques which reveals the underlying geometrical content is completely missing. In this paper, we provide the first comprehensive analysis in the continuum domain utilizing the novel concept of clustered sparsity, which besides leading to asymptotic error bounds also makes the superior behavior of directional representation systems over wavelets precise. First, we propose an abstract model for problems of data recovery and derive error bounds for two different recovery schemes, namely l_1 minimization and thresholding. Second, we set up a particular microlocal model for an image governed by edges inspired by seismic data as well as a particular mask to model the missing data, namely a linear singularity masked by a horizontal strip. Applying the abstract estimate in the case of wavelets and of shearlets we prove that -- provided the size of the missing part is asymptotically to the size of the analyzing functions -- asymptotically precise inpainting can be obtained for this model. Finally, we show that shearlets can fill strictly larger gaps than wavelets in this model.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Clustered Sparsity and Separation of Cartoon and Texture

Natural images are typically a composition of cartoon and texture structures. A medical image might, for instance, show a mixture of gray matter and the skull cap. One common task is to separate such an image into two single images, one containing the cartoon part and the other containing the texture part. Recently, a powerful class of algorithms using sparse approximation and $\ell_1$ minimization has been introduced to resolve this problem, and numerous inspiring empirical results have already been obtained. In this paper we provide the first thorough theoretical study of the separation of a combination of cartoon and texture structures in a model situation using this class of algorithms. The methodology we consider expands the image in a combined dictionary consisting of a curvelet tight frame and a Gabor tight frame and minimizes the $\ell_1$ norm on the analysis side. Sparse approximation properties then force the cartoon components into the curvelet coefficients and the texture components into the Gabor coefficients, thereby separating the image. Utilizing the fact that the coefficients are clustered geometrically, we prove that at sufficiently fine scales arbitrarily precise separation is possible. Main ingredients of our analysis are the novel notion of cluster coherence and clustered/geometric sparsity. Our analysis also provides a deep understanding on when separation is still possible.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Geometric Separation by Single-Pass Alternating Thresholding

Modern data is customarily of multimodal nature, and analysis tasks typically require separation into the single components. Although a highly ill-posed problem, the morphological difference of these components sometimes allow a very precise separation such as, for instance, in neurobiological imaging a separation into spines (pointlike structures) and dendrites (curvilinear structures). Recently, applied harmonic analysis introduced powerful methodologies to achieve this task, exploiting specifically designed representation systems in which the components are sparsely representable, combined with either performing $\ell_1$ minimization or thresholding on the combined dictionary. In this paper we provide a thorough theoretical study of the separation of a distributional model situation of point- and curvilinear singularities exploiting a surprisingly simple single-pass alternating thresholding method applied to the two complementary frames: wavelets and curvelets. Utilizing the fact that the coefficients are clustered geometrically, thereby exhibiting clustered/geometric sparsity in the chosen frames, we prove that at sufficiently fine scales arbitrarily precise separation is possible. Even more surprising, it turns out that the thresholding index sets converge to the wavefront sets of the point- and curvilinear singularities in phase space and that those wavefront sets are perfectly separated by the thresholding procedure. Main ingredients of our analysis are the novel notion of cluster coherence and clustered/geometric sparsity as well as a microlocal analysis viewpoint.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimally sparse approximations of 3D functions by compactly supported shearlet frames

We study efficient and reliable methods of capturing and sparsely representing anisotropic structures in 3D data. As a model class for multidimensional data with anisotropic features, we introduce generalized three-dimensional cartoon-like images. This function class will have two smoothness parameters: one parameter βcontrolling classical smoothness and one parameter αcontrolling anisotropic smoothness. The class then consists of piecewise C^β-smooth functions with discontinuities on a piecewise C^α-smooth surface. We introduce a pyramid-adapted, hybrid shearlet system for the three-dimensional setting and construct frames for L^2(R^3) with this particular shearlet structure. For the smoothness range 1<α=< β=< 2 we show that pyramid-adapted shearlet systems provide a nearly optimally sparse approximation rate within the generalized cartoon-like image model class measured by means of non-linear N-term approximations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Scalable Frames

Tight frames can be characterized as those frames which possess optimal numerical stability properties. In this paper, we consider the question of modifying a general frame to generate a tight frame by rescaling its frame vectors; a process which can also be regarded as perfect preconditioning of a frame by a diagonal operator. A frame is called scalable, if such a diagonal operator exists. We derive various characterizations of scalable frames, thereby including the infinite-dimensional situation. Finally, we provide a geometric interpretation of scalability in terms of conical surfaces.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sparsity and spectral properties of dual frames

We study sparsity and spectral properties of dual frames of a given finite frame. We show that any finite frame has a dual with no more than $n^2$ non-vanishing entries, where $n$ denotes the ambient dimension, and that for most frames no sparser dual is possible. Moreover, we derive an expression for the exact sparsity level of the sparsest dual for any given finite frame using a generalized notion of spark. We then study the spectral properties of dual frames in terms of singular values of the synthesis operator. We provide a complete characterization for which spectral patterns of dual frames are possible for a fixed frame. For many cases, we provide simple explicit constructions for dual frames with a given spectrum, in particular, if the constraint on the dual is that it be tight.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Theory and Applications of Compressed Sensing

Compressed sensing is a novel research area, which was introduced in 2006, and since then has already become a key concept in various areas of applied mathematics, computer science, and electrical engineering. It surprisingly predicts that high-dimensional signals, which allow a sparse representation by a suitable basis or, more generally, a frame, can be recovered from what was previously considered highly incomplete linear measurements by using efficient algorithms. This article shall serve as an introduction to and a survey about compressed sensing.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Data Separation by Sparse Representations

Recently, sparsity has become a key concept in various areas of applied mathematics, computer science, and electrical engineering. One application of this novel methodology is the separation of data, which is composed of two (or more) morphologically distinct constituents. The key idea is to carefully select representation systems each providing sparse approximations of one of the components. Then the sparsest coefficient vector representing the data within the composed - and therefore highly redundant - representation system is computed by $\ell_1$ minimization or thresholding. This automatically enforces separation. This paper shall serve as an introduction to and a survey about this exciting area of research as well as a reference for the state-of-the-art of this research field. It will appear as a chapter in a book on "Compressed Sensing: Theory and Applications" edited by Yonina Eldar and Gitta Kutyniok.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Digital Shearlet Transform

Over the past years, various representation systems which sparsely approximate functions governed by anisotropic features such as edges in images have been proposed. We exemplarily mention the systems of contourlets, curvelets, and shearlets. Alongside the theoretical development of these systems, algorithmic realizations of the associated transforms were provided. However, one of the most common shortcomings of these frameworks is the lack of providing a unified treatment of the continuum and digital world, i.e., allowing a digital theory to be a natural digitization of the continuum theory. In fact, shearlet systems are the only systems so far which satisfy this property, yet still deliver optimally sparse approximations of cartoon-like images. In this chapter, we provide an introduction to digital shearlet theory with a particular focus on a unified treatment of the continuum and digital realm. In our survey we will present the implementations of two shearlet transforms, one based on band-limited shearlets and the other based on compactly supported shearlets. We will moreover discuss various quantitative measures, which allow an objective comparison with other directional transforms and an objective tuning of parameters. The codes for both presented transforms as well as the framework for quantifying performance are provided in the Matlab toolbox ShearLab.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Image Separation using Wavelets and Shearlets

In this paper, we present an image separation method for separating images into point- and curvelike parts by employing a combined dictionary consisting of wavelets and compactly supported shearlets utilizing the fact that they sparsely represent point and curvilinear singularities, respectively. Our methodology is based on the very recently introduced mathematical theory of geometric separation, which shows that highly precise separation of the morphologically distinct features of points and curves can be achieved by $\ell^1$ minimization. Finally, we present some experimental results showing the effectiveness of our algorithm, in particular, the ability to accurately separate points from curves even if the curvature is relatively large due to the excellent localization property of compactly supported shearlets.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimally Sparse Frames

Frames have established themselves as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. However, when the signal dimension is large, the computation of the frame measurements of a signal typically requires a large number of additions and multiplications, and this makes a frame decomposition intractable in applications with limited computing budget. To address this problem, in this paper, we focus on frames in finite-dimensional Hilbert spaces and introduce sparsity for such frames as a new paradigm. In our terminology, a sparse frame is a frame whose elements have a sparse representation in an orthonormal basis, thereby enabling low-complexity frame decompositions. To introduce a precise meaning of optimality, we take the sum of the numbers of vectors needed of this orthonormal basis when expanding each frame vector as sparsity measure. We then analyze the recently introduced algorithm Spectral Tetris for construction of unit norm tight frames and prove that the tight frames generated by this algorithm are in fact optimally sparse with respect to the standard unit vector basis. Finally, we show that even the generalization of Spectral Tetris for the construction of unit norm frames associated with a given frame operator produces optimally sparse frames.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

ShearLab: A Rational Design of a Digital Parabolic Scaling Algorithm

Multivariate problems are typically governed by anisotropic features such as edges in images. A common bracket of most of the various directional representation systems which have been proposed to deliver sparse approximations of such features is the utilization of parabolic scaling. One prominent example is the shearlet system. Our objective in this paper is three-fold: We firstly develop a digital shearlet theory which is rationally designed in the sense that it is the digitization of the existing shearlet theory for continuous data. This implicates that shearlet theory provides a unified treatment of both the continuum and digital realm. Secondly, we analyze the utilization of pseudo-polar grids and the pseudo-polar Fourier transform for digital implementations of parabolic scaling algorithms. We derive an isometric pseudo-polar Fourier transform by careful weighting of the pseudo-polar grid, allowing exploitation of its adjoint for the inverse transform. This leads to a digital implementation of the shearlet transform; an accompanying Matlab toolbox called ShearLab is provided. And, thirdly, we introduce various quantitative measures for digital parabolic scaling algorithms in general, allowing one to tune parameters and objectively improve the implementation as well as compare different directional transform implementations. The usefulness of such measures is exemplarily demonstrated for the digital shearlet transform.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Shearlets and Optimally Sparse Approximations

Multivariate functions are typically governed by anisotropic features such as edges in images or shock fronts in solutions of transport-dominated equations. One major goal both for the purpose of compression as well as for an efficient analysis is the provision of optimally sparse approximations of such functions. Recently, cartoon-like images were introduced in 2D and 3D as a suitable model class, and approximation properties were measured by considering the decay rate of the $L^2$ error of the best $N$-term approximation. Shearlet systems are to date the only representation system, which provide optimally sparse approximations of this model class in 2D as well as 3D. Even more, in contrast to all other directional representation systems, a theory for compactly supported shearlet frames was derived which moreover also satisfy this optimality benchmark. This chapter shall serve as an introduction to and a survey about sparse approximations of cartoon-like images by band-limited and also compactly supported shearlet frames as well as a reference for the state-of-the-art of this research field.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sparse Recovery from Combined Fusion Frame Measurements

Sparse representations have emerged as a powerful tool in signal and information processing, culminated by the success of new acquisition and processing techniques such as Compressed Sensing (CS). Fusion frames are very rich new signal representation methods that use collections of subspaces instead of vectors to represent signals. This work combines these exciting 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 does not need to be sparse within each of the subspaces it occupies. This sparsity model is captured using a mixed l1/l2 norm for fusion frames. A signal sparse in a fusion frame can be sampled using very few random projections and exactly reconstructed using a convex optimization that minimizes this mixed l1/l2 norm. The provided sampling conditions generalize coherence and RIP conditions used in standard CS theory. It is demonstrated that they are sufficient to guarantee sparse recovery of any signal sparse in our model. Moreover, a probabilistic analysis is provided using a stochastic model on the sparse signal that shows that under very mild conditions the probability of recovery failure decays exponentially with increasing dimension of the subspaces.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sparsity Equivalence of Anisotropic Decompositions

Anisotropic decompositions using representation systems such as curvelets, contourlet, or shearlets have recently attracted significantly increased attention due to the fact that they were shown to provide optimally sparse approximations of functions exhibiting singularities on lower dimensional embedded manifolds. The literature now contains various direct proofs of this fact and of related sparse approximation results. However, it seems quite cumbersome to prove such a canon of results for each system separately, while many of the systems exhibit certain similarities. In this paper, with the introduction of the concept of sparsity equivalence, we aim to provide a framework which allows categorization of the ability for sparse approximations of representation systems. This framework, in particular, enables transferring results on sparse approximations from one system to another. We demonstrate this concept for the example of curvelets and shearlets, and discuss how this viewpoint immediately leads to novel results for both systems.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Compactly Supported Shearlets

Shearlet theory has become a central tool in analyzing and representing 2D data with anisotropic features. Shearlet systems are systems of functions generated by one single generator with parabolic scaling, shearing, and translation operators applied to it, in much the same way wavelet systems are dyadic scalings and translations of a single function, but including a precise control of directionality. Of the many directional representation systems proposed in the last decade, shearlets are among the most versatile and successful systems. The reason for this being an extensive list of desirable properties: shearlet systems can be generated by one function, they provide precise resolution of wavefront sets, they allow compactly supported analyzing elements, they are associated with fast decomposition algorithms, and they provide a unified treatment of the continuum and the digital realm. The aim of this paper is to introduce some key concepts in directional representation systems and to shed some light on the success of shearlet systems as directional representation systems. In particular, we will give an overview of the different paths taken in shearlet theory with focus on separable and compactly supported shearlets in 2D and 3D. We will present constructions of compactly supported shearlet frames in those dimensions as well as discuss recent results on the ability of compactly supported shearlet frames satisfying weak decay, smoothness, and directional moment conditions to provide optimally sparse approximations of cartoon-like images in 2D as well as in 3D. Finally, we will show that these compactly supported shearlet systems provide optimally sparse approximations of an even generalized model of cartoon-like images comprising of $C^2$ functions that are smooth apart from piecewise $C^2$ discontinuity edges.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Microlocal Analysis of the Geometric Separation Problem

Image data are often composed of two or more geometrically distinct constituents; in galaxy catalogs, for instance, one sees a mixture of pointlike structures (galaxy superclusters) and curvelike structures (filaments). It would be ideal to process a single image and extract two geometrically `pure' images, each one containing features from only one of the two geometric constituents. This seems to be a seriously underdetermined problem, but recent empirical work achieved highly persuasive separations. We present a theoretical analysis showing that accurate geometric separation of point and curve singularities can be achieved by minimizing the $\ell_1$ norm of the representing coefficients in two geometrically complementary frames: wavelets and curvelets. Driving our analysis is a specific property of the ideal (but unachievable) representation where each content type is expanded in the frame best adapted to it. This ideal representation has the property that important coefficients are clustered geometrically in phase space, and that at fine scales, there is very little coherence between a cluster of elements in one frame expansion and individual elements in the complementary frame. We formally introduce notions of cluster coherence and clustered sparsity and use this machinery to show that the underdetermined systems of linear equations can be stably solved by $\ell_1$ minimization; microlocal phase space helps organize the calculations that cluster coherence requires.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Shearlets on Bounded Domains

Shearlet systems have so far been only considered as a means to analyze $L^2$-functions defined on $\R^2$, which exhibit curvilinear singularities. However, in applications such as image processing or numerical solvers of partial differential equations the function to be analyzed or efficiently encoded is typically defined on a non-rectangular shaped bounded domain. Motivated by these applications, in this paper, we first introduce a novel model for cartoon-like images defined on a bounded domain. We then prove that compactly supported shearlet frames satisfying some weak decay and smoothness conditions, when orthogonally projected onto the bounded domain, do provide (almost) optimally sparse approximations of elements belonging to this model class.

0 citations0 reviewsNo code linkedOpen access