Extremum problems of directed information

Abstract

Τα κλασσικά μέτρα θεωρίας της πληροφορίας που χρησιμοποιούνται για τον υπολογισμό της χωρητικότητας του καναλιού και της συμπίεσης της πληροφορίας με απώλειες, ορίζονται μέσω της αμοιβαίας πληροφορίας. Για επικοινωνιακά κανάλια και πηγές πληροφορίας χωρίς μνήμη, το μέτρο της αμοιβαία πληροφορίας έχει εφαρμοστεί με επιτυχία για να υπολογίσει τη λειτουργική χωρητικότητα των καναλιών και την λειτουργική συμπίεση με απώλειες πηγών πληροφορίας αντίστοιχα. Για κανάλια με μνήμη και αιτιατή ανάδραση, και για μη προβλέψιμη συμπίεση με απώλειες πηγών πληροφορίας με μνήμη, το σωστό μέτρο πληροφορίας είναι η κατευθυνόμενη πληροφορία που ορίζεται μέσω των αιτιατών υπό συνθήκη πιθανοτικών κατανομών. Η κατευθυνόμενη πληροφορία χρησιμοποιείται επίσης σε επικοινωνιακά δίκτυα, για να χαρακτηρίσει την πληροφορία σε τυχαία συστήματα ελέγχου που λειτουργούν σε πραγματικό χρόνο και στην ανάλυση βιολογικών συστημάτων. Η παρούσα διδακτορική διατριβή αποσκοπεί στο να ερευνήσει τις συναρτησιακές και τοπολογικές ιδιότητες του μέτρου της κατευθυνόμενης πληροφορίας καθώς και τα δύο βασικά προβλήματα ακροτάτων που απορρέουν από αυτό το μέτρο της θεωρίας πληροφορίας. Το πρώτο πρόβλημα ακρότατου είναι αυτό της μη προβλέψιμης συνάρτησης ρυθμού-παραμόρφωσης για πηγές πληροφορίας με μνήμη και το δεύτερο, αφορά την χωρητικότητα με ανάδραση για κανάλια πληροφορίας με μνήμη και ανάδραση. Για αυτά τα δύο προβλήματα ακροτάτων, αποδεικνύεται η ύπαρξη βέλτιστης λύσης κάνοντας χρήση της τοπολογίας ως προς την ασθενή σύγκλιση για κατανομές πιθανοτήτων. Για το ακρότατο της μη προβλέψιμης συνάρτησης ρυθμού-παραμόρφωσης, περιγράφονται εφαρμογές στο σχεδιασμό από κοινού κωδικοποίησης πηγής - καναλιού βασιζόμενοι στη πιθανότητα μέσης παραμόρφωσης και στην πιθανότητα υπερβολικής παραμόρφωσης, στην οριοθέτηση της βέλτιστης απόδοσης που θεωρητικά διέπει το σύστημα για μη αιτιατούς και αιτιατούς κώδικες πληροφορίας, και στον υπολογισμού της απώλειας ρυθμού ως προς κώδικες μηδενικής καθυστέρησης και αιτιατούς κώδικες. Για το ακρότατο της χωρητικότητας με ανάδραση περιγράφονται διαδοχικές ικανές και αναγκαίες συνθήκες που εφαρμόζονται σε χρονικά μεταβαλλόμενα κανάλια πληροφορίας με μνήμη για να επιτευχθούν κλειστές αναδρομικές εκφράσεις των βέλτιστων κατανομών που περιγράφουν τη μέγιστη τιμή της κατευθυνόμενης πληροφορίας σε πεπερασμένο χρόνο. Επιπρόσθετα, επιτυγχάνεται η εξεύρεση κλειστών εκφράσεων που χαρακτηρίζουν τη χωρητικότητα με ανάδραση διαφόρων χρονικά αμετάβλητων καναλιών πληροφορίας με μνήμη κάνοντας χρήση των ασυμπτωτικών ιδιοτήτων των κλειστών αναδρομικών εκφράσεων των βέλτιστων κατανομών που περιγράφουν τη μέγιστη τιμή της κατευθυνόμενης πληροφορίας σε πεπερασμένο χρόνο.

Traditional information theoretic measures used for evaluating channel capacity and lossy compression are defined via mutual information. For memoryless communication channels and sources this measure has been successfully applied to compute the operation capacity of channels and lossy compression of sources, respectively. For channels with memory and feedback, and nonanticipative lossy compression of sources with memory the valid information measure is the directed information defined via nonanticipative conditional distributions. Directed information is also extensively utilized in networks, communication for real-time stochastic control applications, and in biological system analysis. This thesis investigates the functional and topological properties of directed information and two extremum problems arising from this information theoretic measure. The first, is the extremum problem of nonanticipative rate distortion function of sources with memory and the second, is the extremum problem of feedback capacity of channels with memory and feedback. For these two extremum problems, existence of an optimal solution is shown using the topology of weak convergence of probability distributions. For the extremum problem of nonanticipative rate distortion function, applications in zero-delay Joint Source-Channel Coding design based on average and excess distortion probability, in bounding the Optimal Performance Theoretically Attainable by noncausal and causal codes, and computing the Rate Loss of zero-delay and causal codes with respect to noncausal codes are derived. For the extremum problem of feedback capacity, sequential necessary and sufficient conditions are derived and applied to time-varying channels with memory to establish recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. In addition, the feedback capacity of several time-invariant channels with memory is derived using the asymptotic properties of the optimal distributions of the finite-time horizon directed information.