Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

Mechanisms of substrate selection by the signal recognition particle

The signal recognition particle (SRP) targets membrane and secretory proteins to their correct cellular destination with remarkably high fidelity. Previous studies have shown that multiple checkpoints exist within this targeting pathway that allows ‘correct cargo’ to be quickly and efficiently targeted and for ‘incorrect cargo’ to be promptly rejected. In this work, we delved further into understanding the mechanisms of how substrates are selected or discarded by the SRP. First, we discovered the role of the SRP fingerloop and how it activates the SRP and SRP receptor (SR) GTPases to target and unload cargo in response to signal sequence binding. Second, we learned how an ‘avoidance signal’ found in the bacterial autotransporter, EspP, allows this protein to escape the SRP pathway by causing the SRP and SR to form a ‘distorted’ complex that is inefficient in delivering the cargo to the membrane. Lastly, we determined how Trigger Factor, a co-translational chaperone, helps SRP discriminate against ‘incorrect cargo’ at three distinct stages: SRP binding to RNC; targeting of RNC to the membrane via SRP-FtsY assembly; and stronger antagonism of SRP targeting of ribosomes bearing nascent polypeptides that exceed a critical length. Overall, results delineate the rich underlying mechanisms by which SRP recognizes its substrates, which in turn activates the targeting pathway and provides a conceptual foundation to understand how timely and accurate selection of substrates is achieved by this protein targeting machinery.

The variations and climatic significance of D/H ratios in the carbon-bound hydrogen of cellulose in trees

The σD values of nitrated cellulose from a variety of trees covering a wide geographic range have been measured. These measurements have been used to ascertain which factors are likely to cause σD variations in cellulose C-H hydrogen.

It is found that a primary source of tree σD variation is the σD variation of the environmental precipitation. Superimposed on this are isotopic variations caused by the transpiration of the leaf water incorporated by the tree. The magnitude of this transpiration effect appears to be related to relative humidity.

Within a single tree, it is found that the hydrogen isotope variations which occur for a ring sequence in one radial direction may not be exactly the same as those which occur in a different direction. Such heterogeneities appear most likely to occur in trees with asymmetric ring patterns that contain reaction wood. In the absence of reaction wood such heterogeneities do not seem to occur. Thus, hydrogen isotope analyses of tree ring sequences should be performed on trees which do not contain reaction wood.

Comparisons of tree σD variations with variations in local climate are performed on two levels: spatial and temporal. It is found that the σD values of 20 North American trees from a wide geographic range are reasonably well-correlated with the corresponding average annual temperature. The correlation is similar to that observed for a comparison of the σD values of annual precipitation of 11 North American sites with annual temperature. However, it appears that this correlation is significantly disrupted by trees which grew on poorly drained sites such as those in stagnant marshes. Therefore, site selection may be important in choosing trees for climatic interpretation of σD values, although proper sites do not seem to be uncommon.

The measurement of σD values in 5-year samples from the tree ring sequences of 13 trees from 11 North American sites reveals a variety of relationships with local climate. As it was for the spatial σD vs climate comparison, site selection is also apparently important for temporal tree σD vs climate comparisons. Again, it seems that poorly-drained sites are to be avoided. For nine trees from different "well-behaved" sites, it was found that the local climatic variable best related to the σD variations was not the same for all sites.

Two of these trees showed a strong negative correlation with the amount of local summer precipitation. Consideration of factors likely to influence the isotopic composition of summer rain suggests that rainfall intensity may be important. The higher the intensity, the lower the σD value. Such an effect might explain the negative correlation of σD vs summer precipitation amount for these two trees. A third tree also exhibited a strong correlation with summer climate, but in this instance it was a positive correlation of σD with summer temperature.

The remaining six trees exhibited the best correlation between σD values and local annual climate. However, in none of these six cases was it annual temperature that was the most important variable. In fact annual temperature commonly showed no relationship at all with tree σD values. Instead, it was found that a simple mass balance model incorporating two basic assumptions yielded parameters which produced the best relationships with tree σD values. First, it was assumed that the σD values of these six trees reflected the σD values of annual precipitation incorporated by these trees. Second, it was assumed that the σD value of the annual precipitation was a weighted average of two seasonal isotopic components: summer and winter. Mass balance equations derived from these assumptions yielded combinations of variables that commonly showed a relationship with tree σD values where none had previously been discerned.

It was found for these "well-behaved" trees that not all sample intervals in a σD vs local climate plot fell along a well-defined trend. These departures from the local σD VS climate norm were defined as "anomalous". Some of these anomalous intervals were common to trees from different locales. When such widespread commonalty of an anomalous interval occurred, it was observed that the interval corresponded to an interval in which drought had existed in the North American Great Plains.

Consequently, there appears to be a combination of both local and large scale climatic information in the σD variations of tree cellulose C-H hydrogen.

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 _ω.

Structure-Function Studies of Nicotinic Acetylcholine Receptors Using Selective Agonists and Positive Allosteric Modulators

This dissertation primarily describes chemical-scale studies of nicotinic acetylcholine receptors (nAChRs) in order to better understand ligand-receptor selectivity and allosteric modulation influences during receptor activation. Electrophysiology coupled with canonical and non-canonical amino acids mutagenesis is used to probe subtle changes in receptor function.

The first half of this dissertation focuses on differential agonist selectivity of α4β2-containing nAChRs. The α4β2 nAChR can assemble in alternative stoichiometries as well as assemble with other accessory subunits. Chapter 2 identifies key structural residues that dictate binding and activation of three stoichiometry-dependent α4β2 receptor ligands: sazetidine-A, cytisine, and NS9283. These do not follow previously suggested hydrogen-bonding patterns of selectivity. Instead, three residues on the complementary subunit strongly influence binding ability of a ligand and receptor activation. Chapter 3 involves isolation of a α5α4β2 receptor-enriched population to test for a potential alternative agonist binding location at the α5 α4 interface. Results strongly suggest that agonist occupation of this site is not necessary for receptor activation and that the α5 subunit only incorporates at the accessory subunit location.

The second half of this dissertation seeks to identify residue interactions with positive allosteric modulators (PAMs) of the α7 nAChR. Chapter 4 focuses on methods development to study loss of potentiation of Type I PAMs, which indicate residues vital to propagation of PAM effects and/or binding. Chapter 5 investigates α7 receptor modulation by a Type II PAM (PNU 120596). These results show that PNU 120596 does not alter the agonist binding site, thus is relegated to influencing only the gating component of activation. From this, we were able to map a potential network of residues from the agonist binding site to the proposed PNU 120596 binding site that are essential for receptor potentiation.

Theory of the positive column of a gas discharge

An attempt is made to provide a theoretical explanation of the effect of the positive column on the voltage-current characteristic of a glow or an arc discharge. Such theories have been developed before, and all are based on balancing the production and loss of charged particles and accounting for the energy supplied to the plasma by the applied electric field. Differences among the theories arise from the approximations and omissions made in selecting processes that affect the particle and energy balances. This work is primarily concerned with the deviation from the ambipolar description of the positive column caused by space charge, electron-ion volume recombination, and temperature inhomogeneities.

The presentation is divided into three parts, the first of which involved the derivation of the final macroscopic equations from kinetic theory. The final equations are obtained by taking the first three moments of the Boltzmann equation for each of the three species in the plasma. Although the method used and the equations obtained are not novel, the derivation is carried out in detail in order to appraise the validity of numerous approximations and to justify the use of data from other sources. The equations are applied to a molecular hydrogen discharge contained between parallel walls. The applied electric field is parallel to the walls, and the dependent variables—electron and ion flux to the walls, electron and ion densities, transverse electric field, and gas temperature—vary only in the direction perpendicular to the walls. The mathematical description is given by a sixth-order nonlinear two-point boundary value problem which contains the applied field as a parameter. The amount of neutral gas and its temperature at the walls are held fixed, and the relation between the applied field and the electron density at the center of the discharge is obtained in the process of solving the problem. This relation corresponds to that between current and voltage and is used to interpret the effect of space charge, recombination, and temperature inhomogeneities on the voltage-current characteristic of the discharge.

The complete solution of the equations is impractical both numerically and analytically, and in Part II the gas temperature is assumed uniform so as to focus on the combined effects of space charge and recombination. The terms representing these effects are treated as perturbations to equations that would otherwise describe the ambipolar situation. However, the term representing space charge is not negligible in a thin boundary layer or sheath near the walls, and consequently the perturbation problem is singular. Separate solutions must be obtained in the sheath and in the main region of the discharge, and the relation between the electron density and the applied field is not determined until these solutions are matched.

In Part III the electron and ion densities are assumed equal, and the complicated space-charge calculation is thereby replaced by the ambipolar description. Recombination and temperature inhomogeneities are both important at high values of the electron density. However, the formulation of the problem permits a comparison of the relative effects, and temperature inhomogeneities are shown to be important at lower values of the electron density than recombination. The equations are solved by a direct numerical integration and by treating the term representing temperature inhomogeneities as a perturbation.

The conclusions reached in the study are primarily concerned with the association of the relation between electron density and axial field with the voltage-current characteristic. It is known that the effect of space charge can account for the subnormal glow discharge and that the normal glow corresponds to a close approach to an ambipolar situation. The effect of temperature inhomogeneities helps explain the decreasing characteristic of the arc, and the effect of recombination is not expected to appear except at very high electron densities.

Reggeization of some unequal mass processes involving higher spins : the reactions pion-nucleon going to (V,Nucleon), pion-nucleon going to (V,delta-hyperon), and photon-proton going to (positive pion,neutron)

Recent theoretical developments in the reggeization of inelastic processes involving particles with high spin are incorporated into a model of vector meson production. A number of features of experimental differential cross sections and density matrices are interpreted in terms of this model.

The method chosen for reggeization of helicity amplitudes first separates kinematic zeros and singularities from the parity-conserving amplitudes and then applies results of Freedman and Wang on daughter trajectories to the remaining factors. Kinematic constraints on helicity amplitudes at t = 0 and t = (M – M_Δ)² are also considered.

It is found that data for reactions of types πN→VN and πN→VΔ are consistent with a model of this type in which all kinematic constraints at t = 0 are satisfied by evasion (vanishing of residue functions). As a quantitative test of the parametrization, experimental differential cross sections of vector meson production reactions dominated by pion trajectory exchange are compared with the theory. It is found that reduced residue functions are approximately constant, once the kinematic behavior near t = (M – M_Δ)² has been removed.

The alternative possibility of conspiracy between amplitudes is also discussed; and it is shown that unless conspiracy is present, some amplitudes allowed by angular momentum conservation will not contribute with full strength in the forward direction. An example, γp→π⁺n in which the data for dσ/dt indicate conspiracy, is studied in detail.

Matrices whose hermitian part is positive definite

We are concerned with the class ∏_n of nxn complex matrices A for which the Hermitian part H(A) = A+A*/2 is positive definite.

Various connections are established with other classes such as the stable, D-stable and dominant diagonal matrices. For instance it is proved that if there exist positive diagonal matrices D, E such that DAE is either row dominant or column dominant and has positive diagonal entries, then there is a positive diagonal F such that FA ϵ ∏_n.

Powers are investigated and it is found that the only matrices A for which A^m ϵ ∏_n for all integers m are the Hermitian elements of ∏_n. Products and sums are considered and criteria are developed for AB to be in ∏_n.

Since ∏_n n is closed under inversion, relations between H(A)^-1 and H(A^-1) are studied and a dichotomy observed between the real and complex cases. In the real case more can be said and the initial result is that for A ϵ ∏_n, the difference H(adjA) - adjH(A) ≥ 0 always and is ˃ 0 if and only if S(A) = A-A*/2 has more than one pair of conjugate non-zero characteristic roots. This is refined to characterize real c for which cH(A^-1) - H(A)^-1 is positive definite.

The cramped (characteristic roots on an arc of less than 180°) unitary matrices are linked to ∏_n and characterized in several ways via products of the form A ^-1A*.

Classical inequalities for Hermitian positive definite matrices are studied in ∏_n and for Hadamard's inequality two types of generalizations are given. In the first a large subclass of ∏_n in which the precise statement of Hadamardis inequality holds is isolated while in another large subclass its reverse is shown to hold. In the second Hadamard's inequality is weakened in such a way that it holds throughout ∏_n. Both approaches contain the original Hadamard inequality as a special case.