Show simple item record

dc.contributor.advisorKoltchinskii, Vladimir I.
dc.contributor.authorRangel Walteros, Pedro Andres
dc.date.accessioned2015-01-12T20:43:48Z
dc.date.available2015-01-12T20:43:48Z
dc.date.created2014-12
dc.date.issued2014-07-23
dc.date.submittedDecember 2014
dc.identifier.urihttp://hdl.handle.net/1853/52988
dc.description.abstractThis 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. 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. The motivations for studying such problems come from various real-world applications like recommender systems and social network analysis.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectLow-rank matrix completion
dc.subjectKernels on graphs
dc.subjectHigh dimensional probability
dc.titleA non-asymptotic study of low-rank estimation of smooth kernels on graphs
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentMathematics
thesis.degree.levelDoctoral
dc.contributor.committeeMemberLounici, Karim
dc.contributor.committeeMemberBlekherman, Greg
dc.contributor.committeeMemberLeykin, Anton
dc.contributor.committeeMemberSong, Le
dc.date.updated2015-01-12T20:43:49Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record