Orientador: Renato da Rocha LopesDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de ComputaçãoResumo: A representação esparsa de sinais usando dicionários sobrecompletos tem se mostrado uma ferramenta poderosa com aplicações em remoção de ruído, restauração, compressão, reconstrução e outras. Classicamente isto é feito com dicionários analíticos, como DCT ou wavelets, que permitem capturar a estrutura global de um sinal e dão lugar a implementações rápidas. Em contrapartida, pode-se utilizar um dicionário dito aprendido, que se adapta melhor à classe de sinais em questão. A desvantagem é uma carga computacional mais elevada, visto que os dicionários aprendidos são a princípio representados por matrizes não estruturadas. Isto restringe sua aplicação a sinais de tamanho relativamente reduzido. Nesta dissertação, propomos a introdução de uma certo grau de estrutura nos dicionário aprendidos, de forma reduzir a complexidade em operações envolvendo a matriz dicionário. Duas abordagens distintas são introduzidas para atingir esse objetivo. Primeiro, propomos a utilização do conceito de "Displacement Structure" para quantificar o nível de estrutura do dicionário. Segundo, nós restringimos o aprendizado a dicionários representados como uma soma de produtos de Kronecker de sub-dicionários menores. Além do reduzido custo no produto matriz-vetor, os dicionários obtidos também requerem uma menor quantidade de amostras no treinamento e um menor espaço de armazenamento se comparado a dicionários sem estrutura. Alguns experimentos de remoção de ruído em imagem são realizados de forma a validar as técnicas propostasAbstract: Sparse representation of signals using learned overcomplete dictionaries has proven to be a powerful tool with applications in denoising, restoration, compression, reconstruction, and more. The modern learned dictionaries stand in opposition to classic transforms usually called analytical dictionaries (e.g DCT, wavelets). While the latter permit to capture the global structure of a signal and allow a fast implementation, the former often perform better in applications as the learning process allows them to adapt to the considered class of signals. The drawback is a much higher computational load, since learned dictionaries are a priori represented by unstructured matrices and, therefore, their use is limited to signals of relatively small size. In this work, we introduce some degree of structure on the trained dictionary in order to obtain complexity gains on operations involving the dictionary matrix. To achieve this goal, two different approaches are introduced. First, we propose to use the Displacement Structure concept to quantify the dictionary's structure. Alternatively, we may constrain the dictionary to be a sum of Kronecker products of smaller sub-dictionaries. In addition to reduced matrix-vector multiplication costs, the obtained dictionaries also require less training data and storage space than their unstructured counterpart. Some image denoising experiments are provided to validate the proposed techniquesMestradoTelecomunicações e TelemáticaMestre em Engenharia ElétricaCAPES