# Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 80 references that are in the map.
- First posted on arXiv 5 Nov 2021.

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

- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018)
- [The committee machine: Computational to statistical gaps in learning a two-layers neural network](https://mlsanity.com/paper/1806.05451/) (2018)
- [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Fundamental Limits of Weak Recovery with Applications to Phase Retrieval](https://mlsanity.com/paper/1708.05932/) (2017)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020)
- [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016)
- [Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation](https://mlsanity.com/paper/1702.06435/) (2017)
- [PhaseMax: Convex Phase Retrieval via Basis Pursuit](https://mlsanity.com/paper/1610.07531/) (2016)
- [Approximate Message Passing with Spectral Initialization for Generalized Linear Models](https://mlsanity.com/paper/2010.03460/) (2020)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [Exact asymptotics for phase retrieval and compressed sensing with random generative priors](https://mlsanity.com/paper/1912.02008/) (2019)
- [Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing](https://mlsanity.com/paper/1907.07502/) (2019)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [Inference in Deep Networks in High Dimensions](https://mlsanity.com/paper/1706.06549/) (2017)
- [Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation](https://mlsanity.com/paper/1610.04210/) (2016)
- [Expectation Consistent Approximate Inference: Generalizations and Convergence](https://mlsanity.com/paper/1602.07795/) (2016)
- [Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations](https://mlsanity.com/paper/1605.07719/) (2016)
- [RLS Precoding for Massive MIMO Systems with Nonlinear Front-End](https://mlsanity.com/paper/1905.05227/) (2019)

## Abstract (arXiv)

We consider an inverse problem y= f(Ax), where x∈ℝn is the signal of interest, A is the sensing matrix, f is a nonlinear function and y ∈ ℝm is the measurement vector. In many applications, we have some level of freedom to design the sensing matrix A, and in such circumstances we could optimize 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 x from 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 bmmathbfA 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.