Low Complexity Regularized Phase Retrieval

• URL: http://arxiv.org/abs/2407.16413v1
• Date: Tue, 23 Jul 2024 11:58:08 GMT
• Title: Low Complexity Regularized Phase Retrieval
• Authors: Jean-Jacques Godeme, Jalal Fadili,
• Abstract summary: This regularizer is intended to promote solutions conforming to some notion of simplicity or low complexity. We investigate both noiseless recovery and stability to noise and provide a very general and unified analysis framework.
• Score: 0.6522338519818377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the phase retrieval problem in the situation where the vector to be recovered has an a priori structure that can encoded into a regularization term. This regularizer is intended to promote solutions conforming to some notion of simplicity or low complexity. We investigate both noiseless recovery and stability to noise and provide a very general and unified analysis framework that goes far beyond the sparse phase retrieval mostly considered in the literature. In the noiseless case we provide sufficient conditions under which exact recovery, up to global sign change, is possible. For Gaussian measurement maps, we also provide a sample complexity bound for exact recovery. This bound depends on the Gaussian width of the descent cone at the soughtafter vector which is a geometric measure of the complexity of the latter. In the noisy case, we consider both the constrained (Mozorov) and penalized (Tikhonov) formulations. We provide sufficient conditions for stable recovery and prove linear convergence for sufficiently small noise. For Gaussian measurements, we again give a sample complexity bound for linear convergence to hold with high probability. This bound scales linearly in the intrinsic dimension of the sought-after vector but only logarithmically in the ambient dimension.

Related papers

• 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)
• Stable Phase Retrieval with Mirror Descent [0.5312303275762104]
  We show that mirror descent converges to a critical point of the phase retrieval problem. We provide global convergence guarantees that ensure that with high probability, mirror descent converges to a global minimizer near the true vector.
  arXiv  Detail & Related papers  (2024-05-17T13:07:14Z)
• The Complexity of Being Entangled [0.0]
  Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations. For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost.
  arXiv  Detail & Related papers  (2023-11-07T19:00:02Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  We show that the problem suffers from a $frackSNR2$-to-$frack2SNR2$ statistical-to-computational gap. We also analyze a simple thresholding algorithm which, outside of the narrow regime where the problem is hard, solves the associated mixed regression detection problem.
  arXiv  Detail & Related papers  (2023-03-03T18:03:49Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Convergence bounds for nonlinear least squares for tensor recovery [0.0]
  We consider the problem of approximating a function in general nonlinear subsets of L2 when only a weighted Monte Carlo estimate of the L2-norm can be computed. By restricting the model class to a neighbourhood of the best approximation, we can derive improved worst-case bounds for the sample complexity.
  arXiv  Detail & Related papers  (2022-08-23T13:25:30Z)
• Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs [22.41443027099101]
  We show that standard sparse random designs are with high probability robust to adversarial measurement erasures. This is the first time that partial recoverability of arbitrary sparse signals under erasures has been studied in compressed sensing.
  arXiv  Detail & Related papers  (2022-03-05T22:16:05Z)
• 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)
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors [52.06292503723978]
  Motivated by advances in compressive sensing with generative models, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.Gaussian measurements. We demonstrate that the Binary $epsilon$-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models.
  arXiv  Detail & Related papers  (2020-02-05T09:44:10Z)

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.