Search

Let G = { G 1 = (V , E 1) , ... , 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 , ... , E m . Informally, a function f : V → R is smooth with respect to G k = (V , E k) if f (u) ∼ f (v) whenever (u , v) ∈ E k . We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in G , simultaneously, and how to find it if it exists. [ABSTRACT FROM AUTHOR]

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 non-uniform 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öm extension formulas for the gradients of the eigenfunctions are computed. Applications to discrete point sets and manifold learning are discussed. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we build an organization of high-dimensional datasets that cannot be cleanly embedded into a low-dimensional representation due to missing entries and a subset of the features being irrelevant to modeling functions of interest. Our algorithm begins by defining coarse neighborhoods of the points and defining an expected empirical function value on these neighborhoods. We then generate new non-linear features with deep net representations tuned to model the approximate function, and re-organize the geometry of the points with respect to the new representation. Finally, the points are locally z-scored to create an intrinsic geometric organization which is independent of the parameters of the deep net, a geometry designed to assure smoothness with respect to the empirical function. We examine this approach on data from the Center for Medicare and Medicaid Services Hospital Quality Initiative, and generate an intrinsic low-dimensional organization of the hospitals that is smooth with respect to an expert driven function of quality. [ABSTRACT FROM AUTHOR]

We prove that functions of intrinsic-mode type (a classical models for signals) behave essentially like holomorphic functions: adding a pure carrier frequency eint ensures that the anti-holomorphic part is much smaller than the holomorphic part || P-(f)||L² « P+(f)||L²>. This enables us to use techniques from complex analysis, in particular the unwinding series. We study its stability and convergence properties and show that the unwinding series can provide a high-resolution, noise- robust time-frequency representation. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: Graph Laplacians and related nonlinear mappings into low dimensional spaces have been shown to be powerful tools for organizing high dimensional data. Here we consider a data set X in which the graph associated with it changes depending on some set of parameters. We analyze this type of data in terms of the diffusion distance and the corresponding diffusion map. As the data changes over the parameter space, the low dimensional embedding changes as well. We give a way to go between these embeddings, and furthermore, map them all into a common space, allowing one to track the evolution of X in its intrinsic geometry. A global diffusion distance is also defined, which gives a measure of the global behavior of the data over the parameter space. Approximation theorems in terms of randomly sampled data are presented, as are potential applications. [Copyright &y& Elsevier]

In this paper, we present a method for time series analysis based on empirical intrinsic geometry (EIG). EIG enables one to reveal the low-dimensional parametric manifold as well as to infer the underlying dynamics of high-dimensional time series. By incorporating concepts of information geometry, this method extends existing geometric analysis tools to support stochastic settings and parametrizes the geometry of empirical distributions. However, the statistical models are not required as priors; hence, EIG may be applied to a wide range of real signals without existing definitive models. We show that the inferred model is noise-resilient and invariant under different observation and instrumental modalities. In addition, we show that it can be extended efficiently to newly acquired measurements in a sequential manner. These two advantages enable us to revisit the Bayesian approach and incorporate empirical dynamics and intrinsic geometry into a nonlinear filtering framework. We show applications to nonlinear and non-Gaussian tracking problems as well as to acoustic signal localization. [ABSTRACT FROM AUTHOR]

Abstract: In this short letter we present the construction of a bi-stochastic kernel p for an arbitrary data set X that is derived from an asymmetric affinity function α. The affinity function α measures the similarity between points in X and some reference set Y. Unlike other methods that construct bi-stochastic kernels via some convergent iteration process or through solving an optimization problem, the construction presented here is quite simple. Furthermore, it can be viewed through the lens of out of sample extensions, making it useful for massive data sets. [Copyright &y& Elsevier]

Abstract: The need to organize and analyze real-valued matrices arises in various settings – notably, in data analysis (where matrices are multivariate data sets) and in numerical analysis (where matrices represent linear operators). We provide a formal framework for matrix organization and subsequent analysis. A matrix is organized by providing two metrics – one on the column set and one on the row set. An organization is coherent if matrix entries can be predicted from close-by entries, or formally, if the matrix is mixed Hölder in the two metrics. Coherent matrix organization becomes computationally feasible and theoretically tractable by focusing on special metrics, induced by hierarchical partition trees on the row and column sets. Finding an organization then reduces to performing simultaneous row–column hierarchical metric vector quantization of the matrix. Building on an orthogonal “Haar” transform for matrix space induced by a partition tree pair, we characterize the mixed-Hölder matrix class in terms of tensor product wavelet coefficient decay and calculate its n-width. We also provide procedures for constructing coherent organizations and show how to quantitatively compare candidate organizations for a given matrix. We use the Haar transform to provide optimal sampling, approximation and compression algorithms for coherently organized matrices, proving that they can be substantially subsampled. When a matrix is noisy and cannot be organized so as to achieve a specified mixed-Hölder smoothness, we show that under an easy to check condition of Besov-space type, it can be decomposed as a sum of a coherent matrix, with the specified mixed-Hölder smoothness, and a noisy or incoherent matrix with few nonzero entries. [Copyright &y& Elsevier]

Abstract: Recovering the three-dimensional structure of molecules is important for understanding their functionality. We describe a spectral graph algorithm for reconstructing the three-dimensional structure of molecules from their cryo-electron microscopy images taken at random unknown orientations. We first identify a one-to-one correspondence between radial lines in three-dimensional Fourier space of the molecule and points on the unit sphere. The problem is then reduced to determining the coordinates of points on the sphere given a subset of their pairwise geodesic distances. To recover those coordinates, we exploit the special geometry of the problem, as rendered by the Fourier projection–slice theorem, to construct a weighted graph whose vertices are the radial Fourier lines and whose edges are linked using the common line property. The graph organizes the radial lines on the sphere in a global manner that reveals the acquisition direction of each image. This organization is derived from a global computation of a few eigenvectors of the graph''s sparse adjacency matrix. Once the directions are obtained, the molecule can be reconstructed using classical tomography methods. The presented algorithm is direct (as opposed to iterative refinement schemes), does not require any prior model for the reconstructed object, and is shown to have favorable computational and numerical properties. Moreover, the algorithm does not impose any assumption on the distribution of the projection orientations. Physically, this means that the algorithm is applicable to molecules that have unknown spatial preference. [Copyright &y& Elsevier]

Abstract: The single-particle reconstruction problem of electron cryo-microscopy (cryo-EM) is to find the three-dimensional structure of a macromolecule given its two-dimensional noisy projection images at unknown random directions. Ab initio estimates of the 3D structure are often obtained by the “Angular Reconstitution” method, in which a coordinate system is established from three projections, and the orientation of the particle giving rise to each image is deduced from common lines among the images. However, a reliable detection of common lines is difficult due to the low signal-to-noise ratio of the images. In this paper we describe a global self-correcting voting procedure in which all projection images participate to decide the identity of the consistent common lines. The algorithm determines which common line pairs were detected correctly and which are spurious. We show that the voting procedure succeeds at relatively low detection rates and that its performance improves as the number of projection images increases. We demonstrate the algorithm for both simulative and experimental images of the 50S ribosomal subunit. [Copyright &y& Elsevier]

Data fusion is a natural and common approach to recovering the state of physical systems. But the dissimilar appearance of different sensors remains a fundamental obstacle. We propose a unified embedding scheme for multisensory data, based on the spectral diffusion framework, which addresses this issue. Our scheme is purely data-driven and assumes no a priori statistical or deterministic models of the data sources. To extract the underlying structure, we first embed separately each input channel; the resultant structures are then combined in diffusion coordinates. In particular, as different sensors sample similar phenomena with different sampling densities, we apply the density invariant Laplace-Beltrami embedding. This is a fundamental issue in multisensor acquisition and processing, overlooked in prior approaches. We extend previous work on group recognition and suggest a novel approach to the selection of diffusion coordinates. To verify our approach, we demonstrate performance improvements in audio/visual speech recognition. [ABSTRACT FROM AUTHOR]

We introduce a graph Laplacian-based algorithm for the tomographic reconstruction of a planar object from its projections taken at random unknown directions. A Laplace-type operator is constructed on the data set of projections, and the eigenvectors of this operator reveal the projection orientations. The algorithm is shown to successfully reconstruct the Shepp—Logan phantom from its noisy projections. Such a reconstruction algorithm is desirable for the structuring of certain biological proteins using cryo-electron microscopy. [ABSTRACT FROM AUTHOR]

Abstract: We introduce intrinsic, non-linearly invariant, parameterizations of empirical data, generated by a non-linear transformation of independent variables. This is achieved through anisotropic diffusion kernels on observable data manifolds that approximate a Laplacian on the inaccessible independent variable domain. The key idea is a symmetrized second-order approximation of the unknown distances in the independent variable domain, using the metric distortion induced by the Jacobian of the unknown mapping from variables to data. This distortion is estimated using local principal component analysis. Thus, the non-linear independent component analysis problem is solved whenever the generation of the data enables the estimation of the Jacobian. In particular, we obtain the non-linear independent components of stochastic Itô processes and indicate other possible applications. [Copyright &y& Elsevier]

Abstract: Diffusion wavelets can be constructed on manifolds, graphs and allow an efficient multiscale representation of powers of the diffusion operator that generates them. In many applications it is necessary to have time–frequency bases that are more versatile than wavelets, for example for the analysis, denoising and compression of a signal. In the Euclidean setting, wavelet packets have been very successful in many applications, ranging from image denoising, 2- and 3-dimensional compression of data (e.g., images, seismic data, hyper-spectral data) and in discrimination tasks as well. Till now these tools for signal processing have been available mainly in Euclidean settings and in low dimensions. Building upon the recent construction of diffusion wavelets, we show how to construct diffusion wavelet packets, generalizing the classical construction of wavelet packets, and allowing the same algorithms existing in the Euclidean setting to be lifted to rather general geometric and anisotropic settings, in higher dimension, on manifolds, graphs and even more general spaces. We show that efficient algorithms exists for computations of diffusion wavelet packets and discuss some applications and examples. [Copyright &y& Elsevier]

Abstract: Our goal in this paper is to show that many of the tools of signal processing, adapted Fourier and wavelet analysis can be naturally lifted to the setting of digital data clouds, graphs, and manifolds. We use diffusion as a smoothing and scaling tool to enable coarse graining and multiscale analysis. Given a diffusion operator T on a manifold or a graph, with large powers of low rank, we present a general multiresolution construction for efficiently computing, representing and compressing . This allows a direct multiscale computation, to high precision, of functions of the operator, notably the associated Green''s function, in compressed form, and their fast application. Classes of operators for which these computations are fast include certain diffusion-like operators, in any dimension, on manifolds, graphs, and in non-homogeneous media. We use ideas related to the Fast Multipole Methods and to the wavelet analysis of Calderón–Zygmund and pseudo-differential operators, to numerically enforce the emergence of a natural hierarchical coarse graining of a manifold, graph or data set. For example for a body of text documents the construction leads to a directory structure at different levels of generalization. The dyadic powers of an operator can be used to induce a multiresolution analysis, as in classical Littlewood–Paley and wavelet theory: we construct, with efficient and stable algorithms, bases of orthonormal scaling functions and wavelets associated to this multiresolution analysis, together with the corresponding downsampling operators, and use them to compress the corresponding powers of the operator. While most of our discussion deals with symmetric operators and relates to localization to spectral bands, the symmetry of the operators and their spectral theory need not be considered, as the main assumption is reduction of the numerical ranks as we take powers of the operator. [Copyright &y& Elsevier]

Abstract: We describe a simple scheme, based on the Nyström method, for extending empirical functions f defined on a set X to a larger set . The extension process that we describe involves the construction of a specific family of functions that we term geometric harmonics. These functions constitute a generalization of the prolate spheroidal wave functions of Slepian in the sense that they are optimally concentrated on X. We study the case when X is a submanifold of in greater detail. In this situation, any empirical function f on X can be characterized by its decomposition over the intrinsic Fourier modes, i.e., the eigenfunctions of the Laplace–Beltrami operator, and we show that this intrinsic frequency spectrum determines the largest domain of extension of f to the entire space . Our analysis relates the complexity of the function on the training set to the scale of extension off this set. This approach allows us to present a novel multiscale extension scheme for empirical functions. [Copyright &y& Elsevier]

Abstract: In this paper, we provide a framework based upon diffusion processes for finding meaningful geometric descriptions of data sets. We show that eigenfunctions of Markov matrices can be used to construct coordinates called diffusion maps that generate efficient representations of complex geometric structures. The associated family of diffusion distances, obtained by iterating the Markov matrix, defines multiscale geometries that prove to be useful in the context of data parametrization and dimensionality reduction. The proposed framework relates the spectral properties of Markov processes to their geometric counterparts and it unifies ideas arising in a variety of contexts such as machine learning, spectral graph theory and eigenmap methods. [Copyright &y& Elsevier]

Harmonic analysis on manifolds and graphs has recently led to mathematical developments in the field of data analysis. The resulting new tools can be used to compress and analyze large and complex data sets, such as those derived from sensor networks or neuronal activity datasets, obtained in the laboratory or through computer modeling. The nature of the algorithms (based on diffusion maps and connectivity strengths on graphs) possesses a certain analogy with neural information processing, and has the potential to provide inspiration for modeling and understanding biological organization in perception and memory formation. [Copyright &y& Elsevier]

The authors previously developed the so-called local discriminant basis (LDB) method for signal and image classification problems. The original LDB method relies on differences in the time–frequency energy distribution of each class: it selects the subspaces where these energy distributions are well separated by some measure such as the Kullback–Leibler divergence. Through our experience and experiments on various datasets, however, we realized that the time–frequency energy distribution is not always the best quantity to analyze for classification. In this paper, we propose to use the discrimination of coordinates based, instead, on empirical probability densities. That is, we estimate the probability density of each class in each coordinate in the wavelet packet/local trigonometric bases after expanding signals into such bases. We then evaluate a power of discrimination of each subspace by selecting the m most discriminant coordinates in terms of the “distance” among the corresponding densities (e.g., by the Kullback–Leibler divergence among the densities). This information is then used for selecting a basis for classification. We will demonstrate the capability of this algorithm using both synthetic and real datasets. [Copyright &y& Elsevier]

We consider the functional of total variation for functions of either one or two discrete variables. We introduce a new principle for construction of evolution processes that gradually reduce the total variation of a function. The method is derived from analysis of relaxation of the functional along the directions given by the Haar wavelets - an approach that does not require regularization of either the functional or its singular gradient. We further present a rigorous analysis of the analytical properties of the resulting evolution schemes. The purely discrete theory grows out of universal observations about the relation between the total variation and the Haar functions. An additional advantage of the method is that it can be directly implemented as an effective numerical procedure. Moreover, it can be intertwined in a natural way with a nonlinear phase-space filtering which further increases control of the deformation of a signal. Finally, we report that the algorithms can be used as remarkable tools for signal processing and image enhancement. [ABSTRACT FROM AUTHOR]

The paper introduces a new kernel-based Maximum Mean Discrepancy (MMD) statistic for measuring the distance between two distributions given finitely many multivariate samples. When the distributions are locally low-dimensional, the proposed test can be made more powerful to distinguish certain alternatives by incorporating local covariance matrices and constructing an anisotropic kernel. The kernel matrix is asymmetric; it computes the affinity between |$n$| data points and a set of |$n_R$| reference points, where |$n_R$| can be drastically smaller than |$n$|⁠. While the proposed statistic can be viewed as a special class of Reproducing Kernel Hilbert Space MMD, the consistency of the test is proved, under mild assumptions of the kernel, as long as |$\|p-q\| \sqrt{n} \to \infty $|⁠ , and a finite-sample lower bound of the testing power is obtained. Applications to flow cytometry and diffusion MRI datasets are demonstrated, which motivate the proposed approach to compare distributions. [ABSTRACT FROM AUTHOR]

Abstract We discuss approximation of functions using deep neural nets. Given a function f on a d -dimensional manifold Γ ⊂ R m , we construct a sparsely-connected depth-4 neural network and bound its error in approximating f. The size of the network depends on dimension and curvature of the manifold Γ, the complexity of f , in terms of its wavelet description, and only weakly on the ambient dimension m. Essentially, our network computes wavelet functions, which are computed from Rectified Linear Units (ReLU). [ABSTRACT FROM AUTHOR]

Abstract 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We describe and implement a computer-assisted approach for accelerating the exploration of uncharted effective free-energy surfaces (FESs). More generally, the aim is the extraction of coarsegrained, macroscopic information from stochastic or atomistic simulations, such as molecular dynamics (MD). The approach functionally links the MD simulator with nonlinear manifold learning techniques. The added value comes from biasing the simulator toward unexplored phase-space regions by exploiting the smoothness of the gradually revealed intrinsic low-dimensional geometry of the FES. [ABSTRACT FROM AUTHOR]

Abstract: Patch-based de-noising algorithms and patch manifold smoothing have emerged as efficient de-noising methods. This paper provides a new insight on these methods. We show how to extend them to separate oscillatory patterns that could be entangled. A collection of particular patches, that we call reference set, is selected by the user. We define a notion of similarity relative to this reference set that is used to extend the Non-Local Means (see Buades et al., 2005) [1] and the graph-based de-noising method (see Szlam et al., 2008) [12]. [Copyright &y& Elsevier]

Highlights: [•] We tackled the problem of determining the location in the human body of some CT scan images of different patients. [•] We introduce diffusion metrics in a prediction context, useful for working with misaligned data. [•] A comparative study of different methods based on a kNN search was carried out. [•] Our method based on anisotropic diffusion outperforms the state-of-the-art. [ABSTRACT FROM AUTHOR]

Abstract: We introduce a multiscale scheme for sampling scattered data and extending functions defined on the sampled data points, which overcomes some limitations of the Nyström interpolation method. The multiscale extension (MSE) method is based on mutual distances between data points. It uses a coarse-to-fine hierarchy of the multiscale decomposition of a Gaussian kernel. It generates a sequence of subsamples, which we refer to as adaptive grids, and a sequence of approximations to a given empirical function on the data, as well as their extensions to any newly-arrived data point. The subsampling is done by a special decomposition of the associated Gaussian kernel matrix in each scale in the hierarchical procedure. [Copyright &y& Elsevier]

Objective: We propose an automated nutritional assessment algorithm that provides a method for malnutrition risk prediction with high accuracy and reliability. Methods: The database used for this study was a file of 432 patients, where each patient was described by 4 laboratory parameters and 11 clinical parameters. A malnutrition risk assessment of low (1), moderate (2), or high (3) was assigned by a dietitian for each patient. An algorithm for data organization and classification using characteristic metrics for each patient was developed. For each patient, the algorithm characterized the patients' unique profile and built a characteristic metric to identify similar patients who were mapped into a classification. For each patient, the algorithm characterized the patients' classification. Results: The algorithm assigned a malnutrition risk level for different training sizes that were taken from the data. Our method resulted in average errors (distance between the automated score and the real score) of 0.386, 0.3507, 0.3454, 0.34, and 0.2907 for the 10%, 30%, 50%, 70%, and 90% training sizes, respectively. Our method outperformed the compared method even when our method used a smaller training set than the compared method. In addition, we showed that the laboratory parameters themselves were sufficient for the automated risk prediction and organized the patients into clusters that corresponded to low-, low--moderate-, moderate-, moderate--high-, and high-risk areas. The organization and visualization methods provided a tool for the exploration and navigation of the data points. Conclusion: The problem of rapidly identifying risk and severity of malnutrition is crucial for minimizing medical and surgical complications. These are not easily performed or adequately expedited. We characterized for each patient a unique profile and mapped similar patients into a classification. We also found that the laboratory parameters were sufficient for the automated risk prediction. [ABSTRACT FROM AUTHOR]

Abstract: We introduce a method to re-parameterize massive high dimensional data, generated by nonlinear mixing, into its independent physical parameters. Our method enables the identification of the original parameters and their extension to new observations without any knowledge of the true physical model. The suggested approach in this paper is related to spectral independent components analysis (ICA) via the construction of an anisotropic diffusion kernel whose eigenfunctions comprise the independent components. However, we use a novel anisotropic diffusion process, utilizing only a small observed subset , that approximates the isotropic diffusion on the parametric manifold of the full set Y. We employ a Nyström-type extension of the independent components of to the independent components of Y, and provide a validation scheme for our algorithm parameters choice. We demonstrate our method on synthetic examples and on real application examples. [Copyright &y& Elsevier]

Modeling natural and artificial systems has played a key role in various applications and has long been a task that has drawn enormous efforts. In this work, instead of exploring predefined models, we aim to identify implicitly the system degrees of freedom. This approach circumvents the dependency of a specific predefined model for a specific task or system and enables a generic data-driven method to characterize a system based solely on its output observations. We claim that each system can be viewed as a black box controlled by several independent parameters. Moreover, we assume that the perceptual characterization of the system output is determined by these independent parameters. Consequently, by recovering the independent controlling parameters, we find in fact a generic model for the system. In this work, we propose a supervised algorithm to recover the controlling parameters of natural and artificial linear systems. The proposed algorithm relies on nonlinear independent component analysis using diffusion kernels and spectral analysis. Employment of the proposed algorithm on both synthetic and practical examples has shown accurate recovery of parameters. [ABSTRACT FROM PUBLISHER]

Harmonic analysis and diffusion on discrete data has been shown to lead to state-of-the-art algorithms for machine learning tasks, especially in the context of semi-supervised and transductive learning. The success of these algorithms rests on the assumption that the function(s) to be studied (learned, interpolated, etc.) are smooth with respect to the geometry of the data. In this paper we present a method for modifying the given geometry so the function(s) to be studied are smoother with respect to the modified geometry, and thus more amenable to treatment using harmonic analysis methods. Among the many possible applications, we consider the problems of image denoising and transductive classification. In both settings, our approach improves on standard diffusion based methods. [ABSTRACT FROM AUTHOR]

Data fusion and multicue data matching are fundamental tasks of high-dimensional data analysis. In this paper, we apply the recently introduced diffusion framework to address these tasks. Our contribution is three-fold: First, we present the Laplace-Beltrami approach for computing density invariant embeddings which are essential for integrating different sources of data. Second, we describe a refinement of the Nyström extension algorithm called ‘geometric harmonics.’ We also explain how to use this tool for data assimilation. Finally, we introduce a multicue data matching scheme based on nonlinear spectral graphs alignment. The effectiveness of the presented schemes is validated by applying it to the problems of lipreading and image sequence alignment. [ABSTRACT FROM AUTHOR]

Abstract: A central problem in data analysis is the low dimensional representation of high dimensional data and the concise description of its underlying geometry and density. In the analysis of large scale simulations of complex dynamical systems, where the notion of time evolution comes into play, important problems are the identification of slow variables and dynamically meaningful reaction coordinates that capture the long time evolution of the system. In this paper we provide a unifying view of these apparently different tasks, by considering a family of diffusion maps, defined as the embedding of complex (high dimensional) data onto a low dimensional Euclidean space, via the eigenvectors of suitably defined random walks defined on the given datasets. Assuming that the data is randomly sampled from an underlying general probability distribution , we show that as the number of samples goes to infinity, the eigenvectors of each diffusion map converge to the eigenfunctions of a corresponding differential operator defined on the support of the probability distribution. Different normalizations of the Markov chain on the graph lead to different limiting differential operators. Specifically, the normalized graph Laplacian leads to a backward Fokker–Planck operator with an underlying potential of , best suited for spectral clustering. A different anisotropic normalization of the random walk leads to the backward Fokker–Planck operator with the potential , best suited for the analysis of the long time asymptotics of high dimensional stochastic systems governed by a stochastic differential equation with the same potential . Finally, yet another normalization leads to the eigenfunctions of the Laplace–Beltrami (heat) operator on the manifold in which the data resides, best suited for the analysis of the geometry of the dataset regardless of its possibly non-uniform density. [Copyright &y& Elsevier]

Studies the paradigm for image representation and image compression using a multilayered algorithm. Construction of wavelet packets; Quantization of wavelet packets coefficients; Consideration of the sequence of library functions.

Finding informative low-dimensional descriptions of high-dimensional simulation data (like the ones arising in molecular dynamics or kinetic Monte Carlo simulations of physical and chemical processes) is crucial to understanding physical phenomena, and can also dramatically assist in accelerating the simulations themselves. In this paper, we discuss and illustrate the use of nonlinear intrinsic variables (NIV) in the mining of high-dimensional multiscale simulation data. In particular, we focus on the way NIV allows us to functionally merge different simulation ensembles, and different partial observations of these ensembles, as well as to infer variables not explicitly measured. The approach relies on certain simple features of the underlying process variability to filter out measurement noise and systematically recover a unique reference coordinate frame. We illustrate the approach through two distinct sets of atomistic simulations: a stochastic simulation of an enzyme reaction network exhibiting both fast and slow time scales, and a molecular dynamics simulation of alanine dipeptide in explicit water. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. PHATE, a new data visualization tool, better preserves patterns in high-dimensional data after dimensionality reduction. [ABSTRACT FROM AUTHOR]

Public reporting of measures of hospital performance is an important component of quality improvement efforts in many countries. However, it can be challenging to provide an overall characterization of hospital performance because there are many measures of quality. In the United States, the Centers for Medicare and Medicaid Services reports over 100 measures that describe various domains of hospital quality, such as outcomes, the patient experience and whether established processes of care are followed. Although individual quality measures provide important insight, it is challenging to understand hospital performance as characterized by multiple quality measures. Accordingly, we developed a novel approach for characterizing hospital performance that highlights the similarities and differences between hospitals and identifies common patterns of hospital performance. Specifically, we built a semi-supervised machine learning algorithm and applied it to the publicly-available quality measures for 1,614 U.S. hospitals to graphically and quantitatively characterize hospital performance. In the resulting visualization, the varying density of hospitals demonstrates that there are key clusters of hospitals that share specific performance profiles, while there are other performance profiles that are rare. Several popular hospital rating systems aggregate some of the quality measures included in our study to produce a composite score; however, hospitals that were top-ranked by such systems were scattered across our visualization, indicating that these top-ranked hospitals actually excel in many different ways. Our application of a novel graph analytics method to data describing U.S. hospitals revealed nuanced differences in performance that are obscured in existing hospital rating systems. [ABSTRACT FROM AUTHOR]

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 analysis of the approach provides conditions for successfully recovering the underlying slow variables, as well as an empirical protocol guiding the selection of the method parameters. Interestingly, the recovered underlying variables are gauge invariant--they are insensitive to the measuring instrument/observation function. [ABSTRACT FROM AUTHOR]

Highlights: [•] We tested if a relationship between distant parts of the default mode network (DMN), a resting state network defined by fMRI studies, could be observed in the intracranial EEG. [•] Relationship was measured with linear and non-linear relationship measures of the intracranial EEG and an evaluation of the gamma power envelope. [•] The relationship within the DMN was not greater than the relationship from DMN locations to a control location outside it, suggesting a lack of intracranial EEG support for the fMRI defined DMN. [Copyright &y& Elsevier]

Nonlinear independent component analysis is combined with diffusion-map data analysis techniques to detect good observables in high-dimensional dynamic data. These detections are achieved by integrating local principal component analysis of simulation bursts by using eigenvectors of a Markov matrix describing anisotropic diffusion. The widely applicable procedure, a crucial step in model reduction approaches, is illustrated on stochastic chemical reaction network simulations. [ABSTRACT FROM AUTHOR]

Image coding methods based on adaptive wavelet transform and those employing zerotree quantization have been shown to be successful in recent years. In this paper, we present a general zerotree structure for an arbitrary wavelet packet geometry in an image coding framework. A fast basis selection algorithm which uses a Markov chain based cost estimate of encoding the image using this structure is developed. As a result, our adaptive wavelet zerotree image coder has a relatively low computational complexity, performs comparably to the state-of-the-art image coders and is capable of progressively encoding images. [ABSTRACT FROM AUTHOR]

An amendment to this paper has been published and can be accessed via a link at the top of the paper. [ABSTRACT FROM AUTHOR]