Georgia Institute of Technology College of Sciences

This dissertation investigates the problem of estimating a kernel over a large graph based on a sample of noisy observations of linear measurements of the kernel. We are interested in solving this estimation problem in the case when the sample size is much smaller than the ambient dimension of the kernel. As is typical in high-dimensional statistics, we are able to design a suitable estimator based on a small number of samples only when the target kernel belongs to a subset of restricted complexity. In our study, we restrict the complexity by considering scenarios where the target kernel is both low-rank and smooth over a graph. The motivations for studying such problems come from various real-world applications like recommender systems and social network analysis. We study the problem of estimating smooth kernels on graphs. Using standard tools of non-parametric estimation, we derive a minimax lower bound on the least squares error in terms of the rank and the degree of smoothness of the target kernel. To prove the optimality of our lower-bound, we proceed to develop upper bounds on the error for a least-square estimator based on a non-convex penalty. The proof of these upper bounds depends on bounds for estimators over uniformly bounded function classes in terms of Rademacher complexities. We also propose a computationally tractable estimator based on least-squares with convex penalty. We derive an upper bound for the computationally tractable estimator in terms of a coherence function introduced in this work. Finally, we present some scenarios wherein this upper bound achieves a near-optimal rate.

In this talk we discuss a recent paper by Andrew Chan and Diane Maclagan on Groebner bases for fields, where the valuation of the coefficients is taken into account, when defining initial terms. For these orderings the usual division algorithm does not terminate, and ideas from standard bases needs to be introduced. Groebner bases for fields with valuations play an important role in tropical geometry, where they can be used to compute tropical varieties of a larger class of polynomial ideals than usual Groebner bases.

The work in this dissertation is mainly focused on three subjects which are essentially related to linear systems on metric graphs and its application: (1) rank-determining sets of metric graphs, which can be employed to actually compute the rank function of arbitrary divisors on an arbitrary metric graph, (2) a tropical convexity theory for linear systems on metric graphs, and (3) smoothing of limit linear series of rank one on refined metrized complex (an intermediate object between metric graphs and algebraic curves),

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions on systems linear inequalities. The purpose of this paper is to present the following ``weighted'' generalization: Given an integer k, we prove that there exists a constant c(k,n), depending only on the dimension n and k, such that if a polyhedron {x : Ax <= b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. We work on both upper and lower bounds for this constant. This is joint work with Quentin Louveaux, Iskander Aliev and Robert Bassett.