In this thesis, we consider an analog antenna combining architecture for a MIMO wireless transceiver, while pointing out its advantages with respect to the traditional MIMO architectures. In the first part of this work, we focus on the transceiver design, especially the calculation of the beamformers that must be applied at the RF. This analysis is performed in an OFDM system under different assumptions on the channel state information. As a result, several criteria and algorithms for the selection of the beamformers are proposed. In the second part, we address the FPGA design and implementation of a baseband processor for this architecture. This baseband processor is based on the standard IEEE 802.11a. Finally, some real-time tests of the implemented baseband processor are carried out both in stand-alone configuration and also with the whole physical layer setup. / En esta tesis consideramos una arquitectura de combinación analógica de antenas para una estación inalámbrica MIMO, señalando las ventajas de ésta con respecto a la arquitectura tradicional MIMO. En la primera parte de este trabajo analizamos el cálculo de los pesos que se deben aplicar en RF. Este análisis es realizado para un sistema OFDM bajo diferentes suposiciones sobre el conocimiento del canal en el transmisor. Como resultado, se ofrecen varios criterios y algoritmos para el cálculo de los pesos. La segunda parte se centra en el diseño y la implementación FPGA de un procesador banda base para esta arquitectura. Este procesador está basando en el estándar IEEE 802.11a. Finalmente se llevan a cabo algunos experimentos en tiempo-real del procesador banda base. Estos experimentos se han realizado tanto con el procesador aislado como integrado en el resto de la capa física del sistema.

Lagrangian relaxation is a successful solution approach for many combinatorial optimisation problems, one of them being the train timetabling problem (TTP). We model this problem using time expanded networks for the single train schedules and coupling constraints to enforce restrictions like station capacities and headway times. Lagrangian relaxation of these coupling constraints leads to shortest path subproblems in the time expanded networks and is solved using a proximal bundle method. However, large instances of our practical partner Deutsche Bahn lead to computationally intractable models. In this thesis we develop two new algorithmic techniques to improve the solution process for this kind of optimisation problems. The first new technique, Dynamic Graph Generation (DGG), aims at improving the computation of the shortest path subproblems in large time expanded networks. Without sacrificing any accuracy, DGG allows to store only small parts of the networks and to dynamically extend them whenever the stored part proves to be too small. This is possible by exploiting the properties of the objective function in many scheduling applications to prefer early paths or due times, respectively. We prove that DGG can be implemented very efficiently and its running time and the size of nodes that have to be stored additionally does not depend on the size of the time expanded network but only on the length of the train routes. The second technique is an asynchronous and parallel bundle method (APBM). Traditional bundle methods require one solution of each subproblem in each iteration. However, many practical applications, e.g. the TTP, consist of rather loosely coupled subproblems. The APBM chooses only small subspaces corresponding to the Lagrange multipliers of strongly violated coupling constraints and optimises only these variables while keeping all other variables fixed. Several subspaces of disjoint variables may be chosen simultaneously and are optimised in parallel. The solutions of the subspace problem are incorporated into the global data as soon as it is available without any synchronisation mechanism. However, in order to guarantee convergence, the algorithm detects automatically dependencies between different subspaces and respects these dependencies in future subspace selections. We prove the convergence of the APBM under reasonable assumptions for both, the dual and associated primal aggregate data. The APBM is then further extended to problems with unknown dependencies between subproblems and constraints in the Lagrangian relaxation problem. The algorithm automatically detects these dependencies and respects them in future iterations. Again we prove the convergence of this algorithm under reasonable assumptions. Finally we test our solution approach for the TTP on some real world instances of Deutsche Bahn. Using an iterative rounding heuristic based on the approximate fractional solutions obtained by the Lagrangian relaxation we are able to compute feasible schedules for all trains in a subnetwork of about 10% of the whole German network in about 12 hours. In these timetables 99% of all passenger trains could be scheduled with no significant delay and the travel time of the freight trains could be reduced by about one hour on average.

The research on optimal reinsurance design dated back to the 1960’s. For nearly half a century, the quest for optimal reinsurance designs has remained a fascinating subject, drawing significant interests from both academicians and practitioners. Its fascination lies in its potential as an effective risk management tool for the insurers. There are many ways of formulating the optimal design of reinsurance, depending on the chosen objective and constraints. In this thesis, we address the problem of optimal reinsurance designs from an insurer’s perspective. For an insurer, an appropriate use of the reinsurance helps to reduce the adverse risk exposure and improve the overall viability of the underlying business. On the other hand, reinsurance incurs additional cost to the insurer in the form of reinsurance premium. This implies a classical risk and reward tradeoff faced by the insurer. The primary objective of the thesis is to develop theoretically sound and yet practical solution in the quest for optimal reinsurance designs. In order to achieve such an objective, this thesis is divided into two parts. In the first part, a number of reinsurance models are developed and their optimal reinsurance treaties are derived explicitly. This part focuses on the risk measure minimization reinsurance models and discusses the optimal reinsurance treaties by exploiting two of the most common risk measures known as the Value-at-Risk (VaR) and the Conditional Tail Expectation (CTE). Some additional important economic factors such as the reinsurance premium budget, the insurer’s profitability are also considered. The second part proposes an innovative method in formulating the reinsurance models, which we refer as the empirical approach since it exploits explicitly the insurer’s empirical loss data. The empirical approach has the advantage that it is practical and intuitively appealing. This approach is motivated by the difficulty that the reinsurance models are often infinite dimensional optimization problems and hence the explicit solutions are achievable only in some special cases. The empirical approach effectively reformulates the optimal reinsurance problem into a finite dimensional optimization problem. Furthermore, we demonstrate that the second-order conic programming can be used to obtain the optimal solutions for a wide range of reinsurance models formulated by the empirical approach.

Spectrum sharing is known as a key solution to accommodate the increasing number of users and the growing demand for throughput in wireless networks. While spectrum sharing improves the data rate in sparse networks, it suffers from interference of concurrent links in dense networks. In fact, interference is the primary barrier to enhance the overall throughput of the network, especially in the medium and high signal-to-noise ratios (SNR’s). Managing interference to overcome this barrier has emerged as a crucial step in developing efficient wireless networks. This thesis deals with optimum and sub-optimum interference management-cancelation in non-cooperative networks. Several techniques for interference management including novel strategies such as interference alignment and structural coding are investigated. These methods are applied to obtain optimum and sub-optimum coding strategies in such networks. It is shown that a single strategy is not able to achieve the maximum throughput in all possible scenarios and in fact a careful design is required to fully exploit all available resources in each realization of the system. This thesis begins with a complete investigation of the capacity region of the two-user Gaussian interference channel. This channel models the basic interaction between two users sharing the same spectrum for data communication. New outer bounds outperforming known bounds are derived using Genie-aided techniques. It is proved that these outer bounds meet the known inner bounds in some special cases, revealing the sum capacity of this channel over a certain range of parameters which has not been known in the past. A novel coding scheme applicable in networks with single antenna nodes is proposed next. This scheme converts a single antenna system to an equivalent Multiple Input Multiple Output (MIMO) system with fractional dimensions. Interference can be aligned along these dimensions and higher multiplexing gains can be achieved. Tools from the field of Diophantine approximation in number theory are used to show that the proposed coding scheme in fact mimics the traditional schemes used in MIMO systems where each data stream is sent along a direction and alignment happens when several streams are received along the same direction. Two types of constellation are proposed for the encoding part, namely the single layer constellation and the multi-layer constellation. Using single layer constellations, the coding scheme is applied to the two-user $X$ channel. It is proved that the total Degrees-of-Freedom (DOF), i.e. $\frac{4}{3}$, of the channel is achievable almost surely. This is the first example in which it is shown that a time invariant single antenna system does not fall short of achieving this known upper bound on the DOF. Using multi-layer constellations, the coding scheme is applied to the symmetric three-user GIC. Achievable DOFs are derived for all channel gains. It is observed that the DOF is everywhere discontinuous (as a function of the channel gain). In particular, it is proved that for the irrational channel gains the achievable DOF meets the upper bound of $\frac{3}{2}$. For the rational gains, the achievable DOF has a gap to the known upper bounds. By allowing carry over from multiple layers, however, it is shown that higher DOFs can be achieved for the latter. The $K$-user single-antenna Gaussian Interference Channel (GIC) is considered, where the channel coefficients are NOT necessarily time-variant or frequency selective. It is proved that the total DOF of this channel is $\frac{K}{2}$ almost surely, i.e. each user enjoys half of its maximum DOF. Indeed, we prove that the static time-invariant interference channels are rich enough to allow simultaneous interference alignment at all receivers. To derive this result, we show that single-antenna interference channels can be treated as \emph{pseudo multiple-antenna systems} with infinitely-many antennas. Such machinery enables us to prove that the real or complex $M \times M$ MIMO GIC achieves its total DOF, i.e., $\frac{MK}{2}$, $M \geq 1$. The pseudo multiple-antenna systems are developed based on a recent result in the field of Diophantine approximation which states that the convergence part of the Khintchine-Groshev theorem holds for points on non-degenerate manifolds. As a byproduct of the scheme, the total DOFs of the $K\times M$ $X$ channel and the uplink of cellular systems are derived. Interference alignment requires perfect knowledge of channel state information at all nodes. This requirement is sometimes infeasible and users invoke random coding to communicate with their corresponding receivers. Alternative interference management needs to be implemented and this problem is addressed in the last part of the thesis. A coding scheme for a single user communicating in a shared medium is proposed. Moreover, polynomial time algorithms are proposed to obtain best achievable rates in the system. Successive rate allocation for a $K$-user interference channel is performed using polynomial time algorithms.

The research on optimal reinsurance design dated back to the 1960’s. For nearly half a century, the quest for optimal reinsurance designs has remained a fascinating subject, drawing significant interests from both academicians and practitioners. Its fascination lies in its potential as an effective risk management tool for the insurers. There are many ways of formulating the optimal design of reinsurance, depending on the chosen objective and constraints. In this thesis, we address the problem of optimal reinsurance designs from an insurer’s perspective. For an insurer, an appropriate use of the reinsurance helps to reduce the adverse risk exposure and improve the overall viability of the underlying business. On the other hand, reinsurance incurs additional cost to the insurer in the form of reinsurance premium. This implies a classical risk and reward tradeoff faced by the insurer. The primary objective of the thesis is to develop theoretically sound and yet practical solution in the quest for optimal reinsurance designs. In order to achieve such an objective, this thesis is divided into two parts. In the first part, a number of reinsurance models are developed and their optimal reinsurance treaties are derived explicitly. This part focuses on the risk measure minimization reinsurance models and discusses the optimal reinsurance treaties by exploiting two of the most common risk measures known as the Value-at-Risk (VaR) and the Conditional Tail Expectation (CTE). Some additional important economic factors such as the reinsurance premium budget, the insurer’s profitability are also considered. The second part proposes an innovative method in formulating the reinsurance models, which we refer as the empirical approach since it exploits explicitly the insurer’s empirical loss data. The empirical approach has the advantage that it is practical and intuitively appealing. This approach is motivated by the difficulty that the reinsurance models are often infinite dimensional optimization problems and hence the explicit solutions are achievable only in some special cases. The empirical approach effectively reformulates the optimal reinsurance problem into a finite dimensional optimization problem. Furthermore, we demonstrate that the second-order conic programming can be used to obtain the optimal solutions for a wide range of reinsurance models formulated by the empirical approach.

Spectrum sharing is known as a key solution to accommodate the increasing number of users and the growing demand for throughput in wireless networks. While spectrum sharing improves the data rate in sparse networks, it suffers from interference of concurrent links in dense networks. In fact, interference is the primary barrier to enhance the overall throughput of the network, especially in the medium and high signal-to-noise ratios (SNR’s). Managing interference to overcome this barrier has emerged as a crucial step in developing efficient wireless networks. This thesis deals with optimum and sub-optimum interference management-cancelation in non-cooperative networks. Several techniques for interference management including novel strategies such as interference alignment and structural coding are investigated. These methods are applied to obtain optimum and sub-optimum coding strategies in such networks. It is shown that a single strategy is not able to achieve the maximum throughput in all possible scenarios and in fact a careful design is required to fully exploit all available resources in each realization of the system. This thesis begins with a complete investigation of the capacity region of the two-user Gaussian interference channel. This channel models the basic interaction between two users sharing the same spectrum for data communication. New outer bounds outperforming known bounds are derived using Genie-aided techniques. It is proved that these outer bounds meet the known inner bounds in some special cases, revealing the sum capacity of this channel over a certain range of parameters which has not been known in the past. A novel coding scheme applicable in networks with single antenna nodes is proposed next. This scheme converts a single antenna system to an equivalent Multiple Input Multiple Output (MIMO) system with fractional dimensions. Interference can be aligned along these dimensions and higher multiplexing gains can be achieved. Tools from the field of Diophantine approximation in number theory are used to show that the proposed coding scheme in fact mimics the traditional schemes used in MIMO systems where each data stream is sent along a direction and alignment happens when several streams are received along the same direction. Two types of constellation are proposed for the encoding part, namely the single layer constellation and the multi-layer constellation. Using single layer constellations, the coding scheme is applied to the two-user $X$ channel. It is proved that the total Degrees-of-Freedom (DOF), i.e. $\frac{4}{3}$, of the channel is achievable almost surely. This is the first example in which it is shown that a time invariant single antenna system does not fall short of achieving this known upper bound on the DOF. Using multi-layer constellations, the coding scheme is applied to the symmetric three-user GIC. Achievable DOFs are derived for all channel gains. It is observed that the DOF is everywhere discontinuous (as a function of the channel gain). In particular, it is proved that for the irrational channel gains the achievable DOF meets the upper bound of $\frac{3}{2}$. For the rational gains, the achievable DOF has a gap to the known upper bounds. By allowing carry over from multiple layers, however, it is shown that higher DOFs can be achieved for the latter. The $K$-user single-antenna Gaussian Interference Channel (GIC) is considered, where the channel coefficients are NOT necessarily time-variant or frequency selective. It is proved that the total DOF of this channel is $\frac{K}{2}$ almost surely, i.e. each user enjoys half of its maximum DOF. Indeed, we prove that the static time-invariant interference channels are rich enough to allow simultaneous interference alignment at all receivers. To derive this result, we show that single-antenna interference channels can be treated as \emph{pseudo multiple-antenna systems} with infinitely-many antennas. Such machinery enables us to prove that the real or complex $M \times M$ MIMO GIC achieves its total DOF, i.e., $\frac{MK}{2}$, $M \geq 1$. The pseudo multiple-antenna systems are developed based on a recent result in the field of Diophantine approximation which states that the convergence part of the Khintchine-Groshev theorem holds for points on non-degenerate manifolds. As a byproduct of the scheme, the total DOFs of the $K\times M$ $X$ channel and the uplink of cellular systems are derived. Interference alignment requires perfect knowledge of channel state information at all nodes. This requirement is sometimes infeasible and users invoke random coding to communicate with their corresponding receivers. Alternative interference management needs to be implemented and this problem is addressed in the last part of the thesis. A coding scheme for a single user communicating in a shared medium is proposed. Moreover, polynomial time algorithms are proposed to obtain best achievable rates in the system. Successive rate allocation for a $K$-user interference channel is performed using polynomial time algorithms.

In this thesis, we consider a vector Gaussian multiple access channel (MAC) with users demanding reliable communication at specific (Shannon-theoretic) rates. The objective is to assign vectors and powers to these users such that their rate requirements are met and the sum of powers received is minimum. We identify this power minimization problem as an instance of a separable convex optimization problem with linear ascending constraints. Under an ordering condition on the slopes of the functions at the origin, an algorithm that determines the optimum point in a finite number of steps is described. This provides a complete characterization of the minimum sum power for the vector Gaussian multiple access channel. Furthermore, we prove a strong duality between the above sum power minimization problem and the problem of sum rate maximization under power constraints. We then propose finite step algorithms to explicitly identify an assignment of vectors and powers that solve the above power minimization and sum rate maximization problems. The distinguishing feature of the proposed algorithms is the size of the output vector sets. In particular, we prove an upper bound on the size of the vector sets that is independent of the number of users. Finally, we restrict vectors to an orthonormal set. The goal is to identify an assignment of vectors (from an orthonormal set) to users such that the user rate requirements is met with minimum sum power. This is a combinatorial optimization problem. We study the complexity of the decision version of this problem. Our results indicate that when the dimensionality of the vector set is part of the input, the decision version is NP-complete.

No description available.

Statistical machine learning is a branch of mathematics concerned with developing algorithms for data analysis. This thesis presents new mathematical models and statistical software, and is organized into two parts. In the first part, I present several new algorithms for clustering and segmentation. Clustering and segmentation are a class of techniques that attempt to find structures in data. I discuss the following contributions, with a focus on applications to cancer data from bioinformatics. In the second part, I focus on statistical software contributions which are practical for use in everyday data analysis.

Magnetic Resonance Imaging (MRI) is an important diagnostic tool for imaging soft tissue without the use of ionizing radiation. Moreover, through advanced signal processing, MRI can provide more than just anatomical information, such as estimates of tissue-specific physical properties. Signal processing lies at the very core of the MRI process, which involves input design, information encoding, image reconstruction, and advanced filtering. Based on signal modeling and estimation, it is possible to further improve the images, reduce artifacts, mitigate noise, and obtain quantitative tissue information. In quantitative MRI, different physical quantities are estimated from a set of collected images. The optimization problems solved are typically nonlinear, and require intelligent and application-specific algorithms to avoid suboptimal local minima. This thesis presents several methods for efficiently solving different parameter estimation problems in MRI, such as multi-component T2 relaxometry, temporal phase correction of complex-valued data, and minimizing banding artifacts due to field inhomogeneity. The performance of the proposed algorithms is evaluated using both simulation and in-vivo data. The results show improvements over previous approaches, while maintaining a relatively low computational complexity. Using new and improved estimation methods enables better tissue characterization and diagnosis. Furthermore, a sequence design problem is treated, where the radio-frequency excitation is optimized to minimize image artifacts when using amplifiers of limited quality. In turn, obtaining higher fidelity images enables improved diagnosis, and can increase the estimation accuracy in quantitative MRI.