Toward Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems (Junjie Ma and collaborators)

　　We consider an inverse problem \boldsymbol {y}= f(\boldsymbol {Ax}) , where \boldsymbol {x}\in \mathbb {R}^{n} is the signal of interest, \boldsymbol {A} is the sensing matrix, f is a nonlinear function and \boldsymbol {y} \in \mathbb {R}^{m} is the measurement vector. In many applications, we have some level of freedom to design the sensing matrix \boldsymbol {A}, and in such circumstances we could optimize \boldsymbol {A} to achieve better reconstruction performance. As a first step towards optimal design, it is important to understand the impact of the sensing matrix on the difficulty of recovering \boldsymbol {x} from \boldsymbol {y}. In this paper, we study the performance of one of the most successful recovery methods, i.e., the expectation propagation (EP) algorithm. We define a notion of spikiness for the spectrum of \boldsymbol {A} and show the importance of this measure for the performance of EP. We show that whether a spikier spectrum can hurt or help the recovery performance depends on f. Based on our framework, we are able to show that, in phase-retrieval problems, matrices with spikier spectrums are better for EP, while in 1-bit compressed sensing problems, less spiky spectrums lead to better performance. Our results unify and substantially generalize existing results that compare Gaussian and orthogonal matrices, and provide a platform towards designing optimal sensing systems.

　　Publication:

　　IEEE Transactions on Information Theory, vol. 70, no. 1, pp. 482-508, Jan. 2024

　　http://dx.doi.org/10.1109/TIT.2023.3307553.

　　Author:

　　Junjie Ma

　　Department of Statistics, Columbia University, New York City, NY, USA

　　Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China

　　Email: majunjie@lsec.cc.ac.cn

　　Ji Xu

　　Department of Computer Science, Columbia University, New York City, NY, USA

　　Arian Maleki

　　Department of Statistics, Columbia University, New York City, NY, USA