# Joint estimation of smooth graph signals from partial linear measurements

arXiv: https://arxiv.org/abs/2505.23240 · HTML: https://mlsanity.com/paper/2505.23240/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 17 of 17)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [How Fine-Tuning Allows for Effective Meta-Learning](https://mlsanity.com/paper/2105.02221/) (2021)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Adaptive and Robust Multi-Task Learning](https://mlsanity.com/paper/2202.05250/) (2022)
- [Learning from Similar Linear Representations: Adaptivity, Minimaxity, and Robustness](https://mlsanity.com/paper/2303.17765/) (2023)
- [Spectral and matrix factorization methods for consistent community detection in multi-layer networks](https://mlsanity.com/paper/1704.07353/) (2017)
- [Multitask learning over graphs: An Approach for Distributed, Streaming Machine Learning](https://mlsanity.com/paper/2001.02112/) (2020)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [Learning over Multitask Graphs -- Part I: Stability Analysis](https://mlsanity.com/paper/1805.08535/) (2018)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [The Generalized Elastic Net for least squares regression with network-aligned signal and correlated design](https://mlsanity.com/paper/2211.00292/) (2022)
- [On Consistency of Graph-based Semi-supervised Learning](https://mlsanity.com/paper/1703.06177/) (2017)

## Abstract (arXiv)

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.