Non-Negative Structured Regression with Applications in Communication and Data Science

Abstract

In this project we propose to design efficient algorithms for the reconstruction of redundant-encoded signals in wireless communication and network properties in data science. The main motivation of this line of work comes from model-based compressed sensing (CS) with non-negativity priors. CS is based on the fact that the intrinsic dimension of many digital signals or large data sets is typically far less than their ambient dimensions, for example the sparse representation of images, videos, audio data, network status information like activity and novel coding techniques for wireless communication.

Traditionally, redundancy and structure in the data is exploited after the acquisition (measurement), which may be very costly in terms storage and bandwidth. CS instead attempts to overcome this by performing sampling and compression simultaneously, i.e., acquisition from a sub-Nyquist perspective.

CS works well with provable guarantees for dense matrices. However, in communication engineering and data science problems related to complex networks structured sparse matrices are used due to more efficient storage and processing. Therefore we focus on binary matrices, matrices formed by sampling Hadamard matrices, expander matrices, etc. For such type of matrices CS often reduces to linear sketching, which has been applied in data streaming, and graph sketching.

Furthermore, sparsity (compressibility) can be regarded as first order structure of a signal (object) of interest. In practice, most objects of interest exhibit second other structures like block-sparsity, tree-sparsity, non-negativity, etc. Both the communication and complex networks problems we consider have the non-negativity or other conic constraint, hence the title of the project.

DAAD-Project Description

Related Publications

Bubacarr Bah, Hendrik Bernd Petersen and Peter Jung, “Compressed sensing-based SARS-CoV-2 pool testing,” Notices of the American Mathematical Society, vol. 2, 2024.
[bibtex] [url]

@article{ams:Bah2024,
  author = {Bah, Bubacarr and Petersen, Hendrik Bernd and Jung, Peter},
  title = {Compressed sensing-based SARS-CoV-2 pool testing},
  journal = {Notices of the American Mathematical Society},
  year = {2024},
  volume = {2},
  url = {https://www.ams.org/journals/notices/202402/noti2869/noti2869.html?adat=February 2024&trk=2869}
}

Hendrik Bernd Petersen and Peter Jung, “Robust instance-optimal recovery of sparse signals at unknown noise levels,” Information and Inference: A Journal of the IMA, vol. 11, no. 3, pp. 845-887, aug 2022.
[bibtex] [url]

@article{Petersen:slasso:2021,
  author = {Petersen, Hendrik Bernd and Jung, Peter},
  title = {Robust instance-optimal recovery of sparse signals at unknown noise levels},
  journal = {Information and Inference: A Journal of the IMA},
  year = {2022},
  volume = {11},
  number = {3},
  pages = {845--887},
  url = {http://arxiv.org/abs/2008.08385 https://academic.oup.com/imaiai/advance-article/doi/10.1093/imaiai/iaab015/6340096},
  doi = {https://doi.org/10.1093/imaiai/iaab015}
}

Alexander Fengler, Saeid Haghighatshoar, Peter Jung and Giuseppe Caire, “Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access With a Massive MIMO Receiver,” IEEE Transactions on Information Theory, vol. 67, no. 5, pp. 2925-2951, may 2021.
[bibtex] [url]

@article{Fengler:TIT:Bayesian:2021,
  author = {Fengler, Alexander and Haghighatshoar, Saeid and Jung, Peter and Caire, Giuseppe},
  title = {Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access With a Massive MIMO Receiver},
  journal = {IEEE Transactions on Information Theory},
  year = {2021},
  volume = {67},
  number = {5},
  pages = {2925--2951},
  url = {http://arxiv.org/abs/1910.11266 https://ieeexplore.ieee.org/document/9374476/},
  doi = {https://doi.org/10.1109/TIT.2021.3065291}
}

Alexander Fengler, Peter Jung and Giuseppe Caire, “SPARCs for Unsourced Random Access,” IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6894-6915, oct 2021.
[bibtex] [url]

@article{Fengler:TIT:sparcs,
  author = {Fengler, Alexander and Jung, Peter and Caire, Giuseppe},
  title = {SPARCs for Unsourced Random Access},
  journal = {IEEE Transactions on Information Theory},
  year = {2021},
  volume = {67},
  number = {10},
  pages = {6894--6915},
  url = {http://arxiv.org/abs/1901.06234 https://ieeexplore.ieee.org/document/9432925/},
  doi = {https://doi.org/10.1109/TIT.2021.3081189}
}

Fabian Jaensch and Peter Jung, “Robust Recovery of Sparse Nonnegative Weights from Mixtures of Positive-Semidefinite Matrices,” to appear in Information and Inference: A Journal of the IMA, 2021.
[bibtex] [url]

@article{Jaensch:psd:2021,
  author = {Jaensch, Fabian and Jung, Peter},
  title = {Robust Recovery of Sparse Nonnegative Weights from Mixtures of Positive-Semidefinite Matrices},
  journal = {to appear in Information and Inference: A Journal of the IMA},
  year = {2021},
  url = {http://arxiv.org/abs/2003.12005 https://academic.oup.com/imaiai/advance-article-abstract/doi/10.1093/imaiai/iaab024/6385797},
  doi = {https://doi.org/10.1093/imaiai/iaab024}
}

Hendrik Bernd Petersen, Shankar Agarwal, Peter Jung and Bubacarr Bah, “Improving the Reliability of Pooled Testing with Combinatorial Decoding and Compressed Sensing,” in 55th Annual Conference on Information Sciences and Systems (CISS), 2021.
[bibtex] [url]

@inproceedings{Petersen:ciss21,
  author = {Petersen, Hendrik Bernd and Agarwal, Shankar and Jung, Peter and Bah, Bubacarr},
  title = {Improving the Reliability of Pooled Testing with Combinatorial Decoding and Compressed Sensing},
  booktitle = {55th Annual Conference on Information Sciences and Systems (CISS)},
  year = {2021},
  url = {https://ieeexplore.ieee.org/document/9400261}
}

Hendrik Bernd Petersen, Bubacarr Bah and Peter Jung, “Efficient Tuning-Free l1-Regression of Nonnegative Compressible Signals,” Frontiers in Applied Mathematics and Statistics, vol. 7, jun 2021.
[bibtex] [url]

@article{Petersen:nnlad:2021,
  author = {Petersen, Hendrik Bernd and Bah, Bubacarr and Jung, Peter},
  title = {Efficient Tuning-Free l1-Regression of Nonnegative Compressible Signals},
  journal = {Frontiers in Applied Mathematics and Statistics},
  year = {2021},
  volume = {7},
  url = {http://arxiv.org/abs/2003.13092 https://www.frontiersin.org/articles/10.3389/fams.2021.615573/full},
  doi = {https://doi.org/10.3389/fams.2021.615573}
}

Hendrik Bernd Petersen, Bubacarr Bah and Peter Jung, “Practical High-Throughput, Non-Adaptive and Noise-Robust SARS-CoV-2 Testing,” jul 2020.
[bibtex] [url]

@article{Petersen:covidtesting,
  author = {Petersen, Hendrik Bernd and Bah, Bubacarr and Jung, Peter},
  title = {Practical High-Throughput, Non-Adaptive and Noise-Robust SARS-CoV-2 Testing},
  year = {2020},
  url = {http://arxiv.org/abs/2007.09171}
}

Alexander Fengler, Saeid Haghighatshoar, Peter Jung and Giuseppe Caire, “Grant-Free Massive Random Access with a Massive MIMO Receiver,” in Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2019-Novem, pp. 23-30, nov 2019.
[bibtex] [url]

@inproceedings{fengler:asilomar19,
  author = {Fengler, Alexander and Haghighatshoar, Saeid and Jung, Peter and Caire, Giuseppe},
  title = {Grant-Free Massive Random Access with a Massive MIMO Receiver},
  booktitle = {Conference Record - Asilomar Conference on Signals, Systems and Computers},
  year = {2019},
  volume = {2019-Novem},
  pages = {23--30},
  url = {http://arxiv.org/abs/1912.01459 https://ieeexplore.ieee.org/document/9049039},
  doi = {https://doi.org/10.1109/IEEECONF44664.2019.9049039}
}

Y. Shadmi, P. Jung and G. Caire, “Sparse Non-Negative Recovery from Shifted Symmetric Subgaussian Measurements using NNLS,” in IEEE Int. Symposium on Information Theory (ISIT), 2019.
[bibtex]

@inproceedings{Shadmi:isit19,
  author = {Shadmi, Y. and Jung, P. and Caire, G.},
  title = {Sparse Non-Negative Recovery from Shifted Symmetric Subgaussian Measurements using NNLS},
  booktitle = {IEEE Int. Symposium on Information Theory (ISIT)},
  year = {2019}
}

Yonatan Shadmi, Peter Jung and Giuseppe Caire, “Sparse Non-Negative Recovery from Biased Subgaussian Measurements using NNLS,” arXiv, jan 2019.
[bibtex] [url]

@article{Shadmi2019,
  author = {Shadmi, Yonatan and Jung, Peter and Caire, Giuseppe},
  title = {Sparse Non-Negative Recovery from Biased Subgaussian Measurements using NNLS},
  journal = {arXiv},
  year = {2019},
  url = {http://arxiv.org/abs/1901.05727}
}