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.

Rings faithfully represented on their left socle

In 1964 A. W. Goldie [1] posed the problem of determining all rings with identity and minimal condition on left ideals which are faithfully represented on the right side of their left socle. Goldie showed that such a ring which is indecomposable and in which the left and right principal indecomposable ideals have, respectively, unique left and unique right composition series is a complete blocked triangular matrix ring over a skewfield. The general problem suggested above is very difficult. We obtain results under certain natural restrictions which are much weaker than the restrictive assumptions made by Goldie.

We characterize those rings in which the principal indecomposable left ideals each contain a unique minimal left ideal (Theorem (4.2)). It is sufficient to handle indecomposable rings (Lemma (1.4)). Such a ring is also a blocked triangular matrix ring. There exist r positive integers K₁,..., K_r such that the i,j^th block of a typical matrix is a K_i x K_j matrix with arbitrary entries in a subgroup D_ij of the additive group of a fixed skewfield D. Each D_ii is a sub-skewfield of D and D_ri = D for all i. Conversely, every matrix ring which has this form is indecomposable, faithfully represented on the right side of its left socle, and possesses the property that every principal indecomposable left ideal contains a unique minimal left ideal.

The principal indecomposable left ideals may have unique composition series even though the ring does not have minimal condition on right ideals. We characterize this situation by defining a partial ordering ρ on {i, 2,...,r} where we set iρj if D_ij ≠ 0. Every principal indecomposable left ideal has a unique composition series if and only if the diagram of ρ is an inverted tree and every D_ij is a one-dimensional left vector space over D_ii (Theorem (5.4)).

We show (Theorem (2.2)) that every ring A of the type we are studying is a unique subdirect sum of less complex rings A₁,...,A_s of the same type. Namely, each A_i has only one isomorphism class of minimal left ideals and the minimal left ideals of different A_i are non-isomorphic as left A-modules. We give (Theorem (2.1)) necessary and sufficient conditions for a ring which is a subdirect sum of rings A_i having these properties to be faithfully represented on the right side of its left socle. We show ((4.F), p. 42) that up to technical trivia the rings A_i are matrix rings of the form

[...]. Each Q_j comes from the faithful irreducible matrix representation of a certain skewfield over a fixed skewfield D. The bottom row is filled in by arbitrary elements of D.

In Part V we construct an interesting class of rings faithfully represented on their left socle from a given partial ordering on a finite set, given skewfields, and given additive groups. This class of rings contains the ones in which every principal indecomposable left ideal has a unique minimal left ideal. We identify the uniquely determined subdirect summands mentioned above in terms of the given partial ordering (Proposition (5.2)). We conjecture that this technique serves to construct all the rings which are a unique subdirect sum of rings each having the property that every principal-indecomposable left ideal contains a unique minimal left ideal.

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.