Low rank estimation of smooth kernels on graphs

Vladimir Koltchinskii, Pedro Rangel

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Let (V , A) be a weighted graph with a finite vertex set V , with a symmetric matrix of nonnegative weights A and with Laplacian δ. Let S* :V × V → ℝ be a symmetric kernel defined on the vertex set V . Consider n i.i.d. observations (Xj,X′j ,Yj ), j = 1, . . . , n, where Xj,X′j are independent random vertices sampled from the uniform distribution in V and Yj ∈ ℝ is a real valued response variable such that (Y j |Xj,X′j ) = S*(X j,X′j ), j = 1, . . . , n. The goal is to estimate the kernel S* based on the data (X1,X′1 ,Y1), . . . , (Xn,X′n,Yn) and under the assumption that S* is low rank and, at the same time, smooth on the graph (the smoothness being characterized by discrete Sobolev norms defined in terms of the graph Laplacian). We obtain several results for such problems including minimax lower bounds on the L2-error and upper bounds for penalized least squares estimators both with nonconvex and with convex penalties.

Original languageEnglish (US)
Pages (from-to)604-640
Number of pages37
JournalAnnals of Statistics
Volume41
Issue number2
DOIs
StatePublished - Apr 1 2013

Keywords

  • Discrete sobolev norm
  • Graph laplacian
  • Low-rank matrix estimation
  • Matrix completion
  • Matrix lasso
  • Minimax error bound
  • Nuclear norm
  • Optimal error rate

Fingerprint Dive into the research topics of 'Low rank estimation of smooth kernels on graphs'. Together they form a unique fingerprint.

  • Cite this