A geometric analysis of convex demixing

Demixing is the task of identifying multiple signals given only their sum and prior information about their structures. Examples of demixing problems include (i) separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis; (ii) decomposing an observed matrix into low-rank and sparse components; and (iii) identifying a binary codeword with impulsive corruptions. This thesis describes and analyzes a convex optimization framework for solving an array of demixing problems.

Our framework includes a random orientation model for the constituent signals that ensures the structures are incoherent. This work introduces a summary parameter, the statistical dimension, that reflects the intrinsic complexity of a signal. The main result indicates that the difficulty of demixing under this random model depends only on the total complexity of the constituent signals involved: demixing succeeds with high probability when the sum of the complexities is less than the ambient dimension; otherwise, it fails with high probability.

The fact that a phase transition between success and failure occurs in demixing is a consequence of a new inequality in conic integral geometry. Roughly speaking, this inequality asserts that a convex cone behaves like a subspace whose dimension is equal to the statistical dimension of the cone. When combined with a geometric optimality condition for demixing, this inequality provides precise quantitative information about the phase transition, including the location and width of the transition region.

Mathematical study of complex networks : brain, internet, and power grid

The dissertation is concerned with the mathematical study of various network problems. First, three real-world networks are considered: (i) the human brain network (ii) communication networks, (iii) electric power networks. Although these networks perform very different tasks, they share similar mathematical foundations. The high-level goal is to analyze and/or synthesis each of these systems from a “control and optimization” point of view. After studying these three real-world networks, two abstract network problems are also explored, which are motivated by power systems. The first one is “flow optimization over a flow network” and the second one is “nonlinear optimization over a generalized weighted graph”. The results derived in this dissertation are summarized below.

Brain Networks: Neuroimaging data reveals the coordinated activity of spatially distinct brain regions, which may be represented mathematically as a network of nodes (brain regions) and links (interdependencies). To obtain the brain connectivity network, the graphs associated with the correlation matrix and the inverse covariance matrix—describing marginal and conditional dependencies between brain regions—have been proposed in the literature. A question arises as to whether any of these graphs provides useful information about the brain connectivity. Due to the electrical properties of the brain, this problem will be investigated in the context of electrical circuits. First, we consider an electric circuit model and show that the inverse covariance matrix of the node voltages reveals the topology of the circuit. Second, we study the problem of finding the topology of the circuit based on only measurement. In this case, by assuming that the circuit is hidden inside a black box and only the nodal signals are available for measurement, the aim is to find the topology of the circuit when a limited number of samples are available. For this purpose, we deploy the graphical lasso technique to estimate a sparse inverse covariance matrix. It is shown that the graphical lasso may find most of the circuit topology if the exact covariance matrix is well-conditioned. However, it may fail to work well when this matrix is ill-conditioned. To deal with ill-conditioned matrices, we propose a small modification to the graphical lasso algorithm and demonstrate its performance. Finally, the technique developed in this work will be applied to the resting-state fMRI data of a number of healthy subjects.

Communication Networks: Congestion control techniques aim to adjust the transmission rates of competing users in the Internet in such a way that the network resources are shared efficiently. Despite the progress in the analysis and synthesis of the Internet congestion control, almost all existing fluid models of congestion control assume that every link in the path of a flow observes the original source rate. To address this issue, a more accurate model is derived in this work for the behavior of the network under an arbitrary congestion controller, which takes into account of the effect of buffering (queueing) on data flows. Using this model, it is proved that the well-known Internet congestion control algorithms may no longer be stable for the common pricing schemes, unless a sufficient condition is satisfied. It is also shown that these algorithms are guaranteed to be stable if a new pricing mechanism is used.

Electrical Power Networks: Optimal power flow (OPF) has been one of the most studied problems for power systems since its introduction by Carpentier in 1962. This problem is concerned with finding an optimal operating point of a power network minimizing the total power generation cost subject to network and physical constraints. It is well known that OPF is computationally hard to solve due to the nonlinear interrelation among the optimization variables. The objective is to identify a large class of networks over which every OPF problem can be solved in polynomial time. To this end, a convex relaxation is proposed, which solves the OPF problem exactly for every radial network and every meshed network with a sufficient number of phase shifters, provided power over-delivery is allowed. The concept of “power over-delivery” is equivalent to relaxing the power balance equations to inequality constraints.

Flow Networks: In this part of the dissertation, the minimum-cost flow problem over an arbitrary flow network is considered. In this problem, each node is associated with some possibly unknown injection, each line has two unknown flows at its ends related to each other via a nonlinear function, and all injections and flows need to satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which always finds the optimal injections. A primary application of this work is in the OPF problem. The results of this work on GNF prove that the relaxation on power balance equations (i.e., load over-delivery) is not needed in practice under a very mild angle assumption.

Generalized Weighted Graphs: Motivated by power optimizations, this part aims to find a global optimization technique for a nonlinear optimization defined over a generalized weighted graph. Every edge of this type of graph is associated with a weight set corresponding to the known parameters of the optimization (e.g., the coefficients). The motivation behind this problem is to investigate how the (hidden) structure of a given real/complex valued optimization makes the problem easy to solve, and indeed the generalized weighted graph is introduced to capture the structure of an optimization. Various sufficient conditions are derived, which relate the polynomial-time solvability of different classes of optimization problems to weak properties of the generalized weighted graph such as its topology and the sign definiteness of its weight sets. As an application, it is proved that a broad class of real and complex optimizations over power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.

Fracture of materials undergoing solid-solid phase transformation

A large number of technologically important materials undergo solid-solid phase transformations. Examples range from ferroelectrics (transducers and memory devices), zirconia (Thermal Barrier Coatings) to nickel superalloys and (lithium) iron phosphate (Li-ion batteries). These transformations involve a change in the crystal structure either through diffusion of species or local rearrangement of atoms. This change of crystal structure leads to a macroscopic change of shape or volume or both and results in internal stresses during the transformation. In certain situations this stress field gives rise to cracks (tin, iron phosphate etc.) which continue to propagate as the transformation front traverses the material. In other materials the transformation modifies the stress field around cracks and effects crack growth behavior (zirconia, ferroelectrics). These observations serve as our motivation to study cracks in solids undergoing phase transformations. Understanding these effects will help in improving the mechanical reliability of the devices employing these materials.

In this thesis we present work on two problems concerning the interplay between cracks and phase transformations. First, we consider the directional growth of a set of parallel edge cracks due to a solid-solid transformation. We conclude from our analysis that phase transformations can lead to formation of parallel edge cracks when the transformation strain satisfies certain conditions and the resulting cracks grow all the way till their tips cross over the phase boundary. Moreover the cracks continue to grow as the phase boundary traverses into the interior of the body at a uniform spacing without any instabilities. There exists an optimal value for the spacing between the cracks. We ascertain these conclusion by performing numerical simulations using finite elements.

Second, we model the effect of the semiconducting nature and dopants on cracks in ferroelectric perovskite materials, particularly barium titanate. Traditional approaches to model fracture in these materials have treated them as insulators. In reality, they are wide bandgap semiconductors with oxygen vacancies and trace impurities acting as dopants. We incorporate the space charge arising due the semiconducting effect and dopant ionization in a phase field model for the ferroelectric. We derive the governing equations by invoking the dissipation inequality over a ferroelectric domain containing a crack. This approach also yields the driving force acting on the crack. Our phase field simulations of polarization domain evolution around a crack show the accumulation of electronic charge on the crack surface making it more permeable than was previously believed so, as seen in recent experiments. We also discuss the effect the space charge has on domain formation and the crack driving force.

Optimal uncertainty quantification via convex optimization and relaxation

Many engineering applications face the problem of bounding the expected value of a quantity of interest (performance, risk, cost, etc.) that depends on stochastic uncertainties whose probability distribution is not known exactly. Optimal uncertainty quantification (OUQ) is a framework that aims at obtaining the best bound in these situations by explicitly incorporating available information about the distribution. Unfortunately, this often leads to non-convex optimization problems that are numerically expensive to solve.

This thesis emphasizes on efficient numerical algorithms for OUQ problems. It begins by investigating several classes of OUQ problems that can be reformulated as convex optimization problems. Conditions on the objective function and information constraints under which a convex formulation exists are presented. Since the size of the optimization problem can become quite large, solutions for scaling up are also discussed. Finally, the capability of analyzing a practical system through such convex formulations is demonstrated by a numerical example of energy storage placement in power grids.

When an equivalent convex formulation is unavailable, it is possible to find a convex problem that provides a meaningful bound for the original problem, also known as a convex relaxation. As an example, the thesis investigates the setting used in Hoeffding's inequality. The naive formulation requires solving a collection of non-convex polynomial optimization problems whose number grows doubly exponentially. After structures such as symmetry are exploited, it is shown that both the number and the size of the polynomial optimization problems can be reduced significantly. Each polynomial optimization problem is then bounded by its convex relaxation using sums-of-squares. These bounds are found to be tight in all the numerical examples tested in the thesis and are significantly better than Hoeffding's bounds.

A mulher no mercado de trabalho em Portugal e no Brasil: a procura de um espaço de igualdade de oportunidades

O presente trabalho académico aborda a situação e a relação da mulher no mercado de trabalho. Propomo-nos perceber como funciona a dinâmica do mundo do trabalho e que impacto traz nas relações sociais do indivíduo e na identidade de um país. A questão fundamental deste estudo, é se a desigualdade de oportunidades afecta diferentemente em relação ao género e como é vivida essa situação em cada um dos países estudados: Portugal e Brasil. Centramo-nos especificamente, nos seguintes objectivos: identificar os agentes que determinam a existência da discriminação sexual no mercado de trabalho, reforçar a importância de combater situações discriminatórias para o desenvolvimento de sociedades benéficas, justas e equitativas e finalmente promover o intercâmbio de conhecimentos entre Portugal e Brasil. Com este trabalho de pesquisa teórico-histórica e empírica, concluímos que a desigualdade de oportunidades existe em ambos os países participantes. Deriva primordialmente, de factores económicos, históricos e culturais ainda enraizados nas sociedades actuais. Nitidamente a mulher, ainda hoje, é vítima de uma entrada e presença no mercado de trabalho mais difícil e precária comparativamente ao homem.

Lehiaketa motor baten atzealde-suspentsio sistema doigarri baten elementuen diseinua

[EU]Proiektu hau lehiaketa motor baten atzealde-suspentsio sistema doigarri baten elementuen diseinuan datza. Luzeran erregulagarria izango den tirantea eta suspentsio triangelua diseinatu eta optimizatuko dira. Diseinuak ahalik eta pisu txikiena izatea ahalbidetzen duten makinen elementuak (errotulak eta errodamenduak) aukeratuko dira. Lanaren garapenerako Motostudent izeneko lehiaketatik hartutako datu errealak erabiliko dira. Suspentsio sistemaren diseinua Creo2.0 (lehengo Pro-Engineer) software-arekin egingo da. Bestalde, beste software batzuk ere erabiliko dira, hala nola, Working Model 2D eta ANSYS, sistemaren analisia errazteko.

Classificação étnico-racial e ações afirmativas no contexto do vestibular

Os conceitos de raça e etnia são basilares para a antropologia desde o seu surgimento como área do conhecimento humano e, ainda hoje, são fundamentais para diversos debates nas esferas política, social e das ciências humanas em geral. No pensamento social brasileiro muitos foram os autores de diversas áreas a se debruçarem sobre a questão racial. A instituição do sistema de cotas para o ingresso em universidades acalorou e expandiu o debate tanto no senso comum como na academia e nos meios de comunicação em geral. Essa pesquisa partiu da intenção de investigar a relação entre as ações afirmativas e as identidades de cor/raça. Como metodologia, utilizamos os recursos tanto dos instrumentos quantitativos como qualitativos. Nosso foco foram estudantes do cursinho pré-vestibular Grupo Perspectiva Integral (GPI). Buscamos acessar o ponto de vista dos vestibulandos, seus significados e associações acerca de suas identidades étnico-raciais, opiniões e sentimentos sobre a questão racial no Brasil e, em especial referente às ações afirmativas no contexto da educação e investigar a relação entre quem sou eu e qual é a minha cor/raça no universo proposto. Para tanto, foram aplicados cento e vinte e um questionários e realizadas doze entrevistas. A intenção não era estabelecer uma relação direta e causal entre as ações afirmativas e as identidades de cor/raça e, sim, traçar um perfil geral e racial da população estudada, perceber e analisar diversos elementos referentes às classificações de cor/raça e opiniões e sentimentos acerca das ações afirmativas, do racismo e das expectativas profissionais dos vestibulandos.

Information-theoretic Studies and Capacity Bounds: Group Network Codes and Energy Harvesting Communication Systems

Network information theory and channels with memory are two important but difficult frontiers of information theory. In this two-parted dissertation, we study these two areas, each comprising one part. For the first area we study the so-called entropy vectors via finite group theory, and the network codes constructed from finite groups. In particular, we identify the smallest finite group that violates the Ingleton inequality, an inequality respected by all linear network codes, but not satisfied by all entropy vectors. Based on the analysis of this group we generalize it to several families of Ingleton-violating groups, which may be used to design good network codes. Regarding that aspect, we study the network codes constructed with finite groups, and especially show that linear network codes are embedded in the group network codes constructed with these Ingleton-violating families. Furthermore, such codes are strictly more powerful than linear network codes, as they are able to violate the Ingleton inequality while linear network codes cannot. For the second area, we study the impact of memory to the channel capacity through a novel communication system: the energy harvesting channel. Different from traditional communication systems, the transmitter of an energy harvesting channel is powered by an exogenous energy harvesting device and a finite-sized battery. As a consequence, each time the system can only transmit a symbol whose energy consumption is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is random, instantaneous, and has memory. Furthermore, naturally, the energy harvesting process is observed causally at the transmitter, but no such information is provided to the receiver. Both of these features pose great challenges for the analysis of the channel capacity. In this work we use techniques from channels with side information, and finite state channels, to obtain lower and upper bounds of the energy harvesting channel. In particular, we study the stationarity and ergodicity conditions of a surrogate channel to compute and optimize the achievable rates for the original channel. In addition, for practical code design of the system we study the pairwise error probabilities of the input sequences.

Desigualdades de género en los trabajos : el caso de la CAE.

Este trabajo analiza los avances logrados y las desigualdades existentes en el mercado laboral y en el trabajo no remunerado con respecto a las mujeres, con especial incidencia en la C.A. de Euskadi. En primer lugar, se reflexiona de forma general sobre las medidas promovidas desde distintos niveles: europeo, estatal y de la C.A. de Euskadi, y la evolución que ha ido experimentando la sociedad para fomentar la igualdad entre mujeres y hombres. En segundo lugar, se hace un recorrido a través de los análisis teóricos de la desigualdad. En tercer lugar, se analiza la situación laboral de las mujeres vascas en comparación con la de los hombres, con especial atención en el trabajo no remunerado, la actividad laboral, el paro y los salarios. Finalmente, quedan planteadas una serie de conclusiones a las que se llega tras realizar el análisis.

Three essays on economics and information shocks

A person living in an industrialized society has almost no choice but to receive information daily with negative implications for himself or others. His attention will often be drawn to the ups and downs of economic indicators or the alleged misdeeds of leaders and organizations. Reacting to new information is central to economics, but economics typically ignores the affective aspect of the response, for example, of stress or anger. These essays present the results of considering how the affective aspect of the response can influence economic outcomes.

The first chapter presents an experiment in which individuals were presented with information about various non-profit organizations and allowed to take actions that rewarded or punished those organizations. When social interaction was introduced into this environment an asymmetry between rewarding and punishing appeared. The net effects of punishment became greater and more variable, whereas the effects of reward were unchanged. The individuals were more strongly influenced by negative social information and used that information to target unpopular organizations. These behaviors contributed to an increase in inequality among the outcomes of the organizations.

The second and third chapters present empirical studies of reactions to negative information about local economic conditions. Economic factors are among the most prevalent stressors, and stress is known to have numerous negative effects on health. These chapters document localized, transient effects of the announcement of information about large-scale job losses. News of mass layoffs and shut downs of large military bases are found to decrease birth weights and gestational ages among babies born in the affected regions. The effect magnitudes are close to those estimated in similar studies of disasters.

Preliminary surveys of the fish and fisheries of the Nzoia, Nyando and Sondu Miriu rivers, Kenya

Three Lake Victoria rivers were sampled to assess fish abundance and distribution in preparation for assessment of catches from the river systems. Preliminary fish abundance data indicate that fishing potential upstream is negligible but that important commercial species are present in the downstream floodplain areas. Three catfish species were recorded in the Nzoia river system that have not been found previously in the Kenyan sector of the Lake Victoria system, together with possibly two undescribed Barbus species.

Eigenvalue problems associated with Korn's inequalities in the theory of elasticity

Interest in the possible applications of a priori inequalities in linear elasticity theory motivated the present investigation. Korn's inequality under various side conditions is considered, with emphasis on the Korn's constant. In the "second case" of Korn's inequality, a variational approach leads to an eigenvalue problem; it is shown that, for simply-connected two-dimensional regions, the problem of determining the spectrum of this eigenvalue problem is equivalent to finding the values of Poisson's ratio for which the displacement boundary-value problem of linear homogeneous isotropic elastostatics has a non-unique solution.

Previous work on the uniqueness and non-uniqueness issue for the latter problem is examined and the results applied to the spectrum of the Korn eigenvalue problem. In this way, further information on the Korn constant for general regions is obtained.

A generalization of the "main case" of Korn's inequality is introduced and the associated eigenvalue problem is a gain related to the displacement boundary-value problem of linear elastostatics in two dimensions.

A Direct Approach to Robustness Optimization

This dissertation reformulates and streamlines the core tools of robustness analysis for linear time invariant systems using now-standard methods in convex optimization. In particular, robust performance analysis can be formulated as a primal convex optimization in the form of a semidefinite program using a semidefinite representation of a set of Gramians. The same approach with semidefinite programming duality is applied to develop a linear matrix inequality test for well-connectedness analysis, and many existing results such as the Kalman-Yakubovich--Popov lemma and various scaled small gain tests are derived in an elegant fashion. More importantly, unlike the classical approach, a decision variable in this novel optimization framework contains all inner products of signals in a system, and an algorithm for constructing an input and state pair of a system corresponding to the optimal solution of robustness optimization is presented based on this information. This insight may open up new research directions, and as one such example, this dissertation proposes a semidefinite programming relaxation of a cardinality constrained variant of the H ∞ norm, which we term sparse H ∞ analysis, where an adversarial disturbance can use only a limited number of channels. Finally, sparse H ∞ analysis is applied to the linearized swing dynamics in order to detect potential vulnerable spots in power networks.

Algebraic Techniques in Coding Theory: Entropy Vectors, Frames, and Constrained Coding

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them.

The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding.

The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in sparse signal recovery using linear measurements.

The final problem we investigate is that of coding with constraints, most recently motivated by the demand for ways to encode large amounts of data using error-correcting codes so that any small loss can be recovered from a small set of surviving data. Most often, this involves using a systematic linear error-correcting code in which each parity symbol is constrained to be a function of some subset of the message symbols. We derive bounds on the minimum distance of such a code based on its constraints, and characterize when these bounds can be achieved using subcodes of Reed-Solomon codes.

Diseño de sistema de suspensión progresiva Pro-Link

[ES]Mediante este trabajo se va a diseñar un mecanismo para crear un sistema de suspensión progresiva para la suspensión trasera de una motocicleta a partir de un muelle lineal. El muelle introducido en la suspensión será lineal, por lo tanto, tendrá una sola rigidez, constante y la cual delimita el muelle, pero gracias a un mecanismo diseñado especialmente para la suspensión trasera de una moto, se va conseguir que la rigidez varíe. El mecanismo utilizado para este trabajo se llama Pro-Link y la empresa que lo emplea es Honda. Para ello, se creará un esquema del mecanismo en sí y tras un análisis cinemático mediante el programa Creo Parametric, y haciendo varios cambios en el sistema para ajustarlo a la mejor progresividad posible, se obtendrá la gráfica en la que se observará la curva que marca la rigidez progresiva. Esto es, se verá la evolución de la nueva rigidez dependiendo de la oscilación vertical de la rueda. Por otra parte, gracias a un análisis dinámico del mismo programa se conseguirán las reacciones del sistema y se calcularán los elementos auxiliares de éste para el buen funcionamiento del mismo. Finalmente, se creará el diseño del triángulo y un diseño preliminar del basculante mediante el método de elementos finitos del programa.