61 |
Optimization in multi-relay wireless networksNguyen, Huu Ngoc Duy 08 June 2009 (has links)
The concept of cooperation in communications has drawn a lot of research attention in recent years due to its potential to improve the efficiency of wireless networks. This new form of communications allows some users to act as relays
and assist the transmission of other users' information signals. The aim of this thesis is to apply optimization techniques in the design of multi-relay wireless networks employing cooperative communications. In general, the thesis is organized into two parts: ``Distributed space-time coding' (DSTC) and ``Distributed beamforming', which cover two main approaches in cooperative communications over multi-relay networks.
<br><br>
In Part I of the thesis, various aspects of distributed implementation of space-time coding in a wireless relay network are treated. First, the thesis proposes a new fully-diverse distributed code which allows noncoherent reception at the destination. Second, the problem of coordinating the power allocation (PA) between source and relays to achieve the optimal performance of DSTC is studied and a novel PA scheme is developed. It is shown that the proposed PA scheme can obtain the maximum diversity order of DSTC and significantly outperform other suboptimal PA schemes. Third, the thesis presents the optimal PA scheme to minimize the mean-square error (MSE) in channel estimation during training phase of DSTC. The effect of imperfect channel estimation to the performance of DSTC is also thoroughly studied.
<br><br>
In Part II of the thesis, optimal distributed beamforming designs are developed for a wireless multiuser multi-relay network. Two design criteria for the optimal distributed beamforming at the relays are considered: (i) minimizing the total relay power subject to a guaranteed Quality of Service (QoS) measured in terms of signal-to-noise-ratio (SNR) at the destinations, and (ii) jointly maximizing the SNR margin at the destinations subject to power constraints at the relays. Based on convex optimization techniques,
it is shown that these problems can be formulated and solved via second-order conic programming (SOCP). In addition, this part also proposes simple and fast iterative algorithms to directly solve these optimization problems.
|
62 |
A New Active Constellation Extension Scheme for PAPR Reduction in OFDM SystemsHuang, Bo-Rong 23 August 2011 (has links)
High peak-to-average power ratio (PAPR) is a serious drawback in orthogonal frequency division multiplexing (OFDM) systems. Various methods have been proposed to reduce PAPR, active constellation extension (ACE) scheme has excellent performance. There are two schemes were proposed in traditional ACE, the one of which is ACE-Smart Gradient-Project (SGP) which can significantly reduce PAPR through first iteration. In fact, optimal solution is not obtained in ACE-SGP, we find the scheme can be formulated as convex optimization problem, that is, we can find out optimal solution to minimize PAPR by convex optimization algorithm. Two proposed schemes are based on two low complexity schemes, respectively, and they were proved to satisfy convex optimization problem. Although the power of transmission and complexity of optimization algorithm in the proposed schemes are higher than that of the traditional ACE-SGP scheme, but proposed schemes has proper improvement in PAPR reduction.
|
63 |
Spectrum Sharing in Cognitive Radio Systems Under Outage Probablility ConstraintCai, Pei Li 2009 December 1900 (has links)
For traditional wireless communication systems, static spectrum allocation is
the major spectrum allocation methodology. However, according to the recent investigations
by the FCC, this has led to more than 70 percent of the allocated spectrum in the
United States being under-utilized. Cognitive radio (CR) technology, which supports
opportunistic spectrum sharing, is one idea that is proposed to improve the overall
utilization efficiency of the radio spectrum.
In this thesis we consider a CR communication system based on spectrum sharing
schemes, where we have a secondary user (SU) link with multiple transmitting antennas
and a single receiving antenna, coexisting with a primary user (PU) link with
a single receiving antenna. At the SU transmitter (SU-Tx), the channel state information
(CSI) of the SU link is assumed to be perfectly known; while the interference
channel from the SU-Tx to the PU receiver (PU-Rx) is not perfectly known due to
less cooperation between the SU and the PU. As such, the SU-Tx is only assumed to
know that the interference channel gain can take values from a finite set with certain
probabilities. Considering a SU transmit power constraint, our design objective is to
determine the transmit covariance matrix that maximizes the SU rate, while we protect
the PU by enforcing both a PU average interference constraint and a PU outage
probability constraint. This problem is first formulated as a non-convex optimization
problem with a non-explicit probabilistic constraint, which is then approximated as
a mixed binary integer programming (MBIP) problem and solved with the Branch and Bound (BB) algorithm. The complexity of the BB algorithm is analyzed and numerical
results are presented to validate the eff ectiveness of the proposed algorithm.
A key result proved in this thesis is that the rank of the optimal transmit covariance
matrix is one, i.e., CR beamforming is optimal under PU outage constraints.
Finally, a heuristic algorithm is proposed to provide a suboptimal solution to our
MBIP problem by efficiently (in polynomial time) solving a particularly-constructed
convex problem.
|
64 |
Applications of accuracy certificates for problems with convex structureCox, Bruce 21 February 2011 (has links)
Applications of accuracy certificates for problems with convex structure This dissertation addresses the efficient generation and potential applications of accuracy certificates in the framework of “black-box-represented” convex optimization problems - convex problems where the objective and the constraints are represented by “black boxes” which, given on input a value x of the argument, somehow (perhaps in a fashion unknown to the user) provide on output the values and the derivatives of the objective and the constraints at x. The main body of the dissertation can be split into three parts. In the first part, we provide our background --- state of the art of the theory of accuracy certificates for black-box-represented convex optimization. In the second part, we extend the toolbox of black-box-oriented convex optimization algorithms with accuracy certificates by equipping with these certificates a state-of-the-art algorithm for large-scale nonsmooth black-box-represented problems with convex structure, specifically, the Non-Euclidean Restricted Memory Level (NERML) method. In the third part, we present several novel academic applications of accuracy certificates. The dissertation is organized as follows: In Chapter 1, we motivate our research goals and present a detailed summary of our results. In Chapter 2, we outline the relevant background, specifically, describe four generic black-box-represented generic problems with convex structure (Convex Minimization, Convex-Concave Saddle Point, Convex Nash Equilibrium, and Variational Inequality with Monotone Operator), and outline the existing theory of accuracy certificates for these problems. In Chapter 3, we develop techniques for equipping with on-line accuracy certificates the state-of-the-art NERML algorithm for large-scale nonsmooth problems with convex structure, both in the cases when the domain of the problem is a simple solid and in the case when the domain is given by Separation oracle. In Chapter 4, we develop several novel academic applications of accuracy certificates, primarily to (a) efficient certifying emptiness of the intersection of finitely many solids given by Separation oracles, and (b) building efficient algorithms for convex minimization over solids given by Linear Optimization oracles (both precise and approximate). In Chapter 5, we apply accuracy certificates to efficient decomposition of “well structured” convex-concave saddle point problems, with applications to computationally attractive decomposition of a large-scale LP program with the constraint matrix which becomes block-diagonal after eliminating a relatively small number of possibly dense columns (corresponding to “linking variables”) and possibly dense rows (corresponding to “linking constraints”).
|
65 |
Machine Vision and Autonomous Integration Into an Unmanned Aircraft SystemVan Horne, Chris 10 1900 (has links)
ITC/USA 2013 Conference Proceedings / The Forty-Ninth Annual International Telemetering Conference and Technical Exhibition / October 21-24, 2013 / Bally's Hotel & Convention Center, Las Vegas, NV / The University of Arizona's Aerial Robotics Club (ARC) sponsors the development of an unmanned aerial vehicle (UAV) able to compete in the annual Association for Unmanned Vehicle Systems International (AUVSI) Seafarer Chapter Student Unmanned Aerial Systems competition. Modern programming frameworks are utilized to develop a robust distributed imagery and telemetry pipeline as a backend for a mission operator user interface. This paper discusses the design changes made for the 2013 AUVSI competition including integrating low-latency first-person view, updates to the distributed task backend, and incremental and asynchronous updates the operator's user interface for real-time data analysis.
|
66 |
Unifying Low-Rank Models for Visual LearningCabral, Ricardo da Silveira 01 February 2015 (has links)
Many problems in signal processing, machine learning and computer vision can be solved by learning low rank models from data. In computer vision, problems such as rigid structure from motion have been formulated as an optimization over subspaces with fixed rank. These hard-rank constraints have traditionally been imposed by a factorization that parameterizes subspaces as a product of two matrices of fixed rank. Whilst factorization approaches lead to efficient and kernelizable optimization algorithms, they have been shown to be NP-Hard in presence of missing data. Inspired by recent work in compressed sensing, hard-rank constraints have been replaced by soft-rank constraints, such as the nuclear norm regularizer. Vis-a-vis hard-rank approaches, soft-rank models are convex even in presence of missing data: but how is convex optimization solving a NP-Hard problem? This thesis addresses this question by analyzing the relationship between hard and soft rank constraints in the unsupervised factorization with missing data problem. Moreover, we extend soft rank models to weakly supervised and fully supervised learning problems in computer vision. There are four main contributions of our work: (1) The analysis of a new unified low-rank model for matrix factorization with missing data. Our model subsumes soft and hard-rank approaches and merges advantages from previous formulations, such as efficient algorithms and kernelization. It also provides justifications on the choice of algorithms and regions that guarantee convergence to global minima. (2) A deterministic \rank continuation" strategy for the NP-hard unsupervised factorization with missing data problem, that is highly competitive with the state-of-the-art and often achieves globally optimal solutions. In preliminary work, we show that this optimization strategy is applicable to other NP-hard problems which are typically relaxed to convex semidentite programs (e.g., MAX-CUT, quadratic assignment problem). (3) A new soft-rank fully supervised robust regression model. This convex model is able to deal with noise, outliers and missing data in the input variables. (4) A new soft-rank model for weakly supervised image classification and localization. Unlike existing multiple-instance approaches for this problem, our model is convex.
|
67 |
Structured sparsity-inducing norms : statistical and algorithmic properties with applications to neuroimagingJenatton, Rodolphe 24 November 2011 (has links) (PDF)
Numerous fields of applied sciences and industries have been recently witnessing a process of digitisation. This trend has come with an increase in the amount digital data whose processing becomes a challenging task. In this context, parsimony, also known as sparsity, has emerged as a key concept in machine learning and signal processing. It is indeed appealing to exploit data only via a reduced number of parameters. This thesis focuses on a particular and more recent form of sparsity, referred to as structured sparsity. As its name indicates, we shall consider situations where we are not only interested in sparsity, but where some structural prior knowledge is also available. The goal of this thesis is to analyze the concept of structured sparsity, based on statistical, algorithmic and applied considerations. To begin with, we introduce a family of structured sparsity-inducing norms whose statistical aspects are closely studied. In particular, we show what type of prior knowledge they correspond to. We then turn to sparse structured dictionary learning, where we use the previous norms within the framework of matrix factorization. From an optimization viewpoint, we derive several efficient and scalable algorithmic tools, such as working-set strategies and proximal-gradient techniques. With these methods in place, we illustrate on numerous real-world applications from various fields, when and why structured sparsity is useful. This includes, for instance, restoration tasks in image processing, the modelling of text documents as hierarchy of topics, the inter-subject prediction of sizes of objects from fMRI signals, and background-subtraction problems in computer vision.
|
68 |
Sparse coding for machine learning, image processing and computer visionMairal, Julien 30 November 2010 (has links) (PDF)
We study in this thesis a particular machine learning approach to represent signals that that consists of modelling data as linear combinations of a few elements from a learned dictionary. It can be viewed as an extension of the classical wavelet framework, whose goal is to design such dictionaries (often orthonormal basis) that are adapted to natural signals. An important success of dictionary learning methods has been their ability to model natural image patches and the performance of image denoising algorithms that it has yielded. We address several open questions related to this framework: How to efficiently optimize the dictionary? How can the model be enriched by adding a structure to the dictionary? Can current image processing tools based on this method be further improved? How should one learn the dictionary when it is used for a different task than signal reconstruction? How can it be used for solving computer vision problems? We answer these questions with a multidisciplinarity approach, using tools from statistical machine learning, convex and stochastic optimization, image and signal processing, computer vision, but also optimization on graphs.
|
69 |
Distance Measurement-Based Cooperative Source Localization: A Convex Range-Free ApproachKiraz, Fatma January 2013 (has links)
One of the most essential objectives in WSNs is to determine the spatial coordinates
of a source or a sensor node having information. In this study, the problem of range
measurement-based localization of a signal source or a sensor is revisited. The main challenge of the problem results from the non-convexity associated with range measurements
calculated using the distances from the set of nodes with known positions to a xed sen-
sor node. Such measurements corresponding to certain distances are non-convex in two
and three dimensions. Attempts recently proposed in the literature to eliminate the non-
convexity approach the problem as a non-convex geometric minimization problem, using
techniques to handle the non-convexity.
This study proposes a new fuzzy range-free sensor localization method. The method
suggests using some notions of Euclidean geometry to convert the problem into a convex
geometric problem. The convex equivalent problem is built using convex fuzzy sets, thus
avoiding multiple stable local minima issues, then a gradient based localization algorithm
is chosen to solve the problem.
Next, the proposed algorithm is simulated considering various scenarios, including the
number of available source nodes, fuzzi cation level, and area coverage. The results are
compared with an algorithm having similar fuzzy logic settings. Also, the behaviour of
both algorithms with noisy measurements are discussed. Finally, future extensions of the
algorithm are suggested, along with some guidelines.
|
70 |
Accelerating Convergence of Large-scale Optimization AlgorithmsGhadimi, Euhanna January 2015 (has links)
Several recent engineering applications in multi-agent systems, communication networks, and machine learning deal with decision problems that can be formulated as optimization problems. For many of these problems, new constraints limit the usefulness of traditional optimization algorithms. In some cases, the problem size is much larger than what can be conveniently dealt with using standard solvers. In other cases, the problems have to be solved in a distributed manner by several decision-makers with limited computational and communication resources. By exploiting problem structure, however, it is possible to design computationally efficient algorithms that satisfy the implementation requirements of these emerging applications. In this thesis, we study a variety of techniques for improving the convergence times of optimization algorithms for large-scale systems. In the first part of the thesis, we focus on multi-step first-order methods. These methods add memory to the classical gradient method and account for past iterates when computing the next one. The result is a computationally lightweight acceleration technique that can yield significant improvements over gradient descent. In particular, we focus on the Heavy-ball method introduced by Polyak. Previous studies have quantified the performance improvements over the gradient through a local convergence analysis of twice continuously differentiable objective functions. However, the convergence properties of the method on more general convex cost functions has not been known. The first contribution of this thesis is a global convergence analysis of the Heavy- ball method for a variety of convex problems whose objective functions are strongly convex and have Lipschitz continuous gradient. The second contribution is to tailor the Heavy- ball method to network optimization problems. In such problems, a collection of decision- makers collaborate to find the decision vector that minimizes the total system cost. We derive the optimal step-sizes for the Heavy-ball method in this scenario, and show how the optimal convergence times depend on the individual cost functions and the structure of the underlying interaction graph. We present three engineering applications where our algorithm significantly outperform the tailor-made state-of-the-art algorithms. In the second part of the thesis, we consider the Alternating Direction Method of Multipliers (ADMM), an alternative powerful method for solving structured optimization problems. The method has recently attracted a large interest from several engineering communities. Despite its popularity, its optimal parameters have been unknown. The third contribution of this thesis is to derive optimal parameters for the ADMM algorithm when applied to quadratic programming problems. Our derivations quantify how the Hessian of the cost functions and constraint matrices affect the convergence times. By exploiting this information, we develop a preconditioning technique that allows to accelerate the performance even further. Numerical studies of model-predictive control problems illustrate significant performance benefits of a well-tuned ADMM algorithm. The fourth and final contribution of the thesis is to extend our results on optimal scaling and parameter tuning of the ADMM method to a distributed setting. We derive optimal algorithm parameters and suggest heuristic methods that can be executed by individual agents using local information. The resulting algorithm is applied to distributed averaging problem and shown to yield substantial performance improvements over the state-of-the-art algorithms. / <p>QC 20150327</p>
|
Page generated in 0.0789 seconds