Nonparametric convex regression has been extensively studied over the last two decades. It has been shown any Lipschitz convex function can be approximated with arbitrarily accuracy with a max of linear functions. Using this framework, in this thesis we generalize convex regression to learning an arbitrary Bregman divergence and learning a difference of convex functions. We provide approximation guarantees and sample complexity bounds for both these extensions. Furthermore, we provide algorithms to solve the resulting optimization problems based on 2-block alternative direction method of multipliers (ADMM). For this algorithm, we provide convergence guarantees with iteration complexity of O(n√d/𝜖) for a dataset X 𝝐 ℝ^n,d and arbitrary positive 𝜖. Finally we provide experiments for both the Bregman divergence learning and difference of convex functions learning based on UCI datasets that demonstrate the state of the art on regression and classification datasets.

Abstract Multiple-input multiple-output transmitted signal design for the partially coherent Rayleigh fading channels with discrete inputs under a given average transmit power constraint is consider in this thesis. The objective is to design the space-time constellations and linear precoders to adapt to the degradation caused by the imperfect channel estimation at the receiver and the transmit-receive antenna correlation. The system is partially coherent so that the multiple-input multiple-output channel coefficients are estimated at the receiver and its error covariance matrix is fed back to the transmitter. Two constellation design criteria, one for the single and another for the multiple transmit antennae are proposed. An upper bound on the average bit error probability for the single transmit antenna and cutoff rate, i.e., a lower bound on the mutual information, for multiple transmit antennae are derived. Both criteria are functions of channel estimation error covariance matrix. The designed constellations are called as partially coherent constellation. Additionally, to use the resulting constellations together with forward error control codes requires efficient bit mapping schemes. Because these constellations lack geometrical symmetry in general, the Gray mapping is not always possible in the majority of the constellations obtained. Moreover, different mapping schemes may lead to highly different bit error rate performances. Thus, an efficient bit mapping algorithm called the modified binary switching algorithm is proposed. It minimizes an upper bound on the average bit error probability. It is shown through computer simulations that the designed partially coherent constellation and their optimized bit mapping algorithm together with turbo codes outperform the conventional constellations. Linear precoder design was also considered as a simpler, suboptimal alternative. The cutoff rate expression is again used as a criterion to design the linear precoder. A linear precoder is obtained by numerically maximizing the cutoff rate with respect to the precoder matrix with a given average transmit power constraint. Furthermore, the precoder matrix is decomposed using singular-value-decomposition into the input shaping, power loading, and beamforming matrices. The beamforming matrix is found to coincide with the eigenvectors of the transmit correlation matrix. The power loading and input shaping matrices are solved numerically using the difference of convex functions programming algorithm and optimization under the unitary constraint, respectively. Computer simulations show that the performance gains of the designed precoders are significant compared to the cutoff rate optimized partially coherent constellations without precoding. / Tiivistelmä Väitöskirjassa tarkastellaan lähetyssignaalien suunnittelua osittain koherenteissa Rayleigh-häipyvissä kanavissa toimiviin monitulo-monilähtöjärjestelmiin (MIMO). Lähettimen keskimääräinen lähetysteho oletetaan rajoitetuksi ja lähetyssignaali diskreetiksi. Tavoitteena on suunnitella tila-aikakonstellaatioita ja lineaarisia esikoodereita jotka mukautuvat epätäydellisen kanavaestimoinnin aiheuttamaan suorituskyvyn heikkenemiseen sekä lähetin- ja vastaanotinantennien väliseen korrelaatioon. Tarkasteltavien järjestelmien osittainen koherenttisuus tarkoittaa sitä, että MIMO-kanavan kanavakertoimet estimoidaan vastaanottimessa, josta niiden virhekovarianssimatriisi lähetetään lähettimelle. Työssä esitetään kaksi konstellaatiosuunnittelukriteeriä, toinen yhdelle lähetinantennille ja toinen moniantennilähettimelle. Molemmat kriteerit ovat kanavan estimaatiovirheen kovarianssimatriisin funktioita. Työssä johdetaan yläraja keskimääräiselle bittivirhetodennäköisyydelle yhden lähetinantennin tapauksessa sekä rajanopeus (cutoff rate), joka on alaraja keskinäisinformaatiolle, usean lähetinantennin tapauksessa. Konstellaatioiden käyttö yhdessä virheenkorjauskoodien kanssa edellyttää tehokaita menetelmiä, joilla bitit kuvataan konstellaatiopisteisiin. Koska tarvittavat konstellaatiot eivät ole tyypillisesti geometrisesti symmetrisiä, Gray-kuvaus ei ole yleensä mahdollinen.Lisäksi erilaiset kuvausmenetelmät voivat johtaa täysin erilaisiin bittivirhesuhteisiin. Tästä johtuen työssä esitetään uusi kuvausalgoritmi (modified bit switching algorithm), joka minimoi keskimääräisen bittivirhetodennäköisyyden ylärajan. Simulointitulokset osoittavat, että työssä kehitetyt konstellaatiot antavat paremman suorituskyvyn turbokoodatuissa järjestelmissä kuin perinteiset konstellaatiot. Työssä tarkastellaan myös lineaarista esikoodausta yksinkertaisena, alioptimaalisena vaihtoehtona uusille konstellaatioille. Esikoodauksen suunnittelussa käytetään samaa kriteeriä kuin konstellaatioiden kehityksessä eli rajanopeutta. Lineaarinen esikooderi löydetään numeerisesti maksimoimalla rajanopeus kun rajoitusehtona on lähetysteho. Esikoodausmatriisi hajotetaan singulaariarvohajotelmaa käyttäen esisuodatus, tehoallokaatio ja keilanmuodostusmatriiseiksi, jonka havaitaan vastaavan lähetyskorrelaatiomatriisin ominaisvektoreita. Tehoallokaatiomatriisi ratkaistaan numeerisesti käyttäen difference of convex functions -optimointia ja esisuodatusmatriisi optimoinnilla unitaarista rajoitusehtoa käyttäen. Simulaatiotulokset osoittavat uusien esikoodereiden tarjoavan merkittävän suorituskykyedun sellaisiin rajanopeusoptimoituihin osittain koherentteihin konstellaatioihin nähden, jotka eivät käytä esikoodausta.

Locating a radiating source based on range or range measurements obtained from a network of passive sensors has been a subject of research over the past two decades due to the problem’s importance in applications in wireless communications, surveillance, navigation, geosciences, and several other fields. In this thesis, we develop new solution methods for the problem of localizing a single radiating source based on range and range-difference measurements. Iterative re-weighting algorithms are developed for both range-based and range-difference-based least squares localization. Then we propose a penalty convex-concave procedure for finding an approximate solution to nonlinear least squares problems that are related to the range measurements. Finally, the sequential convex relaxation procedures are proposed to obtain the nonlinear least squares estimate of source coordinates. Localization in wireless sensor network, where the RF signals are used to derive the ranging measurements, is the primary application area of this work. However, the solution methods proposed are general and could be applied to range and range-difference measurements derived from other types of signals. / Graduate / 0544 / ismailds@uvic.ca

De nos jours, avec l'abondance croissante de données de très grande taille, les problèmes de classification de grande dimension ont été mis en évidence comme un challenge dans la communauté d'apprentissage automatique et ont beaucoup attiré l'attention des chercheurs dans le domaine. Au cours des dernières années, les techniques d'apprentissage avec la parcimonie et l'optimisation stochastique se sont prouvées être efficaces pour ce type de problèmes. Dans cette thèse, nous nous concentrons sur le développement des méthodes d'optimisation pour résoudre certaines classes de problèmes concernant ces deux sujets. Nos méthodes sont basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) étant reconnues comme des outils puissants d'optimisation non convexe. La thèse est composée de trois parties. La première partie aborde le problème de la sélection des variables. La deuxième partie étudie le problème de la sélection de groupes de variables. La dernière partie de la thèse liée à l'apprentissage stochastique. Dans la première partie, nous commençons par la sélection des variables dans le problème discriminant de Fisher (Chapitre 2) et le problème de scoring optimal (Chapitre 3), qui sont les deux approches différentes pour la classification supervisée dans l'espace de grande dimension, dans lequel le nombre de variables est beaucoup plus grand que le nombre d'observations. Poursuivant cette étude, nous étudions la structure du problème d'estimation de matrice de covariance parcimonieuse et fournissons les quatre algorithmes appropriés basés sur la programmation DC et DCA (Chapitre 4). Deux applications en finance et en classification sont étudiées pour illustrer l'efficacité de nos méthodes. La deuxième partie étudie la L_p,0régularisation pour la sélection de groupes de variables (Chapitre 5). En utilisant une approximation DC de la L_p,0norme, nous prouvons que le problème approché, avec des paramètres appropriés, est équivalent au problème original. Considérant deux reformulations équivalentes du problème approché, nous développons différents algorithmes basés sur la programmation DC et DCA pour les résoudre. Comme applications, nous mettons en pratique nos méthodes pour la sélection de groupes de variables dans les problèmes de scoring optimal et d'estimation de multiples matrices de covariance. Dans la troisième partie de la thèse, nous introduisons un DCA stochastique pour des problèmes d'estimation des paramètres à grande échelle (Chapitre 6) dans lesquelles la fonction objectif est la somme d'une grande famille des fonctions non convexes. Comme une étude de cas, nous proposons un schéma DCA stochastique spécial pour le modèle loglinéaire incorporant des variables latentes / These days with the increasing abundance of data with high dimensionality, high dimensional classification problems have been highlighted as a challenge in machine learning community and have attracted a great deal of attention from researchers in the field. In recent years, sparse and stochastic learning techniques have been proven to be useful for this kind of problem. In this thesis, we focus on developing optimization approaches for solving some classes of optimization problems in these two topics. Our methods are based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are wellknown as one of the most powerful tools in optimization. The thesis is composed of three parts. The first part tackles the issue of variable selection. The second part studies the problem of group variable selection. The final part of the thesis concerns the stochastic learning. In the first part, we start with the variable selection in the Fisher's discriminant problem (Chapter 2) and the optimal scoring problem (Chapter 3), which are two different approaches for the supervised classification in the high dimensional setting, in which the number of features is much larger than the number of observations. Continuing this study, we study the structure of the sparse covariance matrix estimation problem and propose four appropriate DCA based algorithms (Chapter 4). Two applications in finance and classification are conducted to illustrate the efficiency of our methods. The second part studies the L_p,0regularization for the group variable selection (Chapter 5). Using a DC approximation of the L_p,0norm, we indicate that the approximate problem is equivalent to the original problem with suitable parameters. Considering two equivalent reformulations of the approximate problem we develop DCA based algorithms to solve them. Regarding applications, we implement the proposed algorithms for group feature selection in optimal scoring problem and estimation problem of multiple covariance matrices. In the third part of the thesis, we introduce a stochastic DCA for large scale parameter estimation problems (Chapter 6) in which the objective function is a large sum of nonconvex components. As an application, we propose a special stochastic DCA for the loglinear model incorporating latent variables