Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
From MaRDI portal
Publication:6109969
Abstract: We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e.a sort of random Fourier design and Gaussian design). Despite the wide applicability, the theoretical understanding about these two paradigms remains largely inadequate in the presence of random noise. The current paper makes two contributions by demonstrating that: (1) a two-stage nonconvex algorithm attains minimax-optimal accuracy within a logarithmic number of iterations. (2) convex relaxation also achieves minimax-optimal statistical accuracy vis-`a-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees.
Cites work
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- Blind deconvolution by a steepest descent algorithm on a quotient manifold
- Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
- Blind Deconvolution Using Convex Programming
- Blind Demixing and Deconvolution at Near-Optimal Rate
- Blind Recovery of Sparse Signals From Subsampled Convolution
- BranchHull: convex bilinear inversion from the entrywise product of signals with known signs
- Compressed Sensing Off the Grid
- Convolutional Phase Retrieval via Gradient Descent
- Exact matrix completion via convex optimization
- Fast and Guaranteed Blind Multichannel Deconvolution Under a Bilinear System Model
- GESPAR: Efficient Phase Retrieval of Sparse Signals
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
- Guaranteed Matrix Completion via Non-Convex Factorization
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- Identifiability in Blind Deconvolution With Subspace or Sparsity Constraints
- Inference and uncertainty quantification for noisy matrix completion
- Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis
- Low-rank matrix completion using alternating minimization
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
- Matrix completion from noisy entries
- Multichannel Sparse Blind Deconvolution on the Sphere
- Near-optimal bounds for phase synchronization
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Nonconvex Demixing From Bilinear Measurements
- Nonconvex Low-Rank Tensor Completion from Noisy Data
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
- Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems
- Optimization-Based AMP for Phase Retrieval: The Impact of Initialization and $\ell_{2}$ Regularization
- Phase recovery, MaxCut and complex semidefinite programming
- Phase retrieval via Wirtinger flow: theory and algorithms
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Rank-Sparsity Incoherence for Matrix Decomposition
- Rapid, robust, and reliable blind deconvolution via nonconvex optimization
- Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing
- Robust principal component analysis?
- Robust Spectral Compressed Sensing via Structured Matrix Completion
- ROP: matrix recovery via rank-one projections
- Self-calibration and biconvex compressive sensing
- Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
- Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- Sparse Phase Retrieval via Truncated Amplitude Flow
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Structured Local Optima in Sparse Blind Deconvolution
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
Cited in
(4)- Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
- Bisparse blind deconvolution through hierarchical sparse recovery
- Robust Matrix Completion with Heavy-Tailed Noise
- How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?
This page was built for publication: Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109969)
