Authors:Xing Fu; Dachun Yang Pages: 1 - 37 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Xing Fu, Dachun Yang Let ( X , d , μ ) be a metric measure space of homogeneous type in the sense of R.R. Coifman and G. Weiss and H at 1 ( X ) be the atomic Hardy space. Via orthonormal bases of regular wavelets and spline functions recently constructed by P. Auscher and T. Hytönen, together with obtaining some crucial lower bounds for regular wavelets, the authors give an unconditional basis of H at 1 ( X ) and several equivalent characterizations of H at 1 ( X ) in terms of wavelets, which are proved useful.

Authors:Deguang Han; Fusheng Lv; Wenchang Sun Pages: 38 - 58 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Deguang Han, Fusheng Lv, Wenchang Sun In this paper, we study the feasibility and stability of recovering signals in finite-dimensional spaces from unordered partial frame coefficients. We prove that with an almost self-located robust frame, any signal except from a Lebesgue measure zero subset can be recovered from its unordered partial frame coefficients. However, the recovery is not necessarily stable with almost self-located robust frames. We propose a new class of frames, namely self-located robust frames, that ensures stable recovery for any input signal with unordered partial frame coefficients. In particular, the recovery is exact whenever the received unordered partial frame coefficients are noise-free. We also present some characterizations and constructions for (almost) self-located robust frames. Based on these characterizations and construction algorithms, we prove that any randomly generated frame is almost surely self-located robust. Moreover, frames generated with cube roots of different prime numbers are also self-located robust.

Authors:Jason D. McEwen; Claudio Durastanti; Yves Wiaux Pages: 59 - 88 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Jason D. McEwen, Claudio Durastanti, Yves Wiaux Scale-discretised wavelets yield a directional wavelet framework on the sphere where a signal can be probed not only in scale and position but also in orientation. Furthermore, a signal can be synthesised from its wavelet coefficients exactly, in theory and practice (to machine precision). Scale-discretised wavelets are closely related to spherical needlets (both were developed independently at about the same time) but relax the axisymmetric property of needlets so that directional signal content can be probed. Needlets have been shown to satisfy important quasi-exponential localisation and asymptotic uncorrelation properties. We show that these properties also hold for directional scale-discretised wavelets on the sphere and derive similar localisation and uncorrelation bounds in both the scalar and spin settings. Scale-discretised wavelets can thus be considered as directional needlets.

Authors:Matthieu Kowalski; Adrien Meynard; Hau-tieng Wu Pages: 89 - 122 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Matthieu Kowalski, Adrien Meynard, Hau-tieng Wu Motivated by the limitation of analyzing oscillatory signals composed of multiple components with fast-varying instantaneous frequency, we approach the time-frequency analysis problem by optimization. Based on the proposed adaptive harmonic model, the time-frequency representation of a signal is obtained by directly minimizing a functional, which involves few properties an “ideal time-frequency representation” should satisfy, for example, the signal reconstruction and concentrative time-frequency representation. FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) is applied to achieve an efficient numerical approximation of the functional. We coin the algorithm as Time-frequency bY COnvex OptimizatioN (Tycoon). The numerical results confirm the potential of the Tycoon algorithm.

Authors:Rayan Saab; Rongrong Wang; Özgür Yılmaz Pages: 123 - 143 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Rayan Saab, Rongrong Wang, Özgür Yılmaz In this paper we study the quantization stage that is implicit in any compressed sensing signal acquisition paradigm. We propose using Sigma–Delta (ΣΔ) quantization and a subsequent reconstruction scheme based on convex optimization. We prove that the reconstruction error due to quantization decays polynomially in the number of measurements. Our results apply to arbitrary signals, including compressible ones, and account for measurement noise. Additionally, they hold for sub-Gaussian (including Gaussian and Bernoulli) random compressed sensing measurements, as well as for both high bit-depth and coarse quantizers, and they extend to 1-bit quantization. In the noise-free case, when the signal is strictly sparse we prove that by optimizing the order of the quantization scheme one can obtain root-exponential decay in the reconstruction error due to quantization.

Authors:Hong Chen; Yulong Wang Pages: 144 - 164 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Hong Chen, Yulong Wang The correntropy-induced loss (C-loss) has been employed in learning algorithms to improve their robustness to non-Gaussian noise and outliers recently. Despite its success on robust learning, only little work has been done to study the generalization performance of regularized regression with the C-loss. To enrich this theme, this paper investigates a kernel-based regression algorithm with the C-loss and ℓ 1 -regularizer in data dependent hypothesis spaces. The asymptotic learning rate is established for the proposed algorithm in terms of novel error decomposition and capacity-based analysis technique. The sparsity characterization of the derived predictor is studied theoretically. Empirical evaluations demonstrate its advantages over the related approaches.

Authors:Michaël Fanuel; Carlos M. Alaíz; Ángela Fernández; Johan A.K. Suykens Pages: 189 - 199 Abstract: Publication date: January 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 1 Author(s): Michaël Fanuel, Carlos M. Alaíz, Ángela Fernández, Johan A.K. Suykens We propose a framework for the visualization of directed networks relying on the eigenfunctions of the magnetic Laplacian, called here Magnetic Eigenmaps. The magnetic Laplacian is a complex deformation of the well-known combinatorial Laplacian. Features such as density of links and directionality patterns are revealed by plotting the phases of the first magnetic eigenvectors. An interpretation of the magnetic eigenvectors is given in connection with the angular synchronization problem. Illustrations of our method are given for both artificial and real networks.

Authors:Boris Landa; Yoel Shkolnisky Pages: 381 - 403 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Boris Landa, Yoel Shkolnisky We introduce an approximation scheme for almost bandlimited functions which are sufficiently concentrated in a disk, based on their equally spaced samples on a Cartesian grid. The scheme is based on expanding the function into a series of two-dimensional prolate spheroidal wavefunctions, and estimating the expansion coefficients using the available samples. We prove that the approximate expansion coefficients have particularly simple formulas, in the form of a dot product of the available samples with samples of the basis functions. We also derive error bounds for the error incurred by approximating the expansion coefficients as well as by truncating the expansion. In particular, we derive a bound on the approximation error in terms of the assumed space/frequency concentration, and provide a simple truncation rule to control the length of the expansion and the resulting approximation error.

Authors:Mahdi Shaghaghi; Sergiy A. Vorobyov Pages: 404 - 423 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Mahdi Shaghaghi, Sergiy A. Vorobyov This paper gives the finite-length analysis of a spectrum estimation method for the case that the samples are obtained at a rate lower than the Nyquist rate. The method is referred to as the averaged correlogram for undersampled data. It is based on partitioning the spectrum into a number of segments and estimating the average power within each spectral segment. This method is able to estimate the power spectrum density of a signal from undersampled data without essentially requiring the signal to be sparse. We derive the bias and the variance of the spectrum estimator, and show that there is a tradeoff between the accuracy of the estimation, the frequency resolution, and the complexity of the estimator. A closed-form approximation of the estimation variance is derived, which clearly shows how the variance is related to different parameters. The asymptotic behavior of the estimator is also investigated, and it is proved that in the case of a white Gaussian process, this spectrum estimator is consistent. Moreover, the estimation made for different spectral segments becomes uncorrelated as the signal length tends to infinity. Finally, numerical examples and simulation results are provided, which approve the theoretical conclusions.

Authors:A. Martínez-Finkelshtein; D. Ramos-López; D.R. Iskander Pages: 424 - 448 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): A. Martínez-Finkelshtein, D. Ramos-López, D.R. Iskander We implement an efficient method of computation of two dimensional Fourier-type integrals based on approximation of the integrand by Gaussian radial basis functions, which constitute a standard tool in approximation theory. As a result, we obtain a rapidly converging series expansion for the integrals, allowing for their accurate calculation. We apply this idea to the evaluation of diffraction integrals, used for the computation of the through-focus characteristics of an optical system. We implement this method and compare its performance in terms of complexity, accuracy and execution time with several alternative approaches, especially with the extended Nijboer–Zernike theory, which is also outlined in the text for the reader's convenience. The proposed method yields a reliable and fast scheme for simultaneous evaluation of such kind of integrals for several values of the defocus parameter, as required in the characterization of the through-focus optics.

Authors:Hartmut Führ; Reihaneh Raisi Tousi Pages: 449 - 481 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Hartmut Führ, Reihaneh Raisi Tousi We consider the coorbit theory associated to a square-integrable, irreducible quasi-regular representation of a semidirect product group G = R d ⋊ H . The existence of coorbit spaces for this very general setting has been recently established, together with concrete vanishing moment criteria for analyzing vectors and atoms that can be used in the coorbit scheme. These criteria depend on fairly technical assumptions on the dual action of the dilation group, and it is one of the chief purposes of this paper to considerably simplify these assumptions. We then proceed to verify the assumptions for large classes of dilation groups, in particular for all abelian dilation groups in arbitrary dimensions, as well as a class called generalized shearlet dilation groups, containing and extending all known examples of shearlet dilation groups employed in dimensions two and higher. We explain how these groups can be systematically constructed from certain commutative associative algebras of the same dimension, and give a full list, up to conjugacy, of shearing groups in dimensions three and four. In the latter case, three previously unknown groups are found. As a result, the existence of Banach frames consisting of compactly supported wavelets, with simultaneous convergence in a whole range of coorbit spaces, is established for all groups involved.

Authors:Bernhard G. Bodmann; Nathaniel Hammen Pages: 482 - 503 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Bernhard G. Bodmann, Nathaniel Hammen The main objective of this paper is to find algorithms accompanied by explicit error bounds for phase retrieval from noisy magnitudes of frame coefficients when the underlying frame has a low redundancy. We achieve these goals with frames consisting of N = 6 d − 3 vectors spanning a d-dimensional complex Hilbert space. The two algorithms we use, phase propagation or the kernel method, are polynomial time in the dimension d. To ensure a successful approximate recovery, we assume that the noise is sufficiently small compared to the squared norm of the vector to be recovered. In this regime, we derive an explicit error bound that is inverse proportional to the signal-to-noise ratio, with a constant of proportionality that depends only on the dimension d. Properties of the reproducing kernel space of complex polynomials and of trigonometric polynomials are central in our error estimates.

Authors:Anna V. Little; Mauro Maggioni; Lorenzo Rosasco Pages: 504 - 567 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Anna V. Little, Mauro Maggioni, Lorenzo Rosasco Large data sets are often modeled as being noisy samples from probability distributions μ in R D , with D large. It has been noticed that oftentimes the support M of these probability distributions seems to be well-approximated by low-dimensional sets, perhaps even by manifolds. We shall consider sets that are locally well-approximated by k-dimensional planes, with k ≪ D , with k-dimensional manifolds isometrically embedded in R D being a special case. Samples from μ are furthermore corrupted by D-dimensional noise. Certain tools from multiscale geometric measure theory and harmonic analysis seem well-suited to be adapted to the study of samples from such probability distributions, in order to yield quantitative geometric information about them. In this paper we introduce and study multiscale covariance matrices, i.e. covariances corresponding to the distribution restricted to a ball of radius r, with a fixed center and varying r, and under rather general geometric assumptions we study how their empirical, noisy counterparts behave. We prove that in the range of scales where these covariance matrices are most informative, the empirical, noisy covariances are close to their expected, noiseless counterparts. In fact, this is true as soon as the number of samples in the balls where the covariance matrices are computed is linear in the intrinsic dimension of M . As an application, we present an algorithm for estimating the intrinsic dimension of M .

Authors:Siddhartha Satpathi; Mrityunjoy Chakraborty Pages: 568 - 576 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Siddhartha Satpathi, Mrityunjoy Chakraborty In compressive sensing, one important parameter that characterizes the various greedy recovery algorithms is the iteration bound which provides the maximum number of iterations by which the algorithm is guaranteed to converge. In this letter, we present a new iteration bound for the compressive sampling matching pursuit (CoSaMP) algorithm by certain mathematical manipulations including formulation of appropriate sufficient conditions that ensure passage of a chosen support through the two selection stages of CoSaMP, “Augment” and “Update”. Subsequently, we extend the treatment to the subspace pursuit (SP) algorithm. The proposed iteration bounds for both CoSaMP and SP algorithms are seen to be improvements over their existing counterparts, revealing that both CoSaMP and SP algorithms converge in fewer iterations than suggested by results available in literature.

Authors:Alexander Cloninger; Stefan Steinerberger Pages: 577 - 590 Abstract: Publication date: November 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 3 Author(s): Alexander Cloninger, Stefan Steinerberger Spectral embedding uses eigenfunctions of the discrete Laplacian on a weighted graph to obtain coordinates for an embedding of an abstract data set into Euclidean space. We propose a new pre-processing step of first using the eigenfunctions to simulate a low-frequency wave moving over the data and using both position as well as change in time of the wave to obtain a refined metric to which classical methods of dimensionality reduction can then applied. This is motivated by the behavior of waves, symmetries of the wave equation and the hunting technique of bats. It is shown to be effective in practice and also works for other partial differential equations – the method yields improved results even for the classical heat equation.

Authors:M. Bodner; J. Patera; M. Szajewska Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): M. Bodner, J. Patera, M. Szajewska A method for the decomposition of data functions sampled on a finite fragment of triangular lattices is described for the lattice corresponding to the simple Lie group S U ( 3 ) . The basic tile (fundamental region) of S U ( 3 ) is an equilateral triangle. The decomposition matrices refer to lattices that carry data of any density. This main result is summarized in Section 4 Theorem 2.

Authors:Andrei Osipov Pages: 173 - 211 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Andrei Osipov Evaluation of the eigenvectors of symmetric tridiagonal matrices is one of the most basic tasks in numerical linear algebra. It is a widely known fact that, in the case of well separated eigenvalues, the eigenvectors can be evaluated with high relative accuracy. Nevertheless, in general, each coordinate of the eigenvector is evaluated with only high absolute accuracy. In particular, those coordinates whose magnitude is below the machine precision are not expected to be evaluated with any accuracy whatsoever. It turns out that, under certain conditions, frequently encountered in applications, small (e.g. 10 − 50 ) coordinates of eigenvectors of symmetric tridiagonal matrices can be evaluated with high relative accuracy. In this paper, we investigate such conditions, carry out the analysis, and describe the resulting numerical schemes. While our schemes can be viewed as a modification of already existing (and well known) numerical algorithms, the related error analysis appears to be new. Our results are illustrated via several numerical examples.

Authors:M. Eren Ahsen; M. Vidyasagar Pages: 212 - 232 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): M. Eren Ahsen, M. Vidyasagar 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.

Authors:Sho Sonoda; Noboru Murata Pages: 233 - 268 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Sho Sonoda, Noboru Murata 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.

Authors:Céline Esser; Thomas Kleyntssens; Samuel Nicolay Pages: 269 - 291 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Céline Esser, Thomas Kleyntssens, Samuel Nicolay We present an implementation of a multifractal formalism based on the types of histogram of wavelet leaders. This method yields non-concave spectra and is not limited to their increasing part. We show both from the theoretical and from the applied points of view that this approach is more efficient than the wavelet-based multifractal formalisms previously introduced.

Authors:Yu Guang Wang; Quoc T. Le Gia; Ian H. Sloan; Robert S. Womersley Pages: 292 - 316 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Yu Guang Wang, Quoc T. Le Gia, Ian H. Sloan, Robert S. Womersley Spherical needlets are highly localized radial polynomials on the sphere S d ⊂ R d + 1 , d ≥ 2 , with centers at the nodes of a suitable cubature rule. The original semidiscrete spherical needlet approximation of Narcowich, Petrushev and Ward is not computable, in that the needlet coefficients depend on inner product integrals. In this work we approximate these integrals by a second quadrature rule with an appropriate degree of precision, to construct a fully discrete needlet approximation. We prove that the resulting approximation is equivalent to filtered hyperinterpolation, that is to a filtered Fourier–Laplace series partial sum with inner products replaced by appropriate cubature sums. It follows that the L p -error of discrete needlet approximation of order J for 1 ≤ p ≤ ∞ and s > d / p has for a function f in the Sobolev space W p s ( S d ) the optimal rate of convergence in the sense of optimal recovery, namely O ( 2 − J s ) . Moreover, this is achieved with a filter function that is of smoothness class C ⌊ d + 3 2 ⌋ , in contrast to the usually assumed C ∞ . A numerical experiment for a class of functions in known Sobolev smoothness classes gives L 2 errors for the fully discrete needlet approximation that are almost identical to those for the original semidiscrete needlet approximation. Another experiment uses needlets over the whole sphere for the lower levels together with high-level needlets with centers restricted to a local region. The resulting errors are reduced in the local region away from the boundary, indicating that local refinement in special regions is a promising strategy.

Authors:Say Song Goh; Tim N.T. Goodman; S.L. Lee Pages: 317 - 345 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Say Song Goh, Tim N.T. Goodman, S.L. Lee A series expansion with remainder for functions in a Sobolev space is derived in terms of the classical Bernoulli polynomials, the B-spline scale-space and the continuous wavelet transforms with the derivatives of the standardized B-splines as mother wavelets. In the limit as their orders tend to infinity, the B-splines and their derivatives converge to the Gaussian function and its derivatives respectively, the associated Bernoulli polynomials converge to the Hermite polynomials, and the corresponding series expansion is an expansion in terms of the Hermite polynomials, the Gaussian scale-space and the continuous wavelet transforms with the derivatives of the Gaussian function as mother wavelets. A similar expansion is also derived in terms of continuous wavelet transforms in which the mother wavelets are the spline framelets that approximate the derivatives of the standardized B-splines.

Authors:Lucia Morotti Pages: 354 - 369 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Lucia Morotti 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 ) ) .

Authors:Alexander Cloninger Pages: 370 - 380 Abstract: Publication date: September 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 2 Author(s): Alexander Cloninger We note that building a magnetic Laplacian from the Markov transition matrix, rather than the graph adjacency matrix, yields several benefits for the magnetic eigenmaps algorithm. The two largest benefits are that the embedding becomes more stable as a function of the rotation parameter g, and the principal eigenvector of the magnetic Laplacian now converges to the page rank of the network as a function of diffusion time. We show empirically that this normalization improves the phase and real/imaginary embeddings of the low-frequency eigenvectors of the magnetic Laplacian.

Authors:Yun-Zhang Li; Jian-Ping Zhang Abstract: Publication date: Available online 14 November 2017 Source:Applied and Computational Harmonic Analysis Author(s): Yun-Zhang Li, Jian-Ping Zhang Mixed Oblique Extension Principles (MOEP) provide an important method to construct affine dual frames from refinable functions. This paper addresses MOEP under the setting of reducing subspaces of L 2 ( R d ) . We obtain an MOEP for (non)homogeneous affine dual frames and (non)homogeneous affine Parseval frames.

Authors:Nicholas F. Marshall; Matthew J. Hirn Abstract: Publication date: Available online 7 November 2017 Source:Applied and Computational Harmonic Analysis Author(s): Nicholas F. Marshall, Matthew J. Hirn We consider a collection of n points in R d measured at m times, which are encoded in an n × d × m data tensor. Our objective is to define a single embedding of the n points into Euclidean space which summarizes the geometry as described by the data tensor. In the case of a fixed data set, diffusion maps and related graph Laplacian methods define such an embedding via the eigenfunctions of a diffusion operator constructed on the data. Given a sequence of m measurements of n points, we introduce the notion of time coupled diffusion maps which have natural geometric and probabilistic interpretations. To frame our method in the context of manifold learning, we model evolving data as samples from an underlying manifold with a time-dependent metric, and we describe a connection of our method to the heat equation on such a manifold.

Authors:Richard Mikaël Slevinsky Abstract: Publication date: Available online 7 November 2017 Source:Applied and Computational Harmonic Analysis Author(s): Richard Mikaël Slevinsky A rapid transformation is derived between spherical harmonic expansions and their analogues in a bivariate Fourier series. The change of basis is described in two steps: firstly, expansions in normalized associated Legendre functions of all orders are converted to those of order zero and one; then, these intermediate expressions are re-expanded in trigonometric form. The first step proceeds with a butterfly factorization of the well-conditioned matrices of connection coefficients. The second step proceeds with fast orthogonal polynomial transforms via hierarchically off-diagonal low-rank matrix decompositions. Total pre-computation requires at best O ( n 3 log n ) flops; and, asymptotically optimal execution time of O ( n 2 log 2 n ) is rigorously proved via connection to Fourier integral operators.

Abstract: Publication date: Available online 7 November 2017 Source:Applied and Computational Harmonic Analysis Author(s): I. Iglewska–Nowak We construct spherical wavelets based on approximate identities that are directional, i.e. not rotation-invariant, and have an adaptive angular selectivity. The problem of how to find a proper representation of distinct kinds of details of real images, ranging from highly directional to fully isotropic ones, was quite intensively studied for the case of signals over the Euclidean space. However, the present paper is the first attempt to deal with this task in the case of spherical signals. A multiselectivity scheme, similar to that proposed for R 2 -functions, is presented.

Authors:M.S. Kotzagiannidis; P.L. Dragotti Abstract: Publication date: Available online 18 October 2017 Source:Applied and Computational Harmonic Analysis Author(s): M.S. Kotzagiannidis, P.L. Dragotti With the objective of employing graphs toward a more generalized theory of signal processing, we present a novel sampling framework for (wavelet-)sparse signals defined on circulant graphs which extends basic properties of Finite Rate of Innovation (FRI) theory to the graph domain, and can be applied to arbitrary graphs via suitable approximation schemes. At its core, the introduced Graph-FRI-framework states that any K-sparse signal on the vertices of a circulant graph can be perfectly reconstructed from its dimensionality-reduced representation in the graph spectral domain, the Graph Fourier Transform (GFT), of minimum size 2K. By leveraging the recently developed theory of e-splines and e-spline wavelets on graphs, one can decompose this graph spectral transformation into the multiresolution low-pass filtering operation with a graph e-spline filter, with subsequent transformation to the spectral graph domain; this allows to infer a distinct sampling pattern, and, ultimately, the structure of an associated coarsened graph, which preserves essential properties of the original, including circularity and, where applicable, the graph generating set.

Authors:Rui Zhang; Song Li Abstract: Publication date: Available online 18 October 2017 Source:Applied and Computational Harmonic Analysis Author(s): Rui Zhang, Song Li In this paper, we present a unified analysis of RIP bounds for sparse signals recovery by using ℓ p minimization with 0 < p ≤ 1 and provide optimal RIP bounds which can guarantee sparse signals recovery via ℓ p minimization for each p ∈ ( 0 , 1 ] in both noiseless and noisy settings. It is shown that if the measurement matrix Φ satisfies the RIP condition δ 2 k < δ ( p ) , where δ ( p ) will be specified in the context, then all k-sparse signals x can be recovered stably via the constrained ℓ p minimization based on b = Φ x + z , where z is one type of noise. Furthermore, we show that for any ϵ > 0 , δ 2 k < δ ( p ) + ϵ is not sufficient to guarantee the exact recovery of all k-sparse signals. We also apply the results to the cases of low rank matrix recovery and the reconstruction of sparse vectors in terms of redundant dictionary. In particular, when p = 1 , the corresponding constant δ ( 1 ) = 2 2 , this sharp bound was shown by T. Cai and A. Zhang in their work. Thus, we give a complete characterization for optimal RIP bounds δ 2 k via ℓ p minimization for k-sparse signals recovery with 0 < p ≤ 1 . Our approaches are based on some ideas of sparse representation of a given polytope, which was firstly used by T. Cai and A. Zhang.

Authors:Charles K. Chui; H.N. Mhaskar Abstract: Publication date: Available online 16 October 2017 Source:Applied and Computational Harmonic Analysis Author(s): Charles K. Chui, H.N. Mhaskar Motivated by the interest of observing the growth of cancer cells among normal living cells and exploring how galaxies and stars are truly formed, the objective of this paper is to introduce a rigorous and effective method for counting point-masses, determining their spatial locations, and computing their attributes. Based on computation of Hermite moments that are Fourier-invariant, our approach facilitates the processing of both spatial and Fourier data in any dimension.

Authors:M.S. Kotzagiannidis; P.L. Dragotti Abstract: Publication date: Available online 14 October 2017 Source:Applied and Computational Harmonic Analysis Author(s): M.S. Kotzagiannidis, P.L. Dragotti We present novel families of wavelets and associated filterbanks for the analysis and representation of functions defined on circulant graphs. In this work, we leverage the inherent vanishing moment property of the circulant graph Laplacian operator, and by extension, the e-graph Laplacian, which is established as a parameterization of the former with respect to the degree per node, for the design of vertex-localized and critically-sampled higher-order graph (e-)spline wavelet filterbanks, which can reproduce and annihilate classes of (exponential) polynomial signals on circulant graphs. In addition, we discuss similarities and analogies of the detected properties and resulting constructions with splines and spline wavelets in the Euclidean domain. Ultimately, we consider generalizations to arbitrary graphs in the form of graph approximations, with focus on graph product decompositions. In particular, we proceed to show how the use of graph products facilitates a multi-dimensional extension of the proposed constructions and properties.

Authors:Galatia Cleanthous; Athanasios Georgiadis Morten Nielsen Abstract: Publication date: Available online 9 October 2017 Source:Applied and Computational Harmonic Analysis Author(s): Galatia Cleanthous, Athanasios G. Georgiadis, Morten Nielsen Anisotropic homogeneous mixed-norm Besov and Triebel-Lizorkin spaces are introduced and their properties are explored. A discrete adapted φ-transform decomposition is obtained. An associated class of almost diagonal operators is introduced and a boundedness result for such operators is obtained. Molecular decompositions for all the considered spaces are derived with the help of the algebra of almost diagonal operators. As an application, we obtain boundedness results on the considered spaces for Fourier multipliers and for pseudodifferential operators with suitable adapted homogeneous symbols using the molecular decomposition theory.

Authors:Robert Dahl Jacobsen; Jesper Møller; Morten Nielsen; Morten Grud Rasmussen Abstract: Publication date: Available online 2 October 2017 Source:Applied and Computational Harmonic Analysis Author(s): Robert Dahl Jacobsen, Jesper Møller, Morten Nielsen, Morten Grud Rasmussen Generalized sampling is a mathematical technique for obtaining approximations of signals with respect to different representations in a numerically stable manner. This can for example be relevant in processing MRI images, where hardware often enforces initial frequency measurements, but where a wavelet basis may be better suited for representing the image. Recently the theory of generalized sampling was extended to work with arbitrary patterns in R d . In this article we investigate how the choice of the probability distribution generating random sampling schemes in R 2 affects the numerical stability of generalized sampling.

Authors:M. Fanuel; J.A.K. Suykens Abstract: Publication date: Available online 20 September 2017 Source:Applied and Computational Harmonic Analysis Author(s): M. Fanuel, J.A.K. Suykens Deformations of the combinatorial Laplacian are proposed, which generalize several existing Laplacians. As particular cases of this construction, the dilation Laplacians are shown to be useful tools for ranking in directed networks of pairwise comparisons. In the case of a connected graph, the entries of the eigenvector of the dilation Laplacians with the smallest eigenvalue have all the same sign, and provide directly a ranking score of its nodes. The ranking method, phrased in terms of a group synchronization problem, is applied to artificial and real data, and its performance is compared with other ranking strategies. A main feature of this approach is the presence of a deformation parameter enabling the emphasis of the top-k objects in the ranking. Furthermore, inspired by these results, a family of random walks interpolating between the undirected random walk and the Pagerank random walk is also proposed.

Authors:Dimitrios Giannakis Abstract: Publication date: Available online 15 September 2017 Source:Applied and Computational Harmonic Analysis Author(s): Dimitrios Giannakis We develop a framework for dimension reduction, mode decomposition, and nonparametric forecasting of data generated by ergodic dynamical systems. This framework is based on a representation of the Koopman and Perron–Frobenius groups of unitary operators in a smooth orthonormal basis of the L 2 space of the dynamical system, acquired from time-ordered data through the diffusion maps algorithm. Using this representation, we compute Koopman eigenfunctions through a regularized advection-diffusion operator, and employ these eigenfunctions in dimension reduction maps with projectible dynamics and high smoothness for the given observation modality. In systems with pure point spectra, we construct a decomposition of the generator of the Koopman group into mutually commuting vector fields that transform naturally under changes of observation modality, which we reconstruct in data space through a representation of the pushforward map in the Koopman eigenfunction basis. We also establish a correspondence between Koopman operators and Laplace-Beltrami operators constructed from data in Takens delay-coordinate space, and use this correspondence to provide an interpretation of diffusion-mapped delay coordinates for this class of systems. Moreover, we take advantage of a special property of the Koopman eigenfunction basis, namely that the basis elements evolve as simple harmonic oscillators, to build nonparametric forecast models for probability densities and observables. In systems with more complex spectral behavior, including mixing systems, we develop a method inspired from time change in dynamical systems to transform the generator to a new operator with potentially improved spectral properties, and use that operator for vector field decomposition and nonparametric forecasting.

Authors:Gregory Beylkin; Lucas Monzón; Ignas Satkauskas Abstract: Publication date: Available online 5 September 2017 Source:Applied and Computational Harmonic Analysis Author(s): Gregory Beylkin, Lucas Monzón, Ignas Satkauskas We introduce a new approximate multiresolution analysis (MRA) using a single Gaussian as the scaling function, which we call Gaussian MRA (GMRA). As an initial application, we employ this new tool to accurately and efficiently compute the probability density function (PDF) of the product of independent random variables. In contrast with Monte-Carlo (MC) type methods (the only other universal approach known to address this problem), our method not only achieves accuracies beyond the reach of MC but also produces a PDF expressed as a Gaussian mixture, thus allowing for further efficient computations. We also show that an exact MRA corresponding to our GMRA can be constructed for a matching user-selected accuracy.

Authors:Michael Wilson Abstract: Publication date: Available online 4 September 2017 Source:Applied and Computational Harmonic Analysis Author(s): Michael Wilson We show that, when wavelets in almost-orthogonal expansions of linear operators are replaced by fine dyadic discretizations, the resulting approximations are (in the L 2 → L 2 sense) close to the original operators and that these discretizations are stable with respect to small errors in translation and dilation.

Authors:A. Aldroubi; A. Sekmen; A.B. Koku; A.F. Cakmak Abstract: Publication date: Available online 4 September 2017 Source:Applied and Computational Harmonic Analysis Author(s): A. Aldroubi, A. Sekmen, A.B. Koku, A.F. Cakmak This paper presents a framework for finding similarity matrices for the segmentation of data W = [ w 1 ⋯ w N ] ⊂ R D drawn from a union U = ⋃ i = 1 M S i of independent subspaces { S i } i = 1 M of dimensions { d i } i = 1 M . It is shown that any factorization of W = B P , where columns of B form a basis for data W and they also come from U , can be used to produce a similarity matrix Ξ W . In other words, Ξ W ( i , j ) ≠ 0 , when the columns w i and w j of W come from the same subspace, and Ξ W ( i , j ) = 0 , when the columns w i and w j of W come from different subspaces. Furthermore, Ξ W = Q d m a x , where d m a x = max { d i } i = 1 M and Q ∈ R N × N with Q ( i , j ) = P T P ( i , j ) . It is shown that a similarity matrix obtained from the reduced row echelon form of W is a special case of the theory. It is also proven that the Shape Interaction Matrix defined as V V T , where W = U Σ V T is the skinny singular value decomposition of W, is not necessarily a similarity matrix. But, taking powers of its absolute value always generates a similarity matrix. An interesting finding of this research is that a similarity matrix can be obtained using a skeleton decomposition of W. First, a square sub-matrix A ∈ R r × PubDate: 2017-09-08T02:02:44Z DOI: 10.1016/j.acha.2017.08.006

Authors:Gal Mishne; Uri Shaham; Alexander Cloninger; Israel Cohen Abstract: Publication date: Available online 31 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Gal Mishne, Uri Shaham, Alexander Cloninger, Israel Cohen Non-linear manifold learning enables high-dimensional data analysis, but requires out-of-sample-extension methods to process new data points. In this paper, we propose a manifold learning algorithm based on deep learning to create an encoder, which maps a high-dimensional dataset to its low-dimensional embedding, and a decoder, which takes the embedded data back to the high-dimensional space. Stacking the encoder and decoder together constructs an autoencoder, which we term a diffusion net, that performs out-of-sample-extension as well as outlier detection. We introduce new neural net constraints for the encoder, which preserve the local geometry of the points, and we prove rates of convergence for the encoder. Also, our approach is efficient in both computational complexity and memory requirements, as opposed to previous methods that require storage of all training points in both the high-dimensional and the low-dimensional spaces to calculate the out-of-sample-extension and the pre-image of new points.

Authors:Andrew W. Long; Andrew L. Ferguson Abstract: Publication date: Available online 31 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Andrew W. Long, Andrew L. Ferguson Diffusion maps are a nonlinear manifold learning technique based on harmonic analysis of a diffusion process over the data. Out-of-sample extensions with computational complexity O ( N ) , where N is the number of points comprising the manifold, frustrate applications to online learning applications requiring rapid embedding of high-dimensional data streams. We propose landmark diffusion maps (L-dMaps) to reduce the complexity to O ( M ) , where M ≪ N is the number of landmark points selected using pruned spanning trees or k-medoids. Offering ( N / M ) speedups in out-of-sample extension, L-dMaps enable the application of diffusion maps to high-volume and/or high-velocity streaming data. We illustrate our approach on three datasets: the Swiss roll, molecular simulations of a C24H50 polymer chain, and biomolecular simulations of alanine dipeptide. We demonstrate up to 50-fold speedups in out-of-sample extension for the molecular systems with less than 4% errors in manifold reconstruction fidelity relative to calculations over the full dataset.

Authors:Wojciech Czaja; Weilin Li Abstract: Publication date: Available online 23 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Wojciech Czaja, Weilin Li In this paper we address the problem of constructing a feature extractor which combines Mallat's scattering transform framework with time-frequency (Gabor) representations. To do this, we introduce a class of frames, called uniform covering frames, which includes a variety of semi-discrete Gabor systems. Incorporating a uniform covering frame with a neural network structure yields the Fourier scattering transform S F and the truncated Fourier scattering transform. We prove that S F propagates energy along frequency decreasing paths and its energy decays exponentially as a function of the depth. These quantitative estimates are fundamental in showing that S F satisfies the typical scattering transform properties, and in controlling the information loss due to width and depth truncation. We introduce the fast Fourier scattering transform algorithm, and illustrate the algorithm's performance. The time-frequency covering techniques developed in this paper are flexible and give insight into the analysis of scattering transforms.

Authors:Joel Laity; Barak Shani Abstract: Publication date: Available online 23 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Joel Laity, Barak Shani A function f : Z n → C can be represented as a linear combination f ( x ) = ∑ α ∈ Z n f ˆ ( α ) χ α , n ( x ) where f ˆ is the (discrete) Fourier transform of f. Clearly, the basis { χ α , n ( x ) : = exp ( 2 π i α x / n ) } depends on the value n. We show that if f has “large” Fourier coefficients, then the function f ˜ : Z m → C , given by f ˜ ( x ) = { f ( x ) when 0 ≤ x < min ( n , m ) , 0 otherwise , also has “large” coefficients. Moreover, they are all contained in a “small” interval around ⌊ m n α ⌉ for each α ∈ Z n such that f ˆ ( α ) is large. One can use this result to recover the large Fourier coefficients of a function f by redefining it on a convenient domain. One can also use this result to reprove a result by Morillo and Ràfols: single-bit functions, defined over any domain, are Fourier concentrated.

Authors:Johannes Keller Abstract: Publication date: Available online 18 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Johannes Keller Wigner functions generically attain negative values and hence are not probability densities. We prove an asymptotic expansion of Wigner functions in terms of Hermite spectrograms, which are probability densities. The expansion provides exact formulas for the quantum expectations of polynomial observables. In the high frequency regime it allows to approximate quantum expectation values up to any order of accuracy in the high frequency parameter. We present a Markov Chain Monte Carlo method to sample from the new densities and illustrate our findings by numerical experiments.

Authors:Cheng Cheng; Yingchun Jiang; Qiyu Sun Abstract: Publication date: Available online 14 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Cheng Cheng, Yingchun Jiang, Qiyu Sun A spatially distributed network contains a large amount of agents with limited sensing, data processing, and communication capabilities. Recent technological advances have opened up possibilities to deploy spatially distributed networks for signal sampling and reconstruction. In this paper, we introduce a graph structure for a distributed sampling and reconstruction system by coupling agents in a spatially distributed network with innovative positions of signals. A fundamental problem in sampling theory is the robustness of signal reconstruction in the presence of sampling noises. For a distributed sampling and reconstruction system, the robustness could be reduced to the stability of its sensing matrix. In this paper, we split a distributed sampling and reconstruction system into a family of overlapping smaller subsystems, and we show that the stability of the sensing matrix holds if and only if its quasi-restrictions to those subsystems have uniform stability. This new stability criterion could be pivotal for the design of a robust distributed sampling and reconstruction system against supplement, replacement and impairment of agents, as we only need to check the uniform stability of affected subsystems. In this paper, we also propose an exponentially convergent distributed algorithm for signal reconstruction, that provides a suboptimal approximation to the original signal in the presence of bounded sampling noises.

Authors:Hui Ji; Zuowei Shen; Yufei Zhao Abstract: Publication date: Available online 10 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Hui Ji, Zuowei Shen, Yufei Zhao Gabor frames, especially digital Gabor filters, have long been known as indispensable tools for local time–frequency analysis of discrete signals. With strong orientation selectivity, tensor products discrete (tight) Gabor frames also see their applications in image analysis and restoration. However, the lack of multi-scale structures existing in MRA-based wavelet (tight) frames makes discrete Gabor frames less effective on modeling local structures of signals with varying sizes. Indeed, historically speaking, it was the motivation of studying wavelet systems. By applying the unitary extension principle on some most often seen digital Gabor filters (e.g. local discrete Fourier transform and discrete Cosine transform), we are surprised to find out that these digital filter banks generate MRA-based wavelet tight frames in square integrable function space, and the corresponding refinable functions and wavelets can be explicitly given. In other words, the discrete tight frames associated with these digital Gabor filters can be used as the filter banks of MRA wavelet tight frames, which introduce both multi-scale structures and fast cascade implementation of discrete signal decomposition/reconstruction. Discrete tight frames generated by such filters with both wavelet and Gabor structures can see their potential applications in image processing and recovery.