Search

This paper studies the approximation capacity of ReLU neural networks with norm constraint on the weights. We prove upper and lower bounds on the approximation error of these networks for smooth function classes. The lower bound is derived through the Rademacher complexity of neural networks, which may be of independent interest. We apply these approximation bounds to analyze the convergences of regression using norm constrained neural networks and distribution estimation by GANs. In particular, we obtain convergence rates for over-parameterized neural networks. It is also shown that GANs can achieve optimal rate of learning probability distributions, when the discriminator is a properly chosen norm constrained neural network. [ABSTRACT FROM AUTHOR]

The recovery of multivariate functions and estimating their integrals from finitely many samples is one of the central tasks in modern approximation theory. Marcinkiewicz–Zygmund inequalities provide answers to both the recovery and the quadrature aspect. In this paper, we put ourselves on the q -dimensional sphere S q , and investigate how well continuous L p -norms of polynomials f of maximum degree n on the sphere S q can be discretized by positively weighted L p -sum of finitely many samples, and discuss the distortion between the continuous and discrete quantities, the number and distribution of the (deterministic or randomly chosen) sample points ξ 1 , ... , ξ N on S q , the dimension q , and the degree n of the polynomials. [ABSTRACT FROM AUTHOR]

The paper presents an oversampling technique to overcome the loss incurred at the time of binarizing the images. As such there are very few techniques available in the literature to approximate the loss in the images. This technique is based on the Estimate wavelet transform (EWT) which fulfills the loss and makes the image smooth. Coiflet and Daubechies D8 wavelets are employed in EWT and performances are compared with the traditional Gaussian lowpass filter. All the three approaches are tested on seven distorted images, and observed that the Daubechies D8 and Coiflet wavelets using EWT are better able to approximate the image than Gaussian lowpass filter. Out of seven images two are presented in this paper. [ABSTRACT FROM AUTHOR]

Abstract: Using diffusion to define distances between points on a manifold (or a sampled data set) has been successfully employed in various applications such as data organization and approximately isometric embedding of high dimensional data in low dimensional Euclidean space. Recently, P. Jones has proposed a diffusion distance which is both intuitively appealing and scales appropriately with increasing time. In the first part of our paper, we present an efficient tree-based approach to computing an approximation to Jonesʼs diffusion distance. We also show our approximation is comparable to Jonesʼs distance. Neither Jonesʼs distance, nor our approximation, satisfies the triangle inequality; in particular, in the case of heat flow on , Jonesʼs separation distance gives a scaled square of the Euclidean distance. In the second part of our paper, we present a general construction to obtain an “almost” metric from a general distance. We also discuss a numerical procedure to implement our construction. Additionally, we show that in the case of heat flow on , we recover (scaled) Euclidean distance from Jonesʼs distance. [Copyright &y& Elsevier]

Abstract: In recent years anisotropic transforms like the shearlet or curvelet transform have received a considerable amount of interest due to their ability to efficiently capture anisotropic features in terms of nonlinear N-term approximation. In this paper we study tree-approximation properties of such transforms where the N-term approximant has to satisfy the additional constraint that the set of kept indices possesses a tree structure. The main result of this paper is that for shearlet- and related systems, this additional constraint does not deteriorate the approximation rate. As an application of our results we construct (almost) optimal encoding schemes for cartoon images. [Copyright &y& Elsevier]

Abstract: Recovering missing data from its partial samples is a fundamental problem in mathematics and it has wide range of applications in image and signal processing. While many such algorithms have been developed recently, there are very few papers available on their error estimations. This paper is to analyze the error of a frame based data recovery approach from random samples. In particular, we estimate the error between the underlying original data and the approximate solution that interpolates (or approximates with an error bound depending on the noise level) the given data that has the minimal norm of the canonical frame coefficients among all the possible solutions. [Copyright &y& Elsevier]

Abstract: The objective of this paper is to introduce a multi-resolution approximation (MRA) approach to the study of continuous function extensions with emphasis on surface completion and image inpainting. Along the line of the notion of diffusion maps introduced by Coifman and Lafon with some “heat kernels” as integral kernels of these operators in formulating the diffusion maps, we apply the directional derivatives of the heat kernels with respect to the inner normal vectors (on the boundary of the hole to be filled in) as integral kernels of the “propagation” operators. The extension operators defined by propagations followed by the corresponding sequent diffusion processes provide the MRA continuous function extensions to be discussed in this paper. As a case study, Green''s functions of some “anisotropic” differential operators are used as heat kernels, and the corresponding extension operators provide a vehicle to transport the surface or image data, along with some mixed derivatives, from the exterior of the hole to recover the missing data in the hole in an MRA fashion, with the propagated mixed derivative data to provide the surface or image “details” in the hole. An error formula in terms of the heat kernels is formulated, and this formula is applied to give the exact order of approximation for the isotropic setting. [Copyright &y& Elsevier]

In this paper we construct explicit sampling sets and present reconstruction algorithms for Fourier signals on finite vector spaces G , with | G | = p r for a suitable prime p . The two sampling sets have sizes of order O ( p t 2 r 2 ) and O ( p t 2 r 3 log ⁡ ( p ) ) respectively, where t is the number of large coefficients in the Fourier transform. The algorithms approximate the function up to a small constant of the best possible approximation with t non-zero Fourier coefficients. The fastest of the algorithms has complexity O ( p 2 t 2 r 3 log ⁡ ( p ) ) . [ABSTRACT FROM AUTHOR]

In compressed sensing, in order to recover a sparse or nearly sparse vector from possibly noisy measurements, the most popular approach is ℓ 1 -norm minimization. Upper bounds for the ℓ 2 -norm of the error between the true and estimated vectors are given in [1] and reviewed in [2] , while bounds for the ℓ 1 -norm are given in [3] . When the unknown vector is not conventionally sparse but is “group sparse” instead, a variety of alternatives to the ℓ 1 -norm have been proposed in the literature, including the group LASSO, sparse group LASSO, and group LASSO with tree structured overlapping groups. However, no error bounds are available for any of these modified objective functions. In the present paper, a unified approach is presented for deriving upper bounds on the error between the true vector and its approximation, based on the notion of decomposable and γ -decomposable norms. The bounds presented cover all of the norms mentioned above, and also provide a guideline for choosing norms in future to accommodate alternate forms of sparsity. [ABSTRACT FROM AUTHOR]

This paper presents an investigation of the approximation property of neural networks with unbounded activation functions, such as the rectified linear unit (ReLU), which is the new de-facto standard of deep learning. The ReLU network can be analyzed by the ridgelet transform with respect to Lizorkin distributions. By showing three reconstruction formulas by using the Fourier slice theorem, the Radon transform, and Parseval's relation, it is shown that a neural network with unbounded activation functions still satisfies the universal approximation property. As an additional consequence, the ridgelet transform, or the backprojection filter in the Radon domain, is what the network learns after backpropagation. Subject to a constructive admissibility condition, the trained network can be obtained by simply discretizing the ridgelet transform, without backpropagation. Numerical examples not only support the consistency of the admissibility condition but also imply that some non-admissible cases result in low-pass filtering. [ABSTRACT FROM AUTHOR]

In this paper, we study the Besov regularity of Lévy white noises on the d -dimensional torus. Due to their rough sample paths, the white noises that we consider are defined as generalized stochastic fields. We, initially, obtain regularity results for general Lévy white noises. Then, we focus on two subclasses of noises: compound Poisson and symmetric- α -stable (including Gaussian), for which we make more precise statements. Before measuring regularity, we show that the question is well-posed; we prove that Besov spaces are in the cylindrical σ -field of the space of generalized functions. These results pave the way to the characterization of the n -term wavelet approximation properties of stochastic processes. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a fidelity measure depending on a given sampling scheme and we propose a Galerkin method in Banach space setting for signal reconstruction. We show that the proposed Galerkin method provides a quasi-optimal approximation, and the corresponding Galerkin equations could be solved by an iterative approximation-projection algorithm in a reproducing kernel subspace of L p . Also we present detailed analysis and numerical simulations of the Galerkin method for reconstructing signals with finite rate of innovation. [ABSTRACT FROM AUTHOR]

Many current problems dealing with big data can be cast efficiently as function approximation on graphs. The information in the graph structure can often be reorganized in the form of a tree; for example, using clustering techniques. The objective of this paper is to develop a new system of orthogonal functions on weighted trees. The system is local, easily implementable, and allows for scalable approximations without saturation. A novelty of our orthogonal system is that the Fourier projections are uniformly bounded in the supremum norm. We describe in detail a construction of wavelet-like representations and estimate the degree of approximation of functions on the trees. [ABSTRACT FROM AUTHOR]

Sparse modeling/approximation of images plays an important role in image restoration. Instead of using a fixed system to sparsely model any input image, a more promising approach is using a system that is adaptive to the input image. A non-convex variational model is proposed in [1] for constructing a tight frame that is optimized for the input image, and an alternating scheme is used to solve the resulting non-convex optimization problem. Although it showed good empirical performance in image denoising, the proposed alternating iteration lacks convergence analysis. This paper aims at providing the convergence analysis of the method proposed in [1] . We first established the sub-sequence convergence property of the iteration scheme proposed in [1] , i.e., there exists at least one convergent sub-sequence and any convergent sub-sequence converges to a stationary point of the minimization problem. Moreover, we showed that the original method can be modified to have sequence convergence, i.e., the modified algorithm generates a sequence that converges to a stationary point of the minimization problem. [ABSTRACT FROM AUTHOR]

Diffusion Maps (DM), and other kernel methods, are utilized for the analysis of high dimensional datasets. The DM method uses a Markovian diffusion process to model and analyze data. A spectral analysis of the DM kernel yields a map of the data into a low dimensional space, where Euclidean distances between the mapped data points represent the diffusion distances between the corresponding high dimensional data points. Many machine learning methods, which are based on the Euclidean metric, can be applied to the mapped data points in order to take advantage of the diffusion relations between them. However, a significant drawback of the DM is the need to apply spectral decomposition to a kernel matrix, which becomes infeasible for large datasets. In this paper, we present an efficient approximation of the DM embedding. The presented approximation algorithm produces a dictionary of data points by identifying a small set of informative representatives. Then, based on this dictionary, the entire dataset is efficiently embedded into a low dimensional space. The Euclidean distances in the resulting embedded space approximate the diffusion distances. The properties of the presented embedding and its relation to DM method are analyzed and demonstrated. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: This article considers recovery of signals that are sparse or approximately sparse in terms of a (possibly) highly overcomplete and coherent tight frame from undersampled data corrupted with additive noise. We show that the properly constrained -analysis optimization problem, called analysis Dantzig selector, stably recovers a signal which is nearly sparse in terms of a tight frame provided that the measurement matrix satisfies a restricted isometry property adapted to the tight frame. As a special case, we consider the Gaussian noise. Further, under a sparsity scenario, with high probability, the recovery error from noisy data is within a log-like factor of the minimax risk over the class of vectors which are at most s sparse in terms of the tight frame. Similar results for the analysis LASSO are shown. The above two algorithms provide guarantees only for noise that is bounded or bounded with high probability (for example, Gaussian noise). However, when the underlying measurements are corrupted by sparse noise, these algorithms perform suboptimally. We propose new algorithms for reconstructing signals that are nearly sparse in terms of a tight frame in the presence of bounded noise combined with sparse noise, and present corresponding recovery guarantees. The analysis in this paper is based on the restricted isometry property adapted to a tight frame, which is a natural extension to the standard restricted isometry property. [Copyright &y& Elsevier]

Abstract: In this paper we study the problem of computing wavelet coefficients of compactly supported functions from their Fourier samples. For this, we use the recently introduced framework of generalized sampling. Our first result demonstrates that using generalized sampling one obtains a stable and accurate reconstruction, provided the number of Fourier samples grows linearly in the number of wavelet coefficients recovered. For the class of Daubechies wavelets we derive the exact constant of proportionality. Our second result concerns the optimality of generalized sampling for this problem. Under some mild assumptions we show that generalized sampling cannot be outperformed in terms of approximation quality by more than a constant factor. Moreover, for the class of so-called perfect methods, any attempt to lower the sampling ratio below a certain critical threshold necessarily results in exponential ill-conditioning. Thus generalized sampling provides a nearly-optimal solution to this problem. [Copyright &y& Elsevier]

Abstract: In the present paper we study high-order cubature formulas for the computation of advection–diffusion potentials over boxes. By using the basis functions introduced in the theory of approximate approximations, the cubature of a potential is reduced to the quadrature of one-dimensional integrals. For densities with separated approximation, we derive a tensor product representation of the integral operator which admits efficient cubature procedures in very high dimensions. Numerical tests show that these formulas are accurate and provide approximation of order up to dimension 108. [Copyright &y& Elsevier]

Abstract: This paper is devoted to the definition, analysis and implementation of a new type of subdivision schemes adapted to data (through a stochastic approach) and to a partition of their support. Its construction combines position-dependent multi-scale approximation (Baccou and Liandrat, 2005 [7]) and Kriging theory (Cressie, 1993 [12]). After a full convergence analysis that requires to extend classical results to this new framework, it is applied to data prediction for uni- and bi-variate problems and compared to the Lagrange interpolatory subdivision. [Copyright &y& Elsevier]

Abstract: In this paper we propose a variation of the soft-thresholding algorithm for finding sparse approximate solutions of the equation , where as the sparsity of the iterate increases the penalty function changes. In this approach, sufficiently large entries in a sparse iterate are left untouched. The advantage of this approach is that a higher regularization constant can be used, leading to a significant reduction of the total number of iterations. Numerical experiments for sparse recovery problems, also with noisy data, are included. [Copyright &y& Elsevier]

Abstract: In this paper modified variants of the sparse Fourier transform algorithms from Iwen (2010) [32] are presented which improve on the approximation error bounds of the original algorithms. In addition, simple methods for extending the improved sparse Fourier transforms to higher dimensional settings are developed. As a consequence, approximate Fourier transforms are obtained which will identify a near-optimal k-term Fourier series for any given input function, , in time (neglecting logarithmic factors). Faster randomized Fourier algorithm variants with runtime complexities that scale linearly in the sparsity parameter k are also presented. [Copyright &y& Elsevier]

Abstract: Compressive sensing (CS) has recently emerged as a framework for efficiently capturing signals that are sparse or compressible in an appropriate basis. While often motivated as an alternative to Nyquist-rate sampling, there remains a gap between the discrete, finite-dimensional CS framework and the problem of acquiring a continuous-time signal. In this paper, we attempt to bridge this gap by exploiting the Discrete Prolate Spheroidal Sequences (DPSSʼs), a collection of functions that trace back to the seminal work by Slepian, Landau, and Pollack on the effects of time-limiting and bandlimiting operations. DPSSʼs form a highly efficient basis for sampled bandlimited functions; by modulating and merging DPSS bases, we obtain a dictionary that offers high-quality sparse approximations for most sampled multiband signals. This multiband modulated DPSS dictionary can be readily incorporated into the CS framework. We provide theoretical guarantees and practical insight into the use of this dictionary for recovery of sampled multiband signals from compressive measurements. [Copyright &y& Elsevier]

Abstract: This paper introduces a fast algorithm for computing multilinear integrals which are defined through Fourier multipliers. The algorithm is based on generating a hierarchical decomposition of the summation domain into squares, constructing a low-rank approximation for the multiplier function within each square, and applying an FFT based fast convolution algorithm for the computation associated with each square. The resulting algorithm is accurate and has a linear complexity, up to logarithmic factors, with respect to the number of the unknowns in the input functions. Numerical results are presented to demonstrate the properties of this algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we prove convergence results for multiscale approximation using compactly supported radial basis functions restricted to the unit sphere, for target functions outside the reproducing kernel Hilbert space of the employed kernel. [Copyright &y& Elsevier]

Abstract: Clustering is a widely used technique in machine learning, however, relatively little research in consistency of clustering algorithms has been done so far. In this paper we investigate the consistency of the regularized spectral clustering algorithm, which has been proposed recently. It provides a natural out-of-sample extension for spectral clustering. The presence of the regularization term makes our situation different from that in previous work. Our approach is mainly an elaborate analysis of a functional named the clustering objective. Moreover, we establish a convergence rate. The rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers. Some new methods are exploited for the analysis since the underlying setting is much more complicated than usual. Some new methods are exploited for the analysis since the underlying setting is much more complicated than usual. [Copyright &y& Elsevier]

Abstract: A recurring task in image processing, approximation theory, and the numerical solution of partial differential equations is to reconstruct a piecewise-smooth real-valued function , where , from its truncated Fourier transform (its truncated spectrum). An essential step is edge detection for which a variety of one-dimensional schemes have been developed over the last few decades. Most higher-dimensional edge detection algorithms consist of applying one-dimensional detectors in each component direction in order to recover the locations in where is singular (the singular support). In this paper, we present a multidimensional algorithm which identifies the wavefront of a function from spectral data. The wavefront of f is the set of points which encode both the location of the singular points of a function and the orientation of the singularities. (Here denotes the unit sphere in N dimensions.) More precisely, is the direction of the normal line to the curve or surface of discontinuity at x. Note that the singular support is simply the projection of the wavefront onto its x-component. In one dimension, the wavefront is a subset of , and it coincides with the singular support. In higher dimensions, geometry comes into play and they are distinct. We discuss the advantages of wavefront reconstruction and indicate how it can be used for segmentation in magnetic resonance imaging (MRI). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the relationships of the newly developed continuous shearlet transform with the coorbit space theory. It turns out that all the conditions that are needed to apply the coorbit space theory can indeed be satisfied for the shearlet group. Consequently, we establish new families of smoothness spaces, the shearlet coorbit spaces. Moreover, our approach yields Banach frames for these spaces in a quite natural way. We also study the approximation power of best n-term approximation schemes and present some first numerical experiments. [Copyright &y& Elsevier]

Abstract: This paper introduces and analyzes new approximation procedures for bivariate functions. These procedures are based on an edge-adapted nonlinear reconstruction technique which is an intrinsically two-dimensional extension of the essentially non-oscillatory and subcell resolution techniques introduced in the one-dimensional setting by Harten and Osher. Edge-adapted reconstructions are tailored to piecewise smooth functions with geometrically smooth edge discontinuities, and are therefore attractive for applications such as image compression and shock computations. The local approximation order is investigated both in and in the Hausdorff distance between graphs. In particular, it is shown that for general classes of piecewise smooth functions, edge-adapted reconstructions yield multiscale representations which are optimally sparse and adaptive approximations with optimal rate of convergence, similar to curvelets decompositions for the error. [Copyright &y& Elsevier]

Abstract: Dual frames are very useful tools to reconstruct a function and have been explored in many different aspects. In this paper, we give the conditions under which a class of special weighted irregular wavelet frames could have a dual generator with a very explicit form. We also prove that when the irregular translations are changed in some admissible range, the reconstruction formula has a very small perturbation. An example is given to show the use of our main results. [Copyright &y& Elsevier]

The objective of this paper is to introduce a direct approach for generating local averaging rules for both the √ of 3 and 1-to-4 vector subdivision schemes for computer-aided design of smooth surfaces. Our innovation is to directly construct refinable bivariate spline function vectors with minimum supports and highest approximation orders on the six-directional mesh, and to compute their refinement masks which give rise to the matrix-valued coefficient stencils for the surface subdivision schemes. Both the C1-quadratic and C2-cubic spaces are studied in some detail. In particular, we show that our C2-cubic refinement mask for the 1-to-4 subdivision can be slightly modified to yield an adaptive version of Loop''s surface subdivision scheme. [Copyright &y& Elsevier]

The goal of this paper is to provide wavelet characterizations for anisotropic Besov spaces. Depending on the anisotropy, appropriate biorthogonal tensor product bases are introduced and Jackson and Bernstein estimates are proved for two-parameter families of finite-dimensional spaces. These estimates lead to characterizations for anisotropic Besov spaces by anisotropy-dependent linear approximation spaces and lead further on to interpolation and embedding results. Finally, wavelet characterizations for anisotropic Besov spaces with respect to Lp-spaces with 0