The object of this thesis is the study of constrained measurement systems of signals having low-dimensional structure using analytic tools from Compressed Sensing (CS). Realistic measurement systems usually have architectural constraints that make them differ from their idealized, well-studied counterparts. Nonetheless, these measurement systems can exploit structure in the signals that they measure. Signals considered in this research have low-dimensional structure and can be broken down into two types: static or dynamic. Static signals are either sparse in a specified basis or lying on a low-dimensional manifold (called manifold-modeled signals). Dynamic signals, exemplified as states of a dynamical system, either lie on a low-dimensional manifold or have converged onto a low-dimensional attractor. In CS, the Restricted Isometry Property (RIP) of a measurement system ensures that distances between all signals of a certain sparsity are preserved. This stable embedding ensures that sparse signals can be distinguished one from another by their measurements and therefore be robustly recovered. Moreover, signal-processing and data-inference algorithms can be performed directly on the measurements instead of requiring a prior signal recovery step. Taking inspiration from the RIP, this research analyzes conditions on realistic, constrained measurement systems (of the signals described above) such that they are stable embeddings of the signals that they measure. Specifically, this thesis focuses on four different types of measurement systems. First, we study the concentration of measure and the RIP of random block diagonal matrices that represent measurement systems constrained to make local measurements. Second, we study the stable embedding of manifold-modeled signals by existing CS matrices. The third part of this thesis deals with measurement systems of dynamical systems that produce time series observations. While Takens' embedding result ensures that this time series output can be an embedding of the dynamical systems' states, our research establishes that a stronger stable embedding result is possible under certain conditions. The final part of this thesis is the application of CS ideas to the study of the short-term memory of neural networks. In particular, we show that the nodes of a recurrent neural network can be a stable embedding of sparse input sequences.

Made available in DSpace on 2015-03-03T15:28:33Z (GMT). No. of bitstreams: 1 CatiaRSS_DISSERT.pdf: 4951076 bytes, checksum: 0231a1261bda878faaaf3e30a97857a0 (MD5) Previous issue date: 2012-11-27 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Um dos temas mais populares no tratamento de dados nos ?ltimos dez anos gira em torno da descoberta que a recupera??o de sinais esparsos em sistemas lineares, pode ser feita com um n?mero de equa??es bem menor que o n?mero de vari?veis. Em linhas gerais, se A = AmN, queremos resolver Ax = b e procuramos solu??es esparsas, ou seja, com apenas s << N entradas n~ao-nulas em algum sistema de coordenadas, isto pode ser feito com um n?mero de equa??es m << N, minimizando a norma l1 de x, sujeito ? restri??o Ax = b + r, sob determinadas condi??es (8). Vale dizer, com muito menos equa??es que incognitas. D? o nome de Magica l1" para esta possibilidade de recuperar um sinal esparso, resolvendo um problema de otimiza??o convexa com relativamente poucas restri??es. Para algumas poucas matrizes A, de grande import?ncia em aplica??es, ha teorias razoavelmente estabelecidas indicando esta possibilidade, para muitas n?o. O objetivo desta disserta??o e situar e discutir casos nos quais a Magica l1" funciona, com foco nas rela??es entre a esparsidade s, o n?mero de linhas m e o n?mero de vari?veis N, para algumas matrizes importantes e associadas ? codifica??o de imagens 2D. Em particular, realizamos testes num?ricos com tr?s matrizes A, visando encontrar empiricamente rela??es entre s, m e N para as quais a Magica l1 e bem sucedida. Em duas delas, ha teorias matematicas, ainda em constru??o, indicando condic~oes de sucesso, grosso modo, na forma de m=s C log(N=s), sempre com alguma probabilidade de insucesso associada. Listamos inicialmente A = G, formada por entradas aleatorias com distribui??o gaussiana i.i.d., de media zero e colunas aproximadamente unitarias. A segunda e a transformada de Fourier, que usaremos numa vers~ao de transformada de cossenos 2D. A denotamos por A = DCT. Para probabilidades esmagadoras" de sucesso na recupera??o de sinais esparsos com G, usando a Magica l1", os resultados te?ricos estabelecem regi?es menores, vale dizer, valores mais elevados para a constante C. Se relaxamos um pouco esta exig?ncia de sucesso, obtemos regi?es mais amplas, conforme teremos oportunidade de discutir na disserta ??o. m=s C log(N=s) ainda e uma conjectura no caso de Fourier, se queremos probabilidades esmagadoras" de sucesso na recupera??o de sinais esparsos pela via da otimiza??o convexa acima prescrita. Os resultados emp?ricos por nos obtidos para iv estas duas matrizes ainda s~ao muito preliminares, mas se ajustam bem , via quadrados m??nimos, a m=s C log(s=N), com C em 1:6 e em 1, correspondendo aos resultados mais otimistas encontrados na literatura para G e DCT, nos quais a eficacia da Magica l1" e assumida num sentido mais fraco, no sentido de permitir alguma taxa de insucesso n~ao totalmente desprez??vel, porem de forma probabilisticamente controlada. No caso da matriz da transformada de Radon, n?o ha previs~ao teorica consolidada para o funcionamento daMagica l1" e sequer encontramos conjecturas sobre o que se pode esperar. Em nossos testes com matrizes de Radon, encontramos uma regi~ao para a validade da Magica l1", cujo ajuste de quadrados m??nimos a m=s C log(s=N) se deu com 2; 5 e C 0; 29