The Convex Geometry of Linear Inverse Problems

Abstract

In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered are those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases such as sparse vectors and low-rank matrices, as well as several others including sums of a few permutations matrices, low-rank tensors, orthogonal matrices, and atomic measures. The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery. Thus this work extends the catalog of simple models that can be recovered from limited linear information via tractable convex programming.

Cited by in corpus (127)

• An overview of low-rank matrix recovery from incomplete observations
• Sparse Regularization via Convex Analysis
• On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data
• Convex Optimization for Big Data
• Image Reconstruction: From Sparsity to Data-adaptive Methods and Machine Learning
• Newtonized Orthogonal Matching Pursuit: Frequency Estimation over the Continuum
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• A discretization-free sparse and parametric approach for linear array signal processing
• Computational and Statistical Tradeoffs via Convex Relaxation
• Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
• Sparse Representation for 3D Shape Estimation: A Convex Relaxation Approach
• Grid-free compressive beamforming
• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• Sparse Signal Processing Concepts for Efficient 5G System Design
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• On risk bounds in isotonic and other shape restricted regression problems
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• A new perspective on least squares under convex constraint
• Convex geometry of quantum resource quantification
• Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
• Rank regularization and Bayesian inference for tensor completion and extrapolation
• Super-Resolution Channel Estimation for Arbitrary Arrays in Hybrid Millimeter-Wave Massive MIMO Systems
• Atomic Norm Minimization for Modal Analysis from Random and Compressed Samples
• ${\ell }^1$-Analysis Minimization and Generalized (Co-)Sparsity: When Does Recovery Succeed?
• Corrupted Sensing: Novel Guarantees for Separating Structured Signals
• Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery -- Application in Fast NMR Spectroscopy
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Unknown sparsity in compressed sensing: Denoising and inference
• Symbol Error Rate Performance of Box-relaxation Decoders in Massive MIMO
• One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations
• Maximum Likelihood-based Gridless DoA Estimation Using Structured Covariance Matrix Recovery and SBL with Grid Refinement
• Gridless DOA Estimation with Multiple Frequencies
• Single Snapshot Super-Resolution DOA Estimation for Arbitrary Array Geometries
• Convexity in source separation: Models, geometry, and algorithms
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• Quantized Spectral Compressed Sensing: Cramer-Rao Bounds and Recovery Algorithms
• Continuous Compressed Sensing With a Single or Multiple Measurement Vectors
• Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery
• Consistent Basis Pursuit for Signal and Matrix Estimates in Quantized Compressed Sensing
• Multicompartment Magnetic Resonance Fingerprinting
• Noisy Matrix Completion under Sparse Factor Models
• Learning Model-Based Sparsity via Projected Gradient Descent
• Spatial Source Subtraction Based on Incomplete Measurements of Relative Transfer Function
• Gauge optimization and duality
• Guaranteed recovery of quantum processes from few measurements
• Convex Iteration for Distance-Geometric Inverse Kinematics
• Low-rank Optimization with Convex Constraints
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Matrix completion with deterministic pattern - a geometric perspective
• Super-Resolution MIMO Radar
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• Distributed Compressed Sensing off the Grid
• Approximate Support Recovery of Atomic Line Spectral Estimation: A Tale of Resolution and Precision
• Limits on Sparse Data Acquisition: RIC Analysis of Finite Gaussian Matrices
• Signal reconstruction from the magnitude of subspace components
• Coded Demixing for Unsourced Random Access
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• The sample complexity of weighted sparse approximation
• Estimating Sparse Signals Using Integrated Wideband Dictionaries
• Classical simulation of non-Gaussian fermionic circuits
• Learning Credible Models
• Recovery of Structured Signals with Prior Information via Maximizing Correlation
• High Resolution Radar Sensing with Compressive Illumination
• Identification of Linear Time-Varying Systems Through Waveform Diversity
• A convex variational model for learning convolutional image atoms from incomplete data
• Simultaneous Sparse Recovery and Blind Demodulation
• Heterogeneous Networked Data Recovery from Compressive Measurements Using a Copula Prior
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• Blind Goal-Oriented Massive Access for Future Wireless Networks
• Robust analysis ${\ell }_1$-recovery from Gaussian measurements and total variation minimization
• Quantum State Tomography for Matrix Product Density Operators
• Improving compressed sensing with the diamond norm
• On the Error in Phase Transition Computations for Compressed Sensing
• Living near the edge: A lower-bound on the phase transition of total variation minimization
• Frank-Wolfe Network: An Interpretable Deep Structure for Non-Sparse Coding
• TV-based Reconstruction of Periodic Functions
• Compressed Super-Resolution of Positive Sources
• Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• When does OMP achieve exact recovery with continuous dictionaries?
• Sparse Recovery Beyond Compressed Sensing: Separable Nonlinear Inverse Problems
• New Risk Bounds for 2D Total Variation Denoising
• Blind Two-Dimensional Super Resolution in Multiple Input Single Output Linear Systems
• The geometry of rank-one tensor completion
• Low-Rank Inducing Norms with Optimality Interpretations
• Group Invariant Dictionary Learning
• Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data
• Generalizing CoSaMP to Signals from a Union of Low Dimensional Linear Subspaces
• Demixing Sines and Spikes Using Multiple Measurement Vectors
• Hierarchical Isometry Properties of Hierarchical Measurements
• Weighted ${\ell }_1$-minimization for generalized non-uniform sparse model
• Active User Detection and Channel Estimation for Spatial-based Random Access in Crowded Massive MIMO Systems via Blind Super-resolution
• Rate-Distortion Dimension of Stochastic Processes
• Timely and Painless Breakups: Off-the-grid Blind Message Recovery and Users' Demixing
• A Unified Approach to Uniform Signal Recovery From Non-Linear Observations
• Quantized Corrupted Sensing with Random Dithering
• Recovering Structured Data From Superimposed Non-Linear Measurements
• Local Convergence of Proximal Splitting Methods for Rank Constrained Problems
• Super-resolution of Green's functions on noisy quantum computers
• Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Low Dimensional Atomic Norm Representations in Line Spectral Estimation
• Decomposable Norm Minimization with Proximal-Gradient Homotopy Algorithm
• Off-the-grid Recovery of Time and Frequency Shifts with Multiple Measurement Vectors
• A Geometrical Stability Condition for Compressed Sensing
• Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer
• Robust 1-Bit Compressed Sensing via Hinge Loss Minimization
• On the Stable Resolution Limit of Total Variation Regularization for Spike Deconvolution
• Low-Rank Matrix Recovery from Noise via an MDL Framework-based Atomic Norm
• Tensor Decomposition for EEG Signal Retrieval
• How can one sample images with sampling rates close to the theoretical minimum?
• Convexifying Sparse Interpolation with Infinitely Wide Neural Networks: An Atomic Norm Approach
• Optimality of 1-norm regularization among weighted 1-norms for sparse recovery: a case study on how to find optimal regularizations
• Efficient Two-Dimensional Line Spectrum Estimation Based on Decoupled Atomic Norm Minimization
• Accelerated Nonnegative Tensor Completion via Integer Programming
• Some facts about the optimality of the LSE in the Gaussian sequence model with convex constraint
• On data usage and predictive behavior of data-driven predictive control with 1-norm regularization
• Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros
• Efficient Proximal Mapping Computation for Unitarily Invariant Low-Rank Inducing Norms
• Characterizing the minimax rate of nonparametric regression under bounded star-shaped constraints
• Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix
• Online codes for analog signals
• Exact threshold for approximate ellipsoid fitting of random points
• Multi-Target ISAR Imaging of UAV Swarms Using Fast Reweighted Atomic Norm Denoising
• The Necessary And Sufficient Condition for Generalized Demixing