Convex analysis for minimizing and learning submodular set functions

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Generic differentiability of convex functions and monotone operators

The aim of this paper is to investigate to what extent the known theory of subdifferentiability and generic differentiability of convex functions defined on open sets can be carried out in the context of convex functions defined on not necessarily open sets. Among the main results obtained I would like to mention a Kenderov type theorem (the subdifferential at a generic point is contained in a sphere), a generic Gâteaux differentiability result in Banach spaces of class S and a generic Fréchet differentiability result in Asplund spaces. At least two methods can be used to prove these results: first, a direct one, and second, a more general one, based on the theory of monotone operators. Since this last theory was previously developed essentially for monotone operators defined on open sets, it was necessary to extend it to the context of monotone operators defined on a larger class of sets, our "quasi open" sets. This is done in Chapter III. As a matter of fact, most of these results have an even more general nature and have roots in the theory of minimal usco maps, as shown in Chapter II.

Reflection and transmission of Gaussian beam from a uniaxial crystal slab

We investigate the characteristics of Gaussian beams reflected and transmitted from a uniaxial crystal slab with an arbitrary orientation of its optical axis. The formulas of the total electric and magnetic fields inside and outside the slab are derived by use of Maxwell's equations and by matching the boundary conditions at the interfaces. Numerical simulations are presented and the field values as well as the power densities are computed. Negative refractions are demonstrated when the beam is transmitted through a uniaxial crystal slab. Beam splitting of the reflected beam is observed and is explained by the resonant transmission for plane waves. Dependences of the lateral shift on the incident angle and beam width are discussed. Negative and positive lateral shifts are observed due to the spatial anisotropic properties.

Literature Review of Integrated Impact Assessment Models of Climate Change with Emphasis on Damage Functions

35 p.

Experimental and theoretical developments in extended x-ray absorption fine structure (EXAFS) spectroscopy

To obtain accurate information from a structural tool it is necessary to have an understanding of the physical principles which govern the interaction between the probe and the sample under investigation. In this thesis a detailed study of the physical basis for Extended X-ray Absorption Fine Structure (EXAFS) spectroscopy is presented. A single scattering formalism of EXAFS is introduced which allows a rigorous treatment of the central atom potential. A final state interaction formalism of EXAFS is also discussed. Multiple scattering processes are shown to be significant for systems of certain geometries. The standard single scattering EXAFS analysis produces erroneous results if the data contain a large multiple scattering contribution. The effect of thermal vibrations on such multiple scattering paths is also discussed. From symmetry considerations it is shown that only certain normal modes contribute to the Debye-Waller factor for a particular scattering path. Furthermore, changes in the scattering angles induced by thermal vibrations produces additional EXAFS components called modification factors. These factors are shown to be small for most systems.

A study of the physical basis for the determination of structural information from EXAFS data is also presented. An objective method of determining the background absorption and the threshold energy is discussed and involves Gaussian functions. In addition, a scheme to determine the nature of the scattering atom in EXAFS experiments is introduced. This scheme is based on the fact that the phase intercept is a measure of the type of scattering atom. A method to determine bond distances is also discussed and does not require the use of model compounds or calculated phase shifts. The physical basis for this method is the absence of a linear term in the scattering phases. Therefore, it is possible to separate these phases from the linear term containing the distance information in the total phase.

I. The effects of variations in certain parameters upon the efficiency of in vivo hemodialysis with a Kiil dialyzer. II. Interfacial structure of concurrent air-water flow in a two-inch diameter horizontal tube.

Part I

Regression analyses are performed on in vivo hemodialysis data for the transfer of creatinine, urea, uric acid and inorganic phosphate to determine the effects of variations in certain parameters on the efficiency of dialysis with a Kiil dialyzer. In calculating the mass transfer rates across the membrane, the effects of cell-plasma mass transfer kinetics are considered. The concept of the effective permeability coefficient for the red cell membrane is introduced to account for these effects. A discussion of the consequences of neglecting cell-plasma kinetics, as has been done to date in the literature, is presented.

A physical model for the Kiil dialyzer is presented in order to calculate the available membrane area for mass transfer, the linear blood and dialysate velocities, and other variables. The equations used to determine the independent variables of the regression analyses are presented. The potential dependent variables in the analyses are discussed.

Regression analyses were carried out considering overall mass-transfer coefficients, dialysances, relative dialysances, and relative permeabilities for each substance as the dependent variables. The independent variables were linear blood velocity, linear dialysate velocity, the pressure difference across the membrane, the elapsed time of dialysis, the blood hematocrit, and the arterial plasma concentrations of each substance transferred. The resulting correlations are tabulated, presented graphically, and discussed. The implications of these correlations are discussed from the viewpoint of a research investigator and from the viewpoint of patient treatment.

Recommendations for further experimental work are presented.

Part II

The interfacial structure of concurrent air-water flow in a two-inch diameter horizontal tube in the wavy flow regime has been measured using resistance wave gages. The median water depth, r.m.s. wave height, wave frequency, extrema frequency, and wave velocity have been measured as functions of air and water flow rates. Reynolds numbers, Froude numbers, Weber numbers, and bulk velocities for each phase may be calculated from these measurements. No theory for wave formation and propagation available in the literature was sufficient to describe these results.

The water surface level distribution generally is not adequately represented as a stationary Gaussian process. Five types of deviation from the Gaussian process function were noted in this work. The presence of the tube walls and the relatively large interfacial shear stresses precludes the use of simple statistical analyses to describe the interfacial structure. A detailed study of the behavior of individual fluid elements near the interface may be necessary to describe adequately wavy two-phase flow in systems similar to the one used in this work.