Recovering Structured Data From Superimposed Non-Linear Measurements

This work deals with the problem of distributed data acquisition under non-linear communication constraints. More specifically, we consider a model setup where $M$ distributed nodes take individual measurements of an unknown structured source vector $ \boldsymbol {x}_{0}\in \mathbb {R}^{n}$ , communicating their readings simultaneously to a central receiver . Since this procedure involves collisions and is usually imperfect, the receiver measures a superposition of non-linearly distorted signals . In a first step, we will show that an $s$ -sparse vector $ \boldsymbol {x}_{0}$ can be successfully recovered from $ O(s \cdot \log (2n/s)$ of such superimposed measurements, using a traditional Lasso estimator that does not rely on any knowledge about the non-linear corruptions. This direct method however fails to work for several “uncalibrated” system configurations. These blind reconstruction tasks can be easily handled with the $ \ell ^{}$ -Group-Lasso, but coming along with an increased sampling rate of $ O(s\cdot \max \{M, \log (2n/s) \}$ observations — in fact, the purpose of this lifting strategy is to extend a certain class of bilinear inverse problems to non-linear acquisition. Our two algorithmic approaches are a special instance of a more abstract framework which includes sub-Gaussian measurement designs as well as general (convex) structural constraints. These results are of independent interest for various recovery and learning tasks, as they apply to arbitrary non-linear observation models. Finally, to illustrate the practical scope of our theoretical findings, an application to wireless sensor networks is discussed, which actually serves as the prototypical example of our methodology.