One problem, considered important in Banach space theory since at least the 1970’s, asks for intrinsic characterizations of subspaces of a Banach space with an unconditional basis. A more general question is to give necessary and sufficient conditions for operators from Lp (2 < p < 1) to factor through `p. In this dissertaion, solutions for the above problems are provided. More precisely, I prove that for a reflexive Banach space, being a subspace of a reflexive space with an unconditional basis or being a quotient of such a space, is equivalent to having the unconditional tree property. I also show that a bounded linear operator from Lp (2 < p < 1) factors through `p if and only it satisfies an upper-(C, p)-tree estimate. Results are then extended to operators from asymptotic lp spaces.

It is shown that the cardinal product of graphs does not satisfy unique prime factorization even for a very restrictive class of graphs. It is also proved that every connected graph has a decomposition as a weak cartesian product into indecomposable factors and that this decomposition is unique to within isomorphisms. This latter result is established by considering a certain class of equivalence relations on the edge set of a graph and proving that this collection is a principal filter in the lattice of all equivalences. The least element of this filter is then used to decompose the graph into a weak cartesian product of prime graphs that is unique to within isomorphisms. / Thesis / Doctor of Philosophy (PhD)

We consider the problem of counting <i>transitive factorizations</i> of permutations; that is, we study tuples (&sigma;<i>r</i>,. . . ,&sigma;1) of permutations on {1,. . . ,<i>n</i>} such that (1) the product &sigma;<i>r</i>. . . &sigma;1 is equal to a given target permutation &pi;, and (2) the group generated by the factors &sigma;<i>i</i> acts transitively on {1,. . . ,<i>n</i>}. This problem is widely known as the <i>Hurwitz Enumeration Problem</i>, since an encoding due to Hurwitz shows it to be equivalent to the enumeration of connected branched coverings of the sphere by a surface of given genus with specified branching. Much of our work concerns the enumeration of transitive factorizations of permutations into a minimal number of transposition factors. This problem has received considerable attention, and a formula for the number <i>c</i>(&pi;) of such factorizations of an arbitrary permutation &pi; has been derived through various means. The formula is remarkably simple, being a product of well-known combinatorial numbers, but no bijective proof of it is known except in the special case where &pi; is a full cycle. A major goal of this thesis is to provide further combinatorial rationale for this formula. We begin by introducing an encoding of factorizations (into transpositions) as edge-labelled maps. Our central result is a bijection that allows trees to be "pruned" from such maps. This is shown to explain the appearance of factors of the form <i>k^k</i> in the aforementioned formula for <i>c</i>(&pi;). It also has the effect of shifting focus to the combinatorics of smooth maps (<i>i. e. </i> maps without vertices of degree one). By providing decompositions for certain smooth planar maps, we are able to give combinatorial evaluations of <i>c</i>(&pi;) when &pi; is composed of up to three cycles. Many of these results are generalized to factorizations in which the factors are cycles of any length. We also investigate the <i>Double Hurwitz Problem</i>, which calls for the enumeration of factorizations whose leftmost factor is of specified cycle type, and whose remaining factors are transpositions. Finally, we extend our methods to the enumeration of factorizations up to an equivalence relation induced by possible commutations between adjacent factors.

We consider the problem of counting <i>transitive factorizations</i> of permutations; that is, we study tuples (&sigma;<i>r</i>,. . . ,&sigma;1) of permutations on {1,. . . ,<i>n</i>} such that (1) the product &sigma;<i>r</i>. . . &sigma;1 is equal to a given target permutation &pi;, and (2) the group generated by the factors &sigma;<i>i</i> acts transitively on {1,. . . ,<i>n</i>}. This problem is widely known as the <i>Hurwitz Enumeration Problem</i>, since an encoding due to Hurwitz shows it to be equivalent to the enumeration of connected branched coverings of the sphere by a surface of given genus with specified branching. Much of our work concerns the enumeration of transitive factorizations of permutations into a minimal number of transposition factors. This problem has received considerable attention, and a formula for the number <i>c</i>(&pi;) of such factorizations of an arbitrary permutation &pi; has been derived through various means. The formula is remarkably simple, being a product of well-known combinatorial numbers, but no bijective proof of it is known except in the special case where &pi; is a full cycle. A major goal of this thesis is to provide further combinatorial rationale for this formula. We begin by introducing an encoding of factorizations (into transpositions) as edge-labelled maps. Our central result is a bijection that allows trees to be "pruned" from such maps. This is shown to explain the appearance of factors of the form <i>k^k</i> in the aforementioned formula for <i>c</i>(&pi;). It also has the effect of shifting focus to the combinatorics of smooth maps (<i>i. e. </i> maps without vertices of degree one). By providing decompositions for certain smooth planar maps, we are able to give combinatorial evaluations of <i>c</i>(&pi;) when &pi; is composed of up to three cycles. Many of these results are generalized to factorizations in which the factors are cycles of any length. We also investigate the <i>Double Hurwitz Problem</i>, which calls for the enumeration of factorizations whose leftmost factor is of specified cycle type, and whose remaining factors are transpositions. Finally, we extend our methods to the enumeration of factorizations up to an equivalence relation induced by possible commutations between adjacent factors.

We give a formula for the Chern character on the DG category of global matrix factorizations on a smooth scheme $X$ with superpotential $w\in \Gamma(\O_X)$. Our formula takes values in a Cech model for Hochschild homology. Our methods may also be adapted to get an explicit formula for the Chern character for perfect complexes of sheaves on $X$ taking values in right derived global sections of the De-Rham algebra. Along the way we prove that the DG version of the Chern Character coincides with the classical one for perfect complexes.

The problem we study in this thesis asks under which conditions an r-factorization of Kₘʰ can be embedded into an s-factorization of Kₙʰ. This problem is a generalization of a problem posed by Peter Cameron which asks under which conditions a 1-factorization of Kₘʰ can be embedded into a 1-factorization of Kₙʰ. This was solved by Häggkvist and Hellgren. We study sufficient conditions in the case where s = h and m divides n. To that end, we take inspiration from a paper by Amin Bahmanian and Mike Newman and simplify the problem to the construction of an "acceptable" partition. We introduce the notion of irreducible sums and link them to the main obstacles in constructing acceptable partitions before providing different methods for circumventing these obstacles. Finally, we discuss a series of open problems related to this case.

Symmetric generalized eigenvalue problems arise in many physical applications and frequently only a few of the eigenpairs are of interest. Typically, the problems are large and sparse, and therefore traditional methods such as the QZ algorithm may not be considered. Moreover, it may be impractical to apply shift-and-invert Lanczos, a favored method for problems of this type, due to difficulties in applying the inverse of the shifted matrix. With these difficulties in mind, Golub and Ye developed an inverse free Krylov subspace algorithm for the symmetric generalized eigenvalue problem. This method does not rely on shift-and-invert transformations for convergence acceleration, but rather a preconditioner is used. The algorithm suffers, however, in the presence of multiple or clustered eigenvalues. Also, it is only applicable to the location of extreme eigenvalues. In this work, we extend the method of Golub and Ye by developing a block generalization of their algorithm which enjoys considerably faster convergence than the usual method in the presence of multiplicities and clusters. Preconditioning techniques for the problems are discussed at length, and some insight is given into how these preconditioners accelerate the method. Finally we discuss a transformation which can be applied so that the algorithm extracts interior eigenvalues. A preconditioner based on a QR factorization with respect to the B-1 inner product is developed and applied in locating interior eigenvalues.

The classical discriminant D_n of degree n polynomials detects whether a given univariate polynomial f has a repeated root. It is itself a polynomial in the coefficients of f which, according to several classical results by Bézout, Sylvester, Cayley, and others, may be expressed as the determinant of a matrix whose entries are much simpler polynomials in the coefficients of f. This thesis is concerned with the construction and classification of such determinantal formulae for D_n. In particular, all of the formulae for D_n appearing in the classical literature are equivalent in the sense that the cokernels of their associated matrices are isomorphic as modules over the associated polynomial ring. This begs the question of whether there exist formulae which are not equivalent to the classical formulae and not trivial in the sense of having the same cokernel as the 1 x 1 matrix (D_n). The results of this thesis lie in two directions. First, we construct an explicit non-classical formula: the presentation matrix of the open swallowtail first studied by Arnol'd and Givental. We study the properties of this formula, contrasting them with the properties of the classical formulae. Second, for the discriminant of the polynomial x^4+a_2x^2+a_3x+a_4 we embark on a classification of determinantal formulae which are homogeneous in the sense that the cokernels of their associated matrices are graded modules with respect to the grading deg a_i=i. To this end, we use deformation theory: a moduli space of such modules arises from the base spaces of versal deformations of certain modules over the E_6 singularity {x^4-y^3}. The method developed here can in principle be used to classify determinantal formulae for all discriminants, and, indeed, for all singularities.

The classical discriminant D_n of degree n polynomials detects whether a given univariate polynomial f has a repeated root. It is itself a polynomial in the coefficients of f which, according to several classical results by Bézout, Sylvester, Cayley, and others, may be expressed as the determinant of a matrix whose entries are much simpler polynomials in the coefficients of f. This thesis is concerned with the construction and classification of such determinantal formulae for D_n. In particular, all of the formulae for D_n appearing in the classical literature are equivalent in the sense that the cokernels of their associated matrices are isomorphic as modules over the associated polynomial ring. This begs the question of whether there exist formulae which are not equivalent to the classical formulae and not trivial in the sense of having the same cokernel as the 1 x 1 matrix (D_n). The results of this thesis lie in two directions. First, we construct an explicit non-classical formula: the presentation matrix of the open swallowtail first studied by Arnol'd and Givental. We study the properties of this formula, contrasting them with the properties of the classical formulae. Second, for the discriminant of the polynomial x^4+a_2x^2+a_3x+a_4 we embark on a classification of determinantal formulae which are homogeneous in the sense that the cokernels of their associated matrices are graded modules with respect to the grading deg a_i=i. To this end, we use deformation theory: a moduli space of such modules arises from the base spaces of versal deformations of certain modules over the E_6 singularity {x^4-y^3}. The method developed here can in principle be used to classify determinantal formulae for all discriminants, and, indeed, for all singularities.

The size of data generated every year follows an exponential growth. The number of data points as well as the dimensions have increased dramatically the past 15 years. The gap between the demand from the industry in data processing and the solutions provided by the machine learning community is increasing. Despite the growth in memory and computational power, advanced statistical processing on the order of gigabytes is beyond any possibility. Most sophisticated Machine Learning algorithms require at least quadratic complexity. With the current computer model architecture, algorithms with higher complexity than linear O(N) or O(N logN) are not considered practical. Dimensionality reduction is a challenging problem in machine learning. Often data represented as multidimensional points happen to have high dimensionality. It turns out that the information they carry can be expressed with much less dimensions. Moreover the reduced dimensions of the data can have better interpretability than the original ones. There is a great variety of dimensionality reduction algorithms under the theory of Manifold Learning. Most of the methods such as Isomap, Local Linear Embedding, Local Tangent Space Alignment, Diffusion Maps etc. have been extensively studied under the framework of Kernel Principal Component Analysis (KPCA). In this dissertation we study two current state of the art dimensionality reduction methods, Maximum Variance Unfolding (MVU) and Non-Negative Matrix Factorization (NMF). These two dimensionality reduction methods do not fit under the umbrella of Kernel PCA. MVU is cast as a Semidefinite Program, a modern convex nonlinear optimization algorithm, that offers more flexibility and power compared to iv KPCA. Although MVU and NMF seem to be two disconnected problems, we show that there is a connection between them. Both are special cases of a general nonlinear factorization algorithm that we developed. Two aspects of the algorithms are of particular interest: computational complexity and interpretability. In other words computational complexity answers the question of how fast we can find the best solution of MVU/NMF for large data volumes. Since we are dealing with optimization programs, we need to find the global optimum. Global optimum is strongly connected with the convexity of the problem. Interpretability is strongly connected with local isometry1 that gives meaning in relationships between data points. Another aspect of interpretability is association of data with labeled information. The contributions of this thesis are the following: 1. MVU is modified so that it can scale more efficient. Results are shown on 1 million speech datasets. Limitations of the method are highlighted. 2. An algorithm for fast computations for the furthest neighbors is presented for the first time in the literature. 3. Construction of optimal kernels for Kernel Density Estimation with modern convex programming is presented. For the first time we show that the Leave One Cross Validation (LOOCV) function is quasi-concave. 4. For the first time NMF is formulated as a convex optimization problem 5. An algorithm for the problem of Completely Positive Matrix Factorization is presented. 6. A hybrid algorithm of MVU and NMF the isoNMF is presented combining advantages of both methods. 7. The Isometric Separation Maps (ISM) a variation of MVU that contains classification information is presented. 8. Large scale nonlinear dimensional analysis on the TIMIT speech database is performed. 9. A general nonlinear factorization algorithm is presented based on sequential convex programming. Despite the efforts to scale the proposed methods up to 1 million data points in reasonable time, the gap between the industrial demand and the current state of the art is still orders of magnitude wide.