We study the problem of selecting the best sampling set for bandlimited reconstruction of signals on graphs. A frequency domain representation for graph signals can be defined using the eigenvectors ...and eigenvalues of variation operators that take into account the underlying graph connectivity. Smoothly varying signals defined on the nodes are of particular interest in various applications, and tend to be approximately bandlimited in the frequency basis. Sampling theory for graph signals deals with the problem of choosing the best subset of nodes for reconstructing a bandlimited signal from its samples. Most approaches to this problem require a computation of the frequency basis (i.e., the eigenvectors of the variation operator), followed by a search procedure using the basis elements. This can be impractical, in terms of storage and time complexity, for real datasets involving very large graphs. We circumvent this issue in our formulation by introducing quantities called graph spectral proxies, defined using the powers of the variation operator, in order to approximate the spectral content of graph signals. This allows us to formulate a direct sampling set selection approach that does not require the computation and storage of the basis elements. We show that our approach also provides stable reconstruction when the samples are noisy or when the original signal is only approximately bandlimited. Furthermore, the proposed approach is valid for any choice of the variation operator, thereby covering a wide range of graphs and applications. We demonstrate its effectiveness through various numerical experiments.
Bearing degradation is the most common source of faults in electrical machines. In this context, this work presents a novel monitoring scheme applied to diagnose bearing faults. Apart from detecting ...local defects, i.e., single-point ball and raceway faults, it takes also into account the detection of distributed defects, such as roughness. The development of diagnosis methodologies considering both kinds of bearing faults is, nowadays, subject of concern in fault diagnosis of electrical machines. First, the method analyzes the most significant statistical-time features calculated from vibration signal. Then, it uses a variant of the curvilinear component analysis, a nonlinear manifold learning technique, for compression and visualization of the feature behavior. It allows interpreting the underlying physical phenomenon. This technique has demonstrated to be a very powerful and promising tool in the diagnosis area. Finally, a hierarchical neural network structure is used to perform the classification stage. The effectiveness of this condition-monitoring scheme has been verified by experimental results obtained from different operating conditions.
Graphs are fundamental mathematical structures used in various fields to represent data, signals, and processes. In this paper, we propose a novel framework for learning/estimating graphs from data. ...The proposed framework includes (i) formulation of various graph learning problems, (ii) their probabilistic interpretations, and (iii) associated algorithms. Specifically, graph learning problems are posed as the estimation of graph Laplacian matrices from some observed data under given structural constraints (e.g., graph connectivity and sparsity level). From a probabilistic perspective, the problems of interest correspond to maximum a posteriori parameter estimation of Gaussian-Markov random field models, whose precision (inverse covariance) is a graph Laplacian matrix. For the proposed graph learning problems, specialized algorithms are developed by incorporating the graph Laplacian and structural constraints. The experimental results demonstrate that the proposed algorithms outperform the current state-of-the-art methods in terms of accuracy and computational efficiency.
In this work, we propose the construction of two-channel wavelet filter banks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph. These graph based ...functions are referred to as graph-signals as we build a framework in which many concepts from the classical signal processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to graph domain. Especially, we observe a spectral folding phenomenon in bipartite graphs which occurs during downsampling of these graphs and produces aliasing in graph signals. This property of bipartite graphs, allows us to design critically sampled two-channel filter banks, and we propose quadrature mirror filters (referred to as graph-QMF) for bipartite graph which cancel aliasing and lead to perfect reconstruction. For arbitrary graphs we present a bipartite subgraph decomposition which produces an edge-disjoint collection of bipartite subgraphs. Graph-QMFs are then constructed on each bipartite subgraph leading to "multi-dimensional" separable wavelet filter banks on graphs. Our proposed filter banks are critically sampled and we state necessary and sufficient conditions for orthogonality, aliasing cancellation and perfect reconstruction. The filter banks are realized by Chebychev polynomial approximations.
This paper addresses the problem of selecting an optimal sampling set for signals on graphs. The proposed sampling set selection (SSS) is based on a localization operator that can consider both ...vertex domain and spectral domain localizations. We clarify the relationships among the proposed method, sensor position selection methods in machine learning, and existing SSS methods based on graph frequency. In contrast to the alternative graph signal processing-based approaches, the proposed method does not need to compute the eigendecomposition of a variation operator, while still considering (graph) frequency information. We evaluate the performance of our approach through comparisons of prediction errors and execution time.
Research in graph signal processing (GSP) aims to develop tools for processing data defined on irregular graph domains. In this paper, we first provide an overview of core ideas in GSP and their ...connection to conventional digital signal processing, along with a brief historical perspective to highlight how concepts recently developed in GSP build on top of prior research in other areas. We then summarize recent advances in developing basic GSP tools, including methods for sampling, filtering, or graph learning. Next, we review progress in several application areas using GSP, including processing and analysis of sensor network data, biological data, and applications to image processing and machine learning.
This paper extends previous results on wavelet filterbanks for data defined on graphs from the case of orthogonal transforms to more general and flexible biorthogonal transforms. As in the recent ...work, the construction proceeds in two steps: first we design "one-dimensional" two-channel filterbanks on bipartite graphs, and then extend them to "multi-dimensional" separable two-channel filterbanks for arbitrary graphs via a bipartite subgraph decomposition. We specifically design wavelet filters based on the spectral decomposition of the graph, and state sufficient conditions for the filterbanks to be perfect reconstruction and orthogonal. While our previous designs, referred to as graph-QMF filterbanks, are perfect reconstruction and orthogonal, they are not exactly k-hop localized, i.e., the computation at each node is not localized to a small k-hop neighborhood around the node. In this paper, we relax the condition of orthogonality to design a biorthogonal pair of graph-wavelets that are k-hop localized with compact spectral spread and still satisfy the perfect reconstruction conditions. The design is analogous to the standard Cohen-Daubechies-Feauveau's (CDF) construction of factorizing a maximally-flat Daubechies half-band filter. Preliminary results demonstrate that the proposed filterbanks can be useful for both standard signal processing applications as well as for signals defined on arbitrary graphs.
Demographic and Health Surveys, widely used for estimation of fertility and reproductive health indicators in developing countries, remain underutilized for the study of pregnancy termination. This ...is partly due to most surveys not reporting the type of pregnancy termination, whether spontaneous or induced. Reproductive calendar data makes it possible to examine termination patterns according to contraceptive use at the time of pregnancy. Contraceptive failure is expected to increase the likelihood of induced abortion helping in the interpretation of reported termination patterns.
We use individual-level calendar data regarding 623,966 pregnancies to analyze levels and differentials in reported patterns of pregnancy termination by age, union status, and contraceptive use in 107 DHS surveys from 50 countries. From the estimates of the probability of pregnancy termination, we compute derived reproductive health indicators providing an assessment of what is driving the differences by comparison to the few surveys reporting the type of pregnancy termination.
From our estimates, 10.9% of pregnancies do not end in live-birth and 63.7% of them are spontaneous terminations. Reported pregnancy termination is higher among women using contraceptives, consistent with expectations. Very low levels of reported PT in some countries, particularly in sub-Saharan Africa, suggests possible underreporting. Differential patterns emerging from cluster analysis and regional rates indicate high rates of pregnancy termination driven by induced abortion in countries from the Former Soviet Union and Asian countries with liberal laws. Most countries with restrictive abortion laws have low levels of reported termination. While the probabilities of pregnancy termination are higher at older ages, termination rates generally peak at younger ages due to higher conception rates.
This is the first large comparative study of the patterns of reported pregnancy termination in DHS surveys. While we have explored the extent to which differences arise from spontaneous terminations or induced abortion, more research is needed regarding the determinants of reported pregnancy termination.
Full text
Available for:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
Piecewise smooth (PWS) images (e.g., depth maps or animation images) contain unique signal characteristics such as sharp object boundaries and slowly varying interior surfaces. Leveraging on recent ...advances in graph signal processing, in this paper, we propose to compress the PWS images using suitable graph Fourier transforms (GFTs) to minimize the total signal representation cost of each pixel block, considering both the sparsity of the signal's transform coefficients and the compactness of transform description. Unlike fixed transforms, such as the discrete cosine transform, we can adapt GFT to a particular class of pixel blocks. In particular, we select one among a defined search space of GFTs to minimize total representation cost via our proposed algorithms, leveraging on graph optimization techniques, such as spectral clustering and minimum graph cuts. Furthermore, for practical implementation of GFT, we introduce two techniques to reduce computation complexity. First, at the encoder, we low-pass filter and downsample a high-resolution (HR) pixel block to obtain a low-resolution (LR) one, so that a LR-GFT can be employed. At the decoder, upsampling and interpolation are performed adaptively along HR boundaries coded using arithmetic edge coding, so that sharp object boundaries can be well preserved. Second, instead of computing GFT from a graph in real-time via eigen-decomposition, the most popular LR-GFTs are pre-computed and stored in a table for lookup during encoding and decoding. Using depth maps and computer-graphics images as examples of the PWS images, experimental results show that our proposed multiresolution-GFT scheme outperforms H.264 intra by 6.8 dB on average in peak signal-to-noise ratio at the same bit rate.
PDF
