Title: Geometric wavelet scattering on graphs and manifolds
Convolutional neural networks (CNNs) are revolutionizing imaging science for two- and three-dimensional images over Euclidean domains. However, many data sets are intrinsically non-Euclidean and are better modeled through other mathematical structures, such as graphs or manifolds. This state of affairs has led to the development of geometric deep learning, which refers to a body of research that aims to translate the principles of CNNs to these non-Euclidean structures. In the process, various challenges have arisen, including how to define such geometric networks, how to compute and train them efficiently, and what are their mathematical properties.
In this letter we describe the geometric wavelet scattering transform, which is a type of geometric CNN for graphs and manifolds consisting of alternating multiscale geometric wavelet transforms and nonlinear activation functions. As the name suggests, the geometric wavelet scattering transform is an adaptation of the Euclidean wavelet scattering transform, first introduced by S. Mallat, to graph and manifold data. Like its Euclidean counterpart, the geometric wavelet scattering transform has several desirable properties. In the manifold setting these properties include isometric invariance up to a user specified scale and stability to small diffeomorphisms. Numerical results on manifold and graph data sets, including graph and manifold classification tasks as well as others, illustrate the practical utility of the approach. more »« less
The Euclidean scattering transform was introduced nearly a decade ago to improve the mathematical understanding of convolutional neural networks. Inspired by recent interest in geometric deep learning, which aims to generalize convolutional neural networks to manifold and graph-structured domains, we define a geometric scattering transform on manifolds. Similar to the Euclidean scattering transform, the geometric scattering transform is based on a cascade of wavelet filters and pointwise nonlinearities. It is invariant to local isometries and stable to certain types of diffeomorphisms. Empirical results demonstrate its utility on several geometric learning tasks. Our results generalize the deformation stability and local translation invariance of Euclidean scattering, and demonstrate the importance of linking the used filter structures to the underlying geometry of the data.
In this work we study statistical properties of graph-based algorithms for multi-manifold
clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a
given Euclidean data set when this one is assumed to be obtained by sampling a distribution
on a union of manifolds M = M1 ∪ · · · ∪ MN that may intersect with each other and
that may have different dimensions. We investigate sufficient conditions that similarity
graphs on data sets must satisfy in order for their corresponding graph Laplacians to
capture the right geometric information to solve the MMC problem. Precisely, we provide
high probability error bounds for the spectral approximation of a tensorized Laplacian on
M with a suitable graph Laplacian built from the observations; the recovered tensorized
Laplacian contains all geometric information of all the individual underlying manifolds. We
provide an example of a family of similarity graphs, which we call annular proximity graphs
with angle constraints, satisfying these sufficient conditions. We contrast our family of
graphs with other constructions in the literature based on the alignment of tangent planes.
Extensive numerical experiments expand the insights that our theory provides on the MMC
problem.
Embedding properties of network realizations of dissipative reduced order models
Jörn Zimmerling, Mikhail Zaslavsky,Rob Remis, Shasri Moskow, Alexander Mamonov, Murthy Guddati,
Vladimir Druskin, and Liliana Borcea
Mathematical Sciences Department, Worcester Polytechnic Institute
https://www.wpi.edu/people/vdruskin
Abstract
Realizations of reduced order models of passive SISO or MIMO LTI problems can be transformed to tridiagonal and
block-tridiagonal forms, respectively, via dierent modications of the Lanczos algorithm. Generally, such realizations
can be interpreted as ladder resistor-capacitor-inductor (RCL) networks. They gave rise to network syntheses in the
rst half of the 20th century that was at the base of modern electronics design and consecutively to MOR that
tremendously impacted many areas of engineering (electrical, mechanical, aerospace, etc.) by enabling ecient
compression of the underlining dynamical systems. In his seminal 1950s works Krein realized that in addition to
their compressing properties, network realizations can be used to embed the data back into the state space of the
underlying continuum problems.
In more recent works of the authors Krein's ideas gave rise to so-called nite-dierence Gaussian quadrature rules
(FDGQR), allowing to approximately map the ROM state-space representation to its full order continuum counterpart
on a judicially chosen grid. Thus, the state variables can be accessed directly from the transfer function without
solving the full problem and even explicit knowledge of the PDE coecients in the interior, i.e., the FDGQR directly
learns" the problem from its transfer function. This embedding property found applications in PDE solvers, inverse
problems and unsupervised machine learning.
Here we show a generalization of this approach to dissipative PDE problems, e.g., electromagnetic and acoustic
wave propagation in lossy dispersive media. Potential applications include solution of inverse scattering problems in
dispersive media, such as seismic exploration, radars and sonars.
To x the idea, we consider a passive irreducible SISO ROM
fn(s) = Xn
j=1
yi
s + σj
, (62)
assuming that all complex terms in (62) come in conjugate pairs.
We will seek ladder realization of (62) as
rjuj + vj − vj−1 = −shˆjuj ,
uj+1 − uj + ˆrj vj = −shj vj ,
(63)
for j = 0, . . . , n with boundary conditions
un+1 = 0, v1 = −1,
and 4n real parameters hi, hˆi, ri and rˆi, i = 1, . . . , n, that can be considered, respectively, as the equivalent discrete
inductances, capacitors and also primary and dual conductors. Alternatively, they can be viewed as respectively
masses, spring stiness, primary and dual dampers of a mechanical string. Reordering variables would bring (63)
into tridiagonal form, so from the spectral measure given by (62 ) the coecients of (63) can be obtained via a
non-symmetric Lanczos algorithm written in J-symmetric form and fn(s) can be equivalently computed as
fn(s) = u1.
The cases considered in the original FDGQR correspond to either (i) real y, θ or (ii) real y and imaginary θ. Both
cases are covered by the Stieltjes theorem, that yields in case (i) real positive h, hˆ and trivial r, rˆ, and in case (ii) real
positive h,r and trivial hˆ,rˆ. This result allowed us a simple interpretation of (62) as the staggered nite-dierence
approximation of the underlying PDE problem [2]. For PDEs in more than one variables (including topologically rich
data-manifolds), a nite-dierence interpretation is obtained via a MIMO extensions in block form, e.g., [4, 3].
The main diculty of extending this approach to general passive problems is that the Stieltjes theory is no longer
applicable. Moreover, the tridiagonal realization of a passive ROM transfer function (62) via the ladder network (63)
cannot always be obtained in port-Hamiltonian form, i.e., the equivalent primary and dual conductors may change
sign [1].
100
Embedding of the Stieltjes problems, e.g., the case (i) was done by mapping h and hˆ into values of acoustic (or
electromagnetic) impedance at grid cells, that required a special coordinate stretching (known as travel time coordinate transform) for continuous problems. Likewise, to circumvent possible non-positivity of conductors for the
non-Stieltjes case, we introduce an additional complex s-dependent coordinate stretching, vanishing as s → ∞ [1].
This stretching applied in the discrete setting induces a diagonal factorization, removes oscillating coecients, and
leads to an accurate embedding for moderate variations of the coecients of the continuum problems, i.e., it maps
discrete coecients onto the values of their continuum counterparts.
Not only does this embedding yields an approximate linear algebraic algorithm for the solution of the inverse problems
for dissipative PDEs, it also leads to new insight into the properties of their ROM realizations. We will also discuss
another approach to embedding, based on Krein-Nudelman theory [5], that results in special data-driven adaptive
grids.
References
[1] Borcea, Liliana and Druskin, Vladimir and Zimmerling, Jörn, A reduced order model approach to
inverse scattering in lossy layered media, Journal of Scientic Computing, V. 89, N1, pp. 136,2021
[2] Druskin, Vladimir and Knizhnerman, Leonid, Gaussian spectral rules for the three-point second dierences:
I. A two-point positive denite problem in a semi-innite domain, SIAM Journal on Numerical Analysis, V. 37,
N 2, pp.403422, 1999
[3] Druskin, Vladimir and Mamonov, Alexander V and Zaslavsky, Mikhail, Distance preserving model
order reduction of graph-Laplacians and cluster analysis, Druskin, Vladimir and Mamonov, Alexander V
and Zaslavsky, Mikhail, Journal of Scientic Computing, V. 90, N 1, pp 130, 2022
[4] Druskin, Vladimir and Moskow, Shari and Zaslavsky, Mikhail LippmannSchwingerLanczos algorithm
for inverse scattering problems, Inverse Problems, V. 37, N. 7, 2021,
[5] Mark Adolfovich Nudelman The Krein String and Characteristic Functions of Maximal Dissipative Operators, Journal of Mathematical Sciences, 2004, V 124, pp 49184934
Go back to Plenary Speakers Go back to Speakers Go back
Gaussian processes (GPs) are very widely used for modeling of unknown functions or surfaces in applications ranging from regression to classification to spatial processes. Although there is an increasingly vast literature on applications, methods, theory and algorithms related to GPs, the overwhelming majority of this literature focuses on the case in which the input domain corresponds to a Euclidean space. However, particularly in recent years with the increasing collection of complex data, it is commonly the case that the input domain does not have such a simple form. For example, it is common for the inputs to be restricted to a non-Euclidean manifold, a case which forms the motivation for this article. In particular, we propose a general extrinsic framework for GP modeling on manifolds, which relies on embedding of the manifold into a Euclidean space and then constructing extrinsic kernels for GPs on their images. These extrinsic Gaussian processes (eGPs) are used as prior distributions for unknown functions in Bayesian inferences. Our approach is simple and general, and we show that the eGPs inherit fine theoretical properties from GP models in Euclidean spaces. We consider applications of our models to regression and classification problems with predictors lying in a large class of manifolds, including spheres, planar shape spaces, a space of positive definite matrices, and Grassmannians. Our models can be readily used by practitioners in biological sciences for various regression and classification problems, such as disease diagnosis or detection. Our work is also likely to have impact in spatial statistics when spatial locations are on the sphere or other geometric spaces.
Ma, X.; Kirby, M.; Peterson, C.(
, Neural computing applications)
A flag is a nested sequence of vector spaces. The type of the flag encodes the sequence of dimensions of the vector spaces making up the flag. A flag manifold is a manifold whose points parameterize all flags of a fixed type in a fixed vector space. This paper provides the mathematical framework necessary for implementing self-organizing mappings on flag manifolds. Flags arise implicitly in many data analysis contexts including wavelet, Fourier, and singular value decompositions. The proposed geometric framework in this paper enables the computation of distances between flags, the computation of geodesics between flags, and the ability to move one flag a prescribed distance in the direction of another flag. Using these
operations as building blocks, we implement the SOM algorithm on a flag manifold. The basic algorithm is applied to the problem of parameterizing a set of flags of a fixed type.
Gao, Feng, Hirn, Matthew, Perlmutter, Michael, and Wolf, Guy. Geometric wavelet scattering on graphs and manifolds. Retrieved from https://par.nsf.gov/biblio/10166066. Proceedings SPIE 11138, Wavelets and Sparsity XVIII . Web. doi:10.1117/12.2529615.
Gao, Feng, Hirn, Matthew, Perlmutter, Michael, and Wolf, Guy.
"Geometric wavelet scattering on graphs and manifolds". Proceedings SPIE 11138, Wavelets and Sparsity XVIII (). Country unknown/Code not available. https://doi.org/10.1117/12.2529615.https://par.nsf.gov/biblio/10166066.
@article{osti_10166066,
place = {Country unknown/Code not available},
title = {Geometric wavelet scattering on graphs and manifolds},
url = {https://par.nsf.gov/biblio/10166066},
DOI = {10.1117/12.2529615},
abstractNote = {Convolutional neural networks (CNNs) are revolutionizing imaging science for two- and three-dimensional images over Euclidean domains. However, many data sets are intrinsically non-Euclidean and are better modeled through other mathematical structures, such as graphs or manifolds. This state of affairs has led to the development of geometric deep learning, which refers to a body of research that aims to translate the principles of CNNs to these non-Euclidean structures. In the process, various challenges have arisen, including how to define such geometric networks, how to compute and train them efficiently, and what are their mathematical properties. In this letter we describe the geometric wavelet scattering transform, which is a type of geometric CNN for graphs and manifolds consisting of alternating multiscale geometric wavelet transforms and nonlinear activation functions. As the name suggests, the geometric wavelet scattering transform is an adaptation of the Euclidean wavelet scattering transform, first introduced by S. Mallat, to graph and manifold data. Like its Euclidean counterpart, the geometric wavelet scattering transform has several desirable properties. In the manifold setting these properties include isometric invariance up to a user specified scale and stability to small diffeomorphisms. Numerical results on manifold and graph data sets, including graph and manifold classification tasks as well as others, illustrate the practical utility of the approach.},
journal = {Proceedings SPIE 11138, Wavelets and Sparsity XVIII},
author = {Gao, Feng and Hirn, Matthew and Perlmutter, Michael and Wolf, Guy},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.