La réponse la plus votée à cette question suggère que pour débruiter un signal tout en préservant des transitions nettes, il faut
minimiser la fonction objectif:
où est le signal bruyant, est le signal débruité, est le paramètre de régularisation etest une pénalité de norme L1. Le débruitage est accompli en trouvant la solution à ce problème d'optimisation, et dépend du niveau de bruit.
Cependant, rien n'indique comment on pourrait accomplir cela dans la pratique, car cela pose un problème dans un espace de dimension très élevée, en particulier si le signal fait par exemple 10 millions d'échantillons. Dans la pratique, comment ce type de problème est-il résolu par calcul pour les signaux de grande taille?
noise
denoising
smoothing
convex-optimization
John Robertson
la source
la source
Réponses:
Boyd a un solveur Matlab pour les problèmes de moindres carrés régularisés à grande échelle ℓ1 . La formulation du problème est légèrement différente, mais la méthode peut être appliquée pour le problème.
L'approche classique de majoration-minimisation fonctionne également bien. Cela correspond à effectuer de façon itérative un seuillage progressif ( pour la télévision, l'écrêtage ).
Les solutions peuvent être vues à partir des liens. Cependant, il existe de nombreuses méthodes pour minimiser ces fonctions par l'utilisation extensive de la littérature d'optimisation.
PS: Comme mentionné dans d'autres commentaires, FISTA fonctionnera bien. Une autre famille d'algorithmes «très rapide» est celle des algorithmes primal-dual. Vous pouvez voir l' article intéressant de Chambolle pour un exemple, mais il existe une pléthore d'articles de recherche sur les méthodes primal-dual pour les formulations de problèmes inverses linéaires.
la source
Pour résoudre les problèmes d'optimisation avec la pénalité TV, nous utilisons un algorithme récemment proposé appelé Fast Gradient Based Algorithms for Constrained Total Variation Image Denoising and Deblurred Problems (FISTA) , qui a un meilleur taux de convergence que les méthodes itératives conventionnelles, telles que ASD-POCS.
la source
Prox
opérateur. Un travail vraiment sympa.Dans le cas particulier où , la fonction objectif peut s'écriref(y)=∥y∥1
la minimiser nécessite de minimiser chaque entrée de la somme:
En utilisant des sous-différentielles, il est possible de montrer que le minimiseur est l'opérateur de seuillage progressif avec le seuil . C'est la méthode proposée par Donoho et Johnstone pour le débruitage du signal. Voir leur article Adaptation spatiale idéale par retrait en ondelettes pour plus de détails.b
Donc dans ce cas, je pense que vous n'avez pas besoin d'un solveur plus sophistiqué pour estimer votre signal.
la source
Ajouté: si, les termes sont tous indépendants - comme le souligne @Alejandro, vous pouvez simplement minimiser chaque terme par lui-même. Il est plus intéressant de minimiser où au lieu de est destiné à pousser plusieurs à 0. Les notes suivantes sont pour ce cas. (J'appelle les variables , pas .)f(x)=ℓ1(x)=∑|xi|
∥Ax−b∥22+λ∥x∥1
∥x∥1 ∥x∥2 xi
x y
(Un an plus tard) un autre nom pour cela pour le cas norm est Elastic net regularization . Hastie et al., Elements of Statistical Learning p. 661 ff. discuter de cela pour la classification.
Une manière simple et rapide d'obtenir une solution approximative avec de nombreux est d'alternerxi=0
Il s'agit d'une forme de moindres carrés itérativement repondérés , avec des poids de 0 ou 1. Je m'attends à ce que les méthodes des articles cités dans les réponses précédentes donnent de meilleurs résultats; c'est simple.
(Lorsque vous minimisez une somme , c'est une bonne idée de tracer et sur une échelle log-log pour iter 1 2 3 ... Sinon, un terme risque de submerger l'autre, et vous ne le remarquerez même pas - surtout quand ils évoluent différemment.)f()+λg() f() λg()
la source