Abstract. This paper presents a multilevel framework for inertial and inexact proximal algorithms that encompasses multilevel versions of classical algorithms such as forward-backward and FISTA. The methods are supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We propose a particular instance of IML (Inexact MultiLevel) FISTA, based on the use of the Moreau envelope to build efficient and useful coarse corrections, fully adapted to solve problems in image restoration. Such a construction is derived for a broad class of composite optimization problems with proximable functions. We evaluate our approach on several image reconstruction problems, and we show that it considerably accelerates the convergence of the corresponding one-level (i.e., standard) version of the methods for large-scale images.

This paper presents a multilevel fast iterative soft thresholding algorithm (FISTA), based on the use of the Moreau envelope to incorporate correction from coarse models, which is easy to compute when the explicit form of the proximal operator for the considered functions is known. This approach is supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We evaluate our approach on image restoration problems and we show that it outperforms classical FISTA for large-scale images.

Diffusing a graph signal at multiple scales requires to compute the action of the exponential of as many versions of the Laplacian matrix. Considering the truncated Chebyshev polynomial approximation of the exponential, we derive a tightened bound on the approximation error, allowing thus for a better estimate of the polynomial degree that reaches a prescribed error. We leverage the properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus drastically reducing its computational cost.

The use of the heat kernel on graphs has recently given rise to a family of so-called Diffusion-Wasserstein distances which resort to Optimal Transport theory for comparing attributed graphs. In this paper, we address the open problem of optimizing the diffusion time used in these distances. Inspired from the notion of triplet-based constraints, we design a loss function that aims at bringing two graphs closer together while keeping an impostor away. After a thorough analysis of the properties of this function, we show on synthetic data that the resulting Diffusion-Wasserstein distances outperforms the Gromov and Fused-Gromov Wasserstein distances on unsupervised graph domain adaptation tasks.

We study the inference of conditional independence graph from the partial Phase Locking Value (PLV) index of multivariate time series. A typical application is the inference of temporal functional connectivity from brain data. We extend the recently proposed time-varying graphical lasso to the measurement of partial locking values, yielding a sparse and temporally coherent dynamical graph that characterizes the evolution of the phase synchrony between each pair of signals. Cast as an optimization problem, we solve it using the alternating direction method of multipliers. The approach is validated on simulated Gaussian multivariate signals and Roessler oscillators. The potential of this regularized partial PLV is then illustrated on actual iEEG data during an epileptic seizure.

We study the problem of parametric modeling of network-structured signals with graph filters. To benefit from the properties of several graph shift operators simultaneously, and to enhance interpretability, we investigate combinations of parallel graph filters with different shift operators. Due to their extra degrees of freedom, these models might suffer from over-fitting. We address this problem through a weighted ℓ2-norm regularization formulation to perform model selection by encouraging group sparsity. What makes this formulation interesting is that it is actually a smooth convex optimization problem. Experiments on real-world data structured by undirected and directed graphs show the effectiveness of this method.

The GraSP toolbox aims at processing and visualizing graphs and graphs signal with ease. In the demo, we show those capabilities using several examples from the literature and from our own experiments.

In this letter, we propose a new shift operator for graph signals, enforcing that our operator is isometric. Doing so, we ensure that as many properties of the time shift as possible get carried over. Finally, we show that our operator behaves reasonably for graph signals.

In this contribution, we investigate a graph to signal mapping with the objective of analysing intricate structural properties of graphs with tools borrowed from signal processing. We successfully use a graph-based semi-supervised learning approach to map nodes of a graph to signal amplitudes such that the resulting time series is smooth and the procedure efficient and scalable. Theoretical analysis of this method reveals that it essentially amounts to a linear graph-shift-invariant filter with the a priori knowledge put into the training set as input. Further analysis shows that we can interpret this filter as a Wiener filter on graphs. We finally build upon this interpretation to improve our results.

Intrapartum fetal heart rate monitoring constitutes an important stake aiming at early acidosis detection. Measuring heart rate variability is often considered a powerful tool to assess the intrapartum health status of fetus and has been envisaged using various techniques. In the present contribution, scale invariance parameters, such as the Hurst exponent and the global regularity exponent, are estimated from wavelet coefficients of intrapartum fetal heart rate time series. Their ability to evaluate the health status of fetuses is quantified from a case study database, constituted at a French Academic Hospital in Lyon. Notably, the ability of such parameters to discriminate subjects incorrectly classified according to FIGO rules as abnormal is discussed. Also, the impact of the occurrence of decelerations identified as complicated by obstetricians on the values taken by Hurst parameter is investigated in detail.

We propose a modelling framework, that can be used to reproduce the workload volatility of a Video on Demand (VoD) system. Based on numerical simulations, we evaluate the precision of the estimation procedure we derive to calibrate our parametric model. We also compare its performance to that of other existing models examining the goodness-of-fit of the steady state distribution and of the autocorrelation function of real workload traces. We then give each parameter of the model an interpretation in terms of the workload volatility, that enlightens on some origins of the system dynamics, like the users behaviour.

P2P downloads still represent a large portion of today's Internet traffic. More than 100 million users operate BitTorrent and generate more than 30% of the total Internet traffic. Recently, a significant research effort has been done to develop tools for automatic classification of Internet traffic by application. The purpose of the present work is to provide a framework for subclassification of P2P traffic generated by the BitTorrent protocol. The general intuition is that the users with similar interests download similar contents. This intuition can be rigorously formalized with the help of graph based semi-supervised learning approach. We have chosen to work with a PageRank based semi-supervised learning method, which scales well with very large volumes of data. We provide recommendations for the choice of parameters in the PageRank based semi-supervised learning method. In particular, we show that it is advantageous to choose labelled points with large PageRank score.

We develop a generalized optimization framework for graph-based semi-supervised learning. The framework gives as particular cases the Standard Laplacian, Normalized Laplacian and PageRank based methods. We have also provided new probabilistic interpretation based on random walks and characterized the limiting behaviour of the methods. The random walk based interpretation allows us to explain differences between the performances of methods with different smoothing kernels. It appears that the PageRank based method is robust with respect to the choice of the regularization parameter and the labelled data. We illustrate our theoretical results with two realistic datasets, characterizing different challenges: Les Miserables characters social network and Wikipedia hyper-link graph. The graph-based semi-supervised learning classifies the Wikipedia articles with very good precision and perfect recall employing only the information about the hyper-text links.

The Cloud Computing wave consolidates the on-demand provisioning of configurable virtual machines. Recent projects have proposed the extension of the original IaaS paradigm to provide dynamic virtual networks to interconnect virtual IT resources, composing Virtual Infrastructures (VIs). In this new scenario, users with different objectives and expectations can rent dynamically provisioned virtual infrastructures to execute their applications during a given time slot. VIs can be allocated anywhere on top of a distributed and virtualized substrate. This decoupling from the geographical location introduces concerns such as a latency increase in network communications (user's perspective), and the fragmentation of physical resources (Infrastructure Provider's - InP - perspective). This context motivates efforts to investigate and deploy new models and tools which consider the geographical location of virtual infrastructures. Our work concentrates on the allocation of VIs guided by both the user's and the InP's constraints. We propose a formulation of the allocation problem considering the user's expectations as well as the physical-substrate provider's goals. Our initial experiments demonstrate that it is possible to improve the quality of the virtual-infrastructure allocation (user perspective) while simultaneously decreasing the physical substrate's fragmentation and the substrate's cost.

Intrapartum fetal surveillance aims at preventing neonatal morbidity and mortality due to asphyxia. Continuous fetal heart rate monitoring helps in reducing asphyxia yet generates many unnecessary c-sections. In fetal heart rate time series analysis, variability is a key parameter as its decrease is used to identify asphyxia. Multifractal analysis can be envisaged as a new statistical tool enabling to revisit variability analysis. Applied to data collected at an academic hospital, the wavelet Leader based multifractal analysis is shown here to i) permit a rich and relevant characterization of their variability, ii) to achieve a significant discrimination between healthy and non-healthy fetus, iii) to enable this valid discrimination to hold much earlier than during the last 15 min preceding delivery. This hence opens promising tracks to decrease the number of unnecessary c-sections.

The Semantic Networking concept has been introduced to solve the QoS, scalability and complexity challenges for the Future of Internet. Based on traffic awareness and considering flow entities, it contributes to an adaptive management of the network and provides better knowledge of the transported traffic. Studying the processing time of the classification compatible with real-time operation of such networks is a key question for implementation purposes. In this paper, we present interesting techniques for classification of traffic in semantic networks. The Sample & Hold and multi-stage filter schemes are studied to detect the biggest flows. Their performance is evaluated on real traffic traces. In addition the classification of traffic according to the originating application is investigated. In particular, we analyze the influence of many parameters derived from a traffic flow on the performance of application identification and classify them according to their accuracy. By doing this, a light scheme is proposed able to classify accurately the traffic. We finally discuss the architecture of an hardware implementation to validate the concept of semantic networking.

After the seminal work by Taqqu relating self-similarity to heavy-tailed distributions, a number of research articles verified that aggregated Internet traffic time series show self-similarity and that Internet attributes, like Web file sizes and flow lengths, were heavy-tailed. However, the validation of the theoretical prediction relating self-similarity and heavy tails remains unsatisfactorily addressed, being investigated using either numerical or network simulations, or from uncontrolled Web traffic data. Notably, this prediction has never been conclusively verified on real networks using controlled and stationary scenarios, prescribing specific heavy-tailed distributions, and estimating confidence intervals. With this goal in mind, we use the potential and facilities offered by the large-scale, deeply reconfigurable and fully controllable experimental Grid5000 instrument, combined with state-of-the-art estimators, to investigate the prediction's observability on real networks. To this end, we organize a large number of controlled traffic circulation sessions on a nationwide real network involving 200 independent hosts. We use a FPGA-based measurement system to collect the corresponding traffic at packet level. We then estimate both the self-similarity exponent of the aggregated time series and the heavy-tail index of flow-size distributions, independently. Not only do our results complement and validate, with a striking accuracy, some conclusions drawn from a series of pioneering studies, but they also bring in new insights on the controversial role of certain components of real networks.

We address the problem of fractal dimension estimation of a discrete sample path. After recalling the multiplicity of possible definitions, we focus on the regularity dimension and on the regularization dimension, and report on the common ingredients that underlie these definitions: a scale transform of the signal, and a geometric or statistical measure on the scaled signal. Then, we propose to interchange wavelet transforms, ordinarily used as the scale transform, with empirical mode decomposition (EMD), a recently proposed signal-adaptive transform. The adaptivity of this latter yields estimation performance that overhauls usual wavelet-based techniques. To support our claim, we obtain comprehensive results from a Monte Carlo simulation on fractional Brownian motions.

The empirical mode decomposition (EMD) has been introduced quite recently to adaptively decompose nonstationary and/or nonlinear time series. The method being initially limited to real-valued time series, we propose here an extension to bivariate (or complex-valued) time series that generalizes the rationale underlying the EMD to the bivariate framework. Where the EMD extracts zero-mean oscillating components, the proposed bivariate extension is designed to extract zero-mean rotating components. The method is illustrated on a real-world signal, and properties of the output components are discussed. Free Matlab/C codes are available at http://perso.ens-lyon.fr/patrick.flandrin.

Huang's data-driven technique of empirical mode decomposition (EMD) is applied to the versatile, broadband, model of fractional Gaussian noise (fGn). The spectral analysis and statistical characterization of the obtained modes reveal an equivalent filter bank structure together with gamma distributed variances, both sharing some properties with wavelet decompositions. These common features are then used to mimic wavelet based techniques aimed at estimating the Hurst exponent.

We propose an extension of the adaptive diffusion technique for time-frequency representations proposed by P. Goncalves and E. Payot (see Proc. IEEE Digital Sig. Process. Workshop, 1998). Instead of processing time-frequency representations and keeping the covariance with respect to time and frequency shifts untouched, our adaptive filtering technique processes time-scale representations of the affine class while preserving the covariance properties of such representations. In order to obtain representations with improved readability, we aim at removing cumbersome interference terms while not blurring the signal terms. We show that the association of a conductance function to our diffusion scheme can make significant improvement toward reaching this goal. Indeed, a conductance function provides a way to adapt locally the amount of smoothing to the representation. Note that the adaptivity of this affine technique is not based on any waveform dictionary, such as matching pursuit algorithms.

Empirical mode decomposition (EMD) has recently been pioneered by Huang et al. for adaptively representing nonstationary signals as sums of zero-mean amplitude modulation frequency modulation components. In order to better understand the way EMD behaves in stochastic situations involving broadband noise, we report here on numerical experiments based on fractional Gaussian noise. In such a case, it turns out that EMD acts essentially as a dyadic filter bank resembling those involved in wavelet decompositions. It is also pointed out that the hierarchy of the extracted modes may be similarly exploited for getting access to the Hurst exponent.

We propose here a multiple-window wavelet transform for the purpose of identifying non-stationary self-similar structures in random processes and estimating the time-varying scaling exponent H(t) that controls the local regularity and correlation of the process. More specifically, our final aim is to be able to track even rapidly varying trajectories (t, H(t)). The solution described here combines analysis obtained from scalograms computed with a set of multi-windows designed so as to satisfy to a decorrelation condition. We derive here the statistics for the estimate of H(t), compare it against numerical simulations and show that we obtain a substantial reduction of variance in estimation, without introducing bias.

It is shown using some examples that the problem of estimating the evolution of scaling exponents characterizing locally a self-similar process can be efficiently handled within the general framework of time-scale energy distributions related to the wavelength transform. As is implicit from the structure of the estimators considered, the proposed methodology is dependent on the degree of nonstationarity of such evolutions, with fast changes leading to bias-variance tradeoffs.>