mlsanityData to 7 Oct 2026

Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems

arXiv 2111.03237 ↗First posted 5 Nov 2021cs.IT cs.LG math.ITcited by 0

Not on the map. Why?

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.

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

Builds on

24 of 80 references.

References · 24

  1. 2013Expectation Propagation for approximate Bayesian inferencecited by 172
  2. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  3. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  4. 2018A modern maximum-likelihood theory for high-dimensional logistic regressioncited by 79
  5. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  6. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  7. 2021A unifying tutorial on Approximate Message Passingcited by 49
  8. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  9. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  10. 2020The estimation error of general first order methodscited by 33
  11. 2020Approximate Message Passing algorithms for rotationally invariant matricescited by 31
  12. 2016Solving Systems of Random Quadratic Equations via Truncated Amplitude Flowcited by 28
12 more
  1. 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
  2. 2016PhaseMax: Convex Phase Retrieval via Basis Pursuitcited by 25
  3. 2020Approximate Message Passing with Spectral Initialization for Generalized Linear Modelscited by 22
  4. 2016Finite Sample Analysis of Approximate Message Passing Algorithmscited by 20
  5. 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
  6. 2019Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passingcited by 14
  7. 2021PCA Initialization for Approximate Message Passing in Rotationally Invariant Modelscited by 14
  8. 2017Inference in Deep Networks in High Dimensionscited by 12
  9. 2016Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxationcited by 11
  10. 2016Expectation Consistent Approximate Inference: Generalizations and Convergencecited by 6
  11. 2016Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equationscited by 4
  12. 2019RLS Precoding for Massive MIMO Systems with Nonlinear Front-Endcited by 1

Built on by

Not cited yet.