Neste trabalho, Compressed Sensing é introduzido do ponto de vista da Física Estatística. Após uma introdução sucinta onde os conceitos básicos da teoria são apresentados, incluindo condições necessárias para as medições e métodos básicos de reconstrução do sinal, a performance típica do esquema Bayesiano de reconstrução é analisada através de um cálculo de réplicas exposto em detalhe pedagógico. Em seguida, a principal contribuição original do trabalho é introduzida --- o algoritmo Bayesiano de Compressed Sensing Online faz uso de uma aproximação de campo médio para simplificar cálculos e reduzir os requisitos de memória e computação, enquanto mantém a acurácia de reconstrução do esquema offline na presença de ruído aditivo. A última parte deste trabalho contém duas extensões do algoritmo online que permitem reconstrução otimizada do sinal no cenário mais realista onde conhecimento perfeito da distribuição geradora não está disponível. / In this work, Compressed Sensing is introduced from a Statistical Physics point of view. Following a succinct introduction where the basic concepts of the framework are presented, including necessary measurement conditions and basic signal reconstruction methods, the typical performance of the Bayesian reconstruction scheme is analyzed through a replica calculation shown in pedagogical detail. Thereafter, the main original contribution of this work is introduced --- the Bayesian Online Compressed Sensing algorithm makes use of a mean-field approximation to simplify calculations and reduce memory and computation requirements, while maintaining the asymptotic reconstruction accuracy of the offline scheme in the presence of additive noise. The last part of this work are two extensions of the online algorithm that allow for optimized signal reconstruction in the more realistic scenarios where perfect knowledge of the generating distribution is unavailable.

Neste trabalho, Compressed Sensing é introduzido do ponto de vista da Física Estatística. Após uma introdução sucinta onde os conceitos básicos da teoria são apresentados, incluindo condições necessárias para as medições e métodos básicos de reconstrução do sinal, a performance típica do esquema Bayesiano de reconstrução é analisada através de um cálculo de réplicas exposto em detalhe pedagógico. Em seguida, a principal contribuição original do trabalho é introduzida --- o algoritmo Bayesiano de Compressed Sensing Online faz uso de uma aproximação de campo médio para simplificar cálculos e reduzir os requisitos de memória e computação, enquanto mantém a acurácia de reconstrução do esquema offline na presença de ruído aditivo. A última parte deste trabalho contém duas extensões do algoritmo online que permitem reconstrução otimizada do sinal no cenário mais realista onde conhecimento perfeito da distribuição geradora não está disponível. / In this work, Compressed Sensing is introduced from a Statistical Physics point of view. Following a succinct introduction where the basic concepts of the framework are presented, including necessary measurement conditions and basic signal reconstruction methods, the typical performance of the Bayesian reconstruction scheme is analyzed through a replica calculation shown in pedagogical detail. Thereafter, the main original contribution of this work is introduced --- the Bayesian Online Compressed Sensing algorithm makes use of a mean-field approximation to simplify calculations and reduce memory and computation requirements, while maintaining the asymptotic reconstruction accuracy of the offline scheme in the presence of additive noise. The last part of this work are two extensions of the online algorithm that allow for optimized signal reconstruction in the more realistic scenarios where perfect knowledge of the generating distribution is unavailable.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-30T20:07:56Z No. of bitstreams: 1 robertocarlossoaresnalonpereirasouza.pdf: 1346845 bytes, checksum: e248f967f42f4ef763b613dc39ed0649 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-01T11:51:04Z (GMT) No. of bitstreams: 1 robertocarlossoaresnalonpereirasouza.pdf: 1346845 bytes, checksum: e248f967f42f4ef763b613dc39ed0649 (MD5) / Made available in DSpace on 2017-06-01T11:51:04Z (GMT). No. of bitstreams: 1 robertocarlossoaresnalonpereirasouza.pdf: 1346845 bytes, checksum: e248f967f42f4ef763b613dc39ed0649 (MD5) Previous issue date: 2013-02-21 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho apresenta-se uma nova formulação para regressão ortogonal. O problema é definido como a minimização do risco empírico em relação a uma função de perda com tubo desenvolvida para regressão ortogonal, chamada ρ-insensível. Um algoritmo para resolver esse problema é proposto, baseado na abordagem da descida do gradiente estocástica. Quando formulado em variáveis duais o método permite a introdução de funções kernel e flexibilidade do tubo. Até onde se sabe, este é o primeiro método que permite a introdução de kernels, através do chamado “kernel-trick”, para regressão ortogonal. Apresenta-se ainda um algoritmo para regressão clássica que usa a função de perda ε-insensível e segue também a abordagem da descida do gradiente. Para esse algo ritmo apresenta-se uma prova de convergência que garante um número finito de correções. Finalmente, introduz-se uma estratégia incremental que pode ser usada acoplada com ambos os algoritmos para obter soluções esparsas e também uma aproximação para o “tubo mínimo”que contém os dados. Experimentos numéricos são apresentados e os resultados comparados a outros métodos da literatura. / In this work, we introduce a new formulation for orthogonal regression. The problem is defined as minimization of the empirical risk with respect to a tube loss function de veloped for orthogonal regression, named ρ-insensitive. The method is constructed via an stochastic gradient descent approach. The algorithm can be used in primal or in dual variables. The latter formulation allows the introduction of kernels and soft margins. To the best of our knowledge, this is the first method that allows the introduction of kernels via the so-called “kernel-trick” for orthogonal regression. Also, we present an algorithm to solve the classical regression problem using the ε-insensitive loss function. A conver gence proof that guarantees a finite number of updates is presented for this algorithm. In addition, an incremental strategy algorithm is introduced, which can be used to find sparse solutions and also an approximation to the “minimal tube” containing the data. Numerical experiments are shown and the results compared with other methods.

[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.