Spelling suggestions: "subject:"restricted isometric property"" "subject:"estricted isometric property""
1 |
Constrained measurement systems of low-dimensional signalsYap, Han Lun 20 December 2012 (has links)
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.
|
2 |
Recupera??o de sinais esparsos. Investiga??o num?rica sobre a quantidade de medidas necess?rias para recuperar um sinal esparsoSilva, Catia Regina dos Santos 27 November 2012 (has links)
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
|
Page generated in 0.0972 seconds