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.

Esta Tesis se enmarca dentro del estudio de las aplicaciones lineales entre subespacios de funciones continuas definidas en espacios métricos y que toman valores en espacios normados. En concreto, el Capítulo 1 está dedicado al estudio de las aplicaciones separadoras entre espacios de funciones absolutamente continuas. En el Capítulo 2 consideramos aplicaciones biseparadoras definidas entre espacios de funciones de Lipschitz. Por otro lado, las isometrías entre espacios de funciones de Lipschitz se estudian en el Capítulo 3 y, finalmente, analizaremos las aplicaciones que preservan ceros comunes entre ciertos subespacios de funciones continuas que incluyen, entre otros, los mencionados anteriormente.Así, nuestro objetivo es proporcionar algunos resultados acerca de la representación de las aplicaciones lineales consideradas. Además, observamos que la continuidad de las aplicaciones biseparadoras y de las que preservan ceros comunes se puede deducir de manera automática bajo ciertas condiciones. / In this Thesis we deal with linear maps between subspaces of continuous functions defined on metric spaces and taking values in normed spaces. In particular, the Chapter 1 is devoted to study separating maps between spaces of absolutely continuous functions. In Chapter 2 we consider biseparating maps between Lipschitz function spaces. On the other hand, the isometries between spaces of Lipschitz functions are studied in Chapter 3 and, finally, we consider maps preserving common zeros between some subspaces of continuous functions, which include the subspaces given above.Therefore, our aim is providing some results about the representation of each linear map that we consider in this Thesis. Besides, the automatic continuity of biseparating maps and maps preserving common zeros is derived in some cases.

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

Ma thèse se situe à l'intersection de \textit {la théorie des groupes géométrique} et \textit{la théorie des groupes mesurée}. Une question majeure dans la théorie des groupes géométrique est d'étudier la classe de quasi-isométrie (QI) et la classe d'équivalence mesurée (ME) d'un groupe, respectivement. $L^p$-équivalence mesurée est une relation d'équivalence qui est définie en ajoutant des contraintes géométriques avec d'équivalence mesurée. En plus, QI est une condition géométrique. Il est une question naturelle, si deux groupes sont QI et ME, si elles sont $L^p$-ME pour certains $p>0$. Dans mon premier article, en collaboration avec R. Tessera, nous répondons négativement à cette question pour $p\geq 1$, montrant que l'extension centrale canonique d'un groupe surface de genre plus élevé ne sont pas $L^1$-ME pour le produit direct de ce groupe de surface avec $\mathbb{Z}$ (alors qu'ils sont à la fois quasi-isométrique et équivalente mesurée).Dans mon deuxième papier, j'ai observé un lien général entre la géométrie des expandeurs, defini comme une séquence des quotients finis ( l'espace de boîte) d'un groupe finiment engendré, et les propriétés mesurée theorique du groupe. Plus précisément, je l'ai prouvé que si deux <<espaces de boîte>> sont quasi-isométrique, les groupes correspondants doivent être <<mesurée équivalente uniformément >>, une notion qui combine à la fois QI et ME. Je prouve aussi une version de ce résultat pour le plongement grossière, ce qui permet de distinguer plusieurs classe des expandeurs. Par exemple, je montre que les expandeurs associé à $SL(m, \mathbb{Z})$ ne grossièrement plongent à les expandeurs associés à $SL_n(\mathbb{Z})$ si $m>n$. / My thesis lies at the intersection of \textit{geometric group theory} and \textit{measured group theory}. A major question in geometric group theory is to study the quasi-isometry (QI) class and the measure equivalence (ME) class of a group, respectively. $L^p$-measure equivalence is an equivalence relation which is defined by adding some geometric constraints with measure equivalence. Besides, quasi-isometry is a geometric condition. It is a natural question if two groups are QI and ME, whether they are $L^p$-ME for some $p>0$. In my first paper, together with R. Tessera, we answer this question negatively for $p\geq 1$, showing that the canonical central extension of a surface group of higher genus is not $L^1$-ME to the direct product of this surface group with $\mathbb{Z}$ (while they are both quasi-isometric and measure equivalent). In my second paper, I observed a general link between the geometry of expanders arising as a sequence of finite quotients (box space) of a finitely generated group, and the measured theoretic properties of the group. More precisely, I proved that if two box spaces' are quasi-isometric, then the corresponding groups must be `uniformly measure equivalent', a notion that combines both quasi-isometry and measure equivalence. I also prove a version of this result for coarse embedding, allowing to distinguish many classes of expanders. For instance, I show that the expanders associated to $SL(m,\mathbb{Z})$ do not coarsely embed inside the expanders associated to $SL_n(\mathbb{Z}$ if $m>n$.

La reconstruction 3D monoculaire déformable est le problème général d'estimation de forme 3D d'un objet déformable à partir d'images 2D. Plusieurs scénarios ont émergé : le Shape-from-Template (SfT) et le Non-Rigid Structure-from-Motion (NRSfM) sont deux approches qui ont été grandement étudiées pour leur applicabilité. La première utilise une seule image qui montre un objet se déformant et un patron (une forme 3D texturée de l'objet dans une pose de référence). La seconde n'utilise pas de patron, mais utilise plusieurs images et estime la forme 3D dans chaque image. Les deux approches s'appuient sur le mouvement de points de correspondances entre les images et sur des a priori de déformations, restreignant ainsi leur utilisation à des surfaces texturées qui se déforment de manière lisse. Cette thèse fait avancer l'état de l'art du SfT et du NRSfM dans deux directions. La première est l'étude du SfT dans le cas de patrons 1D (c’est-à-dire des courbes comme des cordes et des câbles). La seconde direction est le développement d'algorithmes de SfT et de NRSfM qui exploitent plusieurs indices visuels et qui résolvent des cas réels et complexes non-résolus précédemment. Nous considérons des déformations isométriques et reconstruisons la partie extérieure de l'objet. Les contributions techniques et scientifiques de cette thèse sont divisées en quatre parties.La première partie de cette thèse étudie le SfT curvilinéaire, qui est le cas du patron curvilinéaire plongé dans un espace 2D ou 3D. Nous proposons une analyse théorique approfondie et des solutions pratiques pour le SfT curvilinéaire. Malgré son apparente simplicité, le SfT curvilinéaire s'est avéré être un problème complexe : il ne peut pas être résolu à l'aide de solutions locales non-holonomes d'une équation différentielle ordinaire et ne possède pas de solution unique, mais un nombre fini de solutions ambiguës. Une contribution technique majeure est un algorithme basé sur notre théorie, qui génère toutes les solutions ambiguës. La deuxième partie de cette thèse traite d'une limitation des méthodes de SfT : la reconstruction de plis. Cette limitation vient de la parcimonie de la contrainte de mouvement et de la régularisation. Nous proposons deux contributions qui s'appuient sur un cadre de minimisation d'énergie non-convexe. Tout d'abord, nous complétons la contrainte de mouvement avec une contrainte robuste de bord. Ensuite, nous modélisons implicitement les plis à l'aide d'une représentation dense de la surface basée maillage et d'une contrainte robuste de lissage qui désactive automatiquement le lissage de la courbure sans connaître a priori la position des plis.La troisième partie de cette thèse est dédiée à une autre limitation du SfT : la reconstruction de surfaces peu texturées. Cette limitation vient de la difficulté d'obtenir des correspondances (parcimonieuses ou denses) sur des surfaces peu texturées. Comme l'ombrage révèle les détails sur des surfaces peu texturées, nous proposons de combiner l'ombrage avec le SfT. Nous présentons deux contributions. La première est une initialisation en cascade qui estime séquentiellement la déformation de la surface, l'illumination de la scène, la réponse de la caméra et enfin les albédos de la surface à partir d'images monoculaires où la surface se déforme. La seconde est l'intégration de l'ombrage à notre précédent cadre de minimisation d'énergie afin de raffiner simultanément les paramètres photométriques et de déformation.La dernière partie de cette thèse relâche la connaissance du patron et aborde deux limitations du NRSfM : la reconstruction de surfaces peu texturées avec des plis. Une contribution majeure est l'extension du second cadre d'optimisation pour la reconstruction conjointe de la forme 3D de la surface sur toutes les images d'entrée et des albédos de la surface sans en connaître un patron. / Monocular deformable 3D reconstruction is the general problem of recovering the 3D shape of a deformable object from monocular 2D images. Several scenarios have emerged: the Shape-from-Template (SfT) and the Non-Rigid Structure-from-Motion (NRSfM) are two approaches intensively studied for their practicability. The former uses a single image depicting the deforming object and a template (a textured 3D shape of this object in a reference pose). The latter does not use a template, but uses several images and recovers the 3D shape in each image. Both approaches rely on the motion of correspondences between the images and deformation priors, which restrict their use to well-textured surfaces which deform smoothly. This thesis advances the state-of-the-art in SfT and NRSfM in two main directions. The first direction is to study SfT for the case of 1D templates (i.e. curved, thin structures such as ropes and cables). The second direction is to develop algorithms in SfT and NRSfM that exploit multiple visual cues and can solve complex, real-world cases which were previously unsolved. We focus on isometric deformations and reconstruct the outer part of the object. The technical and scientific contributions of this thesis are divided into four parts. The first part of this thesis studies the case of a curvilinear template embedded in 2D or 3D space, referred to Curve SfT. We propose a thorough theoretical analysis and practical solutions for Curve SfT. Despite its apparent simplicity, Curve SfT appears to be a complex problem: it cannot be solved locally using exact non-holonomic partial differential equation and is only solvable up to a finite number of ambiguous solutions. A major technical contribution is a computational solution based on our theory, which generates all the ambiguous solutions.The second part of this thesis deals with a limitation of SfT methods: reconstructing creases. This is due to the sparsity of the motion constraint and regularization. We propose two contributions which rely on a non-convex energy minimization framework. First, we complement the motion constraint with a robust boundary contour constraint. Second, we implicitly model creases with a dense mesh-based surface representation and an associated robust smoothing constraint, which deactivates curvature smoothing automatically where needed, without knowing a priori the crease location. The third part of this thesis is dedicated to another limitation of SfT: reconstructing poorly-textured surfaces. This is due to correspondences which cannot be obtained so easily on poorly-textured surfaces (either sparse or dense). As shading reveals details on poorly-textured surfaces, we propose to combine shading and SfT. We have two contributions. The first is a cascaded initialization which estimates sequentially the surface's deformation, the scene illumination, the camera response and then the surface albedos from deformed monocular images. The second is to integrate shading to our previous energy minimization framework for simultaneously refining deformation and photometric parameters.The last part of this thesis relaxes the knowledge of the template and addresses two limitations of NRSfM: reconstructing poorly-textured surfaces with creases. Our major contribution is an extension of the second framework to recover jointly the 3D shapes of all input images and the surface albedos without any template.