Search

The segmentation of piecewise polynomial signals arises in a variety of scientific and engineering fields. When a signal is modeled as a piecewise polynomial, the key then becomes the detection of breakpoints followed by curve fitting and parameter estimation. This paper proposes HOPS, a fast High-Order Polynomial Segmenter, which is based on $\ell _{0}$ -penalized least-square regression. While the least-squares regression ensures fitting fidelity, the $\ell _{0}$ penalty takes the number of breakpoints into account. We show that dynamic programming can be applied to find the optimal solution to this problem and that a pruning strategy and matrix factorization can be utilized to accelerate the execution speed. Finally, we provide some illustrative examples, and compare the proposed method with state-of-the-art alternatives.

National audience; Cette communication concerne la conception d'algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés. Les algorithmes heuristiques proposés sont conçus pour minimiser des critères mixtes 2-0 du type min_x J (x; λ) = || y − Ax ||^2 + λ || x ||_0. Ce sont des algorithmes gloutons " bidirectionnels " définis en tant qu'extensions d'Orthogonal Least Squares (OLS). Leur développement est motivé par le très bon comportement empirique d'OLS et de ses versions dérivées lorsque le dictionnaire A est une matrice mal conditionnée. Nous présentons dans un premier temps l'algorithme Single Best Replacement (SBR) pour minimiser J (x; λ) à λ fixé [1], en mettant en avant ses propriétés de convergence. Nous proposons ensuite deux algorithmes permettant de minimiser J pour un continuum de valeurs de λ, ce qui conduit à estimer le chemin de régularisation L0 [2]. Ces algorithmes sont inspirés de l'algorithme d'homotopie pour la régularisation L1 [3, 4] et exploitent le caractère constant par morceaux du chemin de régularisation L0. Continuation Single Best Replacement (CSBR) est basé sur des appels à SBR pour des valeurs décroissantes de λ, calculées de manièere adaptative. L'algorithme plus sophistiqué L0-regularization Path Descent (L0-PD) effectue une reconstruction (sous-optimale) du chemin de régularisation en maintenant (i) une liste de supports candidats pour des valeurs décroissantes de λ; et (ii) une liste de valeurs critiques de λ autour desquelles la solution change. Les simulations numériques montrent l'efficacité des deux algorithmes pour des problèmes inverses difficiles comme la déconvolution impulsionnelle par un filtre passe-bas. Nous montrons finalement que les algorithmes proposés peuvent être avantageusement couplés avec des méthodes de sélection d'ordre comme le MDL (Minimum Description Length) afin de sélectionner automatiquement l'une des solutions parcimonieuses obtenues.

International audience; Sparse signal restoration is usually formulated as the minimization of a quadratic cost function ||y-Ax||_2^2, where A is a dictionary and x is an unknown sparse vector. It is well-known that imposing an L0 constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the L0-norm is replaced by the L1-norm. Among the many efficient L1 solvers, the homotopy algorithm minimizes ||y-Ax||_2^2+lambda ||x||_1 with respect to x for a continuum of lambda's. It is inspired by the piecewise regularity of the L1-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem ||y-Ax||_2^2+lambda ||x||_0 for a continuum of lambda's and propose two heuristic search algorithms for L0-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for L0-minimization at a given lambda. The adaptive search of the lambda-values is inspired by L1-homotopy. L0 Regularization Path Descent is a more complex algorithm exploiting the structural properties of the L0-regularization path, which is piecewise constant with respect to lambda. Both algorithms are empirically evaluated for difficult inverse problems involving ill-conditioned dictionaries. Finally, we show that they can be easily coupled with usual methods of model order selection.

This thesis handles several inverse problems occurring in sparse signal processing. The main contributions include the conception of algorithms dedicated to the restoration and the separation of sparse signals, and their application to force curve approximation in Atomic Force Microscopy (AFM), where the notion of sparsity is related to the number of discontinuity points in the signal (jumps, change of slope, change of curvature). In the signal processing viewpoint, we propose sub-optimal algorithms dedicated to the sparse signal approximation problem based on the ℓ0 pseudo-norm : the Single Best Replacement algorithm (SBR) is an iterative "forward-backward" algorithm inspired from existing Bernoulli-Gaussian signal restoration algorithms. The Continuation Single Best Replacement algorithm (CSBR) is an extension providing approximations at various sparsity levels. We also address the problem of sparse source separation from delayed mixtures. The proposed algorithm is based on the prior application of CSBR on every mixture followed by a matching procedure which attributes a label for each peak occurring in each mixture. Atomic Force Microscopy (AFM) is a recent technology enabling to measure interaction forces between nano-objects. The force-curve analysis relies on piecewise parametric models. We address the detection of the regions of interest (the pieces) where each model holds and the subsequent estimation of physical parameters (elasticity, adhesion forces, topography, etc.) in each region by least-squares optimization. We finally propose an alternative approach in which a force curve is modeled as a mixture of delayed sparse sources. The research of the source signals and the delays from a force-volume image is done based on a large number of mixtures since there are as many mixtures as the number of image pixels., Cette thèse s'inscrit dans le domaine des problèmes inverses en traitement du signal. Elle est consacrée à la conception d'algorithmes de restauration et de séparation de signaux parcimonieux et à leur application à l'approximation de courbes de forces en microscopie de force atomique (AFM), où la notion de parcimonie est liée au nombre de points de discontinuité dans le signal (sauts, changements de pente, changements de courbure). Du point de vue méthodologique, des algorithmes sous-optimaux sont proposés pour le problème de l'approximation parcimonieuse basée sur la pseudo-norme ℓ0 : l'algorithme Single Best Replacement (SBR) est un algorithme itératif de type « ajout-retrait » inspiré d'algorithmes existants pour la restauration de signaux Bernoulli-Gaussiens. L'algorithme Continuation Single Best Replacement (CSBR) est un algorithme permettant de fournir des approximations à des degrés de parcimonie variables. Nous proposons aussi un algorithme de séparation de sources parcimonieuses à partir de mélanges avec retards, basé sur l'application préalable de l'algorithme CSBR sur chacun des mélanges, puis sur une procédure d'appariement des pics présents dans les différents mélanges. La microscopie de force atomique est une technologie récente permettant de mesurer des forces d'interaction entre nano-objets. L'analyse de courbes de forces repose sur des modèles paramétriques par morceaux. Nous proposons un algorithme permettant de détecter les régions d'intérêt (les morceaux) où chaque modèle s'applique puis d'estimer par moindres carrés les paramètres physiques (élasticité, force d'adhésion, topographie, etc.) dans chaque région. Nous proposons finalement une autre approche qui modélise une courbe de force comme un mélange de signaux sources parcimonieux retardées. La recherche des signaux sources dans une image force-volume s'effectue à partir d'un grand nombre de mélanges car il y autant de mélanges que de pixels dans l'image.

This thesis handles several inverse problems occurring in sparse signal processing. The main contributions include the conception of algorithms dedicated to the restoration and the separation of sparse signals, and their application to force curve approximation in Atomic Force Microscopy (AFM), where the notion of sparsity is related to the number of discontinuity points in the signal (jumps, change of slope, change of curvature). In the signal processing viewpoint, we propose sub-optimal algorithms dedicated to the sparse signal approximation problem based on the ℓ0 pseudo-norm : the Single Best Replacement algorithm (SBR) is an iterative "forward-backward" algorithm inspired from existing Bernoulli-Gaussian signal restoration algorithms. The Continuation Single Best Replacement algorithm (CSBR) is an extension providing approximations at various sparsity levels. We also address the problem of sparse source separation from delayed mixtures. The proposed algorithm is based on the prior application of CSBR on every mixture followed by a matching procedure which attributes a label for each peak occurring in each mixture. Atomic Force Microscopy (AFM) is a recent technology enabling to measure interaction forces between nano-objects. The force-curve analysis relies on piecewise parametric models. We address the detection of the regions of interest (the pieces) where each model holds and the subsequent estimation of physical parameters (elasticity, adhesion forces, topography, etc.) in each region by least-squares optimization. We finally propose an alternative approach in which a force curve is modeled as a mixture of delayed sparse sources. The research of the source signals and the delays from a force-volume image is done based on a large number of mixtures since there are as many mixtures as the number of image pixels.; Cette thèse s'inscrit dans le domaine des problèmes inverses en traitement du signal. Elle est consacrée à la conception d'algorithmes de restauration et de séparation de signaux parcimonieux et à leur application à l'approximation de courbes de forces en microscopie de force atomique (AFM), où la notion de parcimonie est liée au nombre de points de discontinuité dans le signal (sauts, changements de pente, changements de courbure). Du point de vue méthodologique, des algorithmes sous-optimaux sont proposés pour le problème de l'approximation parcimonieuse basée sur la pseudo-norme ℓ0 : l'algorithme Single Best Replacement (SBR) est un algorithme itératif de type « ajout-retrait » inspiré d'algorithmes existants pour la restauration de signaux Bernoulli-Gaussiens. L'algorithme Continuation Single Best Replacement (CSBR) est un algorithme permettant de fournir des approximations à des degrés de parcimonie variables. Nous proposons aussi un algorithme de séparation de sources parcimonieuses à partir de mélanges avec retards, basé sur l'application préalable de l'algorithme CSBR sur chacun des mélanges, puis sur une procédure d'appariement des pics présents dans les différents mélanges. La microscopie de force atomique est une technologie récente permettant de mesurer des forces d'interaction entre nano-objets. L'analyse de courbes de forces repose sur des modèles paramétriques par morceaux. Nous proposons un algorithme permettant de détecter les régions d'intérêt (les morceaux) où chaque modèle s'applique puis d'estimer par moindres carrés les paramètres physiques (élasticité, force d'adhésion, topographie, etc.) dans chaque région. Nous proposons finalement une autre approche qui modélise une courbe de force comme un mélange de signaux sources parcimonieux retardées. La recherche des signaux sources dans une image force-volume s'effectue à partir d'un grand nombre de mélanges car il y autant de mélanges que de pixels dans l'image.

In this technical report, we give a detailed formulation of the force curve segmentation problem based on the fitting of the curve by a piecewise polynomial. The segmentation algorithm is a discrete search in which the unknowns are the positions Dj, j=1,...,k of the discontinuity points. We first formulate the problem as the minimization of a least-square cost function with respect to D=[D1,...,Dk]\in R^k. Then, we describe the structure of the proposed optimization algorithm including the update of the list of discontinuity positions D when their number k increases.

National audience