The convex geometry of linear inverse problems

DOI10.1007/S10208-012-9135-7zbMATH Open1280.52008arXiv1012.0621OpenAlexW3124617746WikidataQ114830779 ScholiaQ114830779MaRDI QIDQ1928276FDOQ1928276

Benjamin Recht, Alan S. Willsky, Venkat Chandrasekaran, Pablo A. Parrilo

Publication date: 3 January 2013

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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.

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

zbMATH Keywords

convex optimizationinverse problemsemidefinite programmingdata recoveryGaussian widthatomic norms

Mathematics Subject Classification ID

Convex programming (90C25) Geometric probability and stochastic geometry (60D05) Semidefinite programming (90C22) Convex functions and convex programs in convex geometry (52A41) Approximation by arbitrary linear expressions (41A45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
• On the conditions used to prove oracle results for the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• Universal approximation bounds for superpositions of a sigmoidal function
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Introductory lectures on convex optimization. A basic course.
• Orthogonal tensor decompositions
• Robust principal component analysis?
• A Singular Value Thresholding Algorithm for Matrix Completion
• Tensor Decompositions and Applications
• Exact matrix completion via convex optimization
• Local operator theory, random matrices and Banach spaces.
• Decoding by Linear Programming
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Convex Analysis
• The concentration of measure phenomenon
• Rank-Sparsity Incoherence for Matrix Decomposition
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Compressed sensing
• Sparse Reconstruction by Separable Approximation
• Signal Recovery by Proximal Forward-Backward Splitting
• Lectures on Polytopes
• Optimization. Algorithms and consistent approximations
• Linearized Bregman iterations for compressed sensing
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• An EM algorithm for wavelet-based image restoration
• A generalized proximal point algorithm for certain non-convex minimization problems
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Precise Stability Phase Transitions for $\ell_1$ Minimization: A Unified Geometric Framework
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Fixed point and Bregman iterative methods for matrix rank minimization
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Approximating the Cut-Norm via Grothendieck's Inequality
• Semidefinite programming relaxations for semialgebraic problems
• Some remarks on greedy algorithms
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Geometry of cuts and metrics
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Probability of unique integer solution to a system of linear equations
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Inferring Rankings Using Constrained Sensing
• Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• Theta Bodies for Polynomial Ideals
• Null space conditions and thresholds for rank minimization
• Combinatorics of random processes and sections of convex bodies
• A GENERAL ATOMIC DECOMPOSITION THEOREM AND BANACH'S CLOSED RANGE THEOREM

Cited In (only showing first 100 items - show all)

• Super-resolution by means of Beurling minimal extrapolation
• Analysis of sparse recovery algorithms via the replica method
• Stable separation and super-resolution of mixture models
• Complex phase retrieval from subgaussian measurements
• Dimension-free bounds for largest singular values of matrix Gaussian series
• Cut Pursuit: Fast Algorithms to Learn Piecewise Constant Functions on General Weighted Graphs
• Noisy tensor completion via the sum-of-squares hierarchy
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Persistent homology for low-complexity models
• Recovery error analysis of noisy measurement in compressed sensing
• Sharp oracle inequalities for low-complexity priors
• Graphical Model Selection for Gaussian Conditional Random Fields in the Presence of Latent Variables
• Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
• Low-Rank Inducing Norms with Optimality Interpretations
• Recovery analysis for weighted \(\ell_{1}\)-minimization using the null space property
• Energy on spheres and discreteness of minimizing measures
• Bayesian computation: a summary of the current state, and samples backwards and forwards
• Modular proximal optimization for multidimensional total-variation regularization
• Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains
• Approximate support recovery of atomic line spectral estimation: a tale of resolution and precision
• Model selection with low complexity priors
• The geometry of convex surfaces and inverse problems of scattering theory
• Biorthogonal greedy algorithms in convex optimization
• The restricted isometry property of block diagonal matrices for group-sparse signal recovery
• Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
• Optimal Injectivity Conditions for Bilinear Inverse Problems with Applications to Identifiability of Deconvolution Problems
• Compressed sensing of data with a known distribution
• Screening for a reweighted penalized conditional gradient method
• A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization
• Super-resolution radar
• Generalized Conditional Gradient for Sparse Estimation
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• On Efficiently Solving the Subproblems of a Level-Set Method for Fused Lasso Problems
• Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing
• Title not available (Why is that?)
• The Geometry of Rank-One Tensor Completion
• One-bit compressed sensing via ℓ _p (0 < p < 1)-minimization method
• Sparse Inverse Problems over Measures: Equivalence of the Conditional Gradient and Exchange Methods
• Superresolution 2D DOA estimation for a rectangular array via reweighted decoupled atomic norm minimization
• Efficient proximal mapping computation for low-rank inducing norms
• Super-resolution for doubly-dispersive channel estimation
• Structured Sparsity: Discrete and Convex Approaches
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• Blind three dimensional deconvolution via convex optimization
• Regularization and the small-ball method II: complexity dependent error rates
• Linear reconstruction problems with convex constraints: Influence of the a priori data
• Linear regression with sparsely permuted data
• Optimal rates of statistical seriation
• Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• Fundamental barriers to high-dimensional regression with convex penalties
• Title not available (Why is that?)
• A Convex Approach to Superresolution and Regularization of Lines in Images
• Optimization Methods for Synthetic Aperture Radar Imaging
• On Representer Theorems and Convex Regularization
• Greedy approximation in convex optimization
• Sharp recovery bounds for convex demixing, with applications
• Small-deviation inequalities for sums of random matrices
• Kernel methods in system identification, machine learning and function estimation: a survey
• Learning semidefinite regularizers
• Estimation in High Dimensions: A Geometric Perspective
• Lasso guarantees for \(\beta \)-mixing heavy-tailed time series
• Randomized numerical linear algebra: Foundations and algorithms
• Guarantees of total variation minimization for signal recovery
• Convex optimization on Banach spaces
• A geometrical stability condition for compressed sensing
• Regularized linear system identification using atomic, nuclear and kernel-based norms: the role of the stability constraint
• High-dimensional change-point estimation: combining filtering with convex optimization
• One condition for solution uniqueness and robustness of both \(\ell_1\)-synthesis and \(\ell_1\)-analysis minimizations
• A Derivative-Free Method for Structured Optimization Problems
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Tensor theta norms and low rank recovery
• Greedy expansions in convex optimization
• Generalized notions of sparsity and restricted isometry property. II: Applications
• Average-case complexity without the black swans
• Stable low-rank matrix recovery via null space properties
• Polynomial Norms
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• Tuning complexity in regularized kernel-based regression and linear system identification: the robustness of the marginal likelihood estimator
• Robust analysis ℓ₁-recovery from Gaussian measurements and total variation minimization
• Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Geometric inference for general high-dimensional linear inverse problems
• On model selection consistency of regularized M-estimators
• System identification using kernel-based regularization: new insights on stability and consistency issues
• Adaptive confidence sets in shape restricted regression
• Riemannian gradient descent methods for graph-regularized matrix completion
• A unified approach to uniform signal recovery from nonlinear observations
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• A new perspective on least squares under convex constraint
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• Symmetric Tensor Nuclear Norms
• Generalization bounds for learning with linear, polygonal, quadratic and conic side knowledge
• Low Complexity Regularization of Linear Inverse Problems
• Computational and statistical tradeoffs via convex relaxation
• Cosparsity in Compressed Sensing
• Sharp MSE bounds for proximal denoising
• Analysis \(\ell_1\)-recovery with frames and Gaussian measurements
• Simple bounds for recovering low-complexity models
• Book Review: A mathematical introduction to compressive sensing

Uses Software

• SDPT3
• YALMIP

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Geometric inference for general high-dimensional linear inverse problems 👍 👎
• Inverse problems in spectral geometry 👍 👎
• Integral geometry and some inverse problems 👍 👎
• Convexity and the Exterior Inverse Problem of Potential Theory 👍 👎
• The inverse problem in convex optimization with linear constraints 👍 👎
• The geometry of convex surfaces and inverse problems of scattering theory 👍 👎
• Geometric Inverse Problems 👍 👎

This page was built for publication: The convex geometry of linear inverse problems

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