{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1315642"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1315642","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Αλγόριθμοι για τον υπολογισμό αραιών λύσεων αορίστων γραμμικών συστημάτων","abstract":"Ένας σημαντικός κλάδος των Εφαρμοσμένων Μαθηματικών ο οποίος τις τελευταίες δεκαετίες γνώρισε ραγδαία ανάπτυξη και συνεχίζει να αναπτύσσεται με ακόμη γρηγορότερο ρυθμό, είναι η Θεωρία Βελτιστοποίησης. Μια ενδιαφέρουσα εφαρμογή της στον τομέα της Πληροφορικής και συγκεκριμένα στην επεξεργασία και μετάδοση σήματος, είναι η αναπαράσταση ενός σήματος το οποίο μεταφέρει πληροφορία (ήχο, εικόνα ή βίντεο) από έναν αραιό μετασχηματισμό διανύσματος. Ο αραιός μετασχηματισμός του διανύσματος χρησιμοποιείται ώστε τα δεδομένα να μεταφέρονται και να αποθηκεύονται καταλαμβάνοντας τον ελάχιστο δυνατό χώρο. Η μαθηματική διατύπωση του προβλήματος είναι πως μπορούμε να λύσουμε ένα γραμμικό σύστημα n εξισώσεων και m αγνώστων με n<m (αόριστο γραμμικό σύστημα), βρίσκοντας όμως λύσεις οι οποίες είναι αραιές. Δηλαδή, επιδιώκουμε η λύση μας να περιέχει αρκετά μηδενικά στοιχεία. Η παρούσα εργασία αποτελείται από δύο μέρη. Αρχικά ορίζουμε κατάλληλο μέτρο για το πρόβλημα βελτιστοποίησης. Δείχνουμε ότι το μέτρο αυτό αποτελεί μετρική και μάλιστα προκύπτει από τη διακριτή. Επειδή το πρόβλημα δεν είναι επιλύσιμο για οποιασδήποτε δομής πίνακα, ορίζουμε τις προϋποθέσεις κάτω υπό τις οποίες θα μπορούσε ένας πίνακας να είναι κατάλληλος. Κατόπιν ορίζουμε το πρόβλημα διαφορετικά, χρησιμοποιώντας μια κυρτή προσέγγιση του αρχικού μέτρου και εξετάζουμε πότε οι δύο μορφές του ίδιου προβλήματος είναι ισοδύναμες. Στο δεύτερο μέρος αντιμετωπίζουμε το πρόβλημα στην πράξη. Γενικά το πρόβλημα είναι επιλύσιμο με μια ποικιλία μεθόδων, εδώ εξετάζουμε τις πιο βασικές. Διατυπώνουμε το πρόβλημα στις τρεις διαφορετικές του μορφές και αναλύουμε τους αλγόριθμους τους οποίους χρησιμοποιούμε σε κάθε περίπτωση. Τέλος, ελέγχουμε κατά πόσο τα θεωρητικά αποτελέσματα επηρεάζουν τη διαδικασία επίλυσης του προβλήματος στην πράξη και ελέγχουμε την ποιότητα των αλγοριθμικών διαδικασιών, συγκρίνοντας τη μια με την άλλη.","abstract_html":"Ένας σημαντικός κλάδος των Εφαρμοσμένων Μαθηματικών ο οποίος τις τελευταίες δεκαετίες γνώρισε ραγδαία ανάπτυξη και συνεχίζει να αναπτύσσεται με ακόμη γρηγορότερο ρυθμό, είναι η Θεωρία Βελτιστοποίησης. Μια ενδιαφέρουσα εφαρμογή της στον τομέα της Πληροφορικής και συγκεκριμένα στην επεξεργασία και μετάδοση σήματος, είναι η αναπαράσταση ενός σήματος το οποίο μεταφέρει πληροφορία (ήχο, εικόνα ή βίντεο) από έναν αραιό μετασχηματισμό διανύσματος. Ο αραιός μετασχηματισμός του διανύσματος χρησιμοποιείται ώστε τα δεδομένα να μεταφέρονται και να αποθηκεύονται καταλαμβάνοντας τον ελάχιστο δυνατό χώρο. Η μαθηματική διατύπωση του προβλήματος είναι πως μπορούμε να λύσουμε ένα γραμμικό σύστημα n εξισώσεων και m αγνώστων με n&lt;m (αόριστο γραμμικό σύστημα), βρίσκοντας όμως λύσεις οι οποίες είναι αραιές. Δηλαδή, επιδιώκουμε η λύση μας να περιέχει αρκετά μηδενικά στοιχεία. Η παρούσα εργασία αποτελείται από δύο μέρη. Αρχικά ορίζουμε κατάλληλο μέτρο για το πρόβλημα βελτιστοποίησης. Δείχνουμε ότι το μέτρο αυτό αποτελεί μετρική και μάλιστα προκύπτει από τη διακριτή. Επειδή το πρόβλημα δεν είναι επιλύσιμο για οποιασδήποτε δομής πίνακα, ορίζουμε τις προϋποθέσεις κάτω υπό τις οποίες θα μπορούσε ένας πίνακας να είναι κατάλληλος. Κατόπιν ορίζουμε το πρόβλημα διαφορετικά, χρησιμοποιώντας μια κυρτή προσέγγιση του αρχικού μέτρου και εξετάζουμε πότε οι δύο μορφές του ίδιου προβλήματος είναι ισοδύναμες. Στο δεύτερο μέρος αντιμετωπίζουμε το πρόβλημα στην πράξη. Γενικά το πρόβλημα είναι επιλύσιμο με μια ποικιλία μεθόδων, εδώ εξετάζουμε τις πιο βασικές. Διατυπώνουμε το πρόβλημα στις τρεις διαφορετικές του μορφές και αναλύουμε τους αλγόριθμους τους οποίους χρησιμοποιούμε σε κάθε περίπτωση. Τέλος, ελέγχουμε κατά πόσο τα θεωρητικά αποτελέσματα επηρεάζουν τη διαδικασία επίλυσης του προβλήματος στην πράξη και ελέγχουμε την ποιότητα των αλγοριθμικών διαδικασιών, συγκρίνοντας τη μια με την άλλη.","abstract_has_math":false,"creators":["Παπαγεωργίου Γεώργιος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-11-19T05:24:15Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1315642"],"render_values":[{"text":"uoadl:1315642","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1315642","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1315642","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1315642","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Παπαγεωργίου Γεώργιος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1315642","https://pergamos.lib.uoa.gr/uoa/dl/object/1315642"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ένας σημαντικός κλάδος των Εφαρμοσμένων Μαθηματικών ο οποίος τις τελευταίες δεκαετίες γνώρισε ραγδαία ανάπτυξη και συνεχίζει να αναπτύσσεται με ακόμη γρηγορότερο ρυθμό, είναι η Θεωρία Βελτιστοποίησης. Μια ενδιαφέρουσα εφαρμογή της στον τομέα της Πληροφορικής και συγκεκριμένα στην επεξεργασία και μετάδοση σήματος, είναι η αναπαράσταση ενός σήματος το οποίο μεταφέρει πληροφορία (ήχο, εικόνα ή βίντεο) από έναν αραιό μετασχηματισμό διανύσματος. Ο αραιός μετασχηματισμός του διανύσματος χρησιμοποιείται ώστε τα δεδομένα να μεταφέρονται και να αποθηκεύονται καταλαμβάνοντας τον ελάχιστο δυνατό χώρο. Η μαθηματική διατύπωση του προβλήματος είναι πως μπορούμε να λύσουμε ένα γραμμικό σύστημα n εξισώσεων και m αγνώστων με n<m (αόριστο γραμμικό σύστημα), βρίσκοντας όμως λύσεις οι οποίες είναι αραιές. Δηλαδή, επιδιώκουμε η λύση μας να περιέχει αρκετά μηδενικά στοιχεία. Η παρούσα εργασία αποτελείται από δύο μέρη. Αρχικά ορίζουμε κατάλληλο μέτρο για το πρόβλημα βελτιστοποίησης. Δείχνουμε ότι το μέτρο αυτό αποτελεί μετρική και μάλιστα προκύπτει από τη διακριτή. Επειδή το πρόβλημα δεν είναι επιλύσιμο για οποιασδήποτε δομής πίνακα, ορίζουμε τις προϋποθέσεις κάτω υπό τις οποίες θα μπορούσε ένας πίνακας να είναι κατάλληλος. Κατόπιν ορίζουμε το πρόβλημα διαφορετικά, χρησιμοποιώντας μια κυρτή προσέγγιση του αρχικού μέτρου και εξετάζουμε πότε οι δύο μορφές του ίδιου προβλήματος είναι ισοδύναμες. Στο δεύτερο μέρος αντιμετωπίζουμε το πρόβλημα στην πράξη. Γενικά το πρόβλημα είναι επιλύσιμο με μια ποικιλία μεθόδων, εδώ εξετάζουμε τις πιο βασικές. Διατυπώνουμε το πρόβλημα στις τρεις διαφορετικές του μορφές και αναλύουμε τους αλγόριθμους τους οποίους χρησιμοποιούμε σε κάθε περίπτωση. Τέλος, ελέγχουμε κατά πόσο τα θεωρητικά αποτελέσματα επηρεάζουν τη διαδικασία επίλυσης του προβλήματος στην πράξη και ελέγχουμε την ποιότητα των αλγοριθμικών διαδικασιών, συγκρίνοντας τη μια με την άλλη.","An important branch of Applied Mathematics, which in recent decades experienced rapid growth and continues to grow at even faster pace, is Optimization Theory. An interesting application in the field of Informatics and Telecommunications and particularly in signal transmission and processing, is the representation of a data signal (sound, image or video) using a sparse vector transformation. The sparse transformation of the initial signal is used so that the data is processed and stored in a more economical way, especially since the size of the data is constantly growing. The mathematical formulation of the problem is how to solve a linear system of n equations and m unknowns n<m (underdetermined), obtaining only sparse solutions, i.e. solutions to the linear system of equations containing as many zero coordinates as possible. The following work consists of two parts. In the beginning we define an appropriate measure, suitable for the optimization problem. We prove that this measure defines a metric and not a norm, resulting from the discrete metric indeed. Because the problem is not solvable for any general matrix structure, we define the conditions under which one could be suitable. We also use a different formulation of the problem using a convex approximation of the original measure and check the equivalence of the problems. In the second part we take a practical approach of the problem. The problem is in general solved using a variety of methods, we examine five basic methods. First we make the three formulations of the problem and analyze the algorithms used in every case. Finally, we check whether the theoretical results affect the process of solving the problem in practice and test the quality of algorithmic procedures, comparing one with another."]},{"key":"dc:title","label":"Title","values":["Αλγόριθμοι για τον υπολογισμό αραιών λύσεων αορίστων γραμμικών συστημάτων"]}]}],"canonical_facts":{"dc:creator":["Παπαγεωργίου Γεώργιος"],"dc:date":["2012"],"dc:description":["Ένας σημαντικός κλάδος των Εφαρμοσμένων Μαθηματικών ο οποίος τις τελευταίες δεκαετίες γνώρισε ραγδαία ανάπτυξη και συνεχίζει να αναπτύσσεται με ακόμη γρηγορότερο ρυθμό, είναι η Θεωρία Βελτιστοποίησης. Μια ενδιαφέρουσα εφαρμογή της στον τομέα της Πληροφορικής και συγκεκριμένα στην επεξεργασία και μετάδοση σήματος, είναι η αναπαράσταση ενός σήματος το οποίο μεταφέρει πληροφορία (ήχο, εικόνα ή βίντεο) από έναν αραιό μετασχηματισμό διανύσματος. Ο αραιός μετασχηματισμός του διανύσματος χρησιμοποιείται ώστε τα δεδομένα να μεταφέρονται και να αποθηκεύονται καταλαμβάνοντας τον ελάχιστο δυνατό χώρο. Η μαθηματική διατύπωση του προβλήματος είναι πως μπορούμε να λύσουμε ένα γραμμικό σύστημα n εξισώσεων και m αγνώστων με n<m (αόριστο γραμμικό σύστημα), βρίσκοντας όμως λύσεις οι οποίες είναι αραιές. Δηλαδή, επιδιώκουμε η λύση μας να περιέχει αρκετά μηδενικά στοιχεία. Η παρούσα εργασία αποτελείται από δύο μέρη. Αρχικά ορίζουμε κατάλληλο μέτρο για το πρόβλημα βελτιστοποίησης. Δείχνουμε ότι το μέτρο αυτό αποτελεί μετρική και μάλιστα προκύπτει από τη διακριτή. Επειδή το πρόβλημα δεν είναι επιλύσιμο για οποιασδήποτε δομής πίνακα, ορίζουμε τις προϋποθέσεις κάτω υπό τις οποίες θα μπορούσε ένας πίνακας να είναι κατάλληλος. Κατόπιν ορίζουμε το πρόβλημα διαφορετικά, χρησιμοποιώντας μια κυρτή προσέγγιση του αρχικού μέτρου και εξετάζουμε πότε οι δύο μορφές του ίδιου προβλήματος είναι ισοδύναμες. Στο δεύτερο μέρος αντιμετωπίζουμε το πρόβλημα στην πράξη. Γενικά το πρόβλημα είναι επιλύσιμο με μια ποικιλία μεθόδων, εδώ εξετάζουμε τις πιο βασικές. Διατυπώνουμε το πρόβλημα στις τρεις διαφορετικές του μορφές και αναλύουμε τους αλγόριθμους τους οποίους χρησιμοποιούμε σε κάθε περίπτωση. Τέλος, ελέγχουμε κατά πόσο τα θεωρητικά αποτελέσματα επηρεάζουν τη διαδικασία επίλυσης του προβλήματος στην πράξη και ελέγχουμε την ποιότητα των αλγοριθμικών διαδικασιών, συγκρίνοντας τη μια με την άλλη.","An important branch of Applied Mathematics, which in recent decades experienced rapid growth and continues to grow at even faster pace, is Optimization Theory. An interesting application in the field of Informatics and Telecommunications and particularly in signal transmission and processing, is the representation of a data signal (sound, image or video) using a sparse vector transformation. The sparse transformation of the initial signal is used so that the data is processed and stored in a more economical way, especially since the size of the data is constantly growing. The mathematical formulation of the problem is how to solve a linear system of n equations and m unknowns n<m (underdetermined), obtaining only sparse solutions, i.e. solutions to the linear system of equations containing as many zero coordinates as possible. The following work consists of two parts. In the beginning we define an appropriate measure, suitable for the optimization problem. We prove that this measure defines a metric and not a norm, resulting from the discrete metric indeed. Because the problem is not solvable for any general matrix structure, we define the conditions under which one could be suitable. We also use a different formulation of the problem using a convex approximation of the original measure and check the equivalence of the problems. In the second part we take a practical approach of the problem. The problem is in general solved using a variety of methods, we examine five basic methods. First we make the three formulations of the problem and analyze the algorithms used in every case. Finally, we check whether the theoretical results affect the process of solving the problem in practice and test the quality of algorithmic procedures, comparing one with another."],"dc:identifier":["uoadl:1315642","https://pergamos.lib.uoa.gr/uoa/dl/object/1315642"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Αλγόριθμοι για τον υπολογισμό αραιών λύσεων αορίστων γραμμικών συστημάτων"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:24:15Z"}