Low rank estimation of smooth kernels on graphs

DOI10.1214/13-AOS1088zbMATH Open1360.62272arXiv1207.4819OpenAlexW3103709271MaRDI QIDQ355091FDOQ355091

Authors: Pedro Rangel, Vladimir Koltchinskii 

Publication date: 24 July 2013

Published in: The Annals of Statistics (Search for Journal in Brave)

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 $Delta$. Let $S_{*}:VimesVmapstomathbbR$ be a symmetric kernel defined on the vertex set V. Consider n i.i.d. observations $(X_j,{X_j}^{\prime },Y_j),j=1,ldots,n$, where $X_j,{X_j}^{\prime }$ are independent random vertices sampled from the uniform distribution in V and $Y_{j}inmathbbR$ is a real valued response variable such that $mathbbE(Y_j|X_j,{X_j}^{\prime })=S_{*}(X_j,{X_j}^{\prime }),j=1,ldots,n$. The goal is to estimate the kernel $S_{*}$ based on the data $(X_1,{X_1}^{\prime },Y_1),ldots,(X_n,{X_n}^{\prime },Y_n)$ 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 $L_2$-error and upper bounds for penalized least squares estimators both with nonconvex and with convex penalties.

Full work available at URL: https://arxiv.org/abs/1207.4819

Recommendations

• Low rank estimation of similarities on graphs
• Kernels and regularization on graphs.
• Estimating a smooth function on a large graph by Bayesian Laplacian regularisation
• Graph kernels
• Graph kernels
• Graph kernels: a survey
• Kernelization using structural parameters on sparse graph classes
• Kernelization using structural parameters on sparse graph classes

zbMATH Keywords

matrix completionnuclear normlow-rank matrix estimationgraph Laplaciandiscrete Sobolev normmatrix Lassominimax error boundoptimal error rate

Mathematics Subject Classification ID

Linear inference, regression (62J99) Estimation in multivariate analysis (62H12) Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15)

Cites Work

• Introduction to nonparametric estimation
• Noisy low-rank matrix completion with general sampling distribution
• Exact matrix completion via convex optimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Estimation of high-dimensional low-rank matrices
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• User-friendly tail bounds for sums of random matrices
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Low Rank Estimation of Similarities on Graphs
• Title not available (Why is that?)

Cited In (3)

• Estimation of low-rank covariance function
• Title not available (Why is that?)
• Estimating a smooth function on a large graph by Bayesian Laplacian regularisation

This page was built for publication: Low rank estimation of smooth kernels on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q355091)