Integer least squares (ILS) problems arise from many applications, such as communications, lattice design, and global navigation satellite systems. However, an ILS problem is NP-hard. The objective of this thesis is to design efficient algorithms for solving box-constrained overdetermined integer least squares (BOILS) problems and box-constrained underdetermined integer least squares (BUILS) problems. A typical method to solve ILS problems consists of two stages: reduction and search. For solving the BOILS problems, we propose a new reduction algorithm and a modified search algorithm. Unlike the usual reduction algorithms which only reorder the columns of the lattice generator matrix, the new reduction algorithm also employs the integer Gauss transformations during the reordering process. Simulation results show that our new method makes the search process perform more efficiently than existing algorithms. For solving the BUILS problems, we present three algorithms: recursive generalized sphere decoding (GSD) algorithm, partial regularization algorithm, and tree search decoder. The main part of the recursive GSD algorithm recursively partitions the candidate set for the unknown integer vector into disjoint ordered subsets. The main idea of the partial regularization algorithm is to transform a BUILS problem to an equivalent BOILS problem by using part of the unknown integer vector to do the regularization. Some strategies are proposed to enhance the efficiency of this algorithm. The tree search decoder uses a depth-first tree search process to solve a BUILS problem. For each of these algorithms, various reduction strategies are proposed, which can significantly reduce the computational cost of the corresponding search process. Simulation results indicate that the recursive GSD algorithm is usually faster than other GSD algorithms in the literature, the partial regularization algorithm is the most efficient one among the existing algorithms for moderately underde / Les problèmes de moindres carrés en nombres entiers apparaissent dans plusieurs domaines, dont les télécommunications, la conception de grilles, et la navigation par système de positionnement mondial. Malheureusement, ces problèmes sont de difficulté NP. Le but de cette thèse est de concevoir des algorithmes efficaces pour la résolution de problèmes de moindres carrés en nombres entiers, soit hyperdéterminés ou hypodéterminés, avec contraintes de boîtes. Les méthodes typiques pour résoudre ces problèmes contiennent deux stages: la réduction et la recherche. Pour les problèmes hyperdéterminés, nous proposons un nouvel algorithme de réduction et un algorithme de recherche modifié. Contrairement aux algorithmes existants, qui ne font que trier les colonnes de la matrice génératrice de grille, notre nouvel algorithme de réduction utilise aussi la transformation de Gauss durant le tri. Nos simulations démontrent que notre nouvelle méthode rend le processus de recherche plus rapide. Pour les problèmes hypodéterminés, nous proposons trois nouveaux algorithmes: un algorithme récursif généralisé de décodage par sphère (GDS), un algorithme de régularization partielle (RP), et un algorithme de recherche arborescente (RA). L'algorithme GDS partitionne les solutions réalisables récursvivement en plusieurs ensembles ordonnés et disjoints. L'algorithme RP transforme le problème hypodéterminé en un problème hyperdéterminé équivalent. Nous proposons des stratégies pour rendre cet algorithme plus efficace. L'algorithme RA utilise un processus de recherche en profondeur. Pour chacun de ces trois algorithmes, nous proposons plusieurs stratégies de réduction. Celles-ci peuvent réduire la complexité de l'algorithme de recherche correspondant. Nos simulations démontrent que l'algorithme GDS est habituellement plus rapide que les algorithmes existants, que l'algorithme RP est le plus rapide pour les problèmes peu hypodétermin
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.22038 |
| Date | January 2008 |
| Creators | Yang, Xiaohua |
| Contributors | Christopher Paige (Internal/Cosupervisor2), 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 | Doctor of Philosophy (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.0018 seconds