Descriptive set theory and the ergodic theory of countable groups

The primary focus of this thesis is on the interplay of descriptive set theory and the ergodic theory of group actions. This incorporates the study of turbulence and Borel reducibility on the one hand, and the theory of orbit equivalence and weak equivalence on the other. Chapter 2 is joint work with Clinton Conley and Alexander Kechris; we study measurable graph combinatorial invariants of group actions and employ the ultraproduct construction as a way of constructing various measure preserving actions with desirable properties. Chapter 3 is joint work with Lewis Bowen; we study the property MD of residually finite groups, and we prove a conjecture of Kechris by showing that under general hypotheses property MD is inherited by a group from one of its co-amenable subgroups. Chapter 4 is a study of weak equivalence. One of the main results answers a question of Abért and Elek by showing that within any free weak equivalence class the isomorphism relation does not admit classification by countable structures. The proof relies on affirming a conjecture of Ioana by showing that the product of a free action with a Bernoulli shift is weakly equivalent to the original action. Chapter 5 studies the relationship between mixing and freeness properties of measure preserving actions. Chapter 6 studies how approximation properties of ergodic actions and unitary representations are reflected group theoretically and also operator algebraically via a group's reduced C^*-algebra. Chapter 7 is an appendix which includes various results on mixing via filters and on Gaussian actions.

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.

The optoelectronic swept-frequency laser and its applications in ranging, three-dimensional imaging, and coherent beam combining of chirped-seed amplifiers

This thesis explores the design, construction, and applications of the optoelectronic swept-frequency laser (SFL). The optoelectronic SFL is a feedback loop designed around a swept-frequency (chirped) semiconductor laser (SCL) to control its instantaneous optical frequency, such that the chirp characteristics are determined solely by a reference electronic oscillator. The resultant system generates precisely controlled optical frequency sweeps. In particular, we focus on linear chirps because of their numerous applications. We demonstrate optoelectronic SFLs based on vertical-cavity surface-emitting lasers (VCSELs) and distributed-feedback lasers (DFBs) at wavelengths of 1550 nm and 1060 nm. We develop an iterative bias current predistortion procedure that enables SFL operation at very high chirp rates, up to 10^16 Hz/sec. We describe commercialization efforts and implementation of the predistortion algorithm in a stand-alone embedded environment, undertaken as part of our collaboration with Telaris, Inc. We demonstrate frequency-modulated continuous-wave (FMCW) ranging and three-dimensional (3-D) imaging using a 1550 nm optoelectronic SFL.

We develop the technique of multiple source FMCW (MS-FMCW) reflectometry, in which the frequency sweeps of multiple SFLs are "stitched" together in order to increase the optical bandwidth, and hence improve the axial resolution, of an FMCW ranging measurement. We demonstrate computer-aided stitching of DFB and VCSEL sweeps at 1550 nm. We also develop and demonstrate hardware stitching, which enables MS-FMCW ranging without additional signal processing. The culmination of this work is the hardware stitching of four VCSELs at 1550 nm for a total optical bandwidth of 2 THz, and a free-space axial resolution of 75 microns.

We describe our work on the tomographic imaging camera (TomICam), a 3-D imaging system based on FMCW ranging that features non-mechanical acquisition of transverse pixels. Our approach uses a combination of electronically tuned optical sources and low-cost full-field detector arrays, completely eliminating the need for moving parts traditionally employed in 3-D imaging. We describe the basic TomICam principle, and demonstrate single-pixel TomICam ranging in a proof-of-concept experiment. We also discuss the application of compressive sensing (CS) to the TomICam platform, and perform a series of numerical simulations. These simulations show that tenfold compression is feasible in CS TomICam, which effectively improves the volume acquisition speed by a factor ten.

We develop chirped-wave phase-locking techniques, and apply them to coherent beam combining (CBC) of chirped-seed amplifiers (CSAs) in a master oscillator power amplifier configuration. The precise chirp linearity of the optoelectronic SFL enables non-mechanical compensation of optical delays using acousto-optic frequency shifters, and its high chirp rate simultaneously increases the stimulated Brillouin scattering (SBS) threshold of the active fiber. We characterize a 1550 nm chirped-seed amplifier coherent-combining system. We use a chirp rate of 5*10^14 Hz/sec to increase the amplifier SBS threshold threefold, when compared to a single-frequency seed. We demonstrate efficient phase-locking and electronic beam steering of two 3 W erbium-doped fiber amplifier channels, achieving temporal phase noise levels corresponding to interferometric fringe visibilities exceeding 98%.

Free algebras in Von Neumann-Bernays-Gӧdel set theory and positive elementary inductions in reasonable structures

This thesis consists of two independent chapters. The first chapter deals with universal algebra. It is shown, in von Neumann-Bernays-Gӧdel set theory, that free images of partial algebras exist in arbitrary varieties. It follows from this, as set-complete Boolean algebras form a variety, that there exist free set-complete Boolean algebras on any class of generators. This appears to contradict a well-known result of A. Hales and H. Gaifman, stating that there is no complete Boolean algebra on any infinite set of generators. However, it does not, as the algebras constructed in this chapter are allowed to be proper classes. The second chapter deals with positive elementary inductions. It is shown that, in any reasonable structure ᶆ, the inductive closure ordinal of ᶆ is admissible, by showing it is equal to an ordinal measuring the saturation of ᶆ. This is also used to show that non-recursively saturated models of the theories ACF, RCF, and DCF have inductive closure ordinals greater than _ω.

On the set of eigenvalues of a class of equimodular matrices

The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger.

If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given.

The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a_ii. Let A be associated with the set of r permutations, π₁, π₂,…, π_r, where each gap in ϐ(A) is associated with one of the π_k. Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A.

Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A).

Studies on photoblastic germination in lettuce seed

It was shown, with the aid of osmotic inhibition of germination, that the action of the far-red-absorbing form of phytochrome (Pf) in promoting germination can be completed even if the seed is held under conditions where germination is not possible. An effect of the continuing action of Pf beyond the point of complete germination promotion was demonstrated by enhancement of germination rate after removal of the osmotically active solute.

Previous reports that the rate of growth in water of seeds freed from the expansion-restricting endosperm is independent of the state of phytochrome were confirmed. However, a marked, phytochrome-mediated enhancement of the growth potential of such seeds was demonstrated through restricting water uptake by incubation in an osmoticum.

An experimental system, utilizing the appearance of a geotropic curvature in the radicle of the excised axial portion of the seed, was developed for more detailed studies of the phytochrome-enhanced growth potential. It was possible to demonstrate the light effect in water as well as in osmotica; this apparently is not possible with de-endospermed entire seeds. As in intact seeds, the effect of the continuing action of Pf is to enhance the rate of the response. Secretion of a chemical inhibitor of growth by the endosperm as a possible mechanism of induction of light sensitivity has been ruled out.

The phytochrome-dependent rate of appearance of geotropic curvature in osmotica is paralleled in time by a similar dependence of the rate of early extension growth of the embryonic axis. Only the first small increment of growth is a differentially responsive to red (R) and far-red (F); the rate of later increase in length is independent of the light regime.

It was shown that the high concentrations of gibberellic acid required for germination promotion in the intact seed are due at least in part to a diffusion barrier in the endosperm, and that the occasional reports in the literature of the ineffectiveness of kinetin are probably due to the same phenomenon. It was shown that gibberellin, like red light, enhances the growth potential of the axis, but kinetin does not. The difference in rates of response obtained after R-irradiation or gibberellin treatment, together with other results reported in the literature, strongly suggests that gibberellic acid and red light promote germination by different means. The idea that kinetin promotes germination by yet another mechanism, probably operating in the cotyledons, was supported through two different experimental approaches.

The phenomenon of temperature-dependent dark germination was examined in detail, using a wide range of both temperatures and incubation times. With the aid of the half-seed system, it was demonstrated that the promotive effect of low temperature on germination could not be due to a low optimum temperature for early growth of the radicle, since the rate of that process increased with increasing temperature, up to the highest temperature used.

It was shown that phytochrome does not function at high temperatures. This fact is of considerable importance in interpreting the phenomenon of thermodormancy, since in the literature only a small part of the effect of high temperature has been ascribed to an effect on phytochrome, and at that, only to an acceleration of dark reversion of Pf to the red-absorbing form of phytochrome (Pr). Partial denaturation of phytochrome may also make some contribution.

It was shown that the germination-promoting effect of low temperature depends on the presence of Pf, and concluded that low temperatures act by delaying or preventing transformation of Pf. Support for the assumption that Pf, not Pr, is the active form of phytochrome in lettuce seeds was drawn from the same evidence.

Attempts to stimulate germination by repeated irradiation with F over relatively prolonged incubation times resulted in failure, as have similar attempts reported in the literature. However, an enhancement of growth potential in the half-seed system by the maintenance of a small amount of Pf over long periods at ordinary temperatures by repeated irradiation with F was demonstrated.

It was observed that cold storage of the dry seed prevents or delays loss of dark dormancy during post-harvest storage. No change in the response of the half-seed in osmoticum to R and F was observed in seeds that has lost dark dormancy; that is, no internal change took place to measurably increase the growth potential of the embryonic axis. This suggests that the endosperm is the seat of changes responsible for after-ripening of photoblastic lettuce seed.