Joint estimation of smooth graph signals from partial linear measurements
This addresses the challenge of signal recovery in graph-based systems with limited data, which is incremental as it extends existing smoothness assumptions to more extreme sampling scenarios.
The paper tackles the problem of jointly estimating smooth graph signals from partial linear measurements, obtaining non-asymptotic bounds on mean squared error and proving weak consistency under stringent sampling conditions, such as measuring only one coordinate per vertex for a vanishingly small fraction of vertices.
Given an undirected and connected graph $G$ on $T$ vertices, suppose each vertex $t$ has a latent signal $x_t \in \mathbb{R}^n$ associated to it. Given partial linear measurements of the signals, for a potentially small subset of the vertices, our goal is to estimate $x_t$'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 $x_t$'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 \infty$) 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 $x_t$ 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 $G_t$. Weak consistency is established for certain choices of $G$ even when the individual $G_t$'s are very sparse and disconnected.