Correlated Compressive Sensing for Networked Data

Tianlin Shi Tsinghua University, Da Tang, Liwen Xu, Thomas Moscibroda
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:489-498, 2014.

Abstract

We consider the problem of recovering sparse correlated data on networks. To improve accu- racy and reduce costs, it is strongly desirable to take the potentially useful side-information of network structure into consideration. In this pa- per we present a novel correlated compressive sensing method called CorrCS for networked data. By naturally extending Bayesian compres- sive sensing, we extract correlations from net- work topology and encode them into a graphical model as prior. Then we derive posterior infer- ence algorithms for the recovery of jointly sparse and correlated networked data. First, we design algorithms to recover the data based on pairwise correlations between neighboring nodes in the network. Next, we generalize this model through a diffusion process to capture higher-order cor- relations. Both real-valued and binary data are considered. Our models are extensively tested on several real datasets from social and sensor networks and are shown to outperform baseline compressive sensing models in terms of recovery performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14n, title = {Correlated Compressive Sensing for Networked Data}, author = {University, Tianlin Shi Tsinghua and Tang, Da and Xu, Liwen and Moscibroda, Thomas}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {489--498}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14n/university14n.pdf}, url = {https://proceedings.mlr.press/r12/university14n.html}, abstract = {We consider the problem of recovering sparse correlated data on networks. To improve accu- racy and reduce costs, it is strongly desirable to take the potentially useful side-information of network structure into consideration. In this pa- per we present a novel correlated compressive sensing method called CorrCS for networked data. By naturally extending Bayesian compres- sive sensing, we extract correlations from net- work topology and encode them into a graphical model as prior. Then we derive posterior infer- ence algorithms for the recovery of jointly sparse and correlated networked data. First, we design algorithms to recover the data based on pairwise correlations between neighboring nodes in the network. Next, we generalize this model through a diffusion process to capture higher-order cor- relations. Both real-valued and binary data are considered. Our models are extensively tested on several real datasets from social and sensor networks and are shown to outperform baseline compressive sensing models in terms of recovery performance.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Correlated Compressive Sensing for Networked Data %A Tianlin Shi Tsinghua University %A Da Tang %A Liwen Xu %A Thomas Moscibroda %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14n %I PMLR %P 489--498 %U https://proceedings.mlr.press/r12/university14n.html %V R12 %X We consider the problem of recovering sparse correlated data on networks. To improve accu- racy and reduce costs, it is strongly desirable to take the potentially useful side-information of network structure into consideration. In this pa- per we present a novel correlated compressive sensing method called CorrCS for networked data. By naturally extending Bayesian compres- sive sensing, we extract correlations from net- work topology and encode them into a graphical model as prior. Then we derive posterior infer- ence algorithms for the recovery of jointly sparse and correlated networked data. First, we design algorithms to recover the data based on pairwise correlations between neighboring nodes in the network. Next, we generalize this model through a diffusion process to capture higher-order cor- relations. Both real-valued and binary data are considered. Our models are extensively tested on several real datasets from social and sensor networks and are shown to outperform baseline compressive sensing models in terms of recovery performance. %Z Reissued by PMLR on 04 October 2026.
APA
University, T.S.T., Tang, D., Xu, L. & Moscibroda, T.. (2014). Correlated Compressive Sensing for Networked Data. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:489-498 Available from https://proceedings.mlr.press/r12/university14n.html. Reissued by PMLR on 04 October 2026.

Related Material