The quickest change-point detection problems with sampling right constraints are considered. Specially, an observer sequentially takes observations from a random sequence, whose distribution will change at an unknown time. Based on the observation sequence, the observer wants to identify the change-point as quickly as possible. Unlike the classic quickest detection problem in which the observer can take an observation at each time slot, we impose a causal sampling right constraint to the observer. In particular, sampling rights are consumed when the observer takes an observation and are replenished randomly by a stochastic process. The observer cannot take observations if there is no sampling right left. The causal sampling right constraint is motivated by several practical applications. For example, in the application of sensor network for monitoring the abrupt change of its ambient environment, the sensor can only take observations if it has energy left in its battery. With this additional constraint, we design and analyze the optimal detection and sampling right allocation strategies to minimize the detection delay under various problem setups. As one of our main contributions, a greedy sampling right allocation strategy, by which the observer spends sampling rights in taking observations as long as there are sampling rights left, is proposed. This strategy possesses a low complexity structure, and leads to simple but (asymptotically) optimal detection algorithms for the problems under consideration. Specially, our main results include: 1) Non-Bayesian quickest change-point detection: we consider non-Bayesian quickest detection problem with stochastic sampling right constraint. Two criteria, namely the algorithm level average run length (ARL) and the system level ARL, are proposed to control the false alarm rate. We show that the greedy sampling right allocation strategy combined with the cumulative sum (CUSUM) algorithm is optimal for Lorden's setup with the algorithm level ARL constraint and is asymptotically optimal for both Lorden's and Pollak's setups with the system level ARL constraint. 2) Bayesian quickest change-point detection: both limited sampling right constraint and stochastic sampling right constraint are considered in the Bayesian quickest detection problem. The limited sampling right constraint can be viewed as a special case of the stochastic sampling right constraint with a zero sampling right replenishing rate. The optimal solutions are derived for both sampling right constraints. However, the structure of the optimal solutions are rather complex. For the problem with the limited sampling right constraint, we provide asymptotic upper and lower bounds for the detection delay. For the problem with the stochastic sampling right constraint, we show that the greedy sampling right allocation strategy combined with Shiryaev's detection rule is asymptotically optimal. 3) Quickest change-point detection with unknown post-change parameters: we extend previous results to the quickest detection problem with unknown post-change parameters. Both non-Bayesian and Bayesian setups with stochastic sampling right constraints are considered. For the non-Bayesian problem, we show that the greedy sampling right allocation strategy combined with the M-CUSUM algorithm is asymptotically optimal. For the Bayesian setups, we show that the greedy sampling right allocation strategy combined with the proposed M-Shiryaev algorithm is asymptotically optimal.

Knowing the uncertainty of a calculated result is always important, but especially so when performing calculations for safety analysis. A traditional way of propagating the uncertainty of input parameters is Monte Carlo (MC) methods. A quicker alternative to MC, especially useful when computations are heavy, is Deterministic Sampling (DS). DS works by hand-picking a small set of samples, rather than randomizing a large set as in MC methods. The samples and its corresponding weights are chosen to represent the uncertainty one wants to propagate by encoding the first few statistical moments of the parameters' distributions. Finding a suitable ensemble for DS in not easy, however. Given a large enough set of samples, one can always calculate weights to encode the first couple of moments, but there is good reason to want an ensemble with only positive weights. How to choose the ensemble for DS so that all weights are positive is the problem investigated in this project. Several methods for generating such ensembles have been derived, and an algorithm for calculating weights while forcing them to be positive has been found. The methods and generated ensembles have been tested for use in uncertainty propagation in many different cases and the ensemble sizes have been compared. In general, encoding two or four moments in an ensemble seems to be enough to get a good result for the propagated mean value and standard deviation. Regarding size, the most favorable case is when the parameters are independent and have symmetrical distributions. In short, DS can work as a quicker alternative to MC methods in uncertainty propagation as well as in other applications.

Wireless communication systems require advanced techniques at the transmitter and at the receiver that improve the performance in hostile radio environments. The received signal is significantly distorted due to the dynamic nature of the wireless channel caused by multipath fading and Doppler spread. In order to mitigate the negative impact of the channel to the received signal quality, techniques as equalization and diversity are usually employed in the system design. During the transmission, the phenomenon of inter-symbol interference (ISI) occurs at the receiver due to the time dispersion of the involved channels. Hence, several delayed replicas of previous symbols interfere with the current symbol. Equalization is usually employed in order to combat the effect of the ISI. Several implementations for equalization filters have been proposed, including linear and non-linear processing, providing complexity-performance trade-offs. It is known that the length of the equalization filter determines the complexity of the technique. Since the wireless channels are characterized by long and sparse impulse responses, the conventional equalizers require high computational complexity due to the large size of their filters. In this dissertation, we have further investigated the long standing problem of equalization in light of the recently derived theory of compressed sampling (CS) for sparse and redundant representations. The developed heuristic algorithms for equalization, can exploit either the sparsity of the channel impulse response (CIR), or the sparsity of the equalizer filters, in order to derive efficient implementation designs. To this end, building on basis pursuit and matching pursuit techniques new equalization schemes have been proposed that exhibit considerable computational savings, increased performance properties and short training sequence requirements. Our main contribution for this part is the Stochastic Gradient Pursuit algorithm for sparse adaptive equalization. An alternative approach to combat ISI is based on the orthogonal frequency division multiplexing (OFDM) system. In this system, the entire channel is divided into many narrow subchannels, so as the transmitted signals to be orthogonal to each other, despite their spectral overlap. However, in the case of doubly selective channels, the Doppler effect destroys the orthogonality between subcarriers. Thus, similarly to ISI, the effect of intercarrier interference (ICI) is introduced at the receiver, where symbols which belong to other subcarriers interfere with the current one. Considering this problem, we have developed iterative algorithms which recursively cancels the ICI at the receiver, providing performance-complexity trade-offs. For low or medium Doppler spreads, the typical approach is to approximate the frequency-domain channel matrix with a banded one. On this premise, we derived reduced-rank preconditioned conjugate gradient (PCG) algorithms in order to estimate the equalization matrix with a reduced number of iterations. Also developed an improved PCG algorithm with the same complexity order, using the Galerkin projections theory. However, in rapidly changing environments, a severe ICI is introduced and the banded approximation results in significant performance degradation. In order to recover this performance loss, we developed regularized estimation framework for ICI equalization, with linear complexity with respect the the number of the subcarriers. Moreover, we proposed a new equalization technique which has the potential to completely cancel the ICI. This approach works in a successive manner through a number of stages, conveying from the fully-connected ordered successive interference cancellation architecture (OSIC) in order to fully suppress the residual interference at each stage of the equalizer. On the other hand, diversity can improve the performance of the communication system by sending the information symbols through multiple signal paths, each of which fades independently. One approach to obtain diversity is through cooperative transmission, considering a group of nearby terminals (relays) as forming one virtual antenna array and applying a spatial beamforming technique so as to optimize the communication via them. Such beamforming techniques differ from their classical counterparts where the array elements are located in a common processing unit, due to the distribution of the relays in the space. In this setting, we developed new distributed algorithms which enable the relay cooperation for the computation of the beamforming weights leveraging the computational abilities of the relays. Each relay can estimate only the corresponding entry of the principal eigenvector, combining data from its network neighbours. The proposed algorithms are applied to two distributed beamforming schemes for relay networks. In the first scheme, the beamforming vector is computed through minimization of a total transmit power subject to the receiver quality-of-service (QoS) constraint. In the second scheme, the beamforming weights are obtained through maximization of the receiver SNR subject to a total transmit power constraint. Moreover, the proposed algorithms operate blindly, implying that no training data are required to be transmitted to the relays, and adaptively, exhibiting a quite short convergence period. / Τα συστήματα ασύρματων επικοινωνιών απαιτούν εξειδικευμένες τεχνικές στον πομπό και στον δέκτη, οι οποίες να βελτιώνουν την απόδοση του συστήματος σε εχθρικά περιβάλλοντα ασύρματης μετάδοσης. Λόγω της δυναμικής φύσης του ασύρματου καναλιού, που περιγράφεται από τα φαινόμενα της απόσβεσης, της πολυδιόδευσης και του Doppler, το λαμβανόμενο σήμα είναι παραμορφωμένο σε σημαντικό βαθμό. Για να αναιρέσουμε αυτήν την αρνητική επίδραση του καναλιού στην ποιότητα του λαμβανόμενου σήματος, κατά τον σχεδιασμό του συστήματος συνήθως υιοθετούνται τεχνικές όπως η ισοστάθμιση και η ποικιλομορφία. Ένα φαινόμενο που προκύπτει στο δέκτη ενός ασύρματου συστήματος επικοινωνίας, λόγω της χρονικής διασποράς που παρουσιάζουν τα κανάλια, είναι η διασυμβολική παρεμβολή, όπου χρονικά καθυστερημένα αντίγραφα προηγούμενων συμβόλων παρεμβάλουν με το τρέχων σύμβολο. Ένας τρόπος για την αντιμετώπιση του φαινομένου αυτού, είναι μέσω της ισοστάθμισης στο δέκτη, όπου χρησιμοποιώντας γραμμικές και μη-γραμμικές τεχνικές επεξεργασίας, τα μεταδιδόμενα σύμβολα ανιχνεύονται από το ληφθέν σήμα. Ωστόσο, συνήθως τα ασύρματα κανάλια χαρακτηρίζονται από κρουστικές αποκρούσεις μεγάλου μήκους αλλά λίγων μη μηδενικών συντελεστών, και σε αυτήν την περίπτωση η υπολογιστική πολυπλοκότητα των συνήθων τεχνικών είναι πολύ υψηλή. Στα πλαίσια αυτής της διατριβής, αναπτύχθηκαν νέοι ευριστικοί αλγόριθμοι για το πρόβλημα της ισοστάθμισης, οι οποίοι εκμεταλλεύονται είτε την αραιότητα της κρουστικής απόκρισης είναι την αραιότητα του αντιστρόφου φίλτρου, προκειμένου να παραχθούν αποδοτικές υλοποιήσεις. Θεωρώντας τον μη γραμμικό ισοσταθμιστή ανατροφοδότησης-απόφασης, έχει δειχθεί ότι κάτω από συνήθεις υποθέσεις για τους συντελεστές της κρουστικής απόκρισης του καναλιού, το εμπρόσθιο φίλτρο και το φίλτρο ανατροφοδότησης μπορούν να αναπαρασταθούν από αραιά διανύσματα. Για τον σκοπό αυτό, τεχνικές Συμπιεσμένης Καταγραφής, οι οποίες έχουν χρησιμοποιηθεί κατα κόρον σε προβλήματα ταυτοποίησης συστήματος, μπορούν να βελτιώσουν σε μεγάλο βαθμό την απόδοση κλασσικών ισοσταθμιστών που δεν λαμβάνουν υπόψιν τους την αραιότητα των διανυσμάτων. Έχοντας ως βάση τις τεχνικές basis pursuit και matching pursuit, αναπτύχθηκαν νέα σχήματα ισοσταθμιστών τα οποία παρουσιάζουν αξιοσημείωτη μείωση στο υπολογιστικό κόστος. Επίσης, αντίθετα με τη συνήθη πρακτική ταυτοποίησης συστήματος, αναπτύχθηκε νέος ευριστικό αλγόριθμος για το πρόβλημα αραιής προσαρμοστικής ισοστάθμισης, με την ονομασία Stochastic Gradient Pursuit. Επιπλέον, ο αλγόριθμος αυτός επεκτάθηκε και για την περίπτωση όπου ο αριθμός των μη μηδενικών στοιχείων του ισοσταθμιστή είναι άγνωστος. Μία διαφορετική προσέγγιση για την αντιμετώπιση του φαινομένου της διασυμβολικής παρεμβολής είναι μέσω του συστήματος orthogonal frequency-division multiplexing (OFDM), όπου το συνολικό κανάλι χωρίζεται σε πολλά στενά υπο-κανάλια, με τέτοιον τρόπο ώστε τα μεταδιδόμενα σήματα να είναι ορθογώνια μεταξύ τους, παρότι παρουσιάζουν φασματική επικάλυψη. Ωστόσο, σε χρονικά και συχνοτικά επιλεκτικά κανάλια, το φαινόμενο Doppler καταστρέφει την ορθογωνιότητα των υπο-καναλιών. Σε αυτήν την περίπτωση, παρόμοια με το φαινόμενο της διασυμβολικής παρεμβολής, εμφανίζεται το φαινόμενο της διακαναλικής παρεμβολής, όπου τα σύμβολα που ανήκουν σε διαφορετικά υπο-κανάλια παρεμβάλουν στο τρέχον. Θεωρώντας αυτό το πρόβλημα, αναπτύχθηκαν νέα σχήματα ισοστάθμισης που ακυρώνουν διαδοχικά την παρεμβολή αυτή, παρέχοντας έναν συμβιβασμό μεταξύ της απόδοσης και της πολυπλοκότητας. Στις περιπτώσεις όπου το φαινόμενο Doppler δεν είναι τόσο ισχυρό, η συνήθης τακτική είναι η προσέγγιση του πίνακα του καναλιού με έναν πίνακα ζώνης. Με αυτό το σκεπτικό, αναπτύχθηκαν αλγόριθμοι μειωμένης τάξης που βασίζονται στην επαναληπτική μέθοδο preconditioned conjugate gradient (PCG), προκειμένου να εκτιμήσουμε τον πίνακα ισοστάθμισης με έναν μειωμένο αριθμό επαναλήψεων. Επίσης, αναπτύχθηκαν τεχνικές που βασίζονται σε προβολές Galerkin για την βελτίωση της απόδοσης των συστημάτων χωρίς να αυξάνουν σημαντικά την πολυπλοκότητα. Ωστόσο, για τις περιπτώσεις όπου το φαινόμενο Doppler έχει ισχυρή επίδραση στο δέκτη του τηλεπικοινωνιακού συστήματος, όπως στις περιπτώσεις πολύ δυναμικών καναλιών, τότε η προσέγγιση με τον πίνακα ζώνης μειώνει σημαντικά την απόδοση του συστήματος. Με στόχο να ανακτήσουμε την απώλεια αυτή, αναπτύχθηκαν τεχνικές κανονικοποιημένης εκτίμησης, με γραμμική πολυπλοκότητα σε σχέση με τον αριθμό των υπο-καναλιών. Επιπρόσθετα, αναπτύχθηκε ένα νέο σχήμα ισοστάθμισης που έχει την δυνατότητα να ακυρώσει πλήρως την διακαναλική παρεμβολή. Το συγκεκριμένο σχήμα λειτουργεί βασιζόμενο σε έναν αριθμό διαδοχικών σταδίων, ακολουθώντας την φιλοσοφία της αρχιτεκτονικής fully-connected ordered successive interference cancellation (OSIC), με στόχο να μειώσει την εναπομείναντα παρεμβολή σε κάθε στάδιο του ισοσταθμιστή Η απόδοση ενός τηλεπικοινωνιακού συστήματος μπορεί επίσης να βελτιωθεί με την χρήση τεχνικών ποικιλομορφίας, δηλαδή με την μετάδοση των συμβόλων μέσω πολλών ανεξάρτητων μονοπατιών. Μία τεχνική ποικιλομορφίας είναι η συνεργατική μετάδοση, όπου μία ομάδα κοντινών τερματικών (relays) σχηματίζουν μία εικονική συστοιχία κεραιών και τεχνικές διαμόρφωσης λοβού μετάδοσης χρησιμοποιούνται προκειμένου να βελτιστοποιηθεί η επικοινωνία μέσω των τερματικών. Οι συγκεκριμένες τεχνικές διαμόρφωσης λοβού μετάδοσης, διαφέρουν από τις κλασσικές όπου η συστοιχία κεραιών βρίσκεται τοποθετημένη σε έναν κόμβο, καθώς τα τερματικά κατανέμονται στον χώρο. Υπό αυτές τις συνθήκες, αναπτύχθηκαν κατανεμημένοι αλγόριθμοι οι οποίοι εκμεταλλεύονται την επικοινωνία και τις υπολογιστικές δυνατότητες των τερματικών για τον υπολογισμό των συνιστωσών του διανύσματος διαμόρφωσης λοβού μετάδοσης. Κάθε τερματικό εκτιμά μόνο την αντίστοιχη συνιστώσα από το κύριο ιδιοδιάνυσμα, συνδιάζοντας δεδομένα από τα γειτονικά τερματικά. Οι προτεινόμενοι αλγόριθμοι εφαρμόστηκαν σε δύο σχήματα κατανεμημένης μετάδοσης μέσω ενδιάμεσων κόμβων. Στο πρώτο σχήμα, τα βάρη του διανύσματος διαμόρφωσης λοβού μετάδοσης υπολογίστηκαν με βάση την ελαχιστοποίηση της συνολικής ισχύος μετάδοσης υπό τον περιορισμό συγκεκριμένου κατωφλίου για την ποιότητα του λαμβανόμενου σήματος. Στο δεύτερο σχήμα, υπολογίστηκαν μεγιστοποιώντας την ποιότητα του λαμβανόμενου σήματος υπό τον περιορισμό ενός κατωφλίου για την συνολική ισχύ μετάδοσης. Επιπλέον, οι αλγόριθμοι που αναπτύχθηκαν λειτουργούν τυφλά, δηλαδή χωρίς φάση εκπαίδευσης, και προσαρμοστικά με μικρό διάστημα σύγκλισης.