Μεθοδολογίες υπολογισμού διγραμμικών μορφών και εφαρμογές

Abstract

The management of large-scale data is necessary nowadays and the development of appropriate methodologies is required. The computation of bilinear forms and related quantities leads to useful results and it is often a criterion for properties related to the corresponding application. Most of the scientific applications such as network analysis, computer science, statistics, economics, etc., require the management of large-scale matrices for the extraction of useful results. In these applications, it is usually not possible the direct computation of the desired bilinear forms and thus it is necessary their estimation.In the present PhD thesis, we derive estimates for the bilinear forms of the type xᵀf(A)y, where A ϵ Rᵖˣᵖ is a given matrix with specific structure, x, y ϵ Rᵖ and f is a smooth function defined on the spectrum of the matrix A. The developed method is based on an extrapolation procedure. Specifically, we generate estimates for the bilinear form xᵀA⁻¹y, where the matrix A is invertible. If the vectors x, y are chosen to be columns of the identity matrix, we can obtain estimates for the elements of the inverse of the given matrix A. We also adjust some numerical methods based on an extrapolation procedure and the Gaussian quadrature rules to estimate the diagonal of the function of symmetric matrices, without approximating the whole matrix f(A).Moreover, we derive families of one, two, and three term vector estimates for the action of the matrix f(A) on a given vector b, i.e. the product f(A)b. The calculation of the quantity f(A)b arises from applications in which it is not necessary to estimate the whole matrix f(A) or it is not feasible to calculate this matrix, especially when A is large. We also deal with the estimation and minimization of the generalized cross-validation function (GCV function) by combining an extrapolation procedure and a statistical approach. The GCV function is a popular tool for determining the tuning parameter in the linear regression model or equivalently the regularization parameter in the Tikhonov regularization. Finally, we apply the generated estimates for the aforementioned quantities in problems which deal with network analysis. Specifically, we will determine the most important nodes of a network and the ease of traveling between nodes. We also use the derived estimates for the GCV function for solving discrete ill-posed problems as well as for estimating the coefficients of the linear regression model which is used in Statistics.

Στην σημερινή εποχή είναι απαραίτητη η διαχείριση δεδομένων μεγάλης διάστασης, γεγονός που απαιτεί την ανάπτυξη κατάλληλων μεθοδολογιών για αυτόν τον σκοπό. Ο υπολογισμός διγραμμικών μορφών και συναφών ποσοτήτων οδηγεί σε χρήσιμα συμπεράσματα και συχνά αποτελεί κριτήριο για ιδιότητες που σχετίζονται με την εκάστοτε εφαρμογή. Σχεδόν σε όλες τις επιστημονικές εφαρμογές όπως είναι η ανάλυση δικτύων, η πληροφορική, η στατιστική, η οικονομία κ.α., η επεξεργασία των δεδομένων και η εξαγωγή συμπερασμάτων απαιτεί τη διαχείριση πινάκων μεγάλης διάστασης. Στις εφαρμογές αυτές, συνήθως δεν είναι εφικτός ο απευθείας υπολογισμός των επιθυμητών διγραμμικών μορφών και έτσι απαιτείται η εκτίμησή τους. Στην παρούσα διδακτορική διατριβή παράγουμε εκτιμήσεις για τις διγραμμικές μορφές του τύπου xᵀf(A)y, όπου A ϵ Rᵖˣᵖ είναι ένας δοσμένος πίνακας, x, y ϵ Rᵖ και f είναι μία ομαλή συνάρτηση ορισμένη στο φάσμα του πίνακα A. Η προτεινόμενη μέθοδος βασίζεται σε μία μέθοδο παρεκβολής. Συγκεκριμένα, δημιουργούμε εκτιμήσεις για τη διγραμμική μορφή xᵀA⁻¹y, όπου ο πίνακας Α είναι αντιστρέψιμος. Αν τα διανύσματα x, y επιλεχθούν να είναι στήλες του ταυτοτικού πίνακα, μπορούν να προκύψουν εκτιμήσεις για τα στοιχεία του αντιστρόφου του δοσμένου πίνακα A. Επίσης, προσαρμόζουμε μερικές αριθμητικές μεθόδους που βασίζονται στη μέθοδο της παρεκβολής και στην αριθμητική ολοκλήρωση του Gauss για την εκτίμηση της διαγωνίου συναρτήσεων συμμετρικών πινάκων, χωρίς να προσεγγίσουμε ολόκληρο τον πίνακα f(A). Επιπροσθέτως, παράγουμε παραμετρικές οικογένειες διανυσματικών εκτιμήσεων ενός, δύο και τριών όρων για τη δράση της συνάρτησης ενός διαγωνίσιμου πίνακα σε ένα διάνυσμα, δηλαδή του γινομένου f(A)b. Ο υπολογισμός της ποσότητας f(A)b, πηγάζει από την ύπαρξη εφαρμογών στις οποίες δεν είναι απαραίτητο να εκτιμηθεί ολόκληρος ο πίνακας f(A) ή δεν είναι εφικτός ο ακριβής υπολογισμός του πίνακα αυτού, ειδικά όταν ο A είναι μεγάλης διάστασης. Ασχολούμαστε επίσης με την εκτίμηση και ελαχιστοποίηση της γενικευμένης συνάρτησης διασταυρωμένης επικύρωσης (συνάρτηση GCV) συνδυάζοντας τη μέθοδο της παρεκβολής και μία στατιστική προσέγγιση. Η συνάρτηση GCV είναι ένα δημοφιλές εργαλείο για τον προσδιορισμό της ρυθμιστικής παραμέτρου στο γραμμικό μοντέλο παλινδρόμησης ή ισοδύναμα της παραμέτρου κανονικοποίησης στην κανονικοποίηση Tikhonov. Τέλος, εφαρμόζουμε τις παραχθείσες εκτιμήσεις για τις προαναφερθείσες ποσότητες σε προβλήματα που πηγάζουν από την ανάλυση δικτύων. Συγκεκριμένα, θα αναγνωρίσουμε τους σημαντικότερους κόμβους ενός δικτύου και θα εξακριβώσουμε την ευκολία μετάβασης ανάμεσα στους κόμβους. Χρησιμοποιούμε τις εκτιμήσεις που έχουν προκύψει για τη συνάρτηση GCV στην επίλυση διακριτών κακώς τοποθετημένων προβλημάτων καθώς και στην εκτίμηση των συντελεστών του γραμμικού μοντέλου παλινδρόμησης που μελετάται στη Στατιστική.