Robust algorithms for linear and nonlinear regression via sparse modeling methods: theory, algorithms and applications to image denoising

Abstract

The task of robust regression is of particular importance in signal processing, statistics and machine learning. Ordinary estimators, such as the Least Squares (LS) one, fail to achieve sufficiently good performance in the presence of outliers. Although the problem has been addressed many decades ago and several methods have been established, it has recently attracted more attention in the context of sparse modeling and sparse optimization techniques. The latter is the line that has been followed in the current dissertation. The reported research, led to the development of a novel approach in the context of greedy algorithms. The model adopts the decomposition of the noise into two parts: a) the inlier noise and b) the outliers, which are explicitly modeled by employing sparse modeling arguments. Based on this rationale and inspired by the popular Orthogonal Matching Pursuit (OMP), two novel efficient greedy algorithms are established, one for the linear and another one for the nonlinear robust regression task.The proposed algorithm for the linear task, i.e., Greedy Algorithm for Robust Denoising (GARD), alternates between a Least Squares (LS) optimization criterion and an OMP selection step, that identifies the outliers. The method is compared against state-of-the-art methods through extensive simulations and the results demonstrate that: a) it exhibits tolerance in the presence of outliers, i.e., robustness, b) it attains a very low approximation error and c) it has relatively low computational requirements. Moreover, due to the simplicity of the method, a number of related theoretical properties are derived. Initially, the convergence of the method in a finite number of iteration steps is established. Next, the focus of the theoretical analysis is turned on the identification of the outliers. The case where only outliers are present has been studied separately; this is mainly due to the following reasons: a) the simplification of technically demanding algebraic manipulations and b) the “articulation” of the method’s interesting geometrical properties. In particular, a bound based on the Restricted Isometry Property (RIP) constant guarantees that the recovery of the signal via GARD is exact (zero error). Finally, for the case where outliers as well as inlier noise coexist, and by assuming that the inlier noise vector is bounded, a similar condition that guarantees the recovery of the support for the sparse outlier vector is derived. If such a condition is satisfied, then it is shown that the approximation error is bounded, and thus the denoising estimator is stable.For the robust nonlinear regression task, it is assumed that the unknown nonlinear function belongs to a Reproducing Kernel Hilbert Space (RKHS). Due to the existence of outliers, common techniques such as the Kernel Ridge Regression (KRR), or the Support Vector Regression (SVR) turn out to be inadequate. By employing the aforementioned noise decomposition, sparse modeling arguments are employed so that the outliers are estimated according to the greedy approach. The proposed robust scheme, i.e., Kernel Greedy Algorithm for Robust Denoising (KGARD), alternates between a KRR task and an OMP-like selection step. Theoretical results regarding the identification of the outliers are provided. Moreover, KGARD is compared against other cutting edge methods via extensive simulations, where its enhanced performance is demonstrated. Finally, the proposed robust estimation framework is applied to the task of image denoising, where the advantages of the proposed method are unveiled. The experiments verify that KGARD improves the denoising process significantly, when outliers are present.

Η εύρωστη παλινδρόμηση κατέχει έναν πολύ σημαντικό ρόλο στην Επεξεργασία Σήματος, τη Στατιστική και τη Μηχανική Μάθηση. Συνήθεις εκτιμητές, όπως τα «Ελάχιστα Τετράγωνα», αποτυγχάνουν να εκτιμήσουν σωστά παραμέτρους, όταν στα δεδομένα υπεισέρχονται ακραίες παρατηρήσεις, γνωστές ως "outliers". Το πρόβλημα αυτό είναι γνωστό εδώ και δεκαετίες, μέσα στις οποίες διάφορες μέθοδοι έχουν προταθεί. Παρόλα αυτά, το ενδιαφέρον της επιστημονικής κοινότητας για αυτό αναζωπυρώθηκε όταν επανεξετάστηκε υπό το πρίσμα της αραιής μοντελοποίησης και των αντίστοιχων τεχνικών, η οποία κυριαρχεί στον τομέα της μηχανικής μάθησης εδώ και δύο δεκαετίες. Αυτή είναι και η κατεύθυνση η οποία ακολουθήθηκε στην παρούσα διατριβή. Το αποτέλεσμα αυτής της εργασίας ήταν η ανάπτυξη μιας νέας προσέγγισης, βασισμένης σε άπληστες τεχνικές αραιής μοντελοποίησης. Το μοντέλο που υιοθετείται βασίζεται στην ανάλυση του θορύβου σε δύο συνιστώσες: α) μια για το συμβατικό (αναμενόμενο) θόρυβο και β) μια για τις ακραίες παρατηρήσεις (outliers), οι οποίες θεωρήθηκε ότι είναι λίγες (αραιές) σε σχέση με τον αριθμό των δεδομένων. Με βάση αυτή τη μοντελοποίηση και τον γνωστό άπληστο αλγόριθμο "Orthogonal Matching Pursuit" (OMP), δύο νέοι αλγόριθμοι αναπτύχθηκαν, ένας για το γραμμικό και ένας για το μη γραμμικό πρόβλημα της εύρωστης παλινδρόμησης.Ο προτεινόμενος αλγόριθμος για τη γραμμική παλινδρόμηση ονομάζεται "Greedy Algorithm for Robust Demoising" (GARD) και εναλλάσσει τα βήματά του μεταξύ της μεθόδου Ελαχίστων Τετραγώνων (LS) και της αναγνώρισης των ακραίων παρατηρήσεων, τεχνικής που βασίζεται στον OMP. Στη συνέχεια, ακολουθεί η σύγκριση της νέας μεθόδου με ανταγωνιστικές της. Συγκεκριμένα, από τα αποτελέσματα παρατηρείται ότι ο GARD: α) δείχνει ανοχή σε ακραίες τιμές (εύρωστος), β) καταφέρνει να προσεγγίσει τη λύση με πολύ μικρό λάθος και γ) απαιτεί μικρό υπολογιστικό κόστος. Επιπλέον, προκύπτουν σημαντικά θεωρητικά ευρήματα, τα οποία οφείλονται στην απλότητα της μεθόδου. Αρχικά, αποδεικνύεται ότι η μέθοδος συγκλίνει σε πεπερασμένο αριθμό βημάτων. Στη συνέχεια, η μελέτη επικεντρώνεται στην αναγνώριση των ακραίων παρατηρήσεων. Το γεγονός ότι η περίπτωση απουσίας συμβατικού θορύβου μελετήθηκε ξεχωριστά, οφείλεται κυρίως στα εξής: α) στην απλοποίηση απαιτητικών πράξεων και β) στην ανάδειξη σημαντικών γεωμετρικών ιδιοτήτων. Συγκεκριμένα, προέκυψε κατάλληλο φράγμα για τη σταθερά της συνθήκης «Περιορισμένης Ισομετρίας» ("Restricted Isometry Property" - (RIP)), το οποίο εξασφαλίζει ότι η ανάκτηση του σήματος μέσω του GARD είναι ακριβής (μηδενικό σφάλμα). Τέλος, για την περίπτωση όπου ακραίες τιμές και συμβατικός θόρυβος συνυπάρχουν και με την παραδοχή ότι το διάνυσμα του συμβατικού θορύβου είναι φραγμένο, προέκυψε μια αντίστοιχη συνθήκη η οποία εξασφαλίζει την ανάκτηση του φορέα του αραιού διανύσματος θορύβου (outliers). Δεδομένου ότι μια τέτοια συνθήκη ικανοποιείται, αποδείχθηκε ότι το σφάλμα προσέγγισης είναι φραγμένο και άρα ο εκτιμητής GARD ευσταθής.Για το πρόβλημα της εύρωστης μη γραμμικής παλινδρόμησης, θεωρείται, επιπλέον, ότι η άγνωστη μη γραμμική συνάρτηση ανήκει σε ένα χώρο Hilbert με αναπαραγωγικούς πυρήνες (RKHS). Λόγω της ύπαρξης ακραίων παρατηρήσεων, τεχνικές όπως το Kernel Ridge Regression (KRR) ή το Support Vector Regression (SVR) αποδεικνύονται ανεπαρκείς. Βασισμένοι στην προαναφερθείσα ανάλυση των συνιστωσών του θορύβου και χρησιμοποιώντας την τεχνική της αραιής μοντελοποίησης, πραγματοποιείται η εκτίμηση των ακραίων παρατηρήσεων σύμφωνα με τα βήματα μιας άπληστης επαναληπτικής διαδικασίας. Ο προτεινόμενος αλγόριθμος ονομάζεται "Kernel Greedy Algorithm for Robust Denoising" (KGARD), και εναλλάσσει τα βήματά μεταξύ ενός εκτιμητή KRR και της αναγνώρισης ακραίων παρατηρήσεων, με βάση τον OMP. Αναλύεται θεωρητικά η ικανότητα του αλγορίθμου να αναγνωρίσει τις πιθανές ακραίες παρατηρήσεις. Επιπλέον, ο αλγόριθμος KGARD συγκρίνεται με άλλες μεθόδους αιχμής μέσα από εκτεταμένο αριθμό πειραμάτων, όπου και παρατηρείται η σαφώς καλύτερη απόδοσή του. Τέλος, η προτεινόμενη μέθοδος για την εύρωστη παλινδρόμηση εφαρμόζεται στην αποθορύβωση εικόνας, όπου αναδεικνύονται τα σαφή πλεονεκτήματα της μεθόδου. Τα πειράματα επιβεβαιώνουν ότι ο αλγόριθμος KGARD βελτιώνει σημαντικά την διαδικασία της αποθορύβωσης, στην περίπτωση όπου στον θόρυβο υπεισέρχονται ακραίες παρατηρήσεις.