Signal processing on graphs

Abstract

In this PhD thesis, several signal-processing models applied on graphs have been studied. Half-quadratic (HQ) optimization, robust estimators, such as marginal median and M-estimators, l21 norm regularization, block least mean squares have been the fundamental basis of the proposed approaches. Specifically, to remedy the vulnerability from erroneous embeddings on Multidimensional Scaling (MDS) problem due to the distortion introduced by outliers, a unified framework is proposed where the MDS is treated as maximization of a correntropy criterion, which is solved by HQ optimization in either multiplicative or additive forms. Three novel algorithms are derived. Their performance is assessed experimentally against three state-of-the-art MDS techniques, namely the Scaling by Majorizing a Complicated Function, the Robust Euclidean Embedding, and the Robust MDS under the same conditions. The experimental results indicate that the proposed algorithms perform substantially better than the aforementioned competing techniques. Furthermore, another unified framework for the solution of MDS problem is proposed, which resorts, again, to HQ optimization and employs potential functions of M-estimators in combination with l21 norm regularization. The numerical tests demonstrate that the proposed algorithms perform better than the competing alternatives. Moreover, a novel HQ framework, employing M-estimators and nuclear norm regularization, has been proposed for solving the MDS problem in the presence of a dissimilarity matrix corrupted with outliers. It has been proven that the proposed algorithms outperform the state-of-the-art MDS techniques. Then, the inclusion of several dimensionality reduction (DR) algorithms within the unified framework, known as graph embedding, is demonstrated. The enforcement of orthogonality to the projection matrix within this framework is proven to be of vital importance, since the use of orthogonal mapping DR algorithms against their non-orthogonal counterparts improves significantly the recognition rate of Nearest Neighbor (NN) classifier. One may simultaneously also impose the l21 regularization on the projection matrix, seeking for row-sparsity. This leads to the known Joint Feature Selection and Subspace Learning (JFSSL) framework. All DR algorithms are employed within JFSSL. It is proven that the use of orthogonal mapping algorithms within JFSSL against their non-orthogonal counterparts does not improve the recognition rate of NN classifier. Then, the case when a randomly chosen subset of agents shares deliberately with its neighborhood local information corrupted with gross errors is considered. A three-fold extension of the state-of-the-art spatio-temporal diffusion algorithms over mobile networks is proposed. First, the agents preserve a limited memory of prior regression vectors and prior estimates of the distance to the target in the time domain so that a block least mean squares is applied. Second, in the time domain, the agents estimate the combination weights employing the M-estimators’ weighting function of the scaled distance of past intermediate location estimates from their mean. Third, in the spatial domain, the agents estimate the combination weights based on negative exponentials of the scaled distance of intermediate location estimates within their neighborhood from the marginal median of these estimates. The experiments demonstrate that, at the expense of some additional computational requirements, the proposed algorithms can cope with the outliers and outperform the contemporary strategies.

Η παρούσα διατριβή πραγματεύτηκε μοντέλα επεξεργασίας σήματος που εφαρμόζονται σε γραφήματα. Η τετραγωνική κατά το ήμισυ ελαχιστοποίηση, οι εύρωστοι εκτιμητές, όπως ο διάμεσος και οι Μ-εκτιμητές, η κανονικοποίηση μέσω της l21 νόρμας, η ομαδική μέθοδος των ελαχίστων τετραγώνων αποτελούν τη βάση των προτεινόμενων προσεγγίσεων. Συγκεκριμένα, για να διορθωθεί η τρωτότητα από λανθασμένες ενσωματώσεις στο πρόβλημα της πολυδιάστατης κλιμάκωσης, εξαιτίας της παραμόρφωσης που εισάγουν οι ακραίες τιμές, προτείνεται ένα ενοποιημένο πλαίσιο όπου το πρόβλημα της πολυδιάστατης κλιμάκωσης αντιμετωπίζεται ως μεγιστοποίηση ενός κριτηρίου συσχεντροπίας, το οποίο επιλύεται με τετραγωνική κατά το ήμισυ ελαχιστοποίηση με χρήση πολλαπλασιαστικών ή προσθετικών μαθηματικών διατυπώσεων. Προκύπτουν τρεις νέοι αλγόριθμοι. Η απόδοσή τους αξιολογείται πειραματικά έναντι τριών σύγχρονων τεχνικών πολυδιάστατης κλιμάκωσης: Κλιμάκωση Μεγιστοποιώντας μία Περίπλοκη Συνάρτηση, Εύρωστη Ευκλείδεια Ενσωμάτωση, και Εύρωστη Πολυδιάστατη Κλιμάκωση. Τα πειραματικά αποτελέσματα καταδεικνύουν ότι οι προτεινόμενοι αλγόριθμοι αποδίδουν σημαντικώς καλύτερα από τις προαναφερθείσες ανταγωνιστικές τεχνικές. Επιπλέον, προτείνεται ένα άλλο ενοποιημένο πλαίσιο για την επίλυση του προβλήματος της πολυδιάστατης κλιμάκωσης, το οποίο χρησιμοποιεί, ομοίως, τετραγωνική κατά το ήμισυ ελαχιστοποίηση, αξιοποιώντας συναρτήσεις των M-εκτιμητών σε συνδυασμό με έναν περιορισμό κανονικοποίησης της l21 νόρμας. Τα πειραματικά δεδομένα κατέδειξαν ότι οι προτεινόμενοι αλγόριθμοι αποδίδουν καλύτερα από τις σύγχρονες ανταγωνιστικές τεχνικές. Επιπροσθέτως, εξετάστηκε μία ακόμη παραλλαγή του προταθέντος πλαισίου η οποία περιλαμβάνει τη χρήση M-εκτιμητών σε συνδυασμό με έναν περιορισμό κανονικοποίησης της πυρηνικής νόρμας. Ομοίως, απεδείχθη ότι οι προτεινόμενοι αλγόριθμοι υπερτερούν έναντι των σύγχρονων τεχνικών. Στη συνέχεια, έλαβε χώρα η συμπερίληψη πολλών αλγορίθμων μείωσης διαστάσεων σε ένα ενιαίο πλαίσιο, γνωστό ως ενσωμάτωση γραφήματος. Η εφαρμογή της ορθογωνικότητας στο γραμμικό πίνακα προβολής, εντός αυτού του πλαισίου, απεδείχθη ζωτικής σημασίας, καθώς οι «ορθογώνιοι» αλγόριθμοι μείωσης διαστάσεων ξεπερνούν σε ποσοστό αναγνώρισης τους αντίστοιχους μη «ορθογώνιους», με τη χρήση του ταξινομητή του πλησιέστερου γείτονα. Για να επιτευχθούν αραιές γραμμές στον πίνακα προβολής, επιβλήθηκε ταυτόχρονα η l21 νόρμα στο συγκεκριμένο πίνακα, οδηγώντας στο γνωστό μοντέλο της από κοινού επιλογής χαρακτηριστικών και μάθησης υποχώρων. Αποδεικνύεται ότι η χρήση των ορθογώνιων αλγορίθμων στο προαναφερθέν πλαίσιο έναντι των αντίστοιχων μη ορθογώνιων αλγορίθμων δεν βελτιώνει το ποσοστό αναγνώρισης του ταξινομητή του πλησιέστερου γείτονα. Στη συνέχεια, εξετάζεται η περίπτωση που ένα τυχαία επιλεγμένο υποσύνολο πρακτόρων μοιράζεται με τους γείτονές του τοπικές πληροφορίες οι οποίες έχουν αλλοιωθεί εσκεμμένα από μεγάλα σφάλματα. Προτείνονται τρεις παραλλαγές των υφιστάμενων αλγορίθμων χωροχρονικής διάχυσης σε προσαρμοστικά δίκτυα. Πρώτα απ’ όλα, οι πράκτορες εφαρμόζουν την ομαδική μέθοδο των ελαχίστων τετραγώνων εκμεταλλευόμενοι στο πεδίο του χρόνου μια περιορισμένη μνήμη προηγούμενων διανυσμάτων παλινδρόμησης καθώς και προηγούμενες εκτιμήσεις της απόστασης από το στόχο. Δεύτερον, οι πράκτορες προχωρούν, στο πεδίο του χρόνου, σε εκτίμηση των συνδυαστικών βαρών χρησιμοποιώντας τη συνάρτηση στάθμισης των M-εκτιμητών της απόστασης κάθε μίας από τις ενδιάμεσες εκτιμήσεις από τη μέση τιμή αυτών των εκτιμήσεων. Τρίτον, οι πράκτορες προχωρούν, στο πεδίο του χώρου, σε εκτίμηση των συνδυαστικών βαρών βασιζόμενοι στα εκθετικά της αρνητικής απόστασης των ενδιάμεσων εκτιμήσεων θέσεως, εντός της γειτονιάς τους, από τη μεσαία τιμή αυτών των εκτιμήσεων. Οι πειραματικές καμπύλες μάθησης κατέδειξαν ότι, σε βάρος ορισμένων επιπλέον υπολογιστικών απαιτήσεων, οι προτεινόμενοι αλγόριθμοι εξομαλύνουν αποτελεσματικότερα την επίδραση των παράτυπων σημείων σε σχέση με τις σύγχρονες στρατηγικές.