Human physiological signals tend to exhibit both global and local structures: the former are shared across a population, while the latter reflect inter-individual variability. For instance, kinetic measurements of the gait cycle during locomotion present common characteristics, although idiosyncrasies may be observed due to biomechanical disposition or pathology. To better represent datasets with local-global structure, this work extends Convolutional Dictionary Learning (CDL), a popular method for learning interpretable representations, or dictionaries, of time-series data. In particular, we propose Personalized CDL (PerCDL), in which a local dictionary models local information as a personalized spatiotemporal transformation of a global dictionary. The transformation is learnable and can combine operations such as time-warping and rotation. Formal computational and statistical guarantees for PerCDL are provided and its effectiveness on synthetic and real human locomotion data is demonstrated.

Finding patterns in time series is crucial to understanding physical or physiological phenomena monitored with sensors. Convolutional sparse coding (CSC) methods, which approximate signals by a sparse combination of short signal templates (also called atoms), are well-suited for this task. Nevertheless, sparsity results in intractable non-convex optimization problems. This paper introduces an algorithm, based on Multi-path Matching Pursuit, which is novel in convolutional settings, to efficiently and accurately estimate atoms’ localizations in time series. We describe a principled way to improve this greedy procedure by returning several candidate solutions instead of one. Our approach yields better localization and signal reconstruction on simulated data and in a real-world use case, which consists in automatically detect damages, such as cracks and broken wires, in overhead power lines.

We propose a new approach for covariance change point detection applied to graph signals. Specifically, our method draws on the notion of graph stationarity to derive a relevant parameterization of the covariance matrix that can be used in a cost function. This parameterization allows prior graph knowledge to be incorporated into the detection process and reduces the number of coefficients to be estimated. We have experimentally validated this method against relevant baselines, on synthetic and real data, and showed the influence of several parameters. These experiments demonstrated very low computational complexity, improved robustness against certain adverse effects and competitive performance in more general contexts.

Automatically extracting robust representations from large and complex time series data is becoming imperative for several real-world applications. Unfortunately, the potential of common neural network architectures in capturing invariant properties of time series remains relatively underexplored. For instance, convolutional layers often fail to capture underlying patterns in time series inputs that encompass strong deformations, such as trends. Indeed, invariances to some deformations may be critical for solving complex time series tasks, such as classification, while guaranteeing good generalization performance. To address these challenges, we mathematically formulate and technically design efficient and hard-coded *invariant convolutions* for specific group actions applicable to the case of time series. We construct these convolutions by considering specific sets of deformations commonly observed in time series, including *scaling*, *offset shift*, and *trend*. We further combine the proposed invariant convolutions with standard convolutions in single embedding layers, and we showcase the layer capacity to capture complex invariant time series properties in several scenarios.

Motif Discovery involves identifying recurring patterns and locating their occurrences within a time series without prior knowledge about their shape or location. In practice, Motif Discovery faces several data-related challenges, leading to various definitions of the problem and multiple algorithms addressing these challenges to different extents. However, there has been no systematic evaluation and comparison of these diverse approaches. Consequently, this paper presents a comprehensive literature review covering data-related challenges, motif definitions, and algorithms. We also analyze the strengths and limitations of algorithms carefully chosen to represent the literature diversity. The analysis is structured around key research questions identified from our review. Our experimental findings provide practical guidelines for selecting Motif Discovery algorithms suitable for a given task and suggest directions for future research.

In this work, we leverage recent graph uncertainty principles to introduce a new dictionary learning method on graphs. Our method considers two distinct classes of atoms, spatially local atoms on the graph, and smooth atoms, together with well suited penalty functions. Notably, the consideration of the notion of localized atoms on graphs allows to model local and interpretable phenomena.

Exploring and comparing non-stationary multivariate time series is an important problem in many domains and real-world applications. In recent work, we introduced dsymb, a symbolic representation that transforms multivariate time series into interpretable symbolic sequences that comes along with a compatible and efficient distance measure to compare the obtained symbolic sequences. We have shown how dsymbcan handle the non-stationarity of multivariate physiological signals, how interpretable the symbolization is, and how suitable the distance measure is compared to Dynamic Time Warping (DTW) variants. We have also empirically shown that the computation time when using dsymbon a clustering time is significantly smaller than with DTW variants (typically 100 times faster). In this demonstration, we present the dsymbplayground, an interactive web-based tool to interpret and compare a large multivariate time series dataset quickly. We showcase the relevance of this tool in several scenarios based on real-world datasets.

Analyzing inter-individual variability of physiological functions is particularly appealing in medical and biological contexts to describe or quantify health conditions. Such analysis can be done by comparing individuals to a reference one with time series as biomedical data. This paper introduces an unsupervised representation learning (URL) algorithm for time series tailored to inter-individual studies. The idea is to represent time series as deformations of a reference time series. The deformations are diffeomorphisms parameterized and learned by our method called TS-LDDMM. Once the deformations and the reference time series are learned, the vector representations of individual time series are given by the parametrization of their corresponding deformation. At the crossroads between URL for time series and shape analysis, the proposed algorithm handles irregularly sampled multivariate time series of variable lengths and provides shape-based representations of temporal data. In this work, we establish a representation theorem for the graph of a time series and derive its consequences on the LDDMM framework. We showcase the advantages of our representation compared to existing methods using synthetic data and real-world examples motivated by biomedical applications.

Motif Discovery consists of finding repeated patterns and locating their occurrences in a time series without prior knowledge about their shape or location. Most state-of-the-art algorithms rely on three core parameters: the number of motifs to discover, the length of the motifs, and a similarity threshold between motif occurrences. Setting these parameters is difficult in practice and often results from a trial-and-error strategy. In this paper, we propose a new algorithm that discovers motifs of variable length given a single motif length and without requiring a similarity threshold. At its core, the algorithm maps a time series onto a graph, summarizes it with persistent homology - a tool from topological data analysis - and identifies the most relevant motifs from the graph summary. We propose two versions of the algorithm, one requiring the number of motifs to discover and another, adaptive, that infers the number of motifs from the graph summary. Empirical evaluation on 9 labeled datasets, including 6 real-world datasets, shows that both algorithm versions significantly outperform state-of-the-art algorithms.

The introduction of affordable wearable cameras and eye trackers have led to a massive amount of egocentric (or first-person view) videos, bringing new challenges to the computer vision community for understanding and leveraging the specificities of the egocentric view. This work proposes a novel approach for unsupervised activity segmentation that detects frames corrupted by ego-motion and estimates action boundaries using kernel change-point detection. The approach leverages the visual characteristics of egocentric videos to improve segments’ temporal accuracy. We report state-of-the-art performances for unsupervised approaches on two challenging large-scale datasets of untrimmed egocentric videos, EGTEA and EPIC-KITCHEN-55, and on the standard third-person view dataset, 50Salads.

In this article, we introduce a novel lower bound on the support size of lowband graph signals. This result allows the deduction of an optimality criterion for the lowband and sparse decomposition of any graph signal, establishing the uniqueness of well behaving solutions. A comparison of the new bound with previously introduced results is performed, showing the improvements brought by the present work. An illustration on a practical denoising usecase on a real graph is also provided.

In this paper, we propose an adaptive subsampling method for multidomain signals based on the constrained learning of a product graph. Given an input multidomain signal, we search for a product graph on which the signal is bandlimited, i.e. have limited spectral occupancy. The subsampling procedure described in this article is composed of two successive steps. First, we use the input data to learn a graph that will be optimized to favor efficient sampling. Then, we derive an algorithm for choosing the best nodes and provide a sampling strategy for multidomain signals. Experiments on synthetic data and two real datasets show the efficiency of the proposed method and its relevance for multidomain data compression and storing.

In this paper, we consider the problem of learning a graph structure from multivariate signals, known as graph signals. Such signals are multivariate observations carrying measurements corresponding to the nodes of an unknown graph, which we desire to infer. They are assumed to enjoy a sparse representation in the graph spectral domain, a feature which is known to carry information related to the cluster structure of a graph. The signals are also assumed to behave smoothly with respect to the underlying graph structure. For the graph learning problem, we propose a new optimization program to learn the Laplacian of this graph and provide two algorithms to solve it, called IGL-3SR and FGL-3SR. Based on a 3-step alternating procedure, both algorithms rely on standard minimization methods --such as manifold gradient descent or linear programming-- and have lower complexity compared to state-of-the-art algorithms. While IGL-3SR ensures convergence, FGL-3SR acts as a relaxation and is significantly faster since its alternating process relies on multiple closed-form solutions. Both algorithms are evaluated on synthetic and real data. They are shown to perform as good or better than their competitors in terms of both numerical performance and scalability. Finally, we present a probabilistic interpretation of the proposed optimization program as a Factor Analysis Model.

In this article, we propose to extend the classical Convolutional Sparse Coding model (CSC) to multivariate data by introducing a new tensor CSC model that enforces sparsity and low-rank constraint on the activations. The advantages of this model are threefold. First, by using tensor algebra, this model takes into account the underlying structure of the data. Second, this model allows for complex atoms but enforces fewer activations to decompose the data, resulting in an improved summary (dictionary) and a better reconstruction of the original multivariate signal. Third, the number of parameters to be estimated are greatly reduced by the low-rank constraint. We exhibit the associated optimization problem and propose a framework based on alternating optimization to solve it. Finally, we evaluate it on both synthetic and real data.

In this paper, we present a method for learning an underlying graph topology using observed graph signals as training data. The novelty of our method lies on the combination of two assumptions that are imposed as constraints to the graph learning process: i) the standard assumption used in the literature that signals are smooth with respect to graph structure (i.e. small signal variation at adjacent nodes), with ii) the additional assumption that signals are bandlimited, which implies sparsity in the signals' representation in the spectral domain. The latter assumption affects the inference of the whole eigenvalue decomposition of the Laplacian matrix and leads to a challenging new optimization problem. The conducted experimental evaluation shows that the proposed algorithm to solve this problem outperforms a reference state-of-the-art method that is based only on the smoothness assumption, when compared in the graph learning task on synthetic and real graph signals.

In this article, we propose an automatic procedure to calibrate change point detection algorithms. Our approach expands on the ability of an expert to provide very rough segmentation estimates, called partial annotations, for a few signal examples. Our contribution consists in a supervised strategy to learn a kernel Mahalanobis metric, which, once combined with a detection algorithm, can replicate the expert's segmentation strategy on new signals. Contrary to previous works, our approach is non-parametric, supervised and naturally accommodates partial annotations. Experiments on real-world data show that supervision significantly improves detection performance.

In this paper, we introduce DICOD, a convolutional sparse coding algorithm which builds shift invariant representations for long signals. This algorithm is designed to run in a distributed setting, with local message passing, making it communication efficient. It is based on coordinate descent and uses locally greedy updates which accelerate the resolution compared to greedy coordinate selection. We prove the convergence of this algorithm and highlight its computational speed-up which is super-linear in the number of cores used. We also provide empirical evidence for the acceleration properties of our algorithm compared to state-of-the-art methods.

This paper presents a method for adapting the cost function in the Monge–Kantorovich Problem (MKP) to a classification task. More specifically, we introduce a criterion that allows to learn a cost function which tends to produce large distance values for elements belonging to different classes and small distance values for elements belonging to the same class. Under some additional constraints (one of them being the well-known Monge condition), we show that the optimization of this criterion writes as a linear programming problem. Experimental results on synthetic data show that the output optimal cost function provides good retrieval performances in the presence of two types of perturbations commonly found in histograms. When compared to a set of various commonly used cost functions, our optimal cost function performs as good as the best cost function of the set, which shows that it can adapt well to the task. Promising results are also obtained on real data for two-class image retrieval based on grayscale intensity histograms.

With the journal Image Processing On Line (IPOL), we propose to promote software to the status of regular research material and subject it to the same treatment as research papers: it must be reviewed, it must be reusable and verifiable by the research community, it must follow style and quality guidelines. In IPOL, algorithms are published with their implementation, codes are peer-reviewed, and a web-based test interface is attached to each of these articles. This results in more software released by the researchers, a better software quality achieved with the review process, and a large collection of test data gathered for each article. IPOL has been active since 2010, and has already published thirty articles.

This paper describes a probabilistic approach to template-based chord recognition in music signals. The algorithm only takes chromagram data and a user-defined dictionary of chord templates as input data. No training or musical information such as key, rhythm, or chord transition models is required. The chord occurrences are treated as probabilistic events, whose probabilities are learned from the song using an expectation-maximization (EM) algorithm. The adaptative estimation of these probabilities (together with an ad-hoc postprocessing filtering) has the desirable effect of smoothing out spurious chords that would occur in our previous baseline work. Our algorithm is compared to various methods that entered the Music Information Retrieval Evaluation eXchange (MIREX) in 2008 and 2009, using a diverse set of evaluation metrics, some of which are new. The systems are tested on two evaluation corpuses; the first one is composed of the Beatles catalog (180 pop-rock songs) and the other one is constituted of 20 songs from various artists and music genres. Results show that our method outperforms state-of-the-art chord recognition systems.

In this paper, we propose a simple and fast method for chord recognition in music signals. We extract a chromagram from the signal which transcribes the harmonic content of the piece over time. We introduce a set of chord templates taking into account one or more harmonics of the pitch notes of the chord and calculate a scale parameter to fit the chromagram frames to these chords templates. Several chord types (major, minor, dominant seventh, etc.) are considered. The detected chord over a frame is the one minimizing a measure of fit between the rescaled chroma vector and the chord templates. Several popular distances and divergences from the signal processing or probability fields are considered for our task. Our system is improved by some post-processing filtering that modifies the recognition criteria so as to favor time-persistence. The transcription tool is evaluated on three corpora: the Beatles corpus used for MIREX 08, a 20-audio-song corpus, and a resynthesized MIDI corpus. Our system is also compared to state-of-the-art chord recognition methods. Experimental results show that our method compares favorably to the state-of-the-art and is less computationally demanding than the other evaluated systems. Our systems entered the MIREX 2009 competition and performed very well.

This paper describes a method for chord recognition from audio signals. Our method provides a coherent and relevant probabilistic framework for template-based transcription. The only information needed for the transcription is the definition of the chords : in particular neither annotated audio data nor music theory knowledge is required. We extract from the signal a succession of chroma vectors which are our model observations. We propose a generative model for these observations from chord distribution probabilities and fixed chord templates. The parameters are evaluated through an EM algorithm. In order to capture the temporal structure, we apply some post-processing filtering methods before detecting the chords. Our method is evaluated on two audio corpus. Results show that our method outperforms state-of-the-art chord recognition methods and also gives more relevant chord transcriptions.