Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems

DOI10.1137/16M1067469MaRDI QIDQ5347292zbMATH OpenOpenAlexWikidataFDO

Authors Michael Kech, Felix Krahmer

Publication date 23 May 2017

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.07316

zbMATH Keywords

bilinear inverse problemsdeconvolutionidentifiabilityinjectivityuniqueness

Mathematics Subject Classification ID

Projective techniques in algebraic geometry (14N05) Inverse problems in linear algebra (15A29) Quadratic and bilinear forms, inner products (15A63) Questions of classical algebraic geometry (51N35) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: We study identifiability for bilinear inverse problems under sparsity and subspace constraints. We show that, up to a global scaling ambiguity, almost all such maps are injective on the set of pairs of sparse vectors if the number of measurements $m$ exceeds $2(s_1+s_2)-2$, where $s_1$ and $s_2$ denote the sparsity of the two input vectors, and injective on the set of pairs of vectors lying in known subspaces of dimensions $n_1$ and $n_2$ if $mgeq2(n_1+n_2)-4$. We also prove that both these bounds are tight in the sense that one cannot have injectivity for a smaller number of measurements. Our proof technique draws from algebraic geometry. As an application we derive optimal identifiability conditions for the deconvolution problem, thus improving on recent work of Li et al. [1].

Recommendations

• Identifiability of the deconvolution problem
• Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
• The convex geometry of linear inverse problems
• Blind inverse problems with isolated spikes
• BranchHull: convex bilinear inversion from the entrywise product of signals with known signs

Cites work

• A mathematical introduction to compressive sensing
• An algebraic characterization of injectivity in phase retrieval
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
• Blind Deconvolution Using Convex Programming
• Compressed sensing
• Constrained quantum tomography of semi-algebraic sets with applications to low-rank matrix recovery
• Exact matrix completion via convex optimization
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• Identifiability and Stability in Blind Deconvolution Under Minimal Assumptions
• Identifiability in Blind Deconvolution With Subspace or Sparsity Constraints
• Improved recovery guarantees for phase retrieval from coded diffraction patterns
• Near-Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices Via Sparse Power Factorization
• On signal reconstruction without phase
• On sparse reconstruction from Fourier and Gaussian measurements
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Phase retrieval from coded diffraction patterns
• Phase retrieval from power spectra of masked signals
• Phase retrieval: stability and recovery guarantees
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Recent developments in blind channel equalization: From cyclostationarity to subspaces
• Self-calibration and biconvex compressive sensing
• Stable signal recovery from incomplete and inaccurate measurements
• Structured random measurements in signal processing
• Suprema of chaos processes and the restricted isometry property
• The convex geometry of linear inverse problems
• The red book of varieties and schemes. Includes the Michigan lectures (1974) on ``Curves and their Jacobians.
• Uniqueness conditions for low-rank matrix recovery

Cited in

(17)

• Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
• Sparse power factorization: balancing peakiness and sample complexity
• Proof methods for robust low-rank matrix recovery
• Information theory and recovery algorithms for data fusion in Earth observation
• Almost everywhere generalized phase retrieval
• Almost everywhere injectivity conditions for the matrix recovery problem
• Self-calibration and bilinear inverse problems via linear least squares
• Geometry and symmetry in short-and-sparse deconvolution
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Maximum likelihood estimation of regularization parameters in high-dimensional inverse problems: an empirical Bayesian approach. II: Theoretical analysis
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Bisparse blind deconvolution through hierarchical sparse recovery
• Auto-calibration and biconvex compressive sensing with applications to parallel MRI
• Jackpot: approximating uncertainty domains with adversarial manifolds

Describes a project that uses

Uses Software

• PhaseLift

This page was built for publication: Optimal injectivity conditions for bilinear inverse problems with applications to identifiability of deconvolution problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347292)