Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

<p>There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.</p> <p>In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:</p> <UL> <LI> For a given number of measurements, can we reliably estimate the true signal?</LI> <LI> If so, how good is the reconstruction as a function of the model parameters?</LI> </UL> <p>More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.</p>

Optimization and Control of Power Flow in Distribution Networks

<p>Climate change is arguably the most critical issue facing our generation and the next. As we move towards a sustainable future, the grid is rapidly evolving with the integration of more and more renewable energy resources and the emergence of electric vehicles. In particular, large scale adoption of residential and commercial solar photovoltaics (PV) plants is completely changing the traditional slowly-varying unidirectional power flow nature of distribution systems. High share of intermittent renewables pose several technical challenges, including voltage and frequency control. But along with these challenges, renewable generators also bring with them millions of new DC-AC inverter controllers each year. These fast power electronic devices can provide an unprecedented opportunity to increase energy efficiency and improve power quality, if combined with well-designed inverter control algorithms. The main goal of this dissertation is to develop scalable power flow optimization and control methods that achieve system-wide efficiency, reliability, and robustness for power distribution networks of future with high penetration of distributed inverter-based renewable generators.</p> <p>Proposed solutions to power flow control problems in the literature range from fully centralized to fully local ones. In this thesis, we will focus on the two ends of this spectrum. In the first half of this thesis (chapters 2 and 3), we seek optimal solutions to voltage control problems provided a centralized architecture with complete information. These solutions are particularly important for better understanding the overall system behavior and can serve as a benchmark to compare the performance of other control methods against. To this end, we first propose a branch flow model (BFM) for the analysis and optimization of radial and meshed networks. This model leads to a new approach to solve optimal power flow (OPF) problems using a two step relaxation procedure, which has proven to be both reliable and computationally efficient in dealing with the non-convexity of power flow equations in radial and weakly-meshed distribution networks. We will then apply the results to fast time- scale inverter var control problem and evaluate the performance on real-world circuits in Southern California Edison’s service territory.</p> <p>The second half (chapters 4 and 5), however, is dedicated to study local control approaches, as they are the only options available for immediate implementation on today’s distribution networks that lack sufficient monitoring and communication infrastructure. In particular, we will follow a reverse and forward engineering approach to study the recently proposed piecewise linear volt/var control curves. It is the aim of this dissertation to tackle some key problems in these two areas and contribute by providing rigorous theoretical basis for future work.</p>

Design, specification, and synthesis of aircraft electric power systems control logic

<p>Cyber-physical systems integrate computation, networking, and physical processes. Substantial research challenges exist in the design and verification of such large-scale, distributed sensing, ac- tuation, and control systems. Rapidly improving technology and recent advances in control theory, networked systems, and computer science give us the opportunity to drastically improve our approach to integrated flow of information and cooperative behavior. Current systems rely on text-based spec- ifications and manual design. Using new technology advances, we can create easier, more efficient, and cheaper ways of developing these control systems. This thesis will focus on design considera- tions for system topologies, ways to formally and automatically specify requirements, and methods to synthesize reactive control protocols, all within the context of an aircraft electric power system as a representative application area.</p> <p>This thesis consists of three complementary parts: synthesis, specification, and design. The first section focuses on the synthesis of central and distributed reactive controllers for an aircraft elec- tric power system. This approach incorporates methodologies from computer science and control. The resulting controllers are correct by construction with respect to system requirements, which are formulated using the specification language of linear temporal logic (LTL). The second section addresses how to formally specify requirements and introduces a domain-specific language for electric power systems. A software tool automatically converts high-level requirements into LTL and synthesizes a controller.</p> <p>The final sections focus on design space exploration. A design methodology is proposed that uses mixed-integer linear programming to obtain candidate topologies, which are then used to synthesize controllers. The discrete-time control logic is then verified in real-time by two methods: hardware and simulation. Finally, the problem of partial observability and dynamic state estimation is ex- plored. Given a set placement of sensors on an electric power system, measurements from these sensors can be used in conjunction with control logic to infer the state of the system.</p>

Branes and supersymmetric quantum field theories

<p>Since the discovery of D-branes as non-perturbative, dynamic objects in string theory, various configurations of branes in type IIA/B string theory and M-theory have been considered to study their low-energy dynamics described by supersymmetric quantum field theories.</p> <p>One example of such a construction is based on the description of Seiberg-Witten curves of four-dimensional N = 2 supersymmetric gauge theories as branes in type IIA string theory and M-theory. This enables us to study the gauge theories in strongly-coupled regimes. Spectral networks are another tool for utilizing branes to study non-perturbative regimes of two- and four-dimensional supersymmetric theories. Using spectral networks of a Seiberg-Witten theory we can find its BPS spectrum, which is protected from quantum corrections by supersymmetry, and also the BPS spectrum of a related two-dimensional N = (2,2) theory whose (twisted) superpotential is determined by the Seiberg-Witten curve. When we don’t know the perturbative description of such a theory, its spectrum obtained via spectral networks is a useful piece of information. In this thesis we illustrate these ideas with examples of the use of Seiberg-Witten curves and spectral networks to understand various two- and four-dimensional supersymmetric theories.</p> <p>First, we examine how the geometry of a Seiberg-Witten curve serves as a useful tool for identifying various limits of the parameters of the Seiberg-Witten theory, including Argyres-Seiberg duality and Argyres-Douglas fixed points. Next, we consider the low-energy limit of a two-dimensional N = (2, 2) supersymmetric theory from an M-theory brane configuration whose (twisted) superpotential is determined by the geometry of the branes. We show that, when the two-dimensional theory flows to its infra-red fixed point, particular cases realize Kazama-Suzuki coset models. We also study the BPS spectrum of an Argyres-Douglas type superconformal field theory on the Coulomb branch by using its spectral networks. We provide strong evidence of the equivalence of superconformal field theories from different string-theoretic constructions by comparing their BPS spectra.</p>

Studies of molecular bonding, interactions and decomposition reactions on the (001) surface of ruthenium

<p>The interactions of N₂, formic acid and acetone on the Ru(001) surface are studied using thermal desorption mass spectrometry (TDMS), electron energy loss spectroscopy (EELS), and computer modeling.</p> <p>Low energy electron diffraction (LEED), EELS and TDMS were used to study chemisorption of N₂ on Ru(001). Adsorption at 75 K produces two desorption states. Adsorption at 95 K fills only the higher energy desorption state and produces a (√3 x √3)R30° LEED pattern. EEL spectra indicate both desorption states are populated by N₂ molecules bonded "on-top" of Ru atoms.</p> <p>Monte Carlo simulation results are presented on Ru(001) using a kinetic lattice gas model with precursor mediated adsorption, desorption and migration. The model gives good agreement with experimental data. The island growth rate was computed using the same model and is well fit by R(t)^m - R(t₀)^m = At, with m approximately 8. The island size was determined from the width of the superlattice diffraction feature.</p> <p>The techniques, algorithms and computer programs used for simulations are documented. Coordinate schemes for indexing sites on a 2-D hexagonal lattice, programs for simulation of adsorption and desorption, techniques for analysis of ordering, and computer graphics routines are discussed.</p> <p>The adsorption of formic acid on Ru(001) has been studied by EELS and TDMS. Large exposures produce a molecular multilayer species. A monodentate formate, bidentate formate, and a hydroxyl species are stable intermediates in formic acid decomposition. The monodentate formate species is converted to the bidentate species by heating. Formic acid decomposition products are CO₂, CO, H₂, H₂O and oxygen adatoms. The ratio of desorbed CO with respect to CO₂ increases both with slower heating rates and with lower coverages.</p> <p>The existence of two different forms of adsorbed acetone, side-on, bonded through the oxygen and acyl carbon, and end-on, bonded through the oxygen, have been verified by EELS. On Pt(111), only the end-on species is observed. On dean Ru(001) and p(2 x 2)O precovered Ru(001), both forms coexist. The side-on species is dominant on clean Ru(001), while O stabilizes the end-on form. The end-on form desorbs molecularly. Bonding geometry stability is explained by surface Lewis acidity and by comparison to organometallic coordination complexes.</p>

Source characteristics of recent and historic earthquakes in Central and Southern California: results from forward modeling

<p> The long- and short-period body waves of a number of moderate earthquakes occurring in central and southern California recorded at regional (200-1400 km) and teleseismic (> 30°) distances are modeled to obtain the source parameters-focal mechanism, depth, seismic moment, and source time history. The modeling is done in the time domain using a forward modeling technique based on ray summation. A simple layer over a half space velocity model is used with additional layers being added if necessary-for example, in a basin with a low velocity lid. </p> <p> The earthquakes studied fall into two geographic regions: 1) the western Transverse Ranges, and 2) the western Imperial Valley. Earthquakes in the western Transverse Ranges include the 1987 Whittier Narrows earthquake, several offshore earthquakes that occurred between 1969 and 1981, and aftershocks to the 1983 Coalinga earthquake (these actually occurred north of the Transverse Ranges but share many characteristics with those that occurred there). These earthquakes are predominantly thrust faulting events with the average strike being east-west, but with many variations. Of the six earthquakes which had sufficient short-period data to accurately determine the source time history, five were complex events. That is, they could not be modeled as a simple point source, but consisted of two or more subevents. The subevents of the Whittier Narrows earthquake had different focal mechanisms. In the other cases, the subevents appear to be the same, but small variations could not be ruled out.</p> <p> The recent Imperial Valley earthquakes modeled include the two 1987 Superstition Hills earthquakes and the 1969 Coyote Mountain earthquake. All are strike-slip events, and the second 1987 earthquake is a complex event With non-identical subevents.</p> <p> In all the earthquakes studied, and particularly the thrust events, constraining the source parameters required modeling several phases and distance ranges. Teleseismic P waves could provide only approximate solutions. P_(nl) waves were probably the most useful phase in determining the focal mechanism, with additional constraints supplied by the SH waves when available. Contamination of the SH waves by shear-coupled PL waves was a frequent problem. Short-period data were needed to obtain the source time function. </p> <p> In addition to the earthquakes mentioned above, several historic earthquakes were also studied. Earthquakes that occurred before the existence of dense local and worldwide networks are difficult to model due to the sparse data set. It has been noticed that earthquakes that occur near each other often produce similar waveforms implying similar source parameters. By comparing recent well studied earthquakes to historic earthquakes in the same region, better constraints can be placed on the source parameters of the historic events. </p> <p> The Lompoc earthquake (M=7) of 1927 is the largest offshore earthquake to occur in California this century. By direct comparison of waveforms and amplitudes with the Coalinga and Santa Lucia Banks earthquakes, the focal mechanism (thrust faulting on a northwest striking fault) and long-period seismic moment (10^(26) dyne cm) can be obtained. The S-P travel times are consistent with an offshore location, rather than one in the Hosgri fault zone.</p> <p> Historic earthquakes in the western Imperial Valley were also studied. These events include the 1942 and 1954 earthquakes. The earthquakes were relocated by comparing S-P and R-S times to recent earthquakes. It was found that only minor changes in the epicenters were required but that the Coyote Mountain earthquake may have been more severely mislocated. The waveforms as expected indicated that all the events were strike-slip. Moment estimates were obtained by comparing the amplitudes of recent and historic events at stations which recorded both. The 1942 event was smaller than the 1968 Borrego Mountain earthquake although some previous studies suggested the reverse. The 1954 and 1937 earthquakes had moments close to the expected value. An aftershock of the 1942 earthquake appears to be larger than previously thought.</p>

Computer system support for data analysis

<p>This thesis is an investigation into the nature of data analysis and computer software systems which support this activity.</p> <p>The first chapter develops the notion of data analysis as an experimental science which has two major components: data-gathering and theory-building. The basic role of language in determining the meaningfulness of theory is stressed, and the informativeness of a language and data base pair is studied. The static and dynamic aspects of data analysis are then considered from this conceptual vantage point. The second chapter surveys the available types of computer systems which may be useful for data analysis. Particular attention is paid to the questions raised in the first chapter about the language restrictions imposed by the computer system and its dynamic properties.</p> <p>The third chapter discusses the REL data analysis system, which was designed to satisfy the needs of the data analyzer in an operational relational data system. The major limitation on the use of such systems is the amount of access to data stored on a relatively slow secondary memory. This problem of the paging of data is investigated and two classes of data structure representations are found, each of which has desirable paging characteristics for certain types of queries. One representation is used by most of the generalized data base management systems in existence today, but the other is clearly preferred in the data analysis environment, as conceptualized in Chapter I.</p> <p>This data representation has strong implications for a fundamental process of data analysis -- the quantification of variables. Since quantification is one of the few means of summarizing and abstracting, data analysis systems are under strong pressure to facilitate the process. Two implementations of quantification are studied: one analagous to the form of the lower predicate calculus and another more closely attuned to the data representation. A comparison of these indicates that the use of the "label class" method results in orders of magnitude improvement over the lower predicate calculus technique.</p>