To reduce cost, many digital cameras use a single sensor array instead of using three arrays for the red, green and blue. Thus at each pixel location only the red, green or blue intensity value is available. And to generate a complete color image, the camera must estimate the missing two values at each pixel location .Color filter arrays are used to capture only one portion of the spectrum (Red, Green or Blue) at each location. Various arrangements of the Color Filter Array (CFA) are possible, but the Bayer array is the most commonly used arrangement and we will deal exclusively with the Bayer array in this thesis. Since each of the three colors channels are effectively downsampled, it leads to aliasing artifacts. This thesis will analyze the effects of aliasing in the frequency- domain and present a method to reduce the deterioration in image quality due to aliasing artifacts. Two reference algorithms, AH-POCS (Adams and Hamilton - Projection Onto Convex Sets) and Adaptive Homogeneity-Directed interpolation, are discussed in de- tail. Both algorithms use the assumption that there is high correlation in the high- frequency regions to reduce aliasing. AH-POCS uses alias cancellation technique to reduce aliasing in the red and blue images, while the Adaptive Homogeneity-Directed interpolation algorithm is an edge-directed algorithm. We present here an algorithm that combines these two techniques and provides a better result on average when compared to the reference algorithms.

O método do Gradiente Espectral, introduzido por Barzilai e Borwein e analisado por Raydan, para minimização irrestrita, é um método simples cujo desempenho é comparável ao de métodos tradicionais como, por exemplo, gradientes conjugados. Desde a introdução do método, assim como da sua extensão para minimização em conjuntos convexos, foram introduzidas várias combinações de passos espectrais diferentes, assim como de buscas lineares não monótonas diferentes. Dos resultados numéricos apresentados em vários trabalhos não é possível inferir se existem diferenças significativas no desempenho dos diversos métodos. Além disso, também não fica clara a relevância das buscas não monótonas como uma ferramenta em si próprias ou se, na verdade, elas são úteis apenas para permitir que o método seja o mais parecido possível com o método original de Barzilai e Borwein. O objetivo deste trabalho é comparar os diversos métodos recentemente introduzidos como combinações de diferentes buscas lineares não monótonas e diferentes passos espectrais para encontrar a melhor combinação e, a partir daí, aferir o desempenho numérico do método. / The Spectral Gradient method, introduced by Barzilai and Borwein and analized by Raydan for unconstrained minimization, is a simple method whose performance is comparable to traditional methods, such as conjugate gradients. Since the introduction of method, as well as its extension to minimization of convex sets, there were introduced various combinations of different spectral steplengths, as well as different nonmonotone line searches. By the numerical results presented in many studies it is not possible to infer whether there are siginificant differences in the performance of various methods. It also is not sure the relevance of the nonmonotone line searches as a tool in themselves or whether, in fact, they are usefull only to allow the method to be as similar as possible with the original method of Barzilai e Borwein. The objective of this study is to compare the different methods recently introduced as different combinations of nonmonotone linear searches and different spectral steplengths to find the best combination and from there, evaluating the numerical performance of the method.

Avec le besoin croissant en bande-passante, les technologies dites de radio-cognitive sont de plus en plus étudiées par la communauté scientifique. L’enjeu est d’utiliser au mieux le spectre disponible. L'une de ces technologies, Transform Domain Communication System (TDCS), dont les performances en termes d’efficacité énergétique et spectrale étaient jusqu'à présent méconnues, constitue le sujet d'étude de cette thèse. Après une présentation du contexte scientifique et industriel de la thèse, le système TDCS est introduit, ainsi que ses similarités et différences avec OFDM et MC-CDMA. Le système est ensuite décrit sous le formalisme algébrique des modulations linaires. Cela a permis d’établir une expression de l’efficacité spectrale du système. Plusieurs techniques sont alors proposées pour améliorer celle-ci tout en améliorant, dans certains cas, le taux d’erreur binaire. Étant composé d’un de plusieurs composantes sinusoïdales, le signal TDCS souffre d’un fort Peak-to-Average Power Ratio (PAPR). La théorie ensembliste est alors présentée puis mise à profit en troisième partie de cette thèse pour proposer les algorithmes Douglas-Rachford et ROCS de réduction du PAPR des signaux TDCS. Ces algorithmes convergent plus rapidement et vers des valeurs plus basses que l’algorithme POCS précédemment utilisé dans la littérature / For about ten years, spectrum scarcity and the growing need of bandwidth have pushed the studies on cognitive-radio technologies to counter this waste. Among them: the Transform Domain Communication System (TDCS), on which this thesis focuses. Until now, TDCS’ performance in terms of spectral and power efficiency was largely unknown. After introducing the thesis’ industrial and scientific context, the TDCS is introduced and compared with popular technologies such as OFDM and MC-CDMA. The system is then studied by means of the linear modulations’ algebraic framework. This has led to the TDCS’ spectral efficiency determination and to new design rules to jointly achieve a better spectral efficiency and a lower BER. Several methods are then proposed to further increase the spectral efficiency by means of a dense multidimensional modulation. Since a TDCS signal is made of several sines, it suffers from a strong Peak-to-Average Power Ratio (PAPR). Set theoretic estimation is then introduced in a third part and new PAPR-reduction algorithms such as Douglas-Rachford and Reflection Onto Convex Sets are brought to light and achieve better performance than the usual POCS algorithm regarding to the convergence rate, as well as the achieved PAPR

Οι πρόσφατες εξελίξεις στις ασύρματες επικοινωνίες και στα ηλεκτρονικά κυκλώματα έχουν επιτρέψει την ανάπτυξη υπολογιστικών διατάξεων χαμηλού κόστους και χαμηλής κατανάλωσης ισχύος, οι οποίες ενσωματώνουν δυνατότητες μέτρησης (sensing), επεξεργασίας και ασύρματης επικοινωνίας. Οι διατάξεις αυτές, οι οποίες έχουν ιδιαίτερα μικρό μέγεθος, καλούνται κόμβοι αισθητήρες. Ένα ασύρματο δίκτυο κόμβων αισθητήρων αποτελείται από ένα πλήθος κόμβων οι οποίοι έχουν αναπτυχθεί σε κάποια περιοχή ενδιαφέροντος προκειμένου να μετρούν κάποια μεταβλητή του περιβάλλοντος. Ανάμεσα σε πολλές εφαρμογές, ο εντοπισμός και η παρακολούθηση των θέσεων πηγών οι οποίες εκπέμπουν κάποιο σήμα (π.χ. ακουστικό, ηλεκτρομαγνητικό) αποτελεί ένα πολύ ενδιαφέρον θέμα, το οποίο μάλιστα μπορεί να χρησιμοποιηθεί και ως βάση για τη μελέτη άλλων προβλημάτων τα οποία εμφανίζονται στα ασύρματα δίκτυα αισθητήρων. Οι περισσότερες από τις υπάρχουσες τεχνικές εντοπισμού θέσης μιας πηγής από μια συστοιχία αισθητήρων μπορούν να ταξινομηθούν σε δυο κατηγορίες: (α) Τις τεχνικές οι οποίες χρησιμοποιούν μετρήσεις διεύθυνσης άφιξης (Direction of Arrival, DOA) και (β) τις τεχνικές οι οποίες χρησιμοποιούν μετρήσεις διαφοράς χρόνων άφιξης (Time Difference of Arrival, TDOA). Ωστόσο, οι τεχνικές αυτές απαιτούν υψηλό ρυθμό δειγματοληψίας και ακριβή συγχρονισμό των κόμβων και δε συνάδουν έτσι με τις περιορισμένες ικανότητες των κόμβων αισθητήρων. Για τους λόγους αυτούς, το ενδιαφέρον έχει στραφεί σε μια τρίτη κατηγορία τεχνικών οι οποίες χρησιμοποιούν μετρήσεις ισχύος (Received Signal Strength, RSS). Το πρόβλημα του εντοπισμού θέσης χρησιμοποιώντας μετρήσεις ισχύος είναι ένα πρόβλημα εκτίμησης, όπου οι μετρήσεις συνδέονται με τις προς εκτίμηση παραμέτρους με μη-γραμμικό τρόπο. Στα πλαίσια της Διδακτορικής Διατριβής ασχολούμαστε αρχικά με την περίπτωση όπου επιθυμούμε να εκτιμήσουμε τη θέση και την ισχύ μιας πηγής χρησιμοποιώντας μετρήσεις ισχύος οι οποίες φθίνουν με βάση το αντίστροφο του τετραγώνου της απόστασης ανάμεσα στην πηγή και το σημείο μέτρησης. Για το πρόβλημα αυτό, προτείνουμε έναν εκτιμητή ο οποίος δίνει τις παραμέτρους της πηγής ως λύση ενός γραμμικού προβλήματος ελαχίστων τετραγώνων. Στη συνέχεια, υπολογίζουμε κατάλληλα βάρη και προτείνουμε έναν εκτιμητή ο οποίος δίνει τις παραμέτρους της πηγής ως λύση ενός προβλήματος ελαχίστων τετραγώνων με βάρη. Ακόμα, τροποποιούμε κατάλληλα τον τελευταίο εκτιμητή έτσι ώστε να είναι δυνατή η κατανεμημένη υλοποίησή του μέσω των προσαρμοστικών αλγορίθμων Least Mean Square (LMS) και Recursive Least Squares (RLS). Στη συνέχεια, εξετάζουμε την περίπτωση όπου ενδιαφερόμαστε να εκτιμήσουμε τη θέση μιας πηγής αλλά δεν έχουμε καμιά πληροφορία σχετικά με το μοντέλο εξασθένισης της ισχύος. Έτσι, υποθέτουμε πως αυτό περιγράφεται από μια άγνωστη γνησίως φθίνουσα συνάρτηση της απόστασης. Αρχικά, προσεγγίζουμε το πρόβλημα εκτίμησης κάνοντας την υπόθεση πως οι θέσεις των κόμβων αποτελούν τυχαία σημεία ομοιόμορφα κατανεμημένα στο επίπεδο. Χρησιμοποιώντας την υπόθεση αυτή, υπολογίζουμε εκτιμήσεις για τις αποστάσεις ανάμεσα στους κόμβους και την πηγή, και αναπτύσσουμε έναν αλγόριθμο εκτίμησης της θέσης της πηγής. Στη συνέχεια, προσεγγίζουμε το πρόβλημα εκτίμησης χωρίς την υπόθεση περί ομοιόμορφης κατανομής των θέσεων των κόμβων στο επίπεδο. Προτείνουμε μια κατάλληλη συνάρτηση κόστους για την περίπτωση αυτή, και δείχνουμε την ύπαρξη μιας συνθήκης υπό την οποία η βέλτιστη λύση μπορεί να υπολογιστεί. Η λύση αυτή είναι εσωτερικό σημείο ενός κυρτού πολυγώνου, το οποίο ονομάζουμε ταξινομημένο τάξης-K κελί Voronoi. Έτσι, δίνουμε αλγορίθμους υπολογισμού της λύσης αυτής, καθώς και κατανεμημένους αλγορίθμους οι οποίοι βασίζονται σε προβολές σε κυρτά σύνολα. Ακόμα, ασχολούμαστε με τις ιδιότητες των κελιών αυτών στην περίπτωση όπου οι θέσεις των κόμβων αισθητήρων είναι ομοιόμορφα κατανεμημένες στο επίπεδο και υπολογίζουμε κάποια φράγματα για το εμβαδόν τους. Τέλος, ασχολούμαστε με την περίπτωση όπου ενδιαφερόμαστε να εκτιμήσουμε τις θέσεις πολλαπλών πηγών με γνωστό μοντέλο εξασθένισης της ισχύος. Για το πρόβλημα αυτό, αρχικά προτείνουμε έναν αλγόριθμο διαδοχικής εκτίμησης και ακύρωσης της συνεισφοράς κάθε πηγής, προκειμένου να υπολογιστούν σταδιακά οι θέσεις όλων των πηγών. Ο αλγόριθμος αυτός, αποτελείται από τρία βήματα κατά τα οποία πρώτα υπολογίζεται μια προσεγγιστική θέση για την πηγή, στη συνέχεια εκτιμάται ένα σύνολο κόμβων το οποίο δέχεται μικρής έντασης παρεμβολή από τις υπόλοιπες πηγές, και τέλος επιχειρείται μια λεπτομερέστερη εκτίμηση της θέσης κάθε πηγής. Στη συνέχεια, επεκτείνοντας την τεχνική αυτή, προτείνουμε έναν επαναληπτικό αλγόριθμο εκτίμησης ο οποίος βασίζεται στον αλγόριθμο εναλλασσόμενων προβολών (Alternating Projections). Εξετάζουμε επίσης μεθόδους οι οποίες οδηγούν στη μείωση της υπολογιστικής πολυπλοκότητας του αλγορίθμου αυτού. / Technology advances in microelectronics and wireless communications have enabled the development of small-scale devices that integrate sensing, processing and short-range radio capabilities. The deployment of a large number of such devices, referred to as sensor nodes, over a territory of interest, defines the so-called wireless sensor network. Wireless sensor networks have attracted considerable attention in recent years and have motivated many new challenges, most of which require the synergy of many disciplines, including signal processing, networking and distributed algorithms. Among many other applications, source localization and tracking has been widely viewed as a canonical problem of wireless sensor networks. Furthermore, it constitutes an easily perceived problem that can be used as a vehicle to study more involved information processing and organization problems. Most of the source localization methods that have appeared in the literature can be classified into two broad categories, according to the physical variable they utilize. The algorithms of the first category utilize “time delay of arrival”(TDOA) measurements, and the algorithms of the second category use “direction of arrival” (DOA) measurements. DOA estimates are particularly useful for locating sources emitting narrowband signals, while TDOA measurements offer the increased capability of localizing sources emitting broadband signals. However, the methods of both categories impose two major requirements that render them inappropriate to be used in wireless sensor networks: (a) the analog signals at the outputs of the spatially distributed sensors should be sampled in a synchronized fashion, and (b) the sampling rate used should be high enough so as to capture the features of interest. These requirements, in turn, imply that accurate distributed synchronization methods should be implemented so as to keep the remote sensor nodes synchronized and that high frequency electronics as well as increased bandwidth are needed to transmit the acquired measurements. Due to the aforementioned limitations, source localization methods that rely upon received signal strength (RSS) measurements - originally explored for locating electromagnetic sources - have recently received revived attention. In this Thesis, we begin our study by considering the localization of an isotropic acoustic source using energy measurements from distributed sensors, in the case where the energy decays according to an inverse square law with respect to the distance. While most acoustic source localization algorithms require that distance estimates between the sensors and the source of interest are available, we propose a linear least squares criterion that does not make such an assumption. The new criterion can yield the location of the source and its transmit power in closed form. A weighted least squares cost function is also considered, and distributed implementation of the proposed estimators is studied. Numerical results indicate significant performance improvement as compared to a linear least squares based approach that utilizes energy ratios, and comparable performance to other estimators of higher computational complexity. In the sequel, we turn our attention to the case where the energy decay model is not known. For solving the localization problem in this case, we first make the assumption that the locations of the nodes near the source can be well described by a uniform distribution. Using this assumption, we derive distance estimates that are independent of both the energy decay model and the transmit power of the source. Numerical results show that these estimates lead to improved localization accuracy as compared to other model-independent approaches. In the sequel, we consider the more general case where the assumption about the uniform deployment of the sensors is not required. For this case, an optimization problem that does not require knowledge of the underlying energy decay model is proposed, and a condition under which the optimal solution can be computed is given. This condition employs a new geometric construct, called the sorted order-K Voronoi diagram. We give centralized and distributed algorithms for source localization in this setting. Finally, analytical results and simulations are used to verify the performance of the developed algorithms. The next problem we consider is the estimation of the locations of multiple acoustic sources by a network of distributed energy measuring sensors. The maximum likelihood (ML) solution to this problem is related to the optimization of a non-convex function of, usually, many variables. Thus, search-based methods of high complexity are required in order to yield an accurate solution. In order to reduce the computational complexity of the multiple source localization problem, we propose two methods. The first method proposes a sequential estimation algorithm, in which each source is localized, its contribution is cancelled, and the next source is considered. The second method makes use of an alternating projection (AP) algorithm that decomposes the original problem into a number of simpler, yet also non-convex, optimization steps. The particular form of the derived cost functions of each such optimization step indicates that, in some cases, an approximate form of these cost functions can be used. These approximate cost functions can be evaluated using considerably lower computational complexity. Thus, a low-complexity version of the AP algorithm is proposed. Extensive simulation results demonstrate that the proposed algorithm offers a performance close to that of the exact AP implementation, and in some cases, similar performance to that of the ML estimator.

Submitted by Milena Rubi ( ri.bso@ufscar.br) on 2017-10-17T16:07:35Z No. of bitstreams: 1 CUNHA_Bruno_2017.pdf: 1281922 bytes, checksum: 605ecd45f46a3b67332ed6bd13043af5 (MD5) / Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2017-10-17T16:07:44Z (GMT) No. of bitstreams: 1 CUNHA_Bruno_2017.pdf: 1281922 bytes, checksum: 605ecd45f46a3b67332ed6bd13043af5 (MD5) / Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2017-10-17T16:07:53Z (GMT) No. of bitstreams: 1 CUNHA_Bruno_2017.pdf: 1281922 bytes, checksum: 605ecd45f46a3b67332ed6bd13043af5 (MD5) / Made available in DSpace on 2017-10-17T16:08:04Z (GMT). No. of bitstreams: 1 CUNHA_Bruno_2017.pdf: 1281922 bytes, checksum: 605ecd45f46a3b67332ed6bd13043af5 (MD5) Previous issue date: 2016-11-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / This work proposes both a study and a development of an algorithm for super-resolution of digital images using projections onto convex sets. The method is based on a classic algorithm for spatial super-resolution which considering the subpixel information present in a set of lower resolution images, generate an image of higher resolution and better visual quality. We propose the incorporation of a new restriction based on the Richardson-Lucy algorithm in order to restore and recover part of the spatial frequencies lost during the degradation and decimation process of the high resolution images. In this way the algorithm provides a hybrid approach based on projections onto convex sets which is capable of promoting both the spatial and spectral image super-resolution. The proposed approach was compared with the original algorithm from Sezan and Tekalp and later with a method based on a robust framework that is considered nowadays one of the most effective methods for super-resolution. The results, considering both the visual and the mean square error analysis, demonstrate that the proposed method has great potential promoting increased visual quality over the images studied. / Este trabalho visa o estudo e o desenvolvimento de um algoritmo para super-resolução de imagens digitais baseado na teoria de projeções sobre conjuntos convexos. O método é baseado em um algoritmo clássico de projeções sobre restrições convexas para super- resolução espacial onde se busca, considerando as informações subpixel presentes em um conjunto de imagens de menor resolução, gerar uma imagem de maior resolução e com melhor qualidade visual. Propomos a incorporação de uma nova restrição baseada no algoritmo de Richardson-Lucy para restaurar e recuperar parte das frequências espaciais perdidas durante o processo de degradação e decimação das imagens de alta resolução. Nesse sentido o algoritmo provê uma abordagem híbrida baseada em projeções sobre conjuntos convexos que é capaz de promover simultaneamente a super-resolução espacial e a espectral. A abordagem proposta foi comparada com o algoritmo original de Sezan e Tekalp e posteriormente com um método baseado em um framework de super-resolução robusta, considerado um dos métodos mais eficazes na atualidade. Os resultados obtidos, considerando as análises visuais e também através do erro médio quadrático, demonstram que o método proposto possui grande potencialidade promovendo o aumento da qualidade visual das imagens estudadas.

Cette thèse est consacrée à l'étude des variétés projectives strictement convexes de volume fini. Une telle variété est le quotient G\U d'un ouvert proprement convexe U de l'espace projectif réel RP^(n-1) par un sous-groupe discret sans torsion G de SLn(R) qui préserve U. Dans un premier temps, on étudie l'adhérence de Zariski des holonomies de variétés projectives strictement convexes de volume fini. Pour une telle variété G\U, on montre que, soit G est Zariski-dense dans SLn(R), soit l'adhérence de Zariski de G est conjuguée à SO(1,n-1). On s'intéresse ensuite à l'espace des modules des structures projectives strictement convexes de volume fini. On montre en particulier que cet espace des modules est un fermé de l'espace des représentations. / In this thesis, we study strictly convex projective manifolds of finite volume. Such a manifold is the quotient G\U of a properly convex open subset U of the real projective space RP^(n-1) by a discrete torsionfree subgroup G of SLn(R) preserving U. We study the Zariski closure of holonomies of convex projective manifolds of finite volume. For such manifolds G\U, we show that either the Zariski closure of G is SLn(R) or it is a conjugate of SO(1,n-1).We also focuss on the moduli space of strictly convex projective structures of finite volume. We show that this moduli space is a closed set of the representation space.

In dieser Arbeit beweisen wir für Optimierungsprobleme in L0-Moduln relevante Resultate und untersuchen Anwendungen für die Darstellung von Präferenzen. Im ersten Kapitel geht es um quasikonkave, monotone und lokale Funktionen von einem L0-Modul X nach L0, die wir robust darstellen. Im zweiten Kapitel entwickeln wir das Ekeland’sche Variationsprinzip für L0-Moduln, die eine L0-Metrik besitzen. Wir beweisen eine L0 -Variante einer Verallgemeinerung des Ekeland’schen Theorems. Der Beweis des Brouwerschen Fixpunktsatzes für Funktionen, die auf (L0)^d definiert sind, wird in Kapitel 3 behandelt. Wir definieren das Konzept des Simplexes in (L0)^d und beweisen, dass jede lokale, folgenstetige Funktion darauf einen Fixpunkt besitzt. Dies nutzen wir, um den Fixpunktsatz auch für Funktionen auf beliebigen abgeschlossenen, L0 -konvexen Mengen zu zeigen. Eine allgemeinere Struktur als L0 ist die bedingte Menge. Im vierten Kapitel behandeln wir bedingte topologische Vektorräume. Wir führen das Konzept der Dualität für bedingte Mengen ein und beweisen Theoreme der Funktionalanalysis darauf, unter anderem das Theorem von Banach-Alaoglu und Krein-Šmulian. Im fünften Kapitel widmen wir uns der Darstellung mit wandernden konvexen Mengen. Wir zeigen danach, wie die Transitivität für diese Darstellungsform beschrieben werden kann. Abschließend modellieren wir die Eigenschaft, dass die Transitivität einer Relation nur für ähnliche Elemente gesichert ist und diskutieren Arten der Darstellung solcher Relationen. / In this thesis, we prove results relevant for optimization problems in L0-modules and study applications to order theory. The first part deals with the notion of an Assessment Index (AI). For an L0 -module X an AI is a quasiconcave, monotone and local function mapping to L0. We prove a robust representation of these AIs. In the second chapter of this thesis, we develop Ekeland’s variational principle for L0-modules allowing for an L0-metric. We prove an L0-Version of a generalization of Ekeland’s theorem. A further application of L0 -theory is examined in the third chapter of this thesis, namely an extension of the Brouwer fixed point theorem to functions on (L0)^d . We define a conditional simplex, which is a simplex with respect to L0 , and prove that every local, sequentially continuous function has a fixed point. We extend the fixed point theorem to arbitrary closed, L0-convex sets. A more general structure than L0 -modules is the concept of conditional sets. In the fourth chapter of the thesis, we study conditional topological vector spaces. We examine the concept of duality for conditional sets and prove results of functional analysis: among others, the Banach-Alaoglu and the Krein-Šmulian theorem. Any L0 -module being a conditional set allows to apply all results to L0 -theory. In the fifth chapter, we discuss the property of transitivity of relations and its connection to certain forms of representations. After a survey of common representations of preferences, we attend to relations induced by moving convex sets which are relations of the form that x is preferred to y if and only if x − y is in a convex set depending on y. We examine in which cases such a representation is transitive. Finally, we exhibit nontransitivity due to dissimilarity of the compared object and discuss representations for relations of that type.