Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Low Rank Estimation of Similarities on Graphs
verfasst von : Vladimir Koltchinskii, Pedro Rangel
Erschienen in: High Dimensional Probability VI
Verlag: Springer Basel
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let (
V,E
) be a graph with vertex set
V
and edge set
E.
Let (
X,X’,Y
)
∈ V × V × {−
1, 1} be a random triple, where
X,X’
are independent uniformly distributed vertices and
Y
is a label indicating whether
X,X’
are “similar” (
Y
= +1), or not (
Y
=
−
1). Our goal is to estimate the regression function
$$S_*(u,v)\,=\, {\mathbb{E}{(Y|X\,=\,u,X^\prime\,=v)}},u,v\, \in\,V$$
based on training data consisting of
n
i.i.d. copies of (
X,X’,Y
)
.
We are interested in this problem in the case when
S
*
is a symmetric low rank kernel and, in addition to this, it is assumed that
S
*
is “smooth” on the graph. We study estimators based on a modified least squares method with complexity penalization involving both the nuclear norm and Sobolev type norms of symmetric kernels on the graph and prove upper bounds on
L
2-type errors of such estimators with explicit dependence both on the rank of
S
*
and on the degree of its smoothness.