Search

Full-waveform inversion (FWI) is considered one of the most promising interpretation tools for hydrogeological applications using ground-penetrating radar. However, FWI has had limited practical uptake for several reasons: large computational requirements, an inability to reconstruct loss mechanisms of soil, and the need for a good initial starting model. We aim to address these issues via a novel FWI subject to a fractally correlated distribution of water. Initially, the dispersive properties of the soil are expressed as a function of the water fraction using a semiempirical model. This approach means that the permittivity, conductivity, and relaxation mechanisms are all correlated, and therefore, sensitivity problems between the permittivity and loss mechanisms no longer affect the performance of FWI. Subsequently, the distribution of the water fraction is constrained to follow a fractal geometry. Fractal-correlated noise is then compressed using a principal component analysis (PCA) in order to further reduce the number of the system's unknowns and accelerate FWI. PCA reduces the volume and dimensions of the optimization space, and thus, initialization is no longer necessary. Finally, a novel measurement configuration is suggested that uses superposition with all the individual measurements in order to reduce the number of forward models that need to be executed for every iteration of FWI. These enhancements substantially reduce the computational requirements of FWI and therefore eliminate the need for high-performance computers and time-consuming algorithms. The proposed scheme has been successfully tested with several numerical case-studies, which indicates the potential of this approach to become a commercially appealing interpretation tool for hydrogeology.

A plethora of network-science related applications call for inference of spatio-temporal graph processes. Such an inference task can be aided by the underlying graph topology that might jump over discrete modes. For example, the connectivity in dynamic brain networks, switches among candidate topologies, each corresponding to a different emotional state, also known as the network mode. Taking advantage of limited nodal observations, the present contribution deals with semi-supervised tracking of dynamic processes over a given candidate set of graphs with unknown switches. Towards this end, a dynamical model is introduced to capture the per-slot spatial correlation using the active topology, as well as the temporal variation across slots through a state-space model. A scalable graph-adaptive Bayesian approach is developed, based on what is termed interacting multi-graph model (IMGM), to track the dynamic nodal processes and the active graph topology on-the-fly. Besides switching topologies, the proposed IMGM algorithm can accommodate various generalizations, including multiple dynamic functions, multiple kernels, and adaptive observation noise covariances. IMGM learns the dynamical model that best fits the data from a pool of available models. Thus, the resultant adaptive algorithm does not require offline model training. Numerical tests with synthetic and real datasets demonstrate the superior tracking performance of the novel approach compared to the mode-clairvoyant existing alternatives.

This article presents a novel, nonlinear, data-driven signal processing method, which can help neuroscience researchers visualize and understand complex dynamical patterns in both time and space. Specifically, we present applications of a Koopman operator approach for eigendecomposition of electrophysiological signals into orthogonal, coherent components and examine their associated spatiotemporal dynamics. This approach thus provides enhanced capabilities over conventional computational neuroscience tools restricted to analyzing signals in either the time or space domains. This is achieved via machine learning and kernel methods for data-driven approximation of skew-product dynamical systems. The approximations successfully converge to theoretical values in the limit of long embedding windows. First, we describe the method, then using electrocorticographic (ECoG) data from a mismatch negativity experiment, we extract time-separable frequencies without bandpass filtering or prior selection of wavelet features. Finally, we discuss in detail two of the extracted components, Beta ($ \sim $∼13 Hz) and high Gamma ($ \sim $∼50 Hz) frequencies, and explore the spatiotemporal dynamics of high- and low- frequency components.

Structural equation models (SEMs) and vector autoregressive models (VARMs) are two broad families of approaches that have been shown useful in effective brain connectivity studies. While VARMs postulate that a given region of interest in the brain is directionally connected to another one by virtue of time-lagged influences, SEMs assert that directed dependencies arise due to instantaneous effects, and may even be adopted when nodal measurements are not necessarily multivariate time series. To unify these complementary perspectives, linear structural vector autoregressive models (SVARMs) that leverage both instantaneous and time-lagged nodal data have recently been put forth. Albeit simple and tractable, linear SVARMs are quite limited since they are incapable of modeling nonlinear dependencies between neuronal time series. To this end, the overarching goal of the present paper is to considerably broaden the span of linear SVARMs by capturing nonlinearities through kernels, which have recently emerged as a powerful nonlinear modeling framework in canonical machine learning tasks, e.g., regression, classification, and dimensionality reduction. The merits of kernel-based methods are extended here to the task of learning the effective brain connectivity, and an efficient regularized estimator is put forth to leverage the edge sparsity inherent to real-world complex networks. Judicious kernel choice from a preselected dictionary of kernels is also addressed using a data-driven approach. Numerical tests on ECoG data captured through a study on epileptic seizures demonstrate that it is possible to unveil previously unknown directed links between brain regions of interest.

Neural networks with REctified Linear Unit (ReLU) activation functions (a.k.a. ReLU networks) have achieved great empirical success in various domains. Nonetheless, existing results for learning ReLU networks either pose assumptions on the underlying data distribution being e.g. Gaussian, or require the network size and/or training size to be sufficiently large. In this context, the problem of learning a two-layer ReLU network is approached in a binary classification setting, where the data are linearly separable and a hinge loss criterion is adopted. Leveraging the power of random noise perturbation, this paper presents a novel stochastic gradient descent (SGD) algorithm, which can \emph{provably} train any single-hidden-layer ReLU network to attain global optimality, despite the presence of infinitely many bad local minima, maxima, and saddle points in general. This result is the first of its kind, requiring no assumptions on the data distribution, training/network size, or initialization. Convergence of the resultant iterative algorithm to a global minimum is analyzed by establishing both an upper bound and a lower bound on the number of non-zero updates to be performed. Moreover, generalization guarantees are developed for ReLU networks trained with the novel SGD leveraging classic compression bounds. These guarantees highlight a key difference (at least in the worst case) between reliably learning a ReLU network as well as a leaky ReLU network in terms of sample complexity. Numerical tests using both synthetic data and real images validate the effectiveness of the algorithm and the practical merits of the theory., 23 pages, 7 figures, work in progress

Gaussian process latent variable models (GPLVMs) are powerful, yet computationally heavy tools for nonlinear dimensionality reduction. Existing scalable variants utilize low- rank kernel matrix approximants that in essence subsample the embedding space. This work develops an efficient online approach based on random features by replacing spatial with spectral subsampling. The novel approach bypasses the need for optimizing over spatial samples, without sacrificing performance. Different from GPLVM, whose performance depends on the choice of the kernel, the proposed algorithm relies on an ensemble of kernels - what allows adaptation to a wide range of operating environments. It further allows for initial exploration of a richer function space, relative to methods adhering to a single fixed kernel, followed by sequential contraction of the search space as more data become available. Tests on benchmark datasets demonstrate the effectiveness of the proposed method.

For 7 years now, the European Space Agency’s Swarm fleet of satellites surveys the Earth’s magnetic field, measuring magnetic and electric fields at low-Earth orbit (LEO) with unprecedented detail. We have recently demonstrated the feasibility of Swarm measurements to derive a Swarm Dst-like index for the intense magnetic storms of solar cycle 24. We have shown that the newly proposed Swarm Dst-like index monitors magnetic storm activity at least as good as the standard Dst index. The Swarm derived Dst index can be used to (1) supplement the standard Dst index in near-real-time geomagnetic applications and (2) replace the ‘prompt’ Dst index during periods of unavailability. Herein, we employ a series of information theory methods, namely Hurst exponent and various entropy measures, for analyzing Swarm Dst-like time series. The results show that information theory techniques can effectively detect the dissimilarity of complexity between the pre-storm activity and intense magnetic storms (Dst < 150 nT), which is convenient for space weather applications.

Aggressive fungal and insect attacks have reached an alarming level, threatening a variety of tree species, such as ash and oak trees, in the United Kingdom and beyond. In this context, Ground Penetrating Radar (GPR) has proven to be an effective non-invasive tool, capable of generating information about the inner structure of tree trunks in terms of existence, location, and geometry of defects. Nevertheless, it had been observed that the currently available and known GPR-related processing and data interpretation methods and tools are able to provide only limited information regarding the existence of defects and anomalies within the tree inner structure. In this study, we present a microwave tomographic approach for improved GPR data processing with the aim of detecting and characterising the geometry of decay and cavities in trees. The microwave tomographic approach is able to pinpoint explicitly the position of the measurement points on the tree surface and thus to consider the actual geometry of the sections beyond the classical (circular) ones. The robustness of the microwave tomographic approach with respect to noise and data uncertainty is tackled by exploiting a regularised scheme in the inversion process based on the Truncated Singular Value Decomposition (TSVD). A demonstration of the potential of the microwave tomography approach is provided for both simulated data and measurements collected in controlled conditions. First, the performance analysis was carried out by processing simulated data achieved by means of a Finite-Difference Time-Domain (FDTD) in three scenarios characterised by different geometric trunk shapes, internal trunk configurations and target dimensions. Finally, the method was validated on a real trunk by proving the viability of the proposed approach in identifying the position of cavities and decay in tree trunks.

Power system state estimation (PSSE) aims at finding the voltage magnitudes and angles at all generation and load buses, using meter readings and other available information. PSSE is often formulated as a nonconvex and nonlinear least-squares (NLS) cost function, which is traditionally solved by the Gauss-Newton method. However, Gauss-Newton iterations for minimizing nonconvex problems are sensitive to the initialization, and they can diverge. In this context, we advocate a deep neural network (DNN) based "trainable regularizer" to incorporate prior information for accurate and reliable state estimation. The resulting regularized NLS does not admit a neat closed form solution. To handle this, a novel end-to-end DNN is constructed subsequently by unrolling a Gauss-Newton-type solver which alternates between least-squares loss and the regularization term. Our DNN architecture can further offer a suite of advantages, e.g., accommodating network topology via graph neural networks based prior. Numerical tests using real load data on the IEEE 118-bus benchmark system showcase the improved estimation performance of the proposed scheme compared with state-of-the-art alternatives. Interestingly, our results suggest that a simple feed forward network based prior implicitly exploits the topology information hidden in data.

In this paper, a coherent framework for estimating the density and the distribution of roots using ground penetrating radar is presented. The proposed methodology is a multi-stage data processing scheme that is applied in semi-circular measurements collected concentrically around the investigated tree. The adopted processing methodology consists of three distinct and sequential steps. In the first step, the raw B-scans are subject to time-zero correction, zero-offset removal, time-varying gain and the singular value decomposition (SVD) filter. The SVD filter is used in order to effectively eliminate multiples and ringing noise from the B-Scans and increase the overall signal-to-clutter ratio. The second step consists of a tracking algorithm that aims at identifying patterns that resemble tree roots. In the last step, a continuous function is fitted to each root in order to effectively interpolate between points and subsequently estimate the density of the roots. This paper concludes with a case study on an urban tree at the Gunnersbury Park, London, United Kingdom. The top soil around the tree was excavated to 40 cm below the surface approximately in order to expose the tree root architecture. Then the exposed tree root system was used to compare the survey results for validity purposes and ultimately support the viability of the proposed data processing methods adopted in this investigation.

A nonparametric method to predict non-Markovian time series of partially observed dynamics is developed. The prediction problem we consider is a supervised learning task of finding a regression function that takes a delay embedded observable to the observable at a future time. When delay embedding theory is applicable, the proposed regression function is a consistent estimator of the flow map induced by the delay embedding. Furthermore, the corresponding Mori-Zwanzig equation governing the evolution of the observable simplifies to only a Markovian term, represented by the regression function. We realize this supervised learning task with a class of kernel-based linear estimators, the kernel analog forecast (KAF), which are consistent in the limit of large data. In a scenario with a high-dimensional covariate space, we employ a Markovian kernel smoothing method which is computationally cheaper than the Nystr\"om projection method for realizing KAF. In addition to the guaranteed theoretical convergence, we numerically demonstrate the effectiveness of this approach on higher-dimensional problems where the relevant kernel features are difficult to capture with the Nystr\"om method. Given noisy training data, we propose a nonparametric smoother as a de-noising method. Numerically, we show that the proposed smoother is more accurate than EnKF and 4Dvar in de-noising signals corrupted by independent (but not necessarily identically distributed) noise, even if the smoother is constructed using a data set corrupted by white noise. We show skillful prediction using the KAF constructed from the denoised data., Comment: 7 figures

Data-driven prediction is becoming increasingly widespread as the volume of data available grows and as algorithmic development matches this growth. The nature of the predictions made, and the manner in which they should be interpreted, depends crucially on the extent to which the variables chosen for prediction are Markovian, or approximately Markovian. Multiscale systems provide a framework in which this issue can be analyzed. In this work kernel analog forecasting methods are studied from the perspective of data generated by multiscale dynamical systems. The problems chosen exhibit a variety of different Markovian closures, using both averaging and homogenization; furthermore, settings where scale-separation is not present and the predicted variables are non-Markovian, are also considered. The studies provide guidance for the interpretation of data-driven prediction methods when used in practice., 30 pages, 14 figures; clarified several ambiguous parts, added references, and a comparison with Lorenz' original method (Sec. 4.5)

Non-destructive testing (NDT) for health monitoring of trees is a suitable candidate for detecting signs of early decay [1]. Recent developments [2,3,4] have highlighted that ground-penetrating radar (GPR) has the potential to provide with a robust and accurate detection tool with minimum computational and operational requirements in the field. In particular, a processing framework is suggested in [2] that can effectively remove ringing noise and unwanted clutter. Subsequently, an arc length parameterisation is employed in order to utilise a wheel-measurement device to accurately position the measured traces. Lastly, two migration schemes; Kirchhoff and reverse-time migration, are successfully applied on numerical and laboratory data in [3]. In the current paper, the detection scheme described in [2,3] using reverse-time migration is tested in two case studies that involve diseased urban trees within the greater London area, UK (Kensington and Gunnersbury park). Both of the trees were cut down after the completion of the measurements and furthermore cut into several slices to get direct information with regards to their internal structure. The processing scheme described in [3,4] managed to adequately detect the internal decay present in both trees. The aforementioned case studies provide coherent evidences to support the premise that GPR is capable of detecting decay in diseased trunks and therefore has the potential to become an accurate and efficient diagnostic tool against emerging infectious diseases of trees. Acknowledgements The authors would like to express their sincere thanks and gratitude to the following trusts, charities, organizations and individuals for their generosity in supporting this project: Lord Faringdon Charitable Trust, The Schroder Foundation, Cazenove Charitable Trust, Ernest Cook, Sir Henry Keswick, Ian Bond, P. F. Charitable Trust, Prospect Investment Manage- ment Limited, The Adrian Swire Charitable Trust, The John Swire 1989 Charitable Trust, The Sackler Trust, The Tanlaw Foundation and The Wyfold Charitable Trust. This paper is dedicated to the memory of Jonathon West, a friend, a colleague, a forester, a conservationist and an environmentalist who died following an accident in the woodland that he loved. References[1] P. Niemz, D. Mannesm, ”Non-destructive testing of wood and wood-based materials,” J. Cult. Heritage, vol. 13, pp. S26-S34, 2012.[2] I. Giannakis, F. Tosti, L. Lantini and A. M. Alani, "Health Monitoring of Tree Trunks Using Ground Penetrating Radar," IEEE Transactions on Geoscience and Remote Sensing, vol. 57, no. 10, pp. 8317-8326, 2019.[3] I. Giannakis, F. Tosti, L. Lantini and A. M. Alani, "Diagnosing Emerging Infectious Diseases of Trees Using Ground Penetrating Radar," IEEE Transactions on Geoscience and Remote Sensing, Early Access, doi: 10.1109/TGRS.2019.2944070 [4] A. M. Alani, F. Soldovieri, I. Catapano, I. Giannakos, G. Gennarelli, L. Lantini, G. Ludeno and F. Tosti, “The Use of Ground Penetrating Radar and Microwave Tomography for the Detection of Decay and Cavities in Tree Trunks,” Remote Sensing, vol. 11, no. 18, 2019.

The present work deals with active sampling of graph nodes representing training data for binary classification. The graph may be given or constructed using similarity measures among nodal features. Leveraging the graph for classification builds on the premise that labels across neighboring nodes are correlated according to a categorical Markov random field (MRF). This model is further relaxed to a Gaussian (G)MRF with labels taking continuous values - an approximation that not only mitigates the combinatorial complexity of the categorical model, but also offers optimal unbiased soft predictors of the unlabeled nodes. The proposed sampling strategy is based on querying the node whose label disclosure is expected to inflict the largest change on the GMRF, and in this sense it is the most informative on average. Such a strategy subsumes several measures of expected model change, including uncertainty sampling, variance minimization, and sampling based on the $\Sigma-$optimality criterion. A simple yet effective heuristic is also introduced for increasing the exploration capabilities of the sampler, and reducing bias of the resultant classifier, by taking into account the confidence on the model label predictions. The novel sampling strategies are based on quantities that are readily available without the need for model retraining, rendering them computationally efficient and scalable to large graphs. Numerical tests using synthetic and real data demonstrate that the proposed methods achieve accuracy that is comparable or superior to the state-of-the-art even at reduced runtime.

Ground penetrating radar (GPR) is traditionally applied to smooth surfaces in which the assumption of half-space is an adequate approximation that does not deviate much from reality. Nonetheless, using GPR for internal structure characterization of tree trunks requires measurements on an irregularly shaped closed curve. A typical hyperbola fitting has no physical meaning in this new context since the reflection patterns are strongly associated with the shape of the tree trunk. Instead of a clinical hyperbola, the reflections give rise to complex-shaped patterns that are difficult to be analyzed even in the absence of clutter. In this paper, a novel processing scheme is described which can interpret complex reflection patterns assuming a circular target subject to any arbitrary shaped surface. The proposed methodology can be applied using commercial hand-held antennas in real time, avoiding computationally costly tomographic approaches that require the usage of custom-made bespoke antenna arrays. The validity of the current approach is illustrated both with numerical and real experiments.

Structural equation models (SEMs) have been widely adopted for inference of causal interactions in complex networks. Recent examples include unveiling topologies of hidden causal networks over which processes such as spreading diseases, or rumors propagate. The appeal of SEMs in these settings stems from their simplicity and tractability, since they typically assume linear dependencies among observable variables. Acknowledging the limitations inherent to adopting linear models, the present paper advocates nonlinear SEMs, which account for (possible) nonlinear dependencies among network nodes. The advocated approach leverages kernels as a powerful encompassing framework for nonlinear modeling, and an efficient estimator with affordable tradeoffs is put forth. Interestingly, pursuit of the novel kernel-based approach yields a convex regularized estimator that promotes edge sparsity, and is amenable to proximal-splitting optimization methods. To this end, solvers with complementary merits are developed by leveraging the alternating direction method of multipliers, and proximal gradient iterations. Experiments conducted on simulated data demonstrate that the novel approach outperforms linear SEMs with respect to edge detection errors. Furthermore, tests on a real gene expression dataset unveil interesting new edges that were not revealed by linear SEMs, which could shed more light on regulatory behavior of human genes., Comment: 13 pages

Power spectral density (PSD) maps providing the distribution of RF power across space and frequency are constructed using power measurements collected by a network of low-cost sensors. By introducing linear compression and quantization to a small number of bits, sensor measurements can be communicated to the fusion center with minimal bandwidth requirements. Strengths of data- and model-driven approaches are combined to develop estimators capable of incorporating multiple forms of spectral and propagation prior information while fitting the rapid variations of shadow fading across space. To this end, novel nonparametric and semiparametric formulations are investigated. It is shown that PSD maps can be obtained using support vector machine-type solvers. In addition to batch approaches, an online algorithm attuned to real-time operation is developed. Numerical tests assess the performance of the novel algorithms., Comment: Submitted Jun. 2016

© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Prior information can be incorporated in matrix completion to improve estimation accuracy and extrapolate the missing entries. Reproducing kernel Hilbert spaces provide tools to leverage the said prior information, and derive more reliable algorithms. This paper analyzes the generalization error of such approaches, and presents numerical tests confirming the theoretical results This work is supported by ERDF funds (TEC2013-41315-R and TEC2016-75067-C4-2), the Catalan Government (2017 SGR 578), and NSF grants(1500713, 1514056, 1711471 and 1509040).

Graphs are pervasive in different fields unveiling complex relationships between data. Two major graph-based learning tasks are topology identification and inference of signals over graphs. Among the possible models to explain data interdependencies, structural equation models (SEMs) accommodate a gamut of applications involving topology identification. Obtaining conventional SEMs though requires measurements across nodes. On the other hand, typical signal inference approaches 'blindly trust' a given nominal topology. In practice however, signal or topology perturbations may be present in both tasks, due to model mismatch, outliers, outages or adversarial behavior. To cope with such perturbations, this work introduces a regularized total least-squares (TLS) approach and iterative algorithms with convergence guarantees to solve both tasks. Further generalizations are also considered relying on structured and/or weighted TLS when extra prior information on the perturbation is available. Analyses with simulated and real data corroborate the effectiveness of the novel TLS-based approaches.

Optimization underpins many of the challenges that science and technology face on a daily basis. Recent years have witnessed a major shift from traditional optimization paradigms grounded on batch algorithms for medium-scale problems to challenging dynamic, time-varying, and even huge-size settings. This is driven by technological transformations that converted infrastructural and social platforms into complex and dynamic networked systems with even pervasive sensing and computing capabilities. The present paper reviews a broad class of state-of-the-art algorithms for time-varying optimization, with an eye to both algorithmic development and performance analysis. It offers a comprehensive overview of available tools and methods, and unveils open challenges in application domains of broad interest. The real-world examples presented include smart power systems, robotics, machine learning, and data analytics, highlighting domain-specific issues and solutions. The ultimate goal is to exempify wide engineering relevance of analytical tools and pertinent theoretical foundations., Comment: 14 pages, 6 figures; to appear in the Proceedings of the IEEE

Graph convolutional networks (GCNs) have well-documented performance in various graph learning tasks, but their analysis is still at its infancy. Graph scattering transforms (GSTs) offer training-free deep GCN models that extract features from graph data, and are amenable to generalization and stability analyses. The price paid by GSTs is exponential complexity in space and time that increases with the number of layers. This discourages deployment of GSTs when a deep architecture is needed. The present work addresses the complexity limitation of GSTs by introducing an efficient so-termed pruned (p)GST approach. The resultant pruning algorithm is guided by a graph-spectrum-inspired criterion, and retains informative scattering features on-the-fly while bypassing the exponential complexity associated with GSTs. Stability of the novel pGSTs is also established when the input graph data or the network structure are perturbed. Furthermore, the sensitivity of pGST to random and localized signal perturbations is investigated analytically and experimentally. Numerical tests showcase that pGST performs comparably to the baseline GST at considerable computational savings. Furthermore, pGST achieves comparable performance to state-of-the-art GCNs in graph and 3D point cloud classification tasks. Upon analyzing the pGST pruning patterns, it is shown that graph data in different domains call for different network architectures, and that the pruning algorithm may be employed to guide the design choices for contemporary GCNs.

The family of $k$ -nearest neighbor ( $k$ NN) schemes comprises simple and effective algorithms that can be used for general machine learning tasks such as classification and regression. The goal of linear $k$ NN regression is to predict the value of an unseen datum as a linear combination of its $k$ neighbors on a graph, which could be found via certain distance metric. Despite the simplicity and effectiveness of $k\mathrm{NN}$ regression, a general problem facing this approach is the proper choice of $k$ . Most of the conventional $k$ NN algorithms simply apply the same $k$ for all data samples, meaning that the data samples are assumed to lie on a regular graph wherein each data sample is connected with $k$ neighbors. However, a constant choice may not be optimal for data lying in a heterogeneous feature space. On the other hand, existing algorithms for adaptively choosing $k$ usually incur high computational complexity, especially for large training datasets. In order to cope with this challenge, this paper introduces a novel algorithm which can adaptively choose $k$ for each data sample; meanwhile it is capable of greatly reducing the training complexity by actively choosing training samples. Real data tests corroborate the efficiency and effectiveness of the novel algorithm.

This work focuses on expressing the TSP with Time Windows (TSPTW for short) as a quadratic unconstrained binary optimization (QUBO) problem. The time windows impose time constraints that a feasible solution must satisfy. These take the form of inequality constraints, which are known to be particularly difficult to articulate within the QUBO framework. This is, we believe, the first time this major obstacle is overcome and the TSPTW is cast in the QUBO formulation. We have every reason to anticipate that this development will lead to the actual execution of small scale TSPTW instances on the D-Wave platform.

Data related to biology are characterized by large volume and requirements for enormous computational power. Biological sequences, either of proteins or DNA/RNA segments, can be large and usually need massive computations in order to discover relations and study particular properties. Aligning sequences is of great importance for various practical reasons. Multiple sequence alignment studies the problem of aligning several strings resulting in a complete alignment, a problem for which several different approaches exist. In this work, a novel heuristic method to progressively solve this problem is proposed using elements of quantum-inspired optimization. The proposed algorithm is described in detail and evaluated through simulations against other aligning methods. The experimental results seem promising for providing a good initial alignment, especially for the case of large sets of sequences.

Background Gene networks in living cells can change depending on various conditions such as caused by different environments, tissue types, disease states, and development stages. Identifying the differential changes in gene networks is very important to understand molecular basis of various biological process. While existing algorithms can be used to infer two gene networks separately from gene expression data under two different conditions, and then to identify network changes, such an approach does not exploit the similarity between two gene networks, and it is thus suboptimal. A desirable approach would be clearly to infer two gene networks jointly, which can yield improved estimates of network changes. Results In this paper, we developed a proximal gradient algorithm for differential network (ProGAdNet) inference, that jointly infers two gene networks under different conditions and then identifies changes in the network structure. Computer simulations demonstrated that our ProGAdNet outperformed existing algorithms in terms of inference accuracy, and was much faster than a similar approach for joint inference of gene networks. Gene expression data of breast tumors and normal tissues in the TCGA database were analyzed with our ProGAdNet, and revealed that 268 genes were involved in the changed network edges. Gene set enrichment analysis identified a significant number of gene sets related to breast cancer or other types of cancer that are enriched in this set of 268 genes. Network analysis of the kidney cancer data in the TCGA database with ProGAdNet also identified a set of genes involved in network changes, and the majority of the top genes identified have been reported in the literature to be implicated in kidney cancer. These results corroborated that the gene sets identified by ProGAdNet were very informative about the cancer disease status. A software package implementing the ProGAdNet, computer simulations, and real data analysis is available as Additional file 1. Conclusion With its superior performance over existing algorithms, ProGAdNet provides a valuable tool for finding changes in gene networks, which may aid the discovery of gene-gene interactions changed under different conditions. Electronic supplementary material The online version of this article (10.1186/s12859-019-2749-x) contains supplementary material, which is available to authorized users.

Multiview canonical correlation analysis (MCCA) looks for shared low-dimensional representations hidden in multiple transformations of common source signals. Existing MCCA approaches do not exploit the geometry of common sources, which can be either given a priori, or constructed from do- main knowledge. In this paper, a novel graph-regularized (G) MCCA is developed to account for such geometry-bearing in- formation via graph regularization in the classical maximum- variance MCCA model. GMCCA minimizes the distance between the sought canonical variables and the common sources, while incorporating the graph-induced prior of these sources. To capture nonlinear dependencies, GMCCA is fur- ther broadened to the graph-regularized kernel (GK) MCCA. Numerical tests using real datasets document the merits of G(K)MCCA in comparison with competing alternatives.

© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Matrix completion and extrapolation (MCEX) are dealt with here over reproducing kernel Hilbert spaces (RKHSs) in order to account for prior information present in the available data. Aiming at a fast and low-complexity solver, the task is formulated as one of kernel ridge regression. The resultant MCEX algorithm can also afford online implementation, while the class of kernel functions also encompasses several existing approaches to MC with prior information. Numerical tests on synthetic and real datasets show that the novel approach is faster than widespread methods such as alternating least-squares (ALS) or stochastic gradient descent (SGD), and that the recovery error is reduced, especially when dealing with noisy data.

Graphs are pervasive in various applications capturing the complex behavior observed in biological, financial, and social networks, to name a few. Two major learning tasks over graphs are topology identification and inference of signals evolving over graphs. Existing approaches typically aim at identifying the topology when signals on all nodes are observed, or, recovering graph signals over networks with known topologies. In practice however, signal or graph perturbations can be present in both tasks, due to model mismatch, outliers, outages or adversaries. To cope with these perturbations, this work introduces regularized total least-squares (TLS) based approaches and corresponding alternating minimization algorithms with convergence guarantees. Tests on simulated data corroborate the effectiveness of the novel TLS-based approaches.

Sparse phase retrieval (PR) aims at reconstructing a sparse signal vector from a few phaseless linear measurements. It emerges naturally in diverse applications, but it is NP-hard in general. Drawing from advances in nonconvex optimization, this paper presents a new algorithm that is termed compressive reweighted amplitude flow (CRAF) for sparse PR. CRAF operates in two stages: Stage one computes an initial guess by means of a new spectral procedure, and stage two implements a few hard thresholding based iteratively reweighted gradient iterations on the amplitude-based least-squares cost. When there are sufficient measurements, CRAF reconstructs the true signal vector exactly under suitable conditions. Furthermore, its sample complexity coincides with that of the state-of-the-art approaches. Numerical experiments showcase improved performance of the proposed approach relative to existing alternatives.

We present a method combining ideas from the theory of operator-valued kernels with delay-coordinate embedding techniques in dynamical systems capable of identifying spatiotemporal patterns, without prior knowledge of the state space or the dynamical laws of the system generating the data. The approach is particularly powerful for systems in which characteristic patterns cannot be readily decomposed into temporal and spatial coordinates. Using simulated and observed sea-surface temperature data, we show our approach reveals coherent patterns of intermittent character with significantly higher skill than conventional analytical methods based on decomposing signals into separable spatial and temporal patterns.

The present work introduces methods for sampling and inference for the purpose of semi-supervised classification over the nodes of a graph. The graph may be given or constructed using similarity measures among nodal features. Leveraging the graph for classification builds on the premise that relation among nodes can be modeled via stationary distributions of a certain class of random walks. The proposed classifier builds on existing scalable random-walk-based methods and improves accuracy and robustness by automatically adjusting a set of parameters to the graph and label distribution at hand. Furthermore, a sampling strategy tailored to random-walk-based classifiers is introduced. Numerical tests on benchmark synthetic and real labeled graphs demonstrate the performance of the proposed sampling and inference methods in terms of classification accuracy.

Linear structural equation models (SEMs) have been very successful in identifying the topology of complex graphs, such as those representing social and brain networks. In many cases however, the presence of highly correlated nodes hinders performance of the available SEM estimators that rely on the least-absolute shrinkage and selection operator (LASSO). To this end, an elastic net based SEM is put forth, to infer causal relations between nodes belonging to networks, in the presence of highly correlated data. An efficient algorithm based on the alternating direction method of multipliers (ADMM) is developed, and preliminary tests on synthetic as well as real data demonstrate the effectiveness of the proposed approach.

Inference of space-time signals evolving over graphs emerges naturally in a number of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filtering approach that leverages the spatio-temporal dynamics to allow for efficient online reconstruction, while also coping with dynamically evolving network topologies. Laplacian kernels are employed to perform kriging over the graph when spatial second-order statistics are unknown, as is often the case. Numerical tests with synthetic and real data illustrate the superior reconstruction performance of the proposed approach.

From the attenuation measurements collected by a network of spatially distributed sensors, radio tomography constructs spatial loss fields (SLFs) that quantify absorption of radiofrequency waves at each location. These SLFs can be used for interference prediction in (possibly cognitive) wireless communication networks, for environmental monitoring or intrusion detection in surveillance applications, for through-the-wall imaging, for survivor localization after earthquakes or fires, etc. The cornerstone of radio tomography is to model attenuation as the bidimensional integral of the SLF of interest scaled by a weight function. Unfortunately, existing approaches (i) rely on heuristic assumptions to select the weight function and (ii) are limited to imaging changes in the propagation medium or they require a separate calibration step with measurements in free space. The first major contribution in this paper addresses (i) by means of a blind radio tomographic approach that learns the SLF together with the aforementioned weight function from the attenuation measurements. This challenging problem is tackled by capitalizing on contemporary kernel-based learning tools together with various forms of regularization that leverage prior knowledge. The second contribution addresses (ii) by means of a novel calibration technique capable of imaging static structures without separate calibration steps. Numerical tests with real and synthetic measurements validate the efficacy of the proposed algorithms.

Radio tomographic imaging (RTI) is an emerging technology to locate physical objects in a geographical area covered by wireless networks. From the attenuation measurements collected at spatially distributed sensors, radio tomography capitalizes on spatial loss fields (SLFs) measuring the absorption of radio frequency waves at each location along the propagation path. These SLFs can be utilized for interference management in wireless communication networks, environmental monitoring, and survivor localization after natural disaster such as earthquakes. Key to success of RTI is to model accurately the shadowing effects as the bi-dimensional integral of the SLF scaled by a weight function, which is estimated using regularized regression. However, the existing approaches are less effective when the propagation environment is heterogeneous. To cope with this, the present work introduces a piecewise homogeneous SLF governed by a hidden Markov random field (MRF) model. Efficient and tractable SLF estimators are developed by leveraging Markov chain Monte Carlo (MCMC) techniques. Furthermore, an uncertainty sampling method is developed to adaptively collect informative measurements in estimating the SLF. Numerical tests using synthetic and real datasets demonstrate capabilities of the proposed algorithm for radio tomography and channel-gain estimation.

A performance-enhancing modification to the convolutional perfectly matched layer (CPML) technique for implementing the complex frequency-shifted perfectly matched layer (CFS-PML) absorbing boundary condition is presented. By adopting this modification, an apparent discrepancy in the time synchronization between the CPML and the main finite-difference time-domain (FDTD) algorithm is resolved. This is achieved by employing a semi-implicit approach that synchronizes CPML with the main FDTD algorithm. It is shown through 2-D and 3-D numerical examples that the suggested modification to the CPML algorithm increases its performance without increasing its computational cost.

Partial correlations (PCs) are well suited for revealing linearly dependent (un)mediated connections in a graph when measurements (e.g., time courses) are available per node. Unfortunately, PC-based approaches to identifying the topology of a graph are less effective if nonlinear dependencies between given nodal measurements are present. To bypass this hurdle, nonlinear PCs relying on the l 2 -norm regularized multi-kernel ridge regression (MKRR) have been recently proposed for brain network connectivity analysis. However, l 2 -norm regularization limits the flexibility in combining kernels, which can compromise performance. For this reason, the present paper broadens the nonlinear PC approach to account for general l p -norm regularized MKRR, in which the user-selected parameter p ≥ 1 is attuned to the problem at hand. Aiming at a scalable algorithm, the Frank-Wolfe iterations are invoked to solve the l p -norm based MKRR, which not only features simple closed-form updates, but it is also fast convergent. The end result is a novel scheme that leverages nonlinear dependencies captured by the generalized PC model to identify the topology of not only radial but also meshed autonomous energy grids. Improved performance is achieved at affordable computational complexity relative to existing alternatives. Simulated tests showcase the merits of the proposed schemes.

Inference of space-time varying signals on graphs emerges naturally in a plethora of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes, given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filter that accounts for the spatio-temporal variations, and offers efficient online reconstruction, even for dynamically evolving network topologies. The kernel-based learning framework bypasses the need for statistical information by capitalizing on the smoothness that graph signals exhibit with respect to the underlying graph. To address the challenge of selecting the appropriate kernel, the proposed filter is combined with a multi-kernel selection module. Such a data-driven method selects a kernel attuned to the signal dynamics on-the-fly within the linear span of a pre-selected dictionary. The novel multi-kernel learning algorithm exploits the eigenstructure of Laplacian kernel matrices to reduce computational complexity. Numerical tests with synthetic and real data demonstrate the superior reconstruction performance of the novel approach relative to state-of-the-art alternatives., Submitted to IEEE Transactions on Signal processing, Nov. 2017

We present a data-driven framework for extracting complex spatiotemporal patterns generated by ergodic dynamical systems. Our approach, called Vector-valued Spectral Analysis (VSA), is based on an eigendecomposition of a kernel integral operator acting on a Hilbert space of vector-valued observables of the system, taking values in a space of functions (scalar fields) on a spatial domain. This operator is constructed by combining aspects of the theory of operator-valued kernels for machine learning with delay-coordinate maps of dynamical systems. In contrast to conventional eigendecomposition techniques, which decompose the input data into pairs of temporal and spatial modes with a separable, tensor product structure, the patterns recovered by VSA can be manifestly non-separable, requiring only a modest number of modes to represent signals with intermittency in both space and time. Moreover, the kernel construction naturally quotients out dynamical symmetries in the data, and exhibits an asymptotic commutativity property with the Koopman evolution operator of the system, enabling decomposition of multiscale signals into dynamically intrinsic patterns. Application of VSA to the Kuramoto-Sivashinsky model demonstrates significant performance gains in efficient and meaningful decomposition over eigendecomposition techniques utilizing scalar-valued kernels., 37 pages, 5 figures

Signal reconstruction over graphs arises naturally in diverse science and engineering applications. Existing methods employ either parametric or nonparametric approaches based on graph kernels. Although the former are adequate when the signals of interest adhere to postulated models, their performance degrades rapidly under model mismatch. Non-parametric alternatives on the other hand are flexible, but not as parsimonious in capturing prior information. Targeting a hybrid “sweet spot,” the present contribution advocates an efficient semi-parametric approach capable of incorporating known signal structure without sacrificing the flexibility of the overall model. Numerical tests on synthetic as well as real data corroborate that the novel method leads to markedly improved signal reconstruction performance.

Despite their well-documented capability in modeling nonlinear functions, kernel methods fall short in large-scale learning tasks due to their excess memory and computational requirements. The present work introduces a novel kernel approximation approach from a dimensionality reduction point of view on virtual lifted data. The proposed framework accommodates feature extraction while considering limited storage and computational availability, and subsequently provides kernel approximation by a linear inner-product over the extracted features. Probabilistic guarantees on the generalization of the proposed task is provided, and efficient solvers with provable convergence guarantees are developed. By introducing a sampling step which precedes the dimensionality reduction task, the framework is further broadened to accommodate learning over large datasets. The connection between the novel method and Nystrom kernel approximation algorithm with its modifications is also presented. Empirical tests validate the effectiveness of the proposed approach.

Linear structural vector autoregressive models constitute a generalization of structural equation models (SEMs) and vector autoregressive (VAR) models, two popular approaches for topology inference of directed graphs. Although simple and tractable, linear SVARMs seldom capture nonlinearities that are inherent to complex systems, such as the human brain. To this end, the present paper advocates kernel-based nonlinear SVARMs, and develops an efficient sparsity-promoting least-squares estimator to learn the hidden topology. Numerical tests on real electrocorticographic (ECoG) data from an Epilepsy study corroborate the efficacy of the novel approach.

A linear-time algorithm termed SPARse Truncated Amplitude flow (SPARTA) is developed for the phase retrieval (PR) of sparse signals. Upon formulating the sparse PR as a non-convex empirical loss minimization task, SPARTA emerges as an iterative solver consisting of two components: s1) a sparse orthogonality-promoting initialization leveraging support recovery and principal component analysis; and, s2) a series of refinements by hard thresholding based truncated gradient iterations. SPARTA is simple, scalable, and fast. It recovers any k-sparse n-dimensional signal (k ≪ n) of large enough minimum (in modulus) nonzero entries from about k2 log n measurements with high probability; this is achieved at computational complexity of order k2n log n, improving upon the state-of-the-art by at least a factor of k. SPARTA is robust against bounded additive noise. Simulated tests corroborate the merits of SPARTA relative to existing alternatives.

Many real-world processes evolve in cascades over complex networks, whose topologies are often unobservable and change over time. However, the so-termed adoption times when blogs mention popular news items, individuals in a community catch an infectious disease, or consumers adopt a trendy electronics product are typically known, and are implicitly dependent on the underlying network. To infer the network topology, a dynamic structural equation model is adopted to capture the relationship between observed adoption times and the unknown edge weights. Assuming a slowly time-varying topology and leveraging the sparse connectivity inherent to social networks, edge weights are estimated by minimizing a sparsity-regularized exponentially-weighted least-squares criterion. To this end, solvers with complementary strengths are developed by leveraging (pseudo) real-time sparsity-promoting proximal gradient iterations, the improved convergence rate of accelerated variants, or reduced computational complexity of stochastic gradient descent. Numerical tests with both synthetic and real data demonstrate the effectiveness of the novel algorithms in unveiling sparse dynamically-evolving topologies, while accounting for external influences in the adoption times. Key events in the political leadership in North Korea and the initial public offering of LinkedIn explain connectivity changes observed in the associated networks inferred from global cascades of online media.

The original version of this article unfortunately contained an error in Acknowledgement section. The authors would like to correct the error with this erratum. The correct text should read as