Abstract 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 l 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.
Redundant systems were considered by Maggioni and Mhaskar @cite_39 where they developed a theory of diffusion polynomial frames that is related to our framework. However, they did not provide any algorithm for efficient computation of the decomposition and reconstruction transforms which are crucial to many applications. Geller and Mayeli @cite_65 studied a construction for wavelets on compact differentiable manifolds. In particular, their scaling is defined using a pseudodifferential operator @math , where @math is the Laplace-Beltrami operator on the given manifold and @math is the scaling parameter. Wavelets are obtained by applying the pseudodifferential operator to a delta impulse. In our framework, the scaling is defined by @math where @math is a refinable function. The wavelets are obtained by applying @math , with @math and @math , to delta impulses at each points of the given manifold. Moreover, we do not need to assume the manifolds are smooth for our approach.
@cite_65 @cite_39
2003334210 2001125076
Let M be a smooth compact oriented Riemannian manifold, and let ΔM be the Laplace–Beltrami operator on M. Say ( 0 f S ( R ^+) ) , and that f (0) = 0. For t > 0, let Kt(x, y) denote the kernel of f (t2 ΔM). We show that Kt is well-localized near the diagonal, in the sense that it satisfies estimates akin to those satisfied by the kernel of the convolution operator f (t2Δ) on ( R ^n ) . We define continuous ( S )-wavelets on M, in such a manner that Kt(x, y) satisfies this definition, because of its localization near the diagonal. Continuous ( S )-wavelets on M are analogous to continuous wavelets on ( R ^n ) in ( S ) ( ( R ^n )). In particular, we are able to characterize the Holder continuous functions on M by the size of their continuous ( S )-wavelet transforms, for Holder exponents strictly between 0 and 1. If M is the torus ( T^2 ) or the sphere S2, and f (s) = se−s (the “Mexican hat” situation), we obtain two explicit approximate formulas for Kt, one to be used when t is large, and one to be used when t is small. We construct a multiscale tight frame based on an arbitrary orthonormal basis for the L2 space of an arbitrary sigma finite measure space. The approximation properties of the resulting multiscale are studied in the context of Besov approximation spaces, which are characterized both in terms of suitable K-functionals and the frame transforms. The only major condition required is the uniform boundedness of a summability operator. We give sufficient conditions for this to hold in the context of a very general class of metric measure spaces. The theory is illustrated using the approximation of characteristic functions of caps on a dumbell manifold, and applied to the problem of recognition of hand-written digits. Our methods outperforms comparable methods for semi-supervised learning.