This thesis contains two parts: the detectability of convex sets and the study on regression models In the first part of this dissertation, we investigate the problem of the detectability of an inhomogeneous convex region in a Gaussian random field. The first proposed detection method relies on checking a constructed statistic on each convex set within an nn image, which is proven to be un-applicable. We then consider using h(v)-parallelograms as the surrogate, which leads to a multiscale strategy. We prove that 2/9 is the minimum proportion of the maximally embedded h(v)-parallelogram in a convex set. Such a constant indicates the effectiveness of the above mentioned multiscale detection method. In the second part, we study the robustness, the optimality, and the computing for regression models. Firstly, for robustness, M-estimators in a regression model where the residuals are of unknown but stochastically bounded distribution are analyzed. An asymptotic minimax M-estimator (RSBN) is derived. Simulations demonstrate the robustness and advantages. Secondly, for optimality, the analysis on the least angle regressions inspired us to consider the conditions under which a vector is the solution of two optimization problems. For these two problems, one can be solved by certain stepwise algorithms, the other is the objective function in many existing subset selection criteria (including Cp, AIC, BIC, MDL, RIC, etc). The latter is proven to be NP-hard. Several conditions are derived. They tell us when a vector is the common optimizer. At last, extending the above idea about finding conditions into exhaustive subset selection in regression, we improve the widely used leaps-and-bounds algorithm (Furnival and Wilson). The proposed method further reduces the number of subsets needed to be considered in the exhaustive subset search by considering not only the residuals, but also the model matrix, and the current coefficients.

In this thesis, a resource allocation problem in OFDMA is studied for the energy efficiency of wireless network. The objective is to minimize the total energy consumption which includes transmission energy consumption, and circuit energy consumption at both transmitter and receiver with required per user’s rate constraint. For problem solution, a heuristic algorithm with low computational complexity and suboptimal solution is proposed, developed in two steps with an increasing order of complexity. Besides, a bounding scheme based on model linearization of formulated nonlinear system model is also proposed to give lower and upper bounds for both small- and large-scale OFDMA network for further algorithm performance evaluation, while the implemented exhaustive search is only capable to provide the optimal solution for small-scale instance for algorithm performance evaluation. Numerical results show that the proposal heuristic algorithm can achieve near-optimal performance with applicable computational complexity even for large-scale networks, and that the bounds from the bounding scheme are very tight for both small- and large-scale OFDMA networks.

Modern applications of XML use automata operating on unranked trees. A common definition of tree automata operating on unranked trees uses a set of vertical states that define the bottom-up computation, and the transitions on vertical states are determined by so called horizontal languages recognized by finite automata on strings. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by DFAs or NFAs. There is also an alternative syntactic definition of determinism introduced by Cristau et al. It is known that a deterministic tree automaton with the smallest total number of states does not need to be unique nor have the smallest possible number of vertical states. We consider the question by how much we can reduce the total number of states by introducing additional vertical states. We give an upper bound for the state trade-off for deterministic tree automata where the horizontal languages are defined by DFAs, and a lower bound construction that, for variable sized alphabets, is close to the upper bound. We establish upper and lower bounds for the state complexity of conversions between different types of deterministic and nondeterministic unranked tree automata. The bounds are, usually, tight for the numbers of vertical states. Because a minimal deterministic unranked tree automaton need not be unique, establishing lower bounds for the number of horizontal states, that is, the combined size of DFAs used to define the horizontal languages, is challenging. Based on existing lower bound results for unambiguous finite automata we develop a lower bound criterion for the number of horizontal states. We consider the state complexity of operations on regular unranked tree languages. The concatenation of trees can be defined either as a sequential or a parallel operation. Furthermore, there are two essentially different ways to iterate sequential concatenation. We establish tight state complexity bounds for concatenation-like operations. In particular, for sequential concatenation and bottom-up iterated concatenation the bounds differ by an order of magnitude from the corresponding state complexity bounds for regular string languages. / Thesis (Ph.D, Computing) -- Queen's University, 2012-01-04 14:48:02.916

In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization. Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables. Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem. An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by Hastad, for some small (unspecified) constant β > 0. The hardness results for Max-Clique and chromatic number are then obtained using the reduction from Min-3Lin-Deletion as given by Khot. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that monotone multilinear Boolean circuits for computing bipartite perfect matching require exponential size. In fact we prove a stronger result by characterizing the structure of the smallest monotone multilinear Boolean circuits for the problem.

A travers la présente thèse, nous nous intéressons à la prévention des accidents d’avalanche survenant à l’occasion de la pratique du hors-piste. Les jeunes pratiquants du hors-piste (15-30 ans) sont repérés comme les principales victimes des avalanches par les données statistiques de l’Association Nationale pour l’Etude de la Neige et des Avalanches. L’objectif principal de la présente thèse est de parvenir à une meilleure connaissance de ce public adepte de sports de glisse. Pour cela, nous proposons d’investiguer leurs habitudes et motivations de pratique du hors-piste, leurs perceptions des risques liés à cette pratique, les explications qu’ils donnent spontanément pour les accidents d’avalanche en hors-piste, ainsi que les comportements qu’ils adoptent en hors-piste et les critères qu’ils utilisent pour prendre la décision de sortir des pistes. Les données recueillies devraient contribuer à l’enrichissement des stratégies de prévention des accidents d’avalanche en hors-piste. Elles permettent de concevoir des stratégies et des messages ciblés et adaptés à cette population de jeunes pratiquants. En effet, les travaux sur la perception des risques (Kouabenan, 2006) et sur l’explication naïve des accidents (Kouabenan, 1999) suggèrent que si l’on souhaite que les individus adhèrent aux messages de prévention, il est nécessaire de connaître la façon dont ils appréhendent les risques, et pour ce qui nous concerne les risques en hors-piste, notamment le risque d’avalanche. Il importe aussi de connaître les causes qu’ils invoquent pour expliquer la production des accidents d’avalanche. Ce travail de thèse comprend quatre études dont la méthodologie repose sur deux questionnaires. L’élaboration des questionnaires s’appuie sur des entretiens préalables menés avec des pratiquants aux profils divers, et sur l’exploitation de la littérature sur les travaux empiriques empruntant le même cadre théorique ainsi que sur les rapports sur les accidents d’avalanche. Concernant les études 1, 2 et 4, nous avons interrogé 304 jeunes pratiquants de sports de glisse. Pour l’étude 4, nous avons questionné 238 pratiquants. Pour le recueil des données concernant les quatre études, nous avons rencontré les participants sur le terrain, dans des stations de sports d’hiver en Isère, en Savoie et en Haute-Savoie, ainsi que sur le campus universitaire et lors de manifestations sportives. Le recueil des données s’est fait par entretien en face à face avec le participant. / Through this thesis, we examine the avalanche accident prevention occurring in out-of-bounds (OB) practice. Young out-of-bounds practitioners (15-30 years-old) are identified as the core of avalanche victims. The main aim of this thesis is to get better knowledge about these boardsports enthusiasts. To do this, we suggest to investigate their habits and motivations relative to OB practice, their perception of the risks associated to this practice, the spontaneous explanations they give for avalanche accidents in OB, as well as the behaviours they adopt in OB, and the criteria they use to decide to go or not to go OB. The data collected would contribute to improve prevention strategies for avalanche accidents in OB, by targeting and adapting these strategies to young practitioners. Indeed, research on risk perception (Kouabenan, 2006) and naive causal explanations of accidents (Kouabenan, 1999) propose that if we want people to adhere to prevention messages, it is necessary to know the way they understand risks, for our case OB risks, particularly avalanche hazard. It is also essential to know the causes they invoke to explain avalanche accidents. This thesis work consists of four studies for which the methodology relies on two questionnaires. The questionnaires were carried out from preliminary interviews conducted with practitioners of varied profiles, and from literature and empirical works of the same theoretical framework, as well as accidents reports. Concerning the studies 1, 2 and 4, we interviewed 304 young boardsports practitioners. For study 3, we questioned 238 practitioners. For the data collect of the four studies, we met participants in the field, in winter sport resorts in Isère, Savoie and Haute-Savoie (France), as well as at the university campus and during sport events. Data collection was done with face-to-face interview with the participant.

La connaissance de l'environnement marin est nécessaire pour un grand nombre d'applications dans le domaine de l'acoustique sous-marine comme la communication, la localisation et détection sonar et la surveillance des mammifères marins. Il constitue le moyen principal pour éviter les interférences néfastes entre le milieu naturel et les actions industriels et militaires conduites en zones côtières.Notre travail de thèse se place dans un contexte de sonar actif avec des fréquences allant de 1 kHz à 10 kHz pour des distances de propagations allant de 1 km à plusieurs dizaines de kilomètres. Nous nous intéressons particulièrement aux environnements de propagation grands fonds, à l'utilisation des antennes industrielles comme les antennes de flancs, les antennes cylindriques et les antennes linéaires remorquées, et à l'utilisation de signaux large bande afin de travailler avec des résolutions en distance et en vitesse très élevées. Le travail de recherche présenté dans ce mémoire est dédié à la recherche de nouveaux paramètres discriminants pour la classification de cible sous-marine en sonar actif et notamment à l'estimation de l'immersion instantanée.Cette étude présente : (1) les calculs de nouvelles bornes de Cramer-Rao pour la position d'une cible en distance en et en profondeur, (2) l'estimation conjointe de la distance et de l'immersion d'une cible à partir de la mesure des temps d'arrivées et des angles d'élévations sur une antenne surfacique et (3) l'estimation conjointe de la distance, de l'immersion et du gisement d'une cible à partir de la mesure des temps d'arrivées et des pseudo-gisements sur une antenne linéaire remorquée.Les méthodes développées lors de cette étude ont été validées sur des simulations, des données expérimentales à petite échelle et des données réelles en mer. / The knowledge of the marine environment is required for many underwater applications such as communications, sonar localization and detection, and marine mammals monitoring. It enables preventing harmful interference between the natural environment and industrial and military actions in coastal areas.This thesis work concentrates upton the context of active sonar with frequencies from 1 kHz to 10 kHz and long propagation ranges from 1 km to several tens of kilometers. We also concentrates upon deep water environment, the use of industrial arrays such as cylindrical arrays, flank arrays and linear towed arrays, and the use of large time-bandwidth signals in order to obtain high distance and speed resolutions. This research work is dedicated to the research of new features for the underwater target classification in active sonar, and specifically to the instantaneous target-depth estimation.This thesis presents: (1) calculations of new Cramer-Rao bounds for the target-position in range and in depth, (2) the joint estimation of the target-depth and the target-range from the arrival time and elevation angle measures with a surface array, (3) the joint estimation of the target-depth, the target-range and the target-bearing from the arrival time and pseudo-bearing angle measures with a linear towed array.The methods presented in this manuscript have been benchmarked on simulation, on reduced-scale experimental data and real marine data.

abstract: There are many wireless communication and networking applications that require high transmission rates and reliability with only limited resources in terms of bandwidth, power, hardware complexity etc.. Real-time video streaming, gaming and social networking are a few such examples. Over the years many problems have been addressed towards the goal of enabling such applications; however, significant challenges still remain, particularly, in the context of multi-user communications. With the motivation of addressing some of these challenges, the main focus of this dissertation is the design and analysis of capacity approaching coding schemes for several (wireless) multi-user communication scenarios. Specifically, three main themes are studied: superposition coding over broadcast channels, practical coding for binary-input binary-output broadcast channels, and signalling schemes for two-way relay channels. As the first contribution, we propose an analytical tool that allows for reliable comparison of different practical codes and decoding strategies over degraded broadcast channels, even for very low error rates for which simulations are impractical. The second contribution deals with binary-input binary-output degraded broadcast channels, for which an optimal encoding scheme that achieves the capacity boundary is found, and a practical coding scheme is given by concatenation of an outer low density parity check code and an inner (non-linear) mapper that induces desired distribution of "one" in a codeword. The third contribution considers two-way relay channels where the information exchange between two nodes takes place in two transmission phases using a coding scheme called physical-layer network coding. At the relay, a near optimal decoding strategy is derived using a list decoding algorithm, and an approximation is obtained by a joint decoding approach. For the latter scheme, an analytical approximation of the word error rate based on a union bounding technique is computed under the assumption that linear codes are employed at the two nodes exchanging data. Further, when the wireless channel is frequency selective, two decoding strategies at the relay are developed, namely, a near optimal decoding scheme implemented using list decoding, and a reduced complexity detection/decoding scheme utilizing a linear minimum mean squared error based detector followed by a network coded sequence decoder. / Dissertation/Thesis / Ph.D. Electrical Engineering 2011

Submitted by Maurício da Silva Medeiros Júnior (mauriciojr.df@gmail.com) on 2016-04-06T21:06:49Z No. of bitstreams: 1 Dissertação - Maurício Medeiros Jr. - FGV-EPGE.pdf: 2837403 bytes, checksum: dc338c6b56e600b8b9194b1c27abb080 (MD5) / Approved for entry into archive by BRUNA BARROS (bruna.barros@fgv.br) on 2016-04-19T18:34:15Z (GMT) No. of bitstreams: 1 Dissertação - Maurício Medeiros Jr. - FGV-EPGE.pdf: 2837403 bytes, checksum: dc338c6b56e600b8b9194b1c27abb080 (MD5) / Approved for entry into archive by Marcia Bacha (marcia.bacha@fgv.br) on 2016-04-27T18:16:31Z (GMT) No. of bitstreams: 1 Dissertação - Maurício Medeiros Jr. - FGV-EPGE.pdf: 2837403 bytes, checksum: dc338c6b56e600b8b9194b1c27abb080 (MD5) / Made available in DSpace on 2016-04-27T18:21:05Z (GMT). No. of bitstreams: 1 Dissertação - Maurício Medeiros Jr. - FGV-EPGE.pdf: 2837403 bytes, checksum: dc338c6b56e600b8b9194b1c27abb080 (MD5) Previous issue date: 2016-03-22 / We aim to provide a review of the stochastic discount factor bounds usually applied to diagnose asset pricing models. In particular, we mainly discuss the bounds used to analyze the disaster model of Barro (2006). Our attention is focused in this disaster model since the stochastic discount factor bounds that are applied to study the performance of disaster models usually consider the approach of Barro (2006). We first present the entropy bounds that provide a diagnosis of the analyzed disaster model which are the methods of Almeida and Garcia (2012, 2016); Ghosh et al. (2016). Then, we discuss how their results according to the disaster model are related to each other and also present the findings of other methodologies that are similar to these bounds but provide different evidence about the performance of the framework developed by Barro (2006).

Kernel Methods in Particle Filtering David Coufal Doctoral thesis - abstract The thesis deals with the use of kernel density estimates in particle filtering. In particular, it examines the convergence of the kernel density estimates to the filtering densities. The estimates are constructed on the basis of an out- put from particle filtering. It is proved theoretically that using the standard kernel density estimation methodology is effective in the context of particle filtering, although particle filtering does not produce random samples from the filtering densities. The main theoretical results are: 1) specification of the upper bounds on the MISE error of the estimates of the filtering densities and their partial derivatives; 2) specification of the related lower bounds and 3) providing a suitable tool for checking persistence of the Sobolev character of the filtering densities over time. In addition, the thesis also focuses on designing kernels suitable for practical use. 1

Submitted by Luciana Sebin (lusebin@ufscar.br) on 2016-09-12T17:21:38Z No. of bitstreams: 1 TeseFMF.pdf: 3344288 bytes, checksum: 3bfb3caf40d3dcd756aa8697b58b5f19 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-12T17:29:02Z (GMT) No. of bitstreams: 1 TeseFMF.pdf: 3344288 bytes, checksum: 3bfb3caf40d3dcd756aa8697b58b5f19 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2016-09-12T17:44:44Z (GMT) No. of bitstreams: 1 TeseFMF.pdf: 3344288 bytes, checksum: 3bfb3caf40d3dcd756aa8697b58b5f19 (MD5) / Made available in DSpace on 2016-09-12T17:46:25Z (GMT). No. of bitstreams: 1 TeseFMF.pdf: 3344288 bytes, checksum: 3bfb3caf40d3dcd756aa8697b58b5f19 (MD5) Previous issue date: 2015-08-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / The aim of this work is to present results about the existence of non-trivial solutions for some classes of resonant and superlinear eliptic systems employing topological methods. More specifcally, we use a-priori bounds on the eventual solutions of this problems and topological degree theory. / Neste trabalho apresentamos a existência de soluções não triviais para classes de sistemas elípticos ressonantes e superlineares. Tais sistemas são tratados via métodos topológicos. Encontramos estimativas a priori para possíveis soluções destes sistemas e utilizamos estas estimativas juntamente com a teoria do grau topológico para garantir a existência de soluções.