In some applied areas such as the Global Positioning System (GPS) and communications, etc., there is a linear model y = Ax + v, where the unknown parameter vector x is an integer vector and the noise vector v follows a normal distribution N(0, sigma^2 I). The typical methods for estimating x are the integer rounding (IR), the Babai nearest plane (BNP), and the integer least squares (ILS) methods. While IR and BNP are polynomial-time methods, the ILS method solves an NP-hard problem. The most effective approach to validating an integer estimator is to find its success rate, which is the probability of correct integer estimation. It has been found in the literature that the ILS estimator is optimal among all admissible integer estimators, including the IR and BNP estimators, as it maximizes the success rate. In communications applications, the integer parameter vector x is often constrained to a box. In this thesis, we first extend the concept of success rates to box-constrained versions of IR (BIR), BNP (BBNP), and ILS (BILS). We then extend some results for the success rates of the corresponding unconstrained estimators to these box-constrained estimators. In addition, we apply the success rate results to improve the efficiency of the BILS estimation process. If some entries of the integer estimator obtained by BBNP have high success rates, then we can fix these entries and solve a smaller BILS problem. This may reduce the overall computational time. Numerical simulations results are presented to support our findings. / Dans certains domaines appliqués comme la navigation utilisant le système mondial de positionnement (GPS) et comme les communications, il y a un modèle linéaire, y = Ax+v, où x est un vecteur de paramètres entiers à estimer et v est un vecteur contenant le bruit et suivant une loi normale N(0, sigma^2 I). Les méthodes typiques pour estimer x sont l'algorithme d'arrondissement à l'entier le plus proche (IR), l'algorithme de l'hyperplan le plus proche de Babai (BNP) et l'algorithme des moindres carrés en nombres entiers (ILS). Tandis que les algorithmes IR et BNP sont polynomiaux, la méthode ILS résout un problème NP-difficile. L'approche la plus efficace pour valider un estimateur entier est de trouver son taux de réussite, qui est la probabilité de trouver la bonne estimation pour le vecteur de paramètres. Dans la littérature, il s'avère que l'estimateur ILS est optimal parmi les estimateurs admissibles, y compris les estimateurs IR et BNP, car il maximise le taux de réussite. Dans les applications de communication, le vecteur de paramètres est souvent contraint à une boîte. Dans cette thèse, nous développons le concept de taux de réussite pour les méthodes d'estimation avec contraintes de boîtes (les méthodes BIR, BBNP et BILS). Nous présentons aussi quelques résultats pour les taux de réussite de ces estimateurs contraints à boîtes. De plus, nous appliquons ces résultats afin d'améliorer l'efficacité de l'algorithme BILS. Si certaines entrées du vecteur obtenu par BILS ont des taux de réussite élevés, nous pouvons les utiliser et résoudre un problème BILS de dimensions réduites. Cela peut réduire le temps de calcul. Des résultats de simulations sont présentés à l'appui de nos conclusions.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.110510 |
| Date | January 2012 |
| Creators | Hanssian, Sevan |
| Contributors | Xiao-Wen Chang (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0019 seconds