Search

Let $\mathcal{G} = \{G_1 = (V, E_1), \dots, G_m = (V, E_m)\}$ be a collection of $m$ graphs defined on a common set of vertices $V$ but with different edge sets $E_1, \dots, E_m$. Informally, a function $f :V \rightarrow \mathbb{R}$ is smooth with respect to $G_k = (V,E_k)$ if $f(u) \sim f(v)$ whenever $(u, v) \in E_k$. We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in $\mathcal{G}$, simultaneously, and how to find it if it exists., Comment: 21 pages, 11 figures

Discrete diffusion semigroups have proven to be highly effective tools for machine learning and data analysis due to the interplay between diffusion processes (of inferences), and their naturally associated geometries. Inspired by the harmonic analysis machinery that E. Stein developed for symmetric diffusion semigroups acting on $$L_p$$ spaces, we show that a correspondence between the rate of diffusion approximation and a Besov-type version of smoothness exists in the general continuous case, even without a local kernel representation. Specifically, let $$\left\{ A_t\right\} _{t\ge 0}$$ be a symmetric diffusion semigroup on $$L_p(X)$$ , for X a complete positive $$\sigma $$ -finite measure space. We first establish that for $$1

The high-dimensional data created by high-throughput technologies require visualization tools that reveal data structure and patterns in an intuitive form. We present PHATE, a visualization method that captures both local and global nonlinear structure using an information-geometric distance between data points. We compare PHATE to other tools on a variety of artificial and biological datasets, and find that it consistently preserves a range of patterns in data, including continual progressions, branches and clusters, better than other tools. We define a manifold preservation metric, which we call denoised embedding manifold preservation (DEMaP), and show that PHATE produces lower-dimensional embeddings that are quantitatively better denoised as compared to existing visualization methods. An analysis of a newly generated single-cell RNA sequencing dataset on human germ-layer differentiation demonstrates how PHATE reveals unique biological insight into the main developmental branches, including identification of three previously undescribed subpopulations. We also show that PHATE is applicable to a wide variety of data types, including mass cytometry, single-cell RNA sequencing, Hi-C and gut microbiome data.

Experimental work across a variety of species has demonstrated that spontaneously generated behaviors are robustly coupled to variation in neural activity within the cerebral cortex. Indeed, functional magnetic resonance imaging (fMRI) data suggest that functional connectivity in cortical networks varies across distinct behavioral states, providing for the dynamic reorganization of patterned activity. However, these studies generally lack the temporal resolution to establish links between cortical signals and the continuously varying fluctuations in spontaneous behavior typically observed in awake animals. Here, we took advantage of recent developments in wide-field, mesoscopic calcium imaging to monitor neural activity across the neocortex of awake mice. We develop a novel “graph of graphs” approach to quantify rapidly time-varying functional connectivity and show that spontaneous behaviors are represented by fast changes in both the activity and correlational structure of cortical network activity. Combining mesoscopic imaging with simultaneous cellular resolution 2-photon microscopy also demonstrated that the correlations among neighboring neurons and between local and large-scale networks also encodes behavior. Finally, the dynamic functional connectivity of mesoscale signals revealed subnetworks that are not predicted by traditional anatomical atlas-based parcellation of the cortex. These results provide new insight into how behavioral information is represented across the mammalian neocortex and demonstrate an analytical framework for investigating time-varying functional connectivity in neural networks.

A fundamental step in many data-analysis techniques is the construction of an affinity matrix describing similarities between data points. When the data points reside in Euclidean space, a widespread approach is to from an affinity matrix by the Gaussian kernel with pairwise distances, and to follow with a certain normalization (e.g. the row-stochastic normalization or its symmetric variant). We demonstrate that the doubly-stochastic normalization of the Gaussian kernel with zero main diagonal (i.e., no self loops) is robust to heteroskedastic noise. That is, the doubly-stochastic normalization is advantageous in that it automatically accounts for observations with different noise variances. Specifically, we prove that in a suitable high-dimensional setting where heteroskedastic noise does not concentrate too much in any particular direction in space, the resulting (doubly-stochastic) noisy affinity matrix converges to its clean counterpart with rate

Significance A fundamental issue in empirical science is the ability to calibrate between different types of measurements/observations of the same phenomenon. This naturally suggests the selection of canonical variables, in the spirit of principal components, to enable matching/calibration among different observation modalities/instruments. We develop a method for extracting standardized, nonlinear, intrinsic coordinates from measured data, leading to a generalized isometric embedding of the observations. This is achieved through a local burst data acquisition strategy that allows us to capture the local z-scored structure. We implement this method using a local conformal autoencoder architecture and illustrate it computationally. The proposed embedding is fast, parallelizable, easy to implement using existing open-source neural network implementations and exhibits surprising interpolation and extrapolation capabilities., We propose a local conformal autoencoder (LOCA) for standardized data coordinates. LOCA is a deep learning-based method for obtaining standardized data coordinates from scientific measurements. Data observations are modeled as samples from an unknown, nonlinear deformation of an underlying Riemannian manifold, which is parametrized by a few normalized, latent variables. We assume a repeated measurement sampling strategy, common in scientific measurements, and present a method for learning an embedding in Rd that is isometric to the latent variables of the manifold. The coordinates recovered by our method are invariant to diffeomorphisms of the manifold, making it possible to match between different instrumental observations of the same phenomenon. Our embedding is obtained using LOCA, which is an algorithm that learns to rectify deformations by using a local z-scoring procedure, while preserving relevant geometric information. We demonstrate the isometric embedding properties of LOCA in various model settings and observe that it exhibits promising interpolation and extrapolation capabilities, superior to the current state of the art. Finally, we demonstrate LOCA’s efficacy in single-site Wi-Fi localization data and for the reconstruction of three-dimensional curved surfaces from two-dimensional projections.

We consider orthogonal decompositions of invariant subspaces of Hardy spaces, these relate to the Blaschke based phase unwinding decompositions. We prove convergence in Lp. In particular we build an explicit multiscale wavelet basis. We also obtain an explicit unwindinig decomposition for the singular inner function, exp 2i\pi/x., Comment: 12 pages

We discuss approximation of functions using deep neural nets. Given a function $f$ on a $d$-dimensional manifold $\Gamma \subset \mathbb{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 $\Gamma$, 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), Comment: accepted for publication in Applied and Computational Harmonic Analysis

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., 16 pages, 8 figures

Multi-time-scale stochastic dynamical systems are ubiquitous in science and engineering, and the reduction of such systems and their models to only their slow components is often essential for scientific computation and further analysis. Rather than being available in the form of an explicit analytical model, often such systems can only be observed as a data set which embodies dynamics on several time scales. We focus on applying and adapting data-mining and manifold learning techniques to detect the slow components in a class of such multiscale data. Traditional data-mining methods are based on metrics (and thus, geometries) which are not informed of the multiscale nature of the underlying system dynamics; such methods cannot successfully recover the slow variables. Here, we present an approach which utilizes both the local geometry and the local noise dynamics within the data set through a metric which is both insensitive to the fast variables and more general than simple statistical averaging. Our anal...

Recent advances in experimental methods in neuroscience enable measuring in-vivo activity of large populations of neurons at cellular level resolution. To leverage the full potential of these complex datasets and analyze the dynamics of individual neurons, it is essential to extract high-resolution regions of interest, while addressing demixing of overlapping spatial components and denoising of the temporal signal of each neuron. In this paper, we propose a data-driven solution to these challenges, by representing the spatiotemporal volume as a graph in the image plane. Based on the spectral embedding of this graph calculated across trials, we propose a new clustering method, Local Selective Spectral Clustering, capable of handling overlapping clusters and disregarding clutter. We also present a new nonlinear mapping which recovers the structural map of the neurons and dendrites, and global video denoising. We demonstrate our approach on in-vivo calcium imaging of neurons and apical dendrites, automatically extracting complex structures in the image domain, and denoising and demixing their time-traces.

With the advent of high-throughput technologies measuring high-dimensional biological data, there is a pressing need for visualization tools that reveal data structure and emergent patterns in an intuitive form. We present PHATE, an unsupervised visualization method that captures both local and global non-linear structure in data by preserving informational distance between data points. PHATE reveals a range of patterns in data including continual progressions, branches, and clusters without imposing any prior assumptions on the latent data structure. We apply PHATE on a wide variety of datasets, including CyTOF, single-cell RNA-sequencing (scRNA-seq), Hi-C, and gut microbiome data and show its effectiveness in generating new insights into the underlying systems. We apply and experimentally validate PHATE using a newly generated scRNA-seq dataset of human germ layer differentiation in which PHATE reveals a dynamic picture of the main developmental branches in unparalleled detail.

It is known that if $(p_n)_{n \in \mathbb{N}}$ is a sequence of orthogonal polynomials in $L^2([-1,1], w(x)dx)$, then the roots are distributed according to an arcsine distribution $\pi^{-1} (1-x^2)^{-1}dx$ for a wide variety of weights $w(x)$. We connect this to a result of the Hilbert transform due to Tricomi: if $f(x)(1-x^2)^{1/4} \in L^2(-1,1)$ and its Hilbert transform $Hf$ vanishes on $(-1,1)$, then the function $f$ is a multiple of the arcsine distribution $$ f(x) = \frac{c}{\sqrt{1-x^2}}\chi_{(-1,1)} \qquad \mbox{where}~c~\in \mathbb{R}.$$ We also prove a localized Parseval-type identity that seems to be new: if $f(x)(1-x^2)^{1/4} \in L^2(-1,1)$ and $f(x) \sqrt{1-x^2}$ has mean value 0 on $(-1,1)$, then $$ \int_{-1}^{1}{ (Hf)(x)^2 \sqrt{1-x^2} dx} = \int_{-1}^{1}{ f(x)^2 \sqrt{1-x^2} dx}.$$, Comment: The Isometry property was derived previously by Ledoux & Popescu (The One Dimensional Free Poincare Inequality)

Dimensionality reduction in multivariate time series analysis has broad applications, ranging from financial data analysis to biomedical research. However, high levels of ambient noise and various interferences result in nonstationary signals, which may lead to inefficient performance of conventional methods. In this paper, we propose a nonlinear dimensionality reduction framework using diffusion maps on a learned statistical manifold, which gives rise to the construction of a low-dimensional representation of the high-dimensional nonstationary time series. We show that diffusion maps, with affinity kernels based on the Kullback-Leibler divergence between the local statistics of samples, allow for efficient approximation of pairwise geodesic distances. To construct the statistical manifold, we estimate time-evolving parametric distributions by designing a family of Bayesian generative models. The proposed framework can be applied to problems in which the time-evolving distributions (of temporally localized data), rather than the samples themselves, are driven by a low-dimensional underlying process. We provide efficient parameter estimation and dimensionality reduction methodologies, and apply them to two applications: music analysis and epileptic-seizure prediction. Author-HighlightsWe build a class of Bayesian models to learn the evolving statistics of time series.We construct diffusion maps based on the time-evolving distributional information.The proposed method recovers the underlying process controlling the time series.The proposed framework is applied to the analysis of music and icEEG recordings.

We study the inference of latent intrinsic variables of dynamical systems from output signal measurements. The primary focus is the construction of an intrinsic distance between signal measurements, which is independent of the measurement device. This distance enables us to infer the latent intrinsic variables through the solution of an eigenvector problem with a Laplace operator based on a kernel. The signal geometry and its dynamics are represented with nonlinear observers. An analysis of the properties of the observers that allow for accurate recovery of the latent variables is given, and a way to test whether these properties are satisfied from the measurements is proposed. Scattering and window Fourier transform observers are compared. Applications are shown on simulated data, and on real intracranial Electroencephalography (EEG) signals of epileptic patients recorded prior to seizures.

In a broad range of natural and real-world dynamical systems, measured signals are controlled by underlying processes or drivers. As a result, these signals exhibit highly redundant representations, while their temporal evolution can often be compactly described by dynamical processes on a low-dimensional manifold. In this paper, we propose a graph-based method for revealing the low-dimensional manifold and inferring the processes. This method provides intrinsic models for measured signals, which are noise resilient and invariant under different random measurements and instrumental modalities. Such intrinsic models may enable mathematical calibration of complex measurements and build an empirical geometry driven by the observations, which is especially suitable for applications without a priori knowledge of models and solutions. We exploit the temporal dynamics and natural small perturbations of the signals to explore the local tangent spaces of the low-dimensional manifold of empirical probability densities. This information is used to define an intrinsic Riemannian metric, which in turn gives rise to the construction of a graph that represents the desired low-dimensional manifold. Such a construction is equivalent to an inverse problem, which is formulated as a nonlinear differential equation and is solved empirically through eigenvectors of an appropriate Laplace operator. We examine our method on two nonlinear filtering applications: a nonlinear and non-Gaussian tracking problem as well as a non-stationary hidden Markov chain scheme. The experimental results demonstrate the power of our theory by extracting the underlying processes, which were measured through different nonlinear instrumental conditions, in an entirely data-driven nonparametric way.

In this paper we answer the following question: what is the infinitesimal generator of the diffusion process defined by a kernel that is normalized such that it is bi-stochastic with respect to a specified measure? More precisely, under the assumption that data is sampled from a Riemannian manifold we determine how the resulting infinitesimal generator depends on the potentially nonuniform distribution of the sample points, and the specified measure for the bi-stochastic normalization. In a special case, we demonstrate a connection to the heat kernel. We consider both the case where only a single data set is given, and the case where a data set and a reference set are given. The spectral theory of the constructed operators is studied, and Nystr\"om extension formulas for the gradients of the eigenfunctions are computed. Applications to discrete point sets and manifold learning are discussed., Comment: 18 pages, 5 figures

The discovery of physical laws consistent with empirical observations is at the heart of (applied) science and engineering. These laws typically take the form of nonlinear differential equations depending on parameters; dynamical systems theory provides, through the appropriate normal forms, an “intrinsic” prototypical characterization of the types of dynamical regimes accessible to a given model. Using an implementation of data-informed geometry learning, we directly reconstruct the relevant “normal forms”: a quantitative mapping from empirical observations to prototypical realizations of the underlying dynamics. Interestingly, the state variables and the parameters of these realizations are inferred from the empirical observations; without prior knowledge or understanding, they parametrize the dynamics intrinsically without explicit reference to fundamental physical quantities.

Significance Direct simulations explore the dynamics of physical systems at their natural pace. Molecular dynamics (MD) simulations (e.g., of macromolecular folding) extensively revisit typical configurations until rare and interesting transition events occur. Biasing the simulator away from regions already explored can, therefore, drastically accelerate the discovery of features. We propose an enhanced sampling simulation framework, where MD and machine learning adaptively bootstrap each other. Machine learning guides the search for important configurations by processing information from previous explorations. This search proceeds iteratively in an algorithmically orchestrated fashion without advance knowledge of suitable collective variables. Applied to a molecular sensor of lipid saturation in membranes, a helix dissociation pathway not seen in millisecond simulations is discovered at the second iteration.