Low-dimensional signal structures naturally arise in a large set of applications in various fields such as medical imaging, machine learning, signal, and array processing. A ubiquitous low-dimensional structure in signals and images is sparsity, and a new sampling theory; namely, compressive sensing, proves that the sparse signals and images can be reconstructed from incomplete measurements. The signal recovery is achieved using efficient algorithms such as \ell_1-minimization. Recently, the research focus has spun-off to encompass other interesting low-dimensional signal structures such as group-sparsity and low-rank structure. This thesis considers low-rank matrix recovery (LRMR) from various structured-random measurement ensembles. These results are then employed for the in depth investigation of the classical blind-deconvolution problem from a new perspective, and for the development of a framework for the efficient sampling of correlated signals (the signals lying in a subspace). In the first part, we study the blind deconvolution; separation of two unknown signals by observing their convolution. We recast the deconvolution of discrete signals w and x as a rank-1 matrix wx* recovery problem from a structured random measurement ensemble. The convex relaxation of the problem leads to a tractable semidefinite program. We show, using some of the mathematical tools developed recently for LRMR, that if we assume the signals convolved with one another live in known subspaces, then this semidefinite relaxation is provably effective. In the second part, we design various efficient sampling architectures for signals acquired using large arrays. The sampling architectures exploit the correlation in the signals to acquire them at a sub-Nyquist rate. The sampling devices are designed using analog components with clear implementation potential. For each of the sampling scheme, we show that the signal reconstruction can be framed as an LRMR problem from a structured-random measurement ensemble. The signals can be reconstructed using the familiar nuclear-norm minimization. The sampling theorems derived for each of the sampling architecture show that the LRMR framework produces the Shannon-Nyquist performance for the sub-Nyquist acquisition of correlated signals. In the final part, we study low-rank matrix factorizations using randomized linear algebra. This specific method allows us to use a least-squares program for the reconstruction of the unknown low-rank matrix from the samples of its row and column space. Based on the principles of this method, we then design sampling architectures that not only acquire correlated signals efficiently but also require a simple least-squares program for the signal reconstruction. A theoretical analysis of all of the LRMR problems above is presented in this thesis, which provides the sufficient measurements required for the successful reconstruction of the unknown low-rank matrix, and the upper bound on the recovery error in both noiseless and noisy cases. For each of the LRMR problem, we also provide a discussion of a computationally feasible algorithm, which includes a least-squares-based algorithm, and some of the fastest algorithms for solving nuclear-norm minimization.

Thesis advisor: Joshua E. Greene / We construct taut foliations in every closed 3-manifold obtained by r-framed Dehn surgery along a positive 3-braid knot K in S^3, where r < 2g(K)-1 and g(K) denotes the Seifert genus of K. This confirms a prediction of the L--space conjecture. For instance, we produce taut foliations in every non-L-space obtained by surgery along the pretzel knot P(-2,3,7), and indeed along every pretzel knot P(-2,3,q), for q a positive odd integer. This is the first construction of taut foliations for every non-L-space obtained by surgery along an infinite family of hyperbolic L-space knots. We adapt our techniques to construct taut foliations in every closed 3-manifold obtained along r-framed Dehn surgery along a positive 1-bridge braid, and indeed, along any positive braid knot, in S^3, where r < g(K)-1. These are the only examples of theorems producing taut foliations in surgeries along hyperbolic knots where the interval of surgery slopes is in terms of g(K). / Thesis (PhD) — Boston College, 2020. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Mathematics.

Across scientific and engineering disciplines, the algorithmic pipeline forprocessing and understanding data increasingly revolves around deep learning, a data-driven approach to learning features for tasks that uses high-capacity compositionally-structured models, large datasets, and scalable gradient-based optimization. At the same time, modern deep learning models are resource-inefficient, require up to trillions of trainable parameters to succeed on tasks, and their predictions are notoriously susceptible to perceptually-indistinguishable changes to the input, limiting their use in applications where reliability and safety are critical. Fortunately, data in scientific and engineering applications are not generic, but structured---they possess low-dimensional nonlinear structure that enables statistical learning in spite of their inherent high-dimensionality---and studying the interactions between deep learning models, training algorithms, and structured data represents a promising approach to understand practical issues such as resource efficiency, robustness and invariance in deep learning. To begin to realize this program, it is necessary to have mathematical model problems that capture the nonlinear structures of data in deep learning applications and features of practical deep learning pipelines, and there is a question of how to translate mathematical insights into practical progress on the aforementioned issues, as well. We address these considerations in this thesis. First, we pose and study the multiple manifold problem, a binary classification task modeled on applications in computer vision, in which a deep fully-connected neural network is trained to separate two low-dimensional submanifolds of the unit sphere. We provide an analysis of the one-dimensional case, proving for a rather general family of configurations that when the network depth is large relative to certain geometric and statistical properties of the data, the network width grows as a sufficiently large polynomial in the depth, and the number of samples from the manifolds is polynomial in the depth, randomly-initialized gradient descent rapidly learns to classify the two manifolds perfectly with high probability. Our analysis demonstrates concrete benefits of depth and width in the context of a practically-motivated model problem: the depth acts as a fitting resource, with larger depths corresponding to smoother networks that can more readily separate the class manifolds, and the width acts as a statistical resource, enabling concentration of the randomly-initialized network and its gradients. Next, we turn our attention to the design of specific network architectures for achieving invariance to nuisance transformations in vision systems. Existing approaches to invariance scale exponentially with the dimension of the family of transformations, making them unable to cope with natural variabilities in visual data such as changes in pose and perspective. We identify a common limitation of these approaches---they rely on sampling to traverse the high-dimensional space of transformations---and propose a new computational primitive for building invariant networks based instead on optimization, which in many scenarios provides a provably more efficient method for high-dimensional exploration than sampling. We provide empirical and theoretical corroboration of the efficiency gains and soundness of our proposed method, and demonstrate its utility in constructing an efficient invariant network for a simple hierarchical object detection task when combined with unrolled optimization. Together, the results in this thesis establish the first end-to-end theoretical guarantees for training deep neural networks with data with nonlinear low-dimensional structure, and provide a methodology to translate these insights into the design of practical neural network architectures with efficiency and invariance benefits.

[pt] Automorfismos genéricos de cubos com alças (handlebodies) aparecem do estudo de classes the isotopia de automorfismos de variedades orientáveis de dimensão três. Automorfismos genéricos permanecem como uma das partes menos entendidas desse estudo.Dado um automorfismo genérico de um cubo com alças, é conhecida uma forma de se construir uma laminação bidimensional que é invariante pelo automorfismo. A essa laminação se associa um fator de crescimento. É sabido que, no caso de tal fator de crescimento ser minimal - uma característica importante, pois mede a complexidade essencial do automorfismo - a laminação deve gozar de uma certa propriedade de incompressibilidade. Nessa tese mostramos que o processo de se achar uma laminação com tal propriedade é algoritmico. Por outro lado, mostramos que tal propriedade não garante que o respectivo fator de crescimento seja minimal. Propomos uma outra propriedade, tensão transversal, mais forte que incompressibilidade, que conjecturamos também ser condição necessária para que o fator de crescimento seja minimal. Provamos a conjectura em alguns casos.Além dos resultados mencionados acima, desenvolvemos métodos para gerar automorfismos genéricos de cubos com alcas, que usamos para apresentar alguma variedade de exemplos. / [en] Generic automorphisms of handlebodies appear naturally in the study of isotopy classes of automophisms of orientable three-dimensional manifolds. Generic automorphisms remain as one of the least understood parts of this study. Given a generic automorphism of a handlebody one can construct a bidimensional lamination that is invariant under the automorphism. There is a growth rate associated to this lamination. It is known that, when this growth rate is minimal among all possible choices (an important property, for it measures the essential complexity of the automorphism), the lamination must have a certain incompressibility property. On this thesis we show that the process of finding a lamination with such a property is algorithmic. On the other hand, we show that this said incompressibility property is not sufficient for the minimality of the growth rate. We propose a stronger property, which we called transverse tightness, and conjecture that it is a necessary condition for the growth rate to be minimal. We prove the conjecture in some particular cases. In addition to the results mentioned above, we develop methods to generate generic automorphisms of handlebodies, which we use to present some variety of examples.

Une théorie des champs quantique topologique (TQFT) en dimension 3 est un foncteur monoidal symétrique de la catégorie des cobordismes de dimension 3 vers celle des espaces vectoriels. Une TQFT fournit en particulier un invariant scalaire des variétés fermées de dimension 3 ainsi que des représentations du groupe de difféotopie des surfaces fermées.Turaev explique en 1994 comment construire à partir d'une catégorie modulaire une TQFT qui étend l'invariant scalaire de 3-variétés fermées introduit en 1991 par Reshetikhin et Turaev. Dans cette thèse, nous généralisons cette construction à l'aide d'une catégorie C en ruban avec coend. On représente un cobordisme par un enchevêtrement d'un type particulier (enchevêtrement de cobordisme) et on associe à celui-ci un morphisme défini entre puissances tensorielles de la coend comme décrit par Lyubashenko en 1995. A l'aide de l'extension du calcul de Kirby aux cobordismes de dimension 3, cette construction nous permet de produire un invariant de cobordismes puis une TQFT à valeurs dans la sous-catégorie monoïdale symétrique des objets transparents de C.Dans le cas où C est une catégorie modulaire, cette sous-catégorie s'identifie à celle des espaces vectoriels et on retrouve ainsi la TQFT de Turaev. Dans le cas où C est une catégorie prémodulaire modularisable, notre TQFT est un relèvement de la TQFT de Turaev associée à la modularisée de C. / A 3-dimensional topological quantum field theory (TQFT) is a symmetric monoidal functor from the category of 3-cobordisms to the category of vector spaces. Such TQFTs provide in particular numerical invariants of closed 3-manifolds and representations of the mapping class group of closed surfaces.In 1994, Turaev explains how to construct a TQFT from a modular category; the scalar invariant is then the Reshethikhin-Turaev invariant introduced in 1991. In this thesis, we describe a generalization of this construction starting from a ribbon category C with coend. We present a cobordism by a certain type of tangle (cobordism tangle) and we associate to such a tangle a morphism between tensor products of the coend as described by Lyubashenko in 1994. Extending the Kirby calculus to 3-cobordisms, we obtain in this way an invariant of cobordisms and a TQFT which takes values in the symmetric monoidal subcategory of transparent objects of C. If the category C is modular, this subcategory can be identified with the category of vector spaces, and we recover Turaev's TQFT. If the category C is modularizable, our TQFT is a lift of the Turaev TQFT for the modularization of C.

L'homologie instanton-symplectique est un invariant associé à une variété de dimension trois close orientée, qui a été dé?ni par Manolescu et Woodward, et qui correspond conjecturalement à une version symplectique d'une homologie des instantons de Floer. Dans cette thèse nous étudions le comportement de cet invariant sous l'effet d'une somme connexe, d'une chirurgie de Dehn, et d'un cobordisme de dimension quatre. Nous établissons une formule de Künneth pour la somme connexe : si Y et Y' désignent deux variétés closes orientées de dimension trois, l'homologie instanton-symplectique associée à leur somme connexe est isomorphe à la somme directe du produit tensoriel de leurs groupes d'homologie instantonsymplectique respectifs, et de leur produit de torsion (après décalage des degrés). Nous définissons des versions tordues de cette homologie, et prouvons un analogue de la suite exacte de Floer, reliant les groupes associés à une triade de chirurgie. Cette suite exacte nous permet de calculer le rang des groupes associés à des familles de variétés, notamment les revêtements doubles ramifiés d'entrelacs quasi-alternés, des chirurgies entières de grande pente le long de certains noeuds, ainsi que certaines variétés obtenues par plombage de fibrés en disques au-dessus de sphères. Nous définissons enfin des invariants pour des cobordismes de dimension 4 prenant la forme d'applications entre groupes d'homologie instantonsymplectique des bords, et prouvons que deux des morphismes intervenant dans la suite exacte de chirurgie s'interprètent comme de telles applications, associées aux cobordismes d'attachement d'anses. Nous donnons également un critère d'annulation pour de telles applications associées à des éclatements. / Symplectic instanton homology is an invariant for closed oriented three-manifolds, defined by Manolescu and Woodward, which conjecturally corresponds to a symplectic version of a variant of Floer's instanton homology. In this thesis we study the behaviour of this invariant under connected sum, Dehn surgery, and four-dimensional cobordisms. We prove a Künneth-type formula for the connected sum: let Y and Y' be two closed oriented three-manifolds, we show that the symplectic instanton homology of their connected sum is isomorphic to the direct sum of the tensor product of their symplectic instanton homology, and a shift of their torsion product. We define twisted versions of this homology, and then prove an analog of the Floer exact sequence, relating the invariants of a Dehn surgery triad. We use this exact sequence to compute the rank of the groups associated to branched double covers of quasi-alternating links, some plumbings of disc bundles over spheres, and some integral Dehn surgeries along certain knots. We then define invariants for four dimensional cobordisms as maps between the symplectic instanton homology of the two boundaries. We show that among the three morphisms in the surgery exact sequence, two are such maps, associated to the handle-attachment cobordisms. We also give a vanishing criteria for such maps associated to blow-ups.

No description available.