Compressed Sensing (CS) is an emerging paradigm in which signals are recovered from undersampled nonadaptive linear measurements taken at a rate proportional to the signal's true information content as opposed to its ambient dimension. The resulting problem consists in finding a sparse solution to an underdetermined system of linear equations. It has now been established, both theoretically and empirically, that certain optimization algorithms are able to solve such problems. Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2007), which is the focus of this thesis, is an established CS recovery algorithm which is known to be effective in practice, both in terms of recovery performance and computational efficiency. However, theoretical analysis of IHT to date suffers from two drawbacks: state-of-the-art worst-case recovery conditions have not yet been quantified in terms of the sparsity/undersampling trade-off, and also there is a need for average-case analysis in order to understand the behaviour of the algorithm in practice. In this thesis, we present a new recovery analysis of IHT, which considers the fixed points of the algorithm. In the context of arbitrary matrices, we derive a condition guaranteeing convergence of IHT to a fixed point, and a condition guaranteeing that all fixed points are 'close' to the underlying signal. If both conditions are satisfied, signal recovery is therefore guaranteed. Next, we analyse these conditions in the case of Gaussian measurement matrices, exploiting the realistic average-case assumption that the underlying signal and measurement matrix are independent. We obtain asymptotic phase transitions in a proportional-dimensional framework, quantifying the sparsity/undersampling trade-off for which recovery is guaranteed. By generalizing the notion of xed points, we extend our analysis to the variable stepsize Normalised IHT (NIHT) (Blumensath and Davies, 2010). For both stepsize schemes, comparison with previous results within this framework shows a substantial quantitative improvement. We also extend our analysis to a related algorithm which exploits the assumption that the underlying signal exhibits tree-structured sparsity in a wavelet basis (Baraniuk et al., 2010). We obtain recovery conditions for Gaussian matrices in a simplified proportional-dimensional asymptotic, deriving bounds on the oversampling rate relative to the sparsity for which recovery is guaranteed. Our results, which are the first in the phase transition framework for tree-based CS, show a further significant improvement over results for the standard sparsity model. We also propose a dynamic programming algorithm which is guaranteed to compute an exact tree projection in low-order polynomial time.

abstract: This dissertation draws upon modern Chomskyan theory to address issues surrounding the development of a unified, minimalist account of language as a mental and biological object, both in terms of its generation and historic change. Towards that end, I investigate, apply, and advance the labeling approach to generative syntax. Labeling is a hypothetical process, operating within the confines of phase theory, which is thought to prepare constructed syntactic objects for interpretation at relevant mental interfaces. I argue a number of points applicable to both synchronic and diachronic linguistics: 1) Labeling failures happen as a matter of course during a derivation, forcing re-evaluation of labeled syntactic structures which ultimately leads to a successful derivation. 2) Labeling and its errors do not happen in real-time, but are bounded by phases. This has consequences for how researchers ought to look at notions and limitations of phasal memory. 3) Labeling not only drives an individual’s mature syntax, but has an effect on how children acquire their syntax, causing them in some cases to alter structures and create new categories. This is responsible for many cases of language change, and I support this argument by investigating data from the history of Chinese and Macedonian that are sensitive to labeling-based phenomena. 4) Research into labeling can help us speculate about the evolution of language generally. Although recursion is sometimes thought to be a defining feature of Universal Grammar, labeling in fact is a much more likely candidate in this regard. / Dissertation/Thesis / Doctoral Dissertation English 2016

abstract: In this thesis, I explore Cognate Object Constructions COCs (e.g. The clown "laughed" a creepy "laugh") through three research questions: (1) What verbs can accept Cognate Objects COs? (2) Why can these verbs accept COs and other verbs cannot? and (3) How are COCs derived? I demonstrate that Sorace's Hierarchy sheds light on which verbs can accept COs and which cannot by explaining the discrepancies in grammaticality judgments that exist in the literature. I then argue that Hale and Keyser's Conflation account of COCs is not minimalist because it relies on a phenomenon that can be reduced to Merge. After commenting and repairing their account, I provide an outline for a more minimalist framework, which I refer to as "Problems of Projection Extensions" PoP+, that focuses on MERGE, workspaces, labeling theory, phases, and determinacy. Inside this framework, I then develop my own account that depends on only Internal Merge and the constraint in English against stranded articles. With my account situated in this PoP+ framework, I am able to approach the research questions from a syntactic perspective, arguing that the Unergative Restriction on COCs is a result of a determinacy violation in the derivation of Unaccusative COCs. Finally, I point out that, being situated in the PoP+ framework, my account opens COCs up to further investigation not possible before. / Dissertation/Thesis / Masters Thesis Linguistics and Applied Linguistics 2019

The goal of this thesis is two-fold. On the one hand, it pursues to provide a contribution to the conjugate duality by proposing a new duality concept, which can be understood as an umbrella for different meaningful perturbation methods. On the other hand, this thesis aims to investigate minimax location problems by means of the duality concept introduced in the first part of this work, followed by a numerical approach using epigraphical splitting methods. After summarizing some elements of the convex analysis as well as introducing important results needed later, we consider an optimization problem with geometric and cone constraints, whose objective function is a composition of n+1 functions. For this problem we propose a conjugate dual problem, where the functions involved in the objective function of the primal problem are decomposed. Furthermore, we formulate generalized interior point regularity conditions for strong duality and give necessary and sufficient optimality conditions. As applications of this approach we determine the formulae of the conjugate as well as the biconjugate of the objective function of the primal problem and analyze an optimization problem having as objective function the sum of reciprocals of concave functions. In the second part of this thesis we discuss in the sense of the introduced duality concept three classes of minimax location problems. The first one consists of nonlinear and linear single minimax location problems with geometric constraints, where the maximum of nonlinear or linear functions composed with gauges between pairs of a new and existing points will be minimized. The version of the nonlinear location problem is additionally considered with set-up costs. The second class of minimax location problems deals with multifacility location problems as suggested by Drezner (1991), where for each given point the sum of weighted distances to all facilities plus set-up costs is determined and the maximal value of these sums is to be minimized. As the last and third class the classical multifacility location problem with geometrical constraints is considered in a generalized form where the maximum of gauges between pairs of new facilities and the maximum of gauges between pairs of new and existing facilities will be minimized. To each of these location problems associated dual problems will be formulated as well as corresponding duality statements and necessary and sufficient optimality conditions. To illustrate the results of the duality approach and to give a more detailed characterization of the relations between the location problems and their corresponding duals, we consider examples in the Euclidean space. This thesis ends with a numerical approach for solving minimax location problems by epigraphical splitting methods. In this framework, we give formulae for the projections onto the epigraphs of several sums of powers of weighted norms as well as formulae for the projection onto the epigraphs of gauges. Numerical experiments document the usefulness of our approach for the discussed location problems.