Joint estimation of smooth graph signals from partial linear measurements

Given an undirected and connected graph G on T vertices, suppose each vertex t has a latent signal xt ∈ ℝn associated to it. Given partial linear measurements of the signals, for a potentially small subset of the vertices, our goal is to estimate xt's. Assuming that the signals are smooth w.r.t G, in the sense that the quadratic variation of the signals over the graph is small, we obtain non-asymptotic bounds on the mean squared error for jointly recovering xt's, for the smoothness penalized least squares estimator. In particular, this implies for certain choices of G that this estimator is weakly consistent (as T rightarrow ∞) under potentially very stringent sampling, where only one coordinate is measured per vertex for a vanishingly small fraction of the vertices. The results are extended to a ``multi-layer'' ranking problem where xt corresponds to the latent strengths of a collection of n items, and noisy pairwise difference measurements are obtained at each ``layer'' t via a measurement graph Gt. Weak consistency is established for certain choices of G even when the individual Gt's are very sparse and disconnected.