Compressive Phase Retrieval: Optimal Sample Complexity with Deep Generative Priors

• URL: http://arxiv.org/abs/2008.10579v1
• Date: Mon, 24 Aug 2020 17:40:04 GMT
• Title: Compressive Phase Retrieval: Optimal Sample Complexity with Deep Generative Priors
• Abstract summary: We show that generative priors can lead to a fundamental advance by permitting optimal sample complexity by a tractable algorithm in a challenging inverse problem. These results provide support for generative priors as a new paradigm for signal recovery in a variety of contexts.
• Score: 12.989855325491163
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Advances in compressive sensing provided reconstruction algorithms of sparse signals from linear measurements with optimal sample complexity, but natural extensions of this methodology to nonlinear inverse problems have been met with potentially fundamental sample complexity bottlenecks. In particular, tractable algorithms for compressive phase retrieval with sparsity priors have not been able to achieve optimal sample complexity. This has created an open problem in compressive phase retrieval: under generic, phaseless linear measurements, are there tractable reconstruction algorithms that succeed with optimal sample complexity? Meanwhile, progress in machine learning has led to the development of new data-driven signal priors in the form of generative models, which can outperform sparsity priors with significantly fewer measurements. In this work, we resolve the open problem in compressive phase retrieval and demonstrate that generative priors can lead to a fundamental advance by permitting optimal sample complexity by a tractable algorithm in this challenging nonlinear inverse problem. We additionally provide empirics showing that exploiting generative priors in phase retrieval can significantly outperform sparsity priors. These results provide support for generative priors as a new paradigm for signal recovery in a variety of contexts, both empirically and theoretically. The strengths of this paradigm are that (1) generative priors can represent some classes of natural signals more concisely than sparsity priors, (2) generative priors allow for direct optimization over the natural signal manifold, which is intractable under sparsity priors, and (3) the resulting non-convex optimization problems with generative priors can admit benign optimization landscapes at optimal sample complexity, perhaps surprisingly, even in cases of nonlinear measurements.

Related papers

• Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing [2.0737159978603925]
  We establish theory for compressed sensing in the setting of a tunable family of linear generative priors.<n>We prove that in noiseless compressed sensing, the full-dimensional linear prior attains the minimum expected reconstruction error.<n>This result indicates that the experimental benefits of tunability in compressed sensing with neural network priors arises due to nonlinearities in the generative models.
  arXiv  Detail & Related papers  (2026-09-02T16:22:26Z)
• Deep Physics Prior for First Order Inverse Optimization [17.536106369025717]
  Inverse design optimization aims to infer system parameters from observed solutions. The lack of explicit mathematical representations in many systems complicates this process. Mainstream approaches, including generative AI and Bayesian optimization, address these challenges but have limitations. This paper introduces Deep Physics Prior (DPP), a novel method enabling first-order gradient-based inverse optimization with surrogate machine learning models.
  arXiv  Detail & Related papers  (2025-04-28T21:48:19Z)
• Unrolled denoising networks provably learn optimal Bayesian inference [54.79172096306631]
  We prove the first rigorous learning guarantees for neural networks based on unrolling approximate message passing (AMP) For compressed sensing, we prove that when trained on data drawn from a product prior, the layers of the network converge to the same denoisers used in Bayes AMP.
  arXiv  Detail & Related papers  (2024-09-19T17:56:16Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Accelerating evolutionary exploration through language model-based transfer learning [7.4439048149751095]
  We propose an approach for integrating transfer learning with gene expression programming applied to symbolic regression. The framework integrates Natural Language Processing techniques to discern correlations and recurring patterns from equations explored during previous optimizations. Our results affirm that initial solutions derived via a transfer learning mechanism enhance the algorithm's convergence rate towards improved solutions.
  arXiv  Detail & Related papers  (2024-06-07T08:05:52Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm. We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights. We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
  arXiv  Detail & Related papers  (2020-10-13T08:02:38Z)
• DeepInit Phase Retrieval [10.385009647156407]
  This paper shows how data deep generative models can be utilized to solve challenging phase retrieval problems. It shows that our hybrid approach is able to deliver very high reconstruction results at low sampling rates.
  arXiv  Detail & Related papers  (2020-07-16T09:39:28Z)
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors [12.798687476698063]
  We study an alternative prior where the low-rank component is in the range of a trained generative network. We establish a favorable global optimization landscape for a nonlinear least squares objective. This result suggests that generative priors have no computational-to-statistical gap for structured rank-one matrix recovery.
  arXiv  Detail & Related papers  (2020-06-14T16:46:16Z)
• Invertible generative models for inverse problems: mitigating representation error and dataset bias [6.07645721775351]
  Trained generative models have shown remarkable performance as priors for inverse problems in imaging.<n>We demonstrate that invertible neural networks, which have zero representation error by design, can be effective natural signal priors at inverse problems.
  arXiv  Detail & Related papers  (2019-05-28T08:27:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.