Authors:Roy R. Lederman; Ronen Talmon Pages: 509 - 536 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Roy R. Lederman, Ronen Talmon One of the challenges in data analysis is to distinguish between different sources of variability manifested in data. In this paper, we consider the case of multiple sensors measuring the same physical phenomenon, such that the properties of the physical phenomenon are manifested as a hidden common source of variability (which we would like to extract), while each sensor has its own sensor-specific effects (hidden variables which we would like to suppress); the relations between the measurements and the hidden variables are unknown. We present a data-driven method based on alternating products of diffusion operators and show that it extracts the common source of variability. Moreover, we show that it extracts the common source of variability in a multi-sensor experiment as if it were a standard manifold learning algorithm used to analyze a simple single-sensor experiment, in which the common source of variability is the only source of variability.

Authors:Uri Shaham; Alexander Cloninger; Ronald R. Coifman Pages: 537 - 557 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Uri Shaham, Alexander Cloninger, Ronald R. Coifman We discuss approximation of functions using deep neural nets. Given a function f on a d-dimensional manifold Γ ⊂ R m , we construct a sparsely-connected depth-4 neural network and bound its error in approximating f. The size of the network depends on dimension and curvature of the manifold Γ, the complexity of f, in terms of its wavelet description, and only weakly on the ambient dimension m. Essentially, our network computes wavelet functions, which are computed from Rectified Linear Units (ReLU).

Authors:Alessandro Cardinali; Guy P. Nason Pages: 558 - 583 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Alessandro Cardinali, Guy P. Nason Methods designed for second-order stationary time series can be misleading when applied to nonstationary series, often resulting in inaccurate models and poor forecasts. Hence, testing time series stationarity is important especially with the advent of the ‘data revolution’ and the recent explosion in the number of nonstationary time series analysis tools. Most existing stationarity tests rely on a single basis. We propose new tests that use nondecimated basis libraries which permit discovery of a wider range of nonstationary behaviours, with greater power whilst preserving acceptable statistical size. Our tests work with a wide range of time series including those whose marginal distributions possess heavy tails. We provide freeware R software that implements our tests and a range of graphical tools to identify the location and duration of nonstationarities. Theoretical and simulated power calculations show the superiority of our wavelet packet approach in a number of important situations and, hence, we suggest that the new tests are useful additions to the analyst's toolbox.

Authors:William Leeb Pages: 584 - 610 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): William Leeb This paper develops a theory of harmonic analysis on spaces with tree metrics, extending previous work in this direction by Gavish, Nadler and Coifman (2010) [30] and Gavish and Coifman (2011, 2012) [28,29]. We show how a natural system of martingales and martingale differences induced by a partition tree leads to simple and effective characterizations of the Lipschitz norm and its dual for functions on a single tree metric space. The restrictions we place on the tree metrics are far more general than those considered in previous work. As the dual norm is equal to the Earth Mover's Distance (EMD) between two probability distributions, we recover a simple formula for EMD with respect to tree distances presented by Charikar (2002) [36]. We also consider the situation where an arbitrary metric is approximated by the average of a family of dominating tree metrics. We show that the Lipschitz norm and its dual for the tree metrics can be combined to yield an approximation to the corresponding norms for the underlying metric. The main contributions of this paper, however, are the generalizations of the aforementioned results to the setting of the product of two or more tree metric spaces. For functions on a product space, the notion of regularity we consider is not the Lipschitz condition, but rather the mixed Lipschitz condition that controls the size of a function's mixed difference quotient. This condition is extremely natural for datasets that can be described as a product of metric spaces, such as word-document databases. We develop effective formulas for norms equivalent to the mixed Lipschitz norm and its dual, and extend our results on combining pairs of trees.

Authors:H.N. Mhaskar Pages: 611 - 644 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): H.N. Mhaskar We present a general framework for studying harmonic analysis of functions in the settings of various emerging problems in the theory of diffusion geometry. The starting point of the now classical diffusion geometry approach is the construction of a kernel whose discretization leads to an undirected graph structure on an unstructured data set. We study the question of constructing such kernels for directed graph structures, and argue that our construction is essentially the only way to do so using discretizations of kernels. We then use our previous theory to develop harmonic analysis based on the singular value decomposition of the resulting non-self-adjoint operators associated with the directed graph. Next, we consider the question of how functions defined on one space evolve to another space in the paradigm of changing data sets recently introduced by Coifman and Hirn. While the approach of Coifman and Hirn requires that the points on one space should be in a known one-to-one correspondence with the points on the other, our approach allows the identification of only a subset of landmark points. We introduce a new definition of distance between points on two spaces, construct localized kernels based on the two spaces and certain interaction parameters, and study the evolution of smoothness of a function on one space to its lifting to the other space via the landmarks. We develop novel mathematical tools that enable us to study these seemingly different problems in a unified manner.

Authors:Jun Lai; Shidong Jiang Pages: 645 - 664 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Jun Lai, Shidong Jiang We present a second kind integral equation (SKIE) formulation for calculating the electromagnetic modes of optical waveguides, where the unknowns are only on material interfaces. The resulting numerical algorithm can handle optical waveguides with a large number of inclusions of arbitrary irregular cross section. It is capable of finding the bound, leaky, and complex modes for optical fibers and waveguides including photonic crystal fibers (PCF), dielectric fibers and waveguides. Most importantly, the formulation is well conditioned even in the case of nonsmooth geometries. Our method is highly accurate and thus can be used to calculate the propagation loss of the electromagnetic modes accurately, which provides the photonics industry a reliable tool for the design of more compact and efficient photonic devices. We illustrate and validate the performance of our method through extensive numerical studies and by comparison with semi-analytical results and previously published results.

Authors:Pengwen Chen; Albert Fannjiang Pages: 665 - 699 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Pengwen Chen, Albert Fannjiang The Fourier-domain Douglas–Rachford (FDR) algorithm is analyzed for phase retrieval with a single random mask. Since the uniqueness of phase retrieval solution requires more than a single oversampled coded diffraction pattern, the extra information is imposed in either of the following forms: 1) the sector condition on the object; 2) another oversampled diffraction pattern, coded or uncoded. For both settings, the uniqueness of projected fixed point is proved and for setting 2) the local, geometric convergence is derived with a rate given by a spectral gap condition. Numerical experiments demonstrate global, power-law convergence of FDR from arbitrary initialization for both settings as well as for 3 or more coded diffraction patterns without oversampling. In practice, the geometric convergence can be recovered from the power-law regime by a simple projection trick, resulting in highly accurate reconstruction from generic initialization.

Authors:Joel A. Tropp Pages: 700 - 736 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Joel A. Tropp Matrix concentration inequalities give bounds for the spectral-norm deviation of a random matrix from its expected value. These results have a weak dimensional dependence that is sometimes, but not always, necessary. This paper identifies one of the sources of the dimensional term and exploits this insight to develop sharper matrix concentration inequalities. In particular, this analysis delivers two refinements of the matrix Khintchine inequality that use information beyond the matrix variance to improve the dimensional dependence.

Authors:Yingzhou Li; Haizhao Yang; Lexing Ying Pages: 737 - 758 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Yingzhou Li, Haizhao Yang, Lexing Ying This paper introduces the multidimensional butterfly factorization as a data-sparse representation of multidimensional kernel matrices that satisfy the complementary low-rank property. This factorization approximates such a kernel matrix of size N × N with a product of O ( log N ) sparse matrices, each of which contains O ( N ) nonzero entries. We also propose efficient algorithms for constructing this factorization when either (i) a fast algorithm for applying the kernel matrix and its adjoint is available or (ii) every entry of the kernel matrix can be evaluated in O ( 1 ) operations. For the kernel matrices of multidimensional Fourier integral operators, for which the complementary low-rank property is not satisfied due to a singularity at the origin, we extend this factorization by combining it with either a polar coordinate transformation or a multiscale decomposition of the integration domain to overcome the singularity. Numerical results are provided to demonstrate the efficiency of the proposed algorithms.

Authors:Carmeline J. Dsilva; Ronen Talmon; Ronald R. Coifman; Ioannis G. Kevrekidis Pages: 759 - 773 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Carmeline J. Dsilva, Ronen Talmon, Ronald R. Coifman, Ioannis G. Kevrekidis Nonlinear manifold learning algorithms, such as diffusion maps, have been fruitfully applied in recent years to the analysis of large and complex data sets. However, such algorithms still encounter challenges when faced with real data. One such challenge is the existence of “repeated eigendirections,” which obscures the detection of the true dimensionality of the underlying manifold and arises when several embedding coordinates parametrize the same direction in the intrinsic geometry of the data set. We propose an algorithm, based on local linear regression, to automatically detect coordinates corresponding to repeated eigendirections. We construct a more parsimonious embedding using only the eigenvectors corresponding to unique eigendirections, and we show that this reduced diffusion maps embedding induces a metric which is equivalent to the standard diffusion distance. We first demonstrate the utility and flexibility of our approach on synthetic data sets. We then apply our algorithm to data collected from a stochastic model of cellular chemotaxis, where our approach for factoring out repeated eigendirections allows us to detect changes in dynamical behavior and the underlying intrinsic system dimensionality directly from data.

Authors:Alexander Cloninger; Ronald R. Coifman; Nicholas Downing; Harlan M. Krumholz Pages: 774 - 785 Abstract: Publication date: May 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 3 Author(s): Alexander Cloninger, Ronald R. Coifman, Nicholas Downing, Harlan M. Krumholz In this paper, we build an organization of high-dimensional datasets that cannot be cleanly embedded into a low-dimensional representation due to missing entries and a subset of the features being irrelevant to modeling functions of interest. Our algorithm begins by defining coarse neighborhoods of the points and defining an expected empirical function value on these neighborhoods. We then generate new non-linear features with deep net representations tuned to model the approximate function, and re-organize the geometry of the points with respect to the new representation. Finally, the points are locally z-scored to create an intrinsic geometric organization which is independent of the parameters of the deep net, a geometry designed to assure smoothness with respect to the empirical function. We examine this approach on data from the Center for Medicare and Medicaid Services Hospital Quality Initiative, and generate an intrinsic low-dimensional organization of the hospitals that is smooth with respect to an expert driven function of quality.

Authors:I. Iglewska-Nowak Pages: 201 - 229 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): I. Iglewska-Nowak Directional Poisson wavelets, being directional derivatives of Poisson kernel, are introduced on n-dimensional spheres. It is shown that, slightly modified and together with another wavelet family, they are an admissible wavelet pair according to the definition derived from the theory of approximate identities. We investigate some of the properties of directional Poisson wavelets, such as recursive formulae for their Fourier coefficients or explicit representations as functions of spherical variables (for some of the wavelets). We derive also an explicit formula for their Euclidean limits.

Authors:Elena Cordero; Maurice de Gosson; Fabio Nicola Pages: 230 - 245 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Elena Cordero, Maurice de Gosson, Fabio Nicola One of the most popular time–frequency representations is certainly the Wigner distribution. To reduce the interferences coming from its quadratic nature, several related distributions have been proposed, among which is the so-called Born–Jordan distribution. It is well known that in the Born–Jordan distribution the ghost frequencies are in fact damped quite well, and the noise is in general reduced. However, the horizontal and vertical directions escape from this general smoothing effect, so that the interferences arranged along these directions are in general kept. Whereas these features are graphically evident on examples and heuristically well understood in the engineering community, there is no at present mathematical explanation of these phenomena, valid for general signals in L 2 and, more in general, in the space S ′ of temperate distributions. In the present note we provide such a rigorous study using the notion of wave-front set of a distribution. We use techniques from Time–frequency Analysis, such as the modulation and Wiener amalgam spaces, and also results of microlocal regularity of linear partial differential operators.

Authors:Gil Shabat; Yaniv Shmueli; Yariv Aizenbud; Amir Averbuch Pages: 246 - 272 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Gil Shabat, Yaniv Shmueli, Yariv Aizenbud, Amir Averbuch Randomized algorithms play a central role in low rank approximations of large matrices. In this paper, the scheme of the randomized SVD is extended to a randomized LU algorithm. Several error bounds are introduced, that are based on recent results from random matrix theory related to subgaussian matrices. The bounds also improve the existing bounds of already known randomized SVD algorithm. The algorithm is fully parallelized and thus can utilize efficiently GPUs without any CPU–GPU data transfer. Numerical examples, which illustrate the performance of the algorithm and compare it to other decomposition methods, are presented.

Authors:Sheng-Chun Yang; Hu-Jun Qian; Zhong-Yuan Lu Pages: 273 - 293 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Sheng-Chun Yang, Hu-Jun Qian, Zhong-Yuan Lu An efficient calculation of NFFT (nonequispaced fast Fourier transforms) is always a challenging task in a variety of application areas, from medical imaging to radio astronomy to chemical simulation. In this article, a new theoretical derivation is proposed for NFFT based on gridding algorithm and new strategies are proposed for the implementation of both forward NFFT and its inverse on both CPU and GPU. The GPU-based version, namely CUNFFT, adopts CUDA (Compute Unified Device Architecture) technology, which supports a fine-grained parallel computing scheme. The approximation errors introduced in the algorithm are discussed with respect to different window functions. Finally, benchmark calculations are executed to illustrate the accuracy and performance of NFFT and CUNFFT. The results show that CUNFFT is not only with high accuracy, but also substantially faster than conventional NFFT on CPU.

Authors:Douglas P. Hardin; Michael C. Northington; Alexander M. Powell Pages: 294 - 311 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Douglas P. Hardin, Michael C. Northington, Alexander M. Powell A sharp version of the Balian–Low theorem is proven for the generators of finitely generated shift-invariant spaces. If generators { f k } k = 1 K ⊂ L 2 ( R d ) are translated along a lattice to form a frame or Riesz basis for a shift-invariant space V, and if V has extra invariance by a suitable finer lattice, then one of the generators f k must satisfy ∫ R d x f k ( x ) 2 d x = ∞ , namely, f k ˆ ∉ H 1 / 2 ( R d ) . Similar results are proven for frames of translates that are not Riesz bases without the assumption of extra lattice invariance. The best previously existing results in the literature give a notably weaker conclusion using the Sobolev space H d / 2 + ϵ ( R d ) ; our results provide an absolutely sharp improvement with H 1 / 2 ( R d ) . Our results are sharp in the sense that H 1 / 2 ( R d ) cannot be replaced by H s ( R d ) for any s < 1 / 2 .

Authors:James Bremer Pages: 312 - 349 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): James Bremer We describe an algorithm for the numerical solution of second order linear ordinary differential equations in the high-frequency regime. It is based on the recent observation that solutions of equations of this type can be accurately represented using nonoscillatory phase functions. Unlike standard solvers for ordinary differential equations, the running time of our algorithm is independent of the frequency of oscillation of the solutions. We illustrate this and other properties of the method with several numerical experiments.

Authors:D.W. Pravica; N. Randriampiry; M.J. Spurr Pages: 350 - 413 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): D.W. Pravica, N. Randriampiry, M.J. Spurr For q > 1 , the nth order q-advanced spherical Bessel functions of the first kind, j n ( q ; t ) , are introduced. Smooth perturbations, H q ( ω ) , of the Haar wavelet are derived. The inverse Fourier transforms F − 1 [ j n ( q ; t ) ] ( ω ) are expressed in terms of the Jacobi theta function and are shown to give genesis to the q-advanced Legendre polynomials P ˜ n ( q ; ω ) . The wavelet F − 1 [ sin ( t ) j 0 ( q ; t ) ] ( ω ) is studied and shown to generate H q ( ω ) . For each n ≥ 1 , F − 1 [ j n ( q ; t ) ] ( ω ) is shown to be a Schwartz wavelet with vanishing jth moments for 0 ≤ j ≤ n − 1 and non-vanishing nth moment. Wavelet frame properties are developed. The family { 2 j / 2 H q ( 2 j ω − k ) j , k ∈ Z } is seen to be a nearly orthonormal frame for L 2 ( R ) and a perturbation of the Haar basis. The corresponding multiplicatively advanced differential equations (MADEs) satisfied by these new functions are presented. As the parameter q → 1 + , convergence of the q-advanced functions to their classical counterparts is shown. A q-Wallis formula is given. Symmetry of the Jacobi theta function is shown to preclude Gibb's type phenomena. A Schwartz function with lower moments vanishing is shown to be a mother wavelet for a frame generating L 2 ( R ) .

Authors:Kenji Nakahira; Atsushi Miyamoto Pages: 414 - 445 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Kenji Nakahira, Atsushi Miyamoto Wavelets on graphs have been studied for the past few years, and in particular, several approaches have been proposed to design wavelet transforms on hierarchical graphs. Although such methods are computationally efficient and easy to implement, their frames are highly restricted. In this paper, we propose a general framework for the design of wavelet transforms on hierarchical graphs. Our design is guaranteed to be a Parseval tight frame, which preserves the l 2 norm of any input signals. To demonstrate the potential usefulness of our approach, we perform several experiments, in which we learn a wavelet frame based on our framework, and show, in inpainting experiments, that it performs better than a Haar-like hierarchical wavelet transform and a learned treelet. We also show with category theory that the algebraic properties of the proposed transform have a strong relationship with those of the hierarchical graph that represents the structure of the given data.

Authors:Gilles Puy; Nicolas Tremblay; Rémi Gribonval; Pierre Vandergheynst Pages: 446 - 475 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Gilles Puy, Nicolas Tremblay, Rémi Gribonval, Pierre Vandergheynst We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than O ( k log ( k ) ) measurements are sufficient to ensure an accurate and stable recovery of all k-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques.

Authors:Matthew Fickus; John Jasper; Dustin G. Mixon; Jesse D. Peterson; Cody E. Watson Pages: 476 - 496 Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Matthew Fickus, John Jasper, Dustin G. Mixon, Jesse D. Peterson, Cody E. Watson An equiangular tight frame (ETF) is a set of unit vectors whose coherence achieves the Welch bound, and so is as incoherent as possible. Though they arise in many applications, only a few methods for constructing them are known. Motivated by the connection between real ETFs and graph theory, we introduce the notion of ETFs that are symmetric about their centroid. We then discuss how well-known constructions, such as harmonic ETFs and Steiner ETFs, can have centroidal symmetry. Finally, we establish a new equivalence between centroid-symmetric real ETFs and certain types of strongly regular graphs (SRGs). Together, these results give the first proof of the existence of certain SRGs, as well as the disproofs of the existence of others.

Authors:Mingjuan Chen; Baoxiang Wang; Shuxia Wang; M.W. Wong Abstract: Publication date: Available online 24 April 2018 Source:Applied and Computational Harmonic Analysis Author(s): Mingjuan Chen, Baoxiang Wang, Shuxia Wang, M.W. Wong Using the local time-frequency analysis techniques, we obtain an equivalent norm on modulation spaces. Secondly, applying this equivalent norm, we consider the Cauchy problem for the dissipative evolutionary pseudo-differential equation ∂ t u + A ( x , D ) u = F ( ( ∂ x α u ) α ⩽ κ ) , u ( 0 , x ) = u 0 ( x ) , where A ( x , D ) is a dissipative pseudo-differential operator and F ( z ) is a multi-polynomial. We will develop the uniform decomposition techniques in both physical and frequency spaces to study its local well posedness in modulation spaces M p , q s and in Sobolev spaces H s . Moreover, the local solution can be extended to a global one in L 2 and in H s ( s > κ + d / 2 ) for certain nonlinearities.

Authors:Xiuyuan Cheng; Manas Rachh; Stefan Steinerberger Abstract: Publication date: Available online 17 April 2018 Source:Applied and Computational Harmonic Analysis Author(s): Xiuyuan Cheng, Manas Rachh, Stefan Steinerberger We study directed, weighted graphs G = ( V , E ) and consider the (not necessarily symmetric) averaging operator ( L u ) ( i ) = − ∑ j ∼ i p i j ( u ( j ) − u ( i ) ) , where p i j are normalized edge weights. Given a vertex i ∈ V , we define the diffusion distance to a set B ⊂ V as the smallest number of steps d B ( i ) ∈ N required for half of all random walks started in i and moving randomly with respect to the weights p i j to visit B within d B ( i ) steps. Our main result is that the eigenfunctions interact nicely with this notion of distance. In particular, if u satisfies L u = λ u on V and ε > 0 is so large that B = { i ∈ V : − ε ≤ u ( i ) ≤ ε } ≠ ∅ , then, for all i ∈ V , d B ( i ) log ( 1 1 − λ ) ≥ log ( u ( i ) ‖ u ‖ L ∞ ) − log ( 1 2 + ε ) . d B ( i ) is a remarkably good approximation of u in the sense of having very high correlation. The result implies that the classical one-dimensional spectral embedding preserves particular aspects of geometry in the presence of clustered data. We also give a continuous variant of the result which has a connection to the hot spots conjecture.

Authors:Ole Christensen; Marzieh Hasannasab Abstract: Publication date: Available online 17 April 2018 Source:Applied and Computational Harmonic Analysis Author(s): Ole Christensen, Marzieh Hasannasab Motivated by recent progress in dynamical sampling we prove that every frame which is norm-bounded below can be represented as a finite union of sequences { ( T j ) n φ j } n = 0 ∞ , j = 1 , … , J for some bounded operators T j and elements φ j in the underlying Hilbert space. The result is optimal, in the sense that it turns out to be problematic to replace the collection of generators φ 1 , … , φ J by a singleton: indeed, for linearly independent frames we prove that we can represent the frame in terms of just one system { T n φ } n = 0 ∞ , but unfortunately this representation often forces the operator T to be unbounded. Several examples illustrate the connection of the results to typical frames like Gabor frames and wavelet frames, as well as generic constructions in arbitrary separable Hilbert spaces.

Authors:Diego H. Díaz Martínez; Facundo Mémoli; Washington Mio Abstract: Publication date: Available online 30 March 2018 Source:Applied and Computational Harmonic Analysis Author(s): Diego H. Díaz Martínez, Facundo Mémoli, Washington Mio We introduce the notion of multiscale covariance tensor fields (CTF) associated with Euclidean random variables as a gateway to the shape of their distributions. Multiscale CTFs quantify variation of the data about every point in the data landscape at all spatial scales, unlike the usual covariance tensor that only quantifies global variation about the mean. Empirical forms of localized covariance previously have been used in data analysis and visualization, for example, in local principal component analysis, but we develop a framework for the systematic treatment of theoretical questions and mathematical analysis of computational models. We prove strong stability theorems with respect to the Wasserstein distance between probability measures, obtain consistency results for estimators, as well as bounds on the rate of convergence of empirical CTFs. These results show that CTFs are robust to sampling, noise and outliers. We provide numerous illustrations of how CTFs let us extract shape from data and also apply CTFs to manifold clustering, the problem of categorizing data points according to their noisy membership in a collection of possibly intersecting smooth submanifolds of Euclidean space. We prove that the proposed manifold clustering method is stable and carry out several experiments to illustrate the method.

Authors:Shuai Lu; Peter Mathé; Sergei V. Pereverzev Abstract: Publication date: Available online 21 March 2018 Source:Applied and Computational Harmonic Analysis Author(s): Shuai Lu, Peter Mathé, Sergei V. Pereverzev We discuss the problem of parameter choice in learning algorithms generated by a general regularization scheme. Such a scheme covers well-known algorithms as regularized least squares and gradient descent learning. It is known that in contrast to classical deterministic regularization methods, the performance of regularized learning algorithms is influenced not only by the smoothness of a target function, but also by the capacity of a space, where regularization is performed. In the infinite dimensional case the latter one is usually measured in terms of the effective dimension. In the context of supervised learning both the smoothness and effective dimension are intrinsically unknown a priori. Therefore we are interested in a posteriori regularization parameter choice, and we propose a new form of the balancing principle. An advantage of this strategy over the known rules such as cross-validation based adaptation is that it does not require any data splitting and allows the use of all available labeled data in the construction of regularized approximants. We provide the analysis of the proposed rule and demonstrate its advantage in simulations.

Authors:Nicki Holighaus; Christoph Wiesmeyr; Peter Balazs Abstract: Publication date: Available online 20 March 2018 Source:Applied and Computational Harmonic Analysis Author(s): Nicki Holighaus, Christoph Wiesmeyr, Peter Balazs We present a novel family of continuous, linear time-frequency transforms adaptable to a multitude of (nonlinear) frequency scales. Similar to classical time-frequency or time-scale representations, the representation coefficients are obtained as inner products with the elements of a continuously indexed family of time-frequency atoms. These atoms are obtained from a single prototype function, by means of modulation, translation and warping. By warping we refer to the process of nonlinear evaluation according to a bijective, increasing function, the warping function. Besides showing that the resulting integral transforms fulfill certain basic, but essential properties, such as continuity and invertibility, we will show that a large subclass of warping functions gives rise to families of generalized coorbit spaces, i.e. Banach spaces of functions whose representations possess a certain localization. Furthermore, we obtain sufficient conditions for subsampled warped time-frequency systems to form atomic decompositions and Banach frames. To this end, we extend results previously presented by Fornasier and Rauhut to a larger class of function systems via a simple, but crucial modification. The proposed method allows for great flexibility, but by choosing particular warping functions Φ we also recover classical time-frequency representations, e.g. Φ ( t ) = c t provides the short-time Fourier transform and Φ ( t ) = log a ( t ) provides wavelet transforms. This is illustrated by a number of examples provided in the manuscript.

Authors:Elona Agora; Jorge Antezana; Mihail N. Kolountzakis Abstract: Publication date: Available online 1 March 2018 Source:Applied and Computational Harmonic Analysis Author(s): Elona Agora, Jorge Antezana, Mihail N. Kolountzakis We study the existence of Gabor orthonormal bases with window the characteristic function of the set Ω = [ 0 , α ] ∪ [ β + α , β + 1 ] of measure 1, with α , β > 0 . By the symmetries of the problem, we can restrict our attention to the case α ≤ 1 / 2 . We prove that either if α < 1 / 2 or ( α = 1 / 2 and β ≥ 1 / 2 ) there exist such Gabor orthonormal bases, with window the characteristic function of the set Ω, if and only if Ω tiles the line. Furthermore, in both cases, we completely describe the structure of the set of time–frequency shifts associated to these bases.

Authors:Simon Marshall; Shayne Waldron Abstract: Publication date: Available online 8 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Simon Marshall, Shayne Waldron There is a finite number h n , d of tight frames of n distinct vectors for C d which are the orbit of a vector under a unitary action of the cyclic group Z n . These cyclic harmonic frames (or geometrically uniform tight frames) are used in signal analysis and quantum information theory, and provide many tight frames of particular interest. Here we investigate the conjecture that h n , d grows like n d − 1 . By using a result of Laurent which describes the set of solutions of algebraic equations in roots of unity, we prove the asymptotic estimate h n , d ≈ n d φ ( n ) ≥ n d − 1 , n → ∞ . By using a group theoretic approach, we also give some exact formulas for h n , d , and estimate the number of cyclic harmonic frames up to projective unitary equivalence.

Authors:Stéphane Jaffard; Stéphane Seuret; Herwig Wendt; Roberto Leonarduzzi; Stéphane Roux; Patrice Abry Abstract: Publication date: Available online 24 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Stéphane Jaffard, Stéphane Seuret, Herwig Wendt, Roberto Leonarduzzi, Stéphane Roux, Patrice Abry We show how a joint multifractal analysis of a collection of signals unravels correlations between the locations of their pointwise singularities. The multivariate multifractal formalism, reformulated in the general setting supplied by multiresolution quantities, provides a framework which allows to estimate joint multifractal spectra. General results on joint multifractal spectra are derived, and illustrated by the theoretical derivation and practical estimation of the joint multifractal spectra of simple mathematical models, including correlated binomial cascades.

Authors:Charles K. Chui; H.N. Mhaskar Abstract: Publication date: Available online 21 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Charles K. Chui, H.N. Mhaskar In this paper, motivated by diffraction of traveling light waves, a simple mathematical model is proposed, both for the multivariate super-resolution problem and the problem of blind-source separation of real-valued exponential sums. This model facilitates the development of a unified theory and a unified solution of both problems in this paper. Our consideration of the super-resolution problem is aimed at applications to fluorescence microscopy and observational astronomy, and the motivation for our consideration of the second problem is the current need of extracting multivariate exponential features in magnetic resonance spectroscopy (MRS) for the neurologist and radiologist as well as for providing a mathematical tool for isotope separation in Nuclear Chemistry. The unified method introduced in this paper can be easily realized by processing only finitely many data, sampled at locations that are not necessarily prescribed in advance, with computational scheme consisting only of matrix-vector multiplication, peak finding, and clustering.

Authors:Diego H. Díaz Martínez; Christine H. Lee; Peter T. Kim; Washington Mio Abstract: Publication date: Available online 13 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Diego H. Díaz Martínez, Christine H. Lee, Peter T. Kim, Washington Mio The state of many complex systems, such as ecosystems formed by multiple microbial taxa that interact in intricate ways, is often summarized as a probability distribution on the nodes of a weighted network. This paper develops methods for modeling the organization of such data, as well as their Euclidean counterparts, across spatial scales. Using the notion of diffusion distance, we introduce diffusion Fréchet functions and diffusion Fréchet vectors associated with probability distributions on Euclidean space and the vertex set of a weighted network, respectively. We prove that these functional statistics are stable with respect to the Wasserstein distance between probability measures, thus yielding robust descriptors of their shapes. We provide several examples that illustrate the geometric characteristics of a distribution that are captured by multi-scale Fréchet functions and vectors.

Authors:Yu Guang Wang; Xiaosheng Zhuang Abstract: Publication date: Available online 8 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Yu Guang Wang, Xiaosheng Zhuang Tight framelets on a smooth and compact Riemannian manifold M provide a tool of multiresolution analysis for data from geosciences, astrophysics, medical sciences, etc. This work investigates the construction, characterizations, and applications of tight framelets on such a manifold M . Characterizations of the tightness of a sequence of framelet systems for L 2 ( M ) in both the continuous and semi-discrete settings are provided. Tight framelets associated with framelet filter banks on M can then be easily designed and fast framelet filter bank transforms on M are shown to be realizable with nearly linear computational complexity. Explicit construction of tight framelets on the sphere S 2 as well as numerical examples are given.

Authors:Chendi Huang; Xinwei Sun; Jiechao Xiong; Yuan Yao Abstract: Publication date: Available online 8 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Chendi Huang, Xinwei Sun, Jiechao Xiong, Yuan Yao Boosting as gradient descent algorithms is one popular method in machine learning. In this paper a novel Boosting-type algorithm is proposed based on restricted gradient descent with structural sparsity control whose underlying dynamics are governed by differential inclusions. In particular, we present an iterative regularization path with structural sparsity where the parameter is sparse under some linear transforms, based on variable splitting and the Linearized Bregman Iteration. Hence it is called Split LBI. Despite its simplicity, Split LBI outperforms the popular generalized Lasso in both theory and experiments. A theory of path consistency is presented that equipped with a proper early stopping, Split LBI may achieve model selection consistency under a family of Irrepresentable Conditions which can be weaker than the necessary and sufficient condition for generalized Lasso. Furthermore, some ℓ 2 error bounds are also given at the minimax optimal rates. The utility and benefit of the algorithm are illustrated by several applications including image denoising, partial order ranking of sport teams, and world university grouping with crowdsourced ranking data.

Authors:Jinming Wen; Zhengchun Zhou; Zilong Liu; Ming-Jun Lai; Xiaohu Tang Abstract: Publication date: Available online 7 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Jinming Wen, Zhengchun Zhou, Zilong Liu, Ming-Jun Lai, Xiaohu Tang In this paper, we use the block orthogonal matching pursuit (BOMP) algorithm to recover block sparse signals x from measurements y = A x + v , where v is an ℓ 2 -bounded noise vector (i.e., ‖ v ‖ 2 ≤ ϵ for some constant ϵ). We investigate some sufficient conditions based on the block restricted isometry property (block-RIP) for exact (when v = 0 ) and stable (when v ≠ 0 ) recovery of block sparse signals x . First, on the one hand, we show that if A satisfies the block-RIP with δ K + 1 < 1 / K + 1 , then every block K-sparse signal x can be exactly or stably recovered by BOMP in K iterations. On the other hand, we show that, for any K ≥ 1 and 1 / K + 1 ≤ δ < 1 , there exists a matrix A satisfying the block-RIP with δ K + 1 = δ and a block K-sparse signal x such that BOMP may fail to recover x in K iterations. Then, we study some sufficient conditions for recovering block α-strongly-decaying K-sparse signals. We show that if A satisfies the block-RIP with δ K + 1 < 2 / 2 , then every α-strongly-decaying block K-sparse signal can be exactly or stably recovered by BOMP in K iterations under some conditions on α. Our newly found sufficient condition on the block-RIP of A is less restrictive than that for ℓ 1 minimization for this special class of sparse signals. Furthermore, for any K ≥ 1 , α > 1 and 2 / 2 ≤ δ < 1 , the recovery of x may fail in K iterations for a sensing matrix A which satisfies the block-RIP with δ K + 1 = δ . Finally, we study some sufficient conditions for partial recovery of block sparse signals. Specifically, if A satisfies the block-RIP with δ K + 1 < 2 / 2 , then BOMP is guaranteed to recover some blocks of x if these blocks satisfy a sufficient condition. We further show that this condition is also sharp.

Authors:Wengu Chen; Yaling Li Abstract: Publication date: Available online 7 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Wengu Chen, Yaling Li In this paper, the sufficient condition in terms of the RIC and ROC for the stable and robust recovery of signals in both noiseless and noisy settings was established via weighted l 1 minimization when there is partial prior information on support of signals. An improved performance guarantee has been derived. We can obtain a less restricted sufficient condition for signal reconstruction and a tighter recovery error bound under some conditions via weighted l 1 minimization. When prior support estimate is at least 50% accurate, the sufficient condition is weaker than the analogous condition by standard l 1 minimization method, meanwhile the reconstruction error upper bound is provably to be smaller under additional conditions. Furthermore, the sufficient condition is also proved sharp.

Authors:Gregory Beylkin; Lucas Monzón; Ignas Satkauskas Abstract: Publication date: Available online 6 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Gregory Beylkin, Lucas Monzón, Ignas Satkauskas We introduce a new functional representation of probability density functions (PDFs) of non-negative random variables via a product of a monomial factor and linear combinations of decaying exponentials with complex exponents. This approximate representation of PDFs is obtained for any finite, user-selected accuracy. Using a fast algorithm involving Hankel matrices, we develop a general numerical method for computing the PDF of the sums, products, or quotients of any number of non-negative independent random variables yielding the result in the same type of functional representation. We present several examples to demonstrate the accuracy of the approach.

Authors:Zhiqiang Abstract: Publication date: March 2018 Source:Applied and Computational Harmonic Analysis, Volume 44, Issue 2 Author(s): Zhiqiang Xu The paper presents several results that address a fundamental question in low-rank matrix recovery: how many measurements are needed to recover low-rank matrices' We begin by investigating the complex matrices case and show that 4 n r − 4 r 2 generic measurements are both necessary and sufficient for the recovery of rank-r matrices in C n × n . Thus, we confirm a conjecture which is raised by Eldar, Needell and Plan for the complex case. We next consider the real case and prove that the bound 4 n r − 4 r 2 is tight provided n = 2 k + r , k ∈ Z + . Motivated by Vinzant's work [19], we construct 11 matrices in R 4 × 4 by computer random search and prove they define injective measurements on rank-1 matrices in R 4 × 4 . This disproves the conjecture raised by Eldar, Needell and Plan for the real case. Finally, we use the results in this paper to investigate the phase retrieval by projection and show fewer than 2 n − 1 orthogonal projections are possible for the recovery of x ∈ R n from the norm of them, which gives a negative answer for a question raised in [1].

Authors:Xiaodong Li; Shuyang Ling; Thomas Strohmer; Ke Wei Abstract: Publication date: Available online 2 February 2018 Source:Applied and Computational Harmonic Analysis Author(s): Xiaodong Li, Shuyang Ling, Thomas Strohmer, Ke Wei We study the question of reconstructing two signals f and g from their convolution y = f ⁎ g . This problem, known as blind deconvolution, pervades many areas of science and technology, including astronomy, medical imaging, optics, and wireless communications. A key challenge of this intricate non-convex optimization problem is that it might exhibit many local minima. We present an efficient numerical algorithm that is guaranteed to recover the exact solution, when the number of measurements is (up to log-factors) slightly larger than the information-theoretical minimum, and under reasonable conditions on f and g . The proposed regularized gradient descent algorithm converges at a geometric rate and is provably robust in the presence of noise. To the best of our knowledge, our algorithm is the first blind deconvolution algorithm that is numerically efficient, robust against noise, and comes with rigorous recovery guarantees under certain subspace conditions. Moreover, numerical experiments do not only provide empirical verification of our theory, but they also demonstrate that our method yields excellent performance even in situations beyond our theoretical framework.

Authors:Ronen Talmon; Hau-Tieng Wu Abstract: Publication date: Available online 31 January 2018 Source:Applied and Computational Harmonic Analysis Author(s): Ronen Talmon, Hau-Tieng Wu The analysis of data sets arising from multiple sensors has drawn significant research attention over the years. Traditional methods, including kernel-based methods, are typically incapable of capturing nonlinear geometric structures. We introduce a latent common manifold model underlying multiple sensor observations for the purpose of multimodal data fusion. A method based on alternating diffusion is presented and analyzed; we provide theoretical analysis of the method under the latent common manifold model. To exemplify the power of the proposed framework, experimental results in several applications are reported.

Authors:Francesca Bartolucci; Filippo De Mari; Ernesto De Vito; Francesca Odone Abstract: Publication date: Available online 3 January 2018 Source:Applied and Computational Harmonic Analysis Author(s): Francesca Bartolucci, Filippo De Mari, Ernesto De Vito, Francesca Odone We prove that the unitary affine Radon transform intertwines the quasi-regular representation of a class of semidirect products, built by shearlet dilation groups and translations, and the tensor product of a standard wavelet representation with a wavelet-like representation. This yields a formula for shearlet coefficients that involves only integral transforms applied to the affine Radon transform of the signal, thereby opening new perspectives in the inversion of the Radon transform.

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.