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

DOI10.1137/16M1067469zbMATH Open1365.15021arXiv1603.07316OpenAlexW2963507583WikidataQ122897659 ScholiaQ122897659MaRDI QIDQ5347292FDOQ5347292

Authors: Michael Kech, Felix Krahmer 

Publication date: 23 May 2017

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

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].

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

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

zbMATH Keywords

identifiabilitydeconvolutionuniquenessinjectivitybilinear inverse problems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Almost everywhere generalized phase retrieval
• Sparse power factorization: balancing peakiness and sample complexity
• Geometry and Symmetry in Short-and-Sparse Deconvolution
• Maximum Likelihood Estimation of Regularization Parameters in High-Dimensional Inverse Problems: An Empirical Bayesian Approach. Part II: Theoretical Analysis
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Efficient Identification of Butterfly Sparse Matrix Factorizations
• Self-Calibration and Bilinear Inverse Problems via Linear Least Squares
• Almost everywhere injectivity conditions for the matrix recovery problem
• Information theory and recovery algorithms for data fusion in Earth observation
• Riemannian thresholding methods for row-sparse and low-rank matrix recovery
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Proof methods for robust low-rank matrix recovery

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)