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:Hassan Mansour; Rayan Saab Pages: 23 - 38 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): Hassan Mansour, Rayan Saab We study the recovery of sparse signals from underdetermined linear measurements when a potentially erroneous support estimate is available. Our results are twofold. First, we derive necessary and sufficient conditions for signal recovery from compressively sampled measurements using weighted ℓ 1 -norm minimization. These conditions, which depend on the choice of weights as well as the size and accuracy of the support estimate, are on the null space of the measurement matrix. They can guarantee recovery even when standard ℓ 1 minimization fails. Second, we derive bounds on the number of Gaussian measurements for these conditions to be satisfied, i.e., for weighted ℓ 1 minimization to successfully recover all sparse signals whose support has been estimated sufficiently accurately. Our bounds show that weighted ℓ 1 minimization requires significantly fewer measurements than standard ℓ 1 minimization when the support estimate is relatively accurate.

Authors:William B. March; George Biros Pages: 39 - 75 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): William B. March, George Biros We consider fast kernel summations in high dimensions: given a large set of points in d dimensions (with d ≫ 3 ) and a pair-potential function (the kernel function), we compute a weighted sum of all pairwise kernel interactions for each point in the set. Direct summation is equivalent to a (dense) matrix–vector multiplication and scales quadratically with the number of points. Fast kernel summation algorithms reduce this cost to log-linear or linear complexity. Treecodes and Fast Multipole Methods (FMMs) deliver tremendous speedups by constructing approximate representations of interactions of points that are far from each other. In algebraic terms, these representations correspond to low-rank approximations of blocks of the overall interaction matrix. Existing approaches require an excessive number of kernel evaluations with increasing d and number of points in the dataset. To address this issue, we use a randomized algebraic approach in which we first sample the rows of a block and then construct its approximate, low-rank interpolative decomposition. We examine the feasibility of this approach theoretically and experimentally. We provide a new theoretical result showing a tighter bound on the reconstruction error from uniformly sampling rows than the existing state-of-the-art. We demonstrate that our sampling approach is competitive with existing (but prohibitively expensive) methods from the literature. We also construct kernel matrices for the Laplacian, Gaussian, and polynomial kernels—all commonly used in physics and data analysis. We explore the numerical properties of blocks of these matrices, and show that they are amenable to our approach. Depending on the data set, our randomized algorithm can successfully compute low rank approximations in high dimensions. We report results for data sets with ambient dimensions from four to 1,000.

Authors:Ha Q. Nguyen; Michael Unser Pages: 76 - 93 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): Ha Q. Nguyen, Michael Unser The classical assumption in sampling and spline theories is that the input signal is square-integrable, which prevents us from applying such techniques to signals that do not decay or even grow at infinity. In this paper, we develop a sampling theory for multidimensional non-decaying signals living in weighted L p spaces. The sampling and reconstruction of an analog signal can be done by a projection onto a shift-invariant subspace generated by an interpolating kernel. We show that, if this kernel and its biorthogonal counterpart are elements of appropriate hybrid-norm spaces, then both the sampling and the reconstruction are stable. This is an extension of earlier results by Aldroubi and Gröchenig. The extension is required because it allows us to develop the theory for the ideal sampling of non-decaying signals in weighted Sobolev spaces. When the d-dimensional signal and its d / p + ε derivatives, for arbitrarily small ε > 0 , grow no faster than a polynomial in the L p sense, the sampling operator is shown to be bounded even without a sampling kernel. As a consequence, the signal can also be interpolated from its samples with a nicely behaved interpolating kernel.

Authors:Michele Berra; Iulia Martina Bulai; Elena Cordero; Fabio Nicola Pages: 94 - 121 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): Michele Berra, Iulia Martina Bulai, Elena Cordero, Fabio Nicola The present paper is devoted to the semiclassical analysis of linear Schrödinger equations from a Gabor frame perspective. We consider (time-dependent) smooth Hamiltonians with at most quadratic growth. Then we construct higher order parametrices for the corresponding Schrödinger equations by means of ħ-Gabor frames, as recently defined by M. de Gosson, and we provide precise L 2 -estimates of their accuracy, in terms of the Planck constant ħ. Nonlinear parametrices, in the spirit of the nonlinear approximation, are also presented. Numerical experiments are exhibited to compare our results with the early literature.

Authors:Yong Sheng Soh; Venkat Chandrasekaran Pages: 122 - 147 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): Yong Sheng Soh, Venkat Chandrasekaran We consider change-point estimation in a sequence of high-dimensional signals given noisy observations. Classical approaches to this problem such as the filtered derivative method are useful for sequences of scalar-valued signals, but they have undesirable scaling behavior in the high-dimensional setting. However, many high-dimensional signals encountered in practice frequently possess latent low-dimensional structure. Motivated by this observation, we propose a technique for high-dimensional change-point estimation that combines the filtered derivative approach from previous work with convex optimization methods based on atomic norm regularization, which are useful for exploiting structure in high-dimensional data. Our algorithm is applicable in online settings as it operates on small portions of the sequence of observations at a time, and it is well-suited to the high-dimensional setting both in terms of computational scalability and of statistical efficiency. The main result of this paper shows that our method performs change-point estimation reliably as long as the product of the smallest-sized change (the Euclidean-norm-squared of the difference between signals at a change-point) and the smallest distance between change-points (number of time instances) is larger than a Gaussian width parameter that characterizes the low-dimensional complexity of the underlying signal sequence.

Authors:I. Iglewska-Nowak Pages: 148 - 161 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): I. Iglewska-Nowak The major goal of the paper is to prove that discrete frames of (directional) wavelets derived from an approximate identity exist. Additionally, a kind of energy conservation property is shown to hold in the case when a wavelet family is not its own reconstruction family. Although an additional constraint on the spectrum of the wavelet family must be satisfied, it is shown that all the wavelets so far defined in the literature possess this property.

Authors:Xiaolin Huang; Andreas Maier; Joachim Hornegger; Johan A.K. Suykens Pages: 162 - 172 Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): Xiaolin Huang, Andreas Maier, Joachim Hornegger, Johan A.K. Suykens Because of several successful applications, indefinite kernels have attracted many research interests in recent years. This paper addresses indefinite learning in the framework of least squares support vector machines (LS-SVM). Unlike existing indefinite kernel learning methods, which usually involve non-convex problems, the indefinite LS-SVM is still easy to solve, but the kernel trick and primal-dual relationship for LS-SVM with a Mercer kernel is no longer valid. In this paper, we give a feature space interpretation for indefinite LS-SVM. In the same framework, kernel principal component analysis with an infinite kernel is discussed as well. In numerical experiments, LS-SVM with indefinite kernels for classification and kernel principal component analysis is evaluated. Its good performance together with the feature space interpretation given in this paper imply the potential use of indefinite LS-SVM in real applications.

Authors:Aline Bonami; Abderrazek Karoui Pages: 361 - 377 Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): Aline Bonami, Abderrazek Karoui Recently, there is a growing interest in the spectral approximation by the Prolate Spheroidal Wave Functions (PSWFs) ψ n , c , c > 0 . This is due to the promising new contributions of these functions in various classical as well as emerging applications from Signal Processing, Geophysics, Numerical Analysis, etc. The PSWFs form a basis with remarkable properties not only for the space of band-limited functions with bandwidth c, but also for the Sobolev space H s ( [ − 1 , 1 ] ) . The quality of the spectral approximation and the choice of the parameter c when approximating a function in H s ( [ − 1 , 1 ] ) by its truncated PSWFs series expansion, are the main issues. By considering a function f ∈ H s ( [ − 1 , 1 ] ) as the restriction to [ − 1 , 1 ] of an almost time-limited and band-limited function, we try to give satisfactory answers to these two issues. Also, we illustrate the different results of this work by some numerical examples.

Authors:A. Aldroubi; C. Cabrelli; U. Molter; S. Tang Pages: 378 - 401 Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): A. Aldroubi, C. Cabrelli, U. Molter, S. Tang Let Y = { f ( i ) , Af ( i ) , … , A l i f ( i ) : i ∈ Ω } , where A is a bounded operator on ℓ 2 ( I ) . The problem under consideration is to find necessary and sufficient conditions on A , Ω , { l i : i ∈ Ω } in order to recover any f ∈ ℓ 2 ( I ) from the measurements Y. This is the so-called dynamical sampling problem in which we seek to recover a function f by combining coarse samples of f and its futures states A l f . We completely solve this problem in finite dimensional spaces, and for a large class of self adjoint operators in infinite dimensional spaces. In the latter case, although Y can be complete, using the Müntz–Szász Theorem we show it can never be a basis. We can also show that, when Ω is finite, Y is not a frame except for some very special cases. The existence of these special cases is derived from Carleson's Theorem for interpolating sequences in the Hardy space H 2 ( D ) . Finally, using the recently proved Kadison–Singer/Feichtinger theorem we show that the set obtained by normalizing the vectors of Y can never be a frame when Ω is finite.

Authors:Jianbin Yang; Dominik Stahl; Zuowei Shen Pages: 480 - 507 Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): Jianbin Yang, Dominik Stahl, Zuowei Shen In real world applications many signals contain singularities, like edges in images. Recent wavelet frame based approaches were successfully applied to reconstruct scattered data from such functions while preserving these features. In this paper we present a recent approach which determines the approximant from shift invariant subspaces by minimizing an ℓ 1 -regularized least squares problem which makes additional use of the wavelet frame transform in order to preserve sharp edges. We give a detailed analysis of this approach, i.e., how the approximation error behaves dependent on data density and noise level. Moreover, a link to wavelet frame based image restoration models is established and the convergence of these models is analyzed. In the end, we present some numerical examples, for instance how to apply this approach to handle coarse-grained models in molecular dynamics.

Authors:Ben Adcock; Milana Gataric; Anders C. Hansen Pages: 508 - 535 Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): Ben Adcock, Milana Gataric, Anders C. Hansen In this paper, we consider the problem of recovering a compactly supported multivariate function from a collection of pointwise samples of its Fourier transform taken nonuniformly. We do this by using the concept of weighted Fourier frames. A seminal result of Beurling shows that sampling points give rise to a classical Fourier frame provided they are relatively separated and of sufficient density. However, this result does not allow for arbitrary clustering of sampling points, as is often the case in practice. Whilst keeping the density condition sharp and dimension independent, our first result removes the separation condition and shows that density alone suffices. However, this result does not lead to estimates for the frame bounds. A known result of Gröchenig provides explicit estimates, but only subject to a density condition that deteriorates linearly with dimension. In our second result we improve these bounds by reducing the dimension dependence. In particular, we provide explicit frame bounds which are dimensionless for functions having compact support contained in a sphere. Next, we demonstrate how our two main results give new insight into a reconstruction algorithm—based on the existing generalized sampling framework—that allows for stable and quasi-optimal reconstruction in any particular basis from a finite collection of samples. Finally, we construct sufficiently dense sampling schemes that are often used in practice—jittered, radial and spiral sampling schemes—and provide several examples illustrating the effectiveness of our approach when tested on these schemes.

Authors:Elena A. Lebedeva Pages: 536 - 549 Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): Elena A. Lebedeva An inequality refining the lower bound for a periodic (Breitenberger) uncertainty constant is proved for a wide class of functions. A connection of uncertainty constants for periodic and non-periodic functions is extended to this class. A particular minimization problem for a non-periodic (Heisenberg) uncertainty constant is studied.

Authors:Paul Hand Pages: 550 - 562 Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): Paul Hand Consider the task of recovering an unknown n-vector from phaseless linear measurements. This nonconvex problem may be convexified into a semidefinite rank-one matrix recovery problem, known as PhaseLift. Under a linear number of Gaussian measurements, PhaseLift recovers the unknown vector exactly with high probability. Under noisy measurements, the solution to a variant of PhaseLift has error proportional to the ℓ 1 norm of the noise. In the present paper, we study the robustness of this variant of PhaseLift to gross, arbitrary corruptions. We prove that PhaseLift can tolerate noise and a small, fixed fraction of gross errors, even in the highly underdetermined regime where there are only O ( n ) measurements. The lifted phase retrieval problem can be viewed as a rank-one robust Principal Component Analysis (PCA) problem under generic rank-one measurements. From this perspective, the proposed convex program is simpler than the semidefinite version of the sparse-plus-low-rank formulation standard in the robust PCA literature. Specifically, the rank penalization through a trace term is unnecessary, and the resulting optimization program has no parameters that need to be chosen.

Authors:Céline Aubel; Helmut Bölcskei Abstract: Publication date: Available online 1 August 2017 Source:Applied and Computational Harmonic Analysis Author(s): Céline Aubel, Helmut Bölcskei We derive bounds on the extremal singular values and the condition number of N × K , with N ⩾ K , Vandermonde matrices with nodes in the unit disk. The mathematical techniques we develop to prove our main results are inspired by a link—first established by Selberg [1] and later extended by Moitra [2]—between the extremal singular values of Vandermonde matrices with nodes on the unit circle and large sieve inequalities. Our main conceptual contribution lies in establishing a connection between the extremal singular values of Vandermonde matrices with nodes in the unit disk and a novel large sieve inequality involving polynomials in z ∈ C with z ⩽ 1 . Compared to Bazán's upper bound on the condition number [3], which, to the best of our knowledge, constitutes the only analytical result—available in the literature—on the condition number of Vandermonde matrices with nodes in the unit disk, our bound not only takes a much simpler form, but is also sharper for certain node configurations. Moreover, the bound we obtain can be evaluated consistently in a numerically stable fashion, whereas the evaluation of Bazán's bound requires the solution of a linear system of equations which has the same condition number as the Vandermonde matrix under consideration and can therefore lead to numerical instability in practice. As a byproduct, our result—when particularized to the case of nodes on the unit circle—slightly improves upon the Selberg–Moitra bound.

Authors:Chun-Kit Lai; Shidong Li; Daniel Mondo Abstract: Publication date: Available online 27 July 2017 Source:Applied and Computational Harmonic Analysis Author(s): Chun-Kit Lai, Shidong Li, Daniel Mondo Solving compressed sensing problems relies on the properties of sparse signals. It is commonly assumed that the sparsity s needs to be less than one half of the spark of the sensing matrix A, and then the unique sparsest solution exists, and is recoverable by ℓ 1 -minimization or related procedures. We discover, however, a measure theoretical uniqueness exists for nearly spark-level sparsity from compressed measurements A x = b . Specifically, suppose A is of full spark with m rows, and suppose m 2 < s < m . Then the solution to A x = b is unique for x with ‖ x ‖ 0 ≤ s up to a set of measure 0 in every s-sparse plane. This phenomenon is observed and confirmed by an ℓ 1 -tail minimization procedure, which recovers sparse signals uniquely with s > m 2 in thousands and thousands of random tests. We further show instead that the mere ℓ 1 -minimization would actually fail if s > m 2 even from the same measure theoretical point of view.

Authors:Ayush Bhandari; Ahmed I. Zayed Abstract: Publication date: Available online 25 July 2017 Source:Applied and Computational Harmonic Analysis Author(s): Ayush Bhandari, Ahmed I. Zayed The Special Affine Fourier Transformation or the SAFT generalizes a number of well known unitary transformations as well as signal processing and optics related mathematical operations. Shift-invariant spaces also play an important role in sampling theory, multiresolution analysis, and many other areas of signal and image processing. Shannon's sampling theorem, which is at the heart of modern digital communications, is a special case of sampling in shift-invariant spaces. Furthermore, it is well known that the Poisson summation formula is equivalent to the sampling theorem and that the Zak transform is closely connected to the sampling theorem and the Poisson summation formula. These results have been known to hold in the Fourier transform domain for decades and were recently shown to hold in the Fractional Fourier transform domain by A. Bhandari and A. Zayed. The main goal of this article is to show that these results also hold true in the SAFT domain. We provide a short, self–contained proof of Shannon's theorem for functions bandlimited in the SAFT domain and then show that sampling in the SAFT domain is equivalent to orthogonal projection of functions onto a subspace of bandlimited basis associated with the SAFT domain. This interpretation of sampling leads to least–squares optimal sampling theorem. Furthermore, we show that this approximation procedure is linked with convolution and semi–discrete convolution operators that are associated with the SAFT domain. We conclude the article with an application of fractional delay filtering of SAFT bandlimited functions.

Authors:Santhosh Karnik; Zhihui Zhu; Michael B. Wakin; Justin Romberg; Mark A. Davenport Abstract: Publication date: Available online 19 July 2017 Source:Applied and Computational Harmonic Analysis Author(s): Santhosh Karnik, Zhihui Zhu, Michael B. Wakin, Justin Romberg, Mark A. Davenport The discrete prolate spheroidal sequences (DPSS's) provide an efficient representation for discrete signals that are perfectly timelimited and nearly bandlimited. Due to the high computational complexity of projecting onto the DPSS basis – also known as the Slepian basis – this representation is often overlooked in favor of the fast Fourier transform (FFT). We show that there exist fast constructions for computing approximate projections onto the leading Slepian basis elements. The complexity of the resulting algorithms is comparable to the FFT, and scales favorably as the quality of the desired approximation is increased. In the process of bounding the complexity of these algorithms, we also establish new nonasymptotic results on the eigenvalue distribution of discrete time-frequency localization operators. We then demonstrate how these algorithms allow us to efficiently compute the solution to certain least-squares problems that arise in signal processing. We also provide simulations comparing these fast, approximate Slepian methods to exact Slepian methods as well as the traditional FFT based methods.

Authors:Rui Wang; Yuesheng Xu Abstract: Publication date: Available online 18 July 2017 Source:Applied and Computational Harmonic Analysis Author(s): Rui Wang, Yuesheng Xu Motivated by the need of processing non-point-evaluation functional data, we introduce the notion of functional reproducing kernel Hilbert spaces (FRKHSs). This space admits a unique functional reproducing kernel which reproduces a family of continuous linear functionals on the space. The theory of FRKHSs and the associated functional reproducing kernels are established. A special class of FRKHSs, which we call the perfect FRKHSs, are studied, which reproduce the family of the standard point-evaluation functionals and at the same time another different family of continuous linear (non-point-evaluation) functionals. The perfect FRKHSs are characterized in terms of features, especially for those with respect to integral functionals. In particular, several specific examples of the perfect FRKHSs are presented. We apply the theory of FRKHSs to sampling and regularized learning, where non-point-evaluation functional data are used. Specifically, a general complete reconstruction formula from linear functional values is established in the framework of FRKHSs. The average sampling and the reconstruction of vector-valued functions are considered in specific FRKHSs. We also investigate in the FRKHS setting the regularized learning schemes, which learn a target element from non-point-evaluation functional data. The desired representer theorems of the learning problems are established to demonstrate the key roles played by the FRKHSs and the functional reproducing kernels in machine learning from non-point-evaluation functional data. We finally illustrate that the continuity of linear functionals, used to obtain the non-point-evaluation functional data, on an FRKHS is necessary for the stability of the numerical reconstruction algorithm using the data.

Authors:Ole Christensen; Say Song Goh Abstract: Publication date: Available online 18 July 2017 Source:Applied and Computational Harmonic Analysis Author(s): Ole Christensen, Say Song Goh The unitary extension principle (UEP) by Ron and Shen yields conditions for the construction of a multi-generated tight wavelet frame for L 2 ( R s ) based on a given refinable function. In this paper we show that the UEP can be generalized to locally compact abelian groups. In the general setting, the resulting frames are generated by modulates of a collection of functions; via the Fourier transform this corresponds to a generalized shift-invariant system. Both the stationary and the nonstationary case are covered. We provide general constructions, based on B-splines on the group itself as well as on characteristic functions on the dual group. Finally, we consider a number of concrete groups and derive explicit constructions of the resulting frames.

Authors:Peter G. Casazza; Amineh Farzannia; John I. Haas; Tin T. Tran Abstract: Publication date: Available online 28 June 2017 Source:Applied and Computational Harmonic Analysis Author(s): Peter G. Casazza, Amineh Farzannia, John I. Haas, Tin T. Tran Equiangular tight frames (ETFs) and biangular tight frames (BTFs) - sets of unit vectors with basis-like properties whose pairwise absolute inner products admit exactly one or two values, respectively - are useful for many applications. A well-understood class of ETFs are those which manifest as harmonic frames – vector sets defined in terms of the characters of finite abelian groups – because they are characterized by combinatorial objects called difference sets. This work is dedicated to the study of the underlying combinatorial structures of harmonic BTFs. We show that if a harmonic frame is generated by a divisible difference set, a partial difference set or by a special structure with certain Gauss summing properties – all three of which are generalizations of difference sets that fall under the umbrella term “bidifference set” – then it is either a BTF or an ETF. However, we also show that the relationship between harmonic BTFs and bidifference sets is not as straightforward as the correspondence between harmonic ETFs and difference sets, as there are examples of bidifference sets that do not generate harmonic BTFs. In addition, we study another class of combinatorial structures, the nested divisible difference sets, which yields an example of a harmonic BTF that is not generated by a bidifference set.

Authors:Bradley Currey; Hartmut Führ; Vignon Oussa Abstract: Publication date: Available online 23 June 2017 Source:Applied and Computational Harmonic Analysis Author(s): Bradley Currey, Hartmut Führ, Vignon Oussa This paper presents a full catalogue, up to conjugacy and subgroups of finite index, of all matrix groups H < GL ( 3 , R ) that give rise to a continuous wavelet transform with associated irreducible quasi-regular representation. For each group in this class, coorbit theory allows to consistently define spaces of sparse signals, and to construct atomic decompositions converging simultaneously in a whole range of these spaces. As an application of the classification, we investigate the existence of compactly supported admissible vectors and atoms for the groups.

Authors:Zheng-Chu Guo; Shao-Bo Lin; Lei Shi Abstract: Publication date: Available online 21 June 2017 Source:Applied and Computational Harmonic Analysis Author(s): Zheng-Chu Guo, Shao-Bo Lin, Lei Shi In this paper, we study distributed learning with multi-penalty regularization based on a divide-and-conquer approach. Using Neumann expansion and a second order decomposition for difference of operator inverses approach, we derive optimal learning rates for distributed multi-penalty regularization in expectation. As a byproduct, we also deduce optimal learning rates for multi-penalty regularization, which was not given in the literature. These results are applied to the distributed manifold regularization and optimal learning rates are given.

Authors:Christian Lessig; Philipp Petersen; Martin Schäfer Abstract: Publication date: Available online 16 June 2017 Source:Applied and Computational Harmonic Analysis Author(s): Christian Lessig, Philipp Petersen, Martin Schäfer We introduce bendlets, a shearlet-like system that is based on anisotropic scaling, translation, shearing, and bending of a compactly supported generator. With shearing being linear and bending quadratic in spatial coordinates, bendlets provide what we term a second-order shearlet system. As we show in this article, the decay rates of the associated transform enable the precise characterization of location, orientation and curvature of discontinuities in piecewise constant images. These results yield an improvement over existing directional representation systems where curvature only controls the constant of the decay rate of the transform. We also detail the construction of shearlet systems of arbitrary order. A practical implementation of bendlets is provided as an extension of the ShearLab toolbox, which we use to verify our theoretical classification results.

Authors:Chen Li; Ben Adcock Abstract: Publication date: Available online 6 June 2017 Source:Applied and Computational Harmonic Analysis Author(s): Chen Li, Ben Adcock In compressed sensing, it is often desirable to consider signals possessing additional structure beyond sparsity. One such structured signal model – which forms the focus of this paper – is the local sparsity in levels class. This class has recently found applications in problems such as compressive imaging, multi-sensor acquisition systems and sparse regularization in inverse problems. In this paper we present uniform recovery guarantees for this class when the measurement matrix corresponds to a subsampled isometry. We do this by establishing a variant of the standard restricted isometry property for sparse in levels vectors, known as the restricted isometry property in levels. Interestingly, besides the usual log factors, our uniform recovery guarantees are simpler and less stringent than existing nonuniform recovery guarantees. For the particular case of discrete Fourier sampling with Haar wavelet sparsity, a corollary of our main theorem yields a new recovery guarantee which improves over the current state-of-the-art.

Authors:Julien Flamant; Nicolas Le Bihan; Pierre Chainais Abstract: Publication date: Available online 1 June 2017 Source:Applied and Computational Harmonic Analysis Author(s): Julien Flamant, Nicolas Le Bihan, Pierre Chainais Many phenomena are described by bivariate signals or bidimensional vectors in applications ranging from radar to EEG, optics and oceanography. We show that an adequate quaternion Fourier transform permits to build relevant time-frequency representations of bivariate signals that naturally identify geometrical or polarization properties. First, a bivariate counterpart of the usual analytic signal of real signals is introduced, called the quaternion embedding of bivariate signals. Then two fundamental theorems ensure that a quaternion short term Fourier transform and a quaternion continuous wavelet transform are well defined and obey desirable properties such as conservation laws and reconstruction formulas. The resulting spectrograms and scalograms provide meaningful representations of both the time-frequency and geometrical/polarization content of the signal. Moreover the numerical implementation remains simply based on the use of FFT. A toolbox is available for reproducibility. Synthetic and real-world examples illustrate the relevance and efficiency of the proposed approach.

Authors:Claire Boyer; Bigot Pierre Weiss Abstract: Publication date: Available online 26 May 2017 Source:Applied and Computational Harmonic Analysis Author(s): Claire Boyer, Jérémie Bigot, Pierre Weiss Compressed Sensing (CS) is an appealing framework for applications such as Magnetic Resonance Imaging (MRI). However, up-to-date, the sensing schemes suggested by CS theories are made of random isolated measurements, which are usually incompatible with the physics of acquisition. To reflect the physical constraints of the imaging device, we introduce the notion of blocks of measurements: the sensing scheme is not a set of isolated measurements anymore, but a set of groups of measurements which may represent any arbitrary shape (parallel or radial lines for instance). Structured acquisition with blocks of measurements are easy to implement, and provide good reconstruction results in practice. However, very few results exist on the theoretical guarantees of CS reconstructions in this setting. In this paper, we derive new CS results for structured acquisitions and signals satisfying a prior structured sparsity. The obtained results provide a recovery probability of sparse vectors that explicitly depends on their support. Our results are thus support-dependent and offer the possibility for flexible assumptions on the sparsity structure. Moreover, the results are drawing-dependent, since we highlight an explicit dependency between the probability of reconstructing a sparse vector and the way of choosing the blocks of measurements. Numerical simulations show that the proposed theory is faithful to experimental observations.

Authors:John Aston; Florent Autin; Gerda Claeskens; Jean-Marc Freyermuth; Christophe Pouet Abstract: Publication date: Available online 18 May 2017 Source:Applied and Computational Harmonic Analysis Author(s): John Aston, Florent Autin, Gerda Claeskens, Jean-Marc Freyermuth, Christophe Pouet We present a novel method for detecting some structural characteristics of multidimensional functions. We consider the multidimensional Gaussian white noise model with an anisotropic estimand. Using the relation between the Sobol decomposition and the geometry of multidimensional wavelet basis we can build test statistics for any of the Sobol functional components. We assess the asymptotical minimax optimality of these test statistics and show that they are optimal in presence of anisotropy with respect to the newly determined minimax rates of separation. An appropriate combination of these test statistics allows to test some general structural characteristics such as the atomic dimension or the presence of some variables. Numerical experiments show the potential of our method for studying spatio-temporal processes.

Authors:Omer Abstract: Publication date: July 2017 Source:Applied and Computational Harmonic Analysis, Volume 43, Issue 1 Author(s): H. Omer, B. Torrésani A class of random non-stationary signals termed timbre×dynamics is introduced and studied. These signals are obtained by non-linear transformations of stationary random Gaussian signals, in such a way that the transformation can be approximated by translations in an appropriate representation domain. In such situations, approximate maximum likelihood estimation techniques can be derived, which yield simultaneous estimation of the transformation and the power spectrum of the underlying stationary signal. This paper focuses on the case of modulation and time warping of stationary signals, and proposes and studies estimation algorithms (based on time-frequency and time-scale representations respectively) for these quantities of interest. The proposed approach is validated on numerical simulations on synthetic signals, and examples on real life car engine sounds.

Authors:Jian Zhai; Bowen Zheng Abstract: Publication date: Available online 15 May 2017 Source:Applied and Computational Harmonic Analysis Author(s): Jian Zhai, Bowen Zheng This paper studies the Strichartz estimate of the solutions for the free fractional Schrödinger equation with spatial variable coefficient, which arises from the integrable model of the inhomogeneous spherically symmetric HFSS. It is different from the classical fractional Schrödinger equation in which the Strichartz estimates have been proved. We establish some harmonic analysis tools such as the equivalence of the Sobolev type spaces W ˙ σ , 2 and H ˙ σ and Hankel type Littlewood-Paley theory. By utilizing these ingredients, we prove the Strichartz estimate.

Authors:Kirill Serkh Abstract: Publication date: Available online 15 May 2017 Source:Applied and Computational Harmonic Analysis Author(s): Kirill Serkh In this paper we investigate the solution of boundary value problems on polygonal domains for elliptic partial differential equations. Previously, we observed that when the boundary value problems are formulated as boundary integral equations of classical potential theory, the solutions are representable by series of elementary functions, to arbitrary order, for all but finitely many values of the angles. Here, we extend this observation to all values of the angles. We show that the solutions near corners are representable, to arbitrary order, by linear combinations of certain non-integer powers and non-integer powers multiplied by logarithms.

Authors:Ben Adcock; Milana Gataric; José Luis Romero Abstract: Publication date: Available online 12 May 2017 Source:Applied and Computational Harmonic Analysis Author(s): Ben Adcock, Milana Gataric, José Luis Romero We study the problem of recovering an unknown compactly-supported multivariate function from samples of its Fourier transform that are acquired nonuniformly, i.e. not necessarily on a uniform Cartesian grid. Reconstruction problems of this kind arise in various imaging applications, where Fourier samples are taken along radial lines or spirals for example. Specifically, we consider finite-dimensional reconstructions, where a limited number of samples is available, and investigate the rate of convergence of such approximate solutions and their numerical stability. We show that the proportion of Fourier samples that allow for stable approximations of a given numerical accuracy is independent of the specific sampling geometry and is therefore universal for different sampling scenarios. This allows us to relate both sufficient and necessary conditions for different sampling setups and to exploit several results that were previously available only for very specific sampling geometries. The results are obtained by developing: (i) a transference argument for different measures of the concentration of the Fourier transform and Fourier samples; (ii) frame bounds valid up to the critical sampling density, which depend explicitly on the sampling set and the spectrum. As an application, we identify sufficient and necessary conditions for stable and accurate reconstruction of algebraic polynomials or wavelet coefficients from nonuniform Fourier data.

Authors:Sylvain Durand Abstract: Publication date: Available online 20 April 2017 Source:Applied and Computational Harmonic Analysis Author(s): Sylvain Durand This article addresses the issue of designing bases for L 2 ( R 2 ) that are generated by translations, rotations and dilations of a single mother wavelet ψ. We show how this construction can be simplified by setting an odd number of directions and by choosing properly the phase of the Fourier transform of ψ. A large part of the article is devoted to the proof of theorems that give sufficient conditions for ψ to generate a Riesz sequence and a Riesz basis for L 2 ( R 2 ) . An example of Riesz sequence whose restriction to each scale is orthonormal is set. Theoretical results are confirmed by numerical experiments where a discrete directional wavelet transform is introduced.

Authors:Joachim Toft Abstract: Publication date: Available online 20 April 2017 Source:Applied and Computational Harmonic Analysis Author(s): Joachim Toft We extend Feichtinger's minimality property on the smallest non-trivial time-frequency shift invariant Banach space, to the quasi-Banach case. Analogous properties are deduced for certain matrix spaces. We use these results to prove that the pseudo-differential operator Op ( a ) is a Schatten-q operator from M ∞ to M p and r-nuclear operator from M ∞ to M r when a ∈ M r for suitable p, q and r in ( 0 , ∞ ] .

Authors:Jian-Feng Cai; Tianming Wang; Ke Wei Abstract: Publication date: Available online 19 April 2017 Source:Applied and Computational Harmonic Analysis Author(s): Jian-Feng Cai, Tianming Wang, Ke Wei A spectrally sparse signal of order r is a mixture of r damped or undamped complex sinusoids. This paper investigates the problem of reconstructing spectrally sparse signals from a random subset of n regular time domain samples, which can be reformulated as a low rank Hankel matrix completion problem. We introduce an iterative hard thresholding (IHT) algorithm and a fast iterative hard thresholding (FIHT) algorithm for efficient reconstruction of spectrally sparse signals via low rank Hankel matrix completion. Theoretical recovery guarantees have been established for FIHT, showing that O ( r 2 log 2 ( n ) ) number of samples are sufficient for exact recovery with high probability. Empirical performance comparisons establish significant computational advantages for IHT and FIHT. In particular, numerical simulations on 3D arrays demonstrate the capability of FIHT on handling large and high-dimensional real data.

Authors:Yingzhou Li; Haizhao Yang; Lexing Ying Abstract: Publication date: Available online 18 April 2017 Source:Applied and Computational Harmonic Analysis 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:Yuanxin Li; Yuejie Chi Abstract: Publication date: Available online 1 April 2017 Source:Applied and Computational Harmonic Analysis Author(s): Yuanxin Li, Yuejie Chi We consider simultaneously identifying the membership and locations of point sources that are convolved with different band-limited point spread functions, from the observation of their superpositions. This problem arises in three-dimensional super-resolution single-molecule imaging, neural spike sorting, multi-user channel identification, among other applications. We propose a novel algorithm, based on convex programming, and establish its near-optimal performance guarantee for exact recovery in the noise-free setting by exploiting the spectral sparsity of the point source models as well as the incoherence between point spread functions. Furthermore, robustness of the recovery algorithm in the presence of bounded noise is also established. Numerical examples are provided to demonstrate the effectiveness of the proposed approach.

Authors:Bin Dong Abstract: Publication date: May 2017 Source:Applied and Computational Harmonic Analysis, Volume 42, Issue 3 Author(s): Bin Dong In this paper, we introduce a new (constructive) characterization of tight wavelet frames on non-flat domains in both continuum setting, i.e. on manifolds, and discrete setting, i.e. on graphs; we discuss how fast tight wavelet frame transforms can be computed and how they can be effectively used to process graph data. We start with defining the quasi-affine systems on a given manifold M . The quasi-affine system is formed by generalized dilations and shifts of a finite collection of wavelet functions Ψ : = { ψ j : 1 ≤ j ≤ r } ⊂ L 2 ( R ) . We further require that ψ j is generated by some refinable function ϕ with mask a j . We present the condition needed for the masks { a j : 0 ≤ j ≤ r } , as well as regularity conditions needed for ϕ and ψ j , so that the associated quasi-affine system generated by Ψ is a tight frame for L 2 ( M ) . The condition needed for the masks is a simple set of algebraic equations which are not only easy to verify for a given set of masks { a j } , but also make the construction of { a j } entirely painless. Then, we discuss how the transition from the continuum (manifolds) to the discrete setting (graphs) can be naturally done. In order for the proposed discrete tight wavelet frame transforms to be useful in applications, we show how the transforms can be computed efficiently and accurately by proposing the fast tight wavelet frame transforms for graph data (WFTG). Finally, we consider two specific applications of the proposed WFTG: graph data denoising and semi-supervised clustering. Utilizing the sparse representation provided by the WFTG, we propose ℓ 1 -norm based optimization models on graphs for denoising and semi-supervised clustering. On one hand, our numerical results show significant advantage of the WFTG over the spectral graph wavelet transform (SGWT) by [1] for both applications. On the other hand, numerical experiments on two real data sets show that the proposed semi-supervised clustering model using the WFTG is overall competitive with the state-of-the-art methods developed in the literature of high-dimensional data classification, and is superior to some of these methods.