The convex geometry of linear inverse problems
From MaRDI portal
Publication:1928276
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.
The authors consider the problem of recovery of object models from limited linear measurements. More precisely, the model is a convex combination of finite number of elements called atoms. The atomic norm \(\| \cdot\|_{\mathcal{A}}\) is defined as the gauge function of the convex hull of atoms. Given an evaluation vector \(y\) and operator \(\Phi\), the problem is to minimize \(\| x\|_{\mathcal{A}}\) subject to \(\Phi x=y\). The authors give many examples of applications. By analyzing the Gaussian width of certain tangent cones, they investigate the number of measurements for exact and robust recovery. When the atomic set has algebraic structure, the basic problem can be solved or approximated via semidefinite programming. Some results of computations illustrating the quality of approximations are also given.
Recommendations
- The inverse problem in convex optimization with linear constraints
- scientific article; zbMATH DE number 1354058
- Inverse problems in spectral geometry
- Geometric inverse problems. With emphasis on two dimensions
- Geometric inference for general high-dimensional linear inverse problems
- scientific article; zbMATH DE number 3862666
- Inverse problem in convex optimization with linear homogeneous constraints
- Integral geometry and some inverse problems
- Convexity and the Exterior Inverse Problem of Potential Theory
- The geometry of convex surfaces and inverse problems of scattering theory
Cites work
- A GENERAL ATOMIC DECOMPOSITION THEOREM AND BANACH'S CLOSED RANGE THEOREM
- A generalized proximal point algorithm for certain non-convex minimization problems
- A random polynomial-time algorithm for approximating the volume of convex bodies
- A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
- A Singular Value Thresholding Algorithm for Matrix Completion
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- An EM algorithm for wavelet-based image restoration
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Approximating the Cut-Norm via Grothendieck's Inequality
- Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
- Combinatorics of random processes and sections of convex bodies
- Compressed sensing
- Convex Analysis
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Counting the faces of randomly-projected hypercubes and orthants, with applications
- Decoding by Linear Programming
- Exact matrix completion via convex optimization
- Fixed point and Bregman iterative methods for matrix rank minimization
- Fixed-Point Continuation for \ell₁-Minimization: Methodology and Convergence
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
- Geometry of cuts and metrics
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 3980111 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 3772326 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 52497 (Why is no real title available?)
- scientific article; zbMATH DE number 1113187 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Inferring Rankings Using Constrained Sensing
- Introductory lectures on convex optimization. A basic course.
- Lectures on Polytopes
- Linearized Bregman iterations for compressed sensing
- Local operator theory, random matrices and Banach spaces.
- Null space conditions and thresholds for rank minimization
- On the conditions used to prove oracle results for the Lasso
- Optimization. Algorithms and consistent approximations
- Orthogonal tensor decompositions
- Precise Stability Phase Transitions for \ell₁ Minimization: A Unified Geometric Framework
- Probability of unique integer solution to a system of linear equations
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust principal component analysis?
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Semidefinite programming relaxations for semialgebraic problems
- Signal Recovery by Proximal Forward-Backward Splitting
- Simultaneous analysis of Lasso and Dantzig selector
- Some remarks on greedy algorithms
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Sparse Reconstruction by Separable Approximation
- Tensor Decompositions and Applications
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- The concentration of measure phenomenon
- The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
- Theta bodies for polynomial ideals
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
- Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
- Universal approximation bounds for superpositions of a sigmoidal function
Cited in
(only showing first 100 items - show all)- Linear reconstruction problems with convex constraints: Influence of the a priori data
- Improved bounds for sparse recovery from subsampled random convolutions
- Compressed sensing of data with a known distribution
- The minimal measurement number for low-rank matrix recovery
- Data recovery on a manifold from linear samples: theory and computation
- Linear regression with sparsely permuted data
- Optimal rates of statistical seriation
- Near-optimality of linear recovery from indirect observations
- Learning semidefinite regularizers
- Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
- Sharp oracle inequalities for least squares estimators in shape restricted regression
- System identification using kernel-based regularization: new insights on stability and consistency issues
- The geometry of convex surfaces and inverse problems of scattering theory
- A convex variational model for learning convolutional image atoms from incomplete data
- Stable separation and super-resolution of mixture models
- Energy on spheres and discreteness of minimizing measures
- Riemannian gradient descent methods for graph-regularized matrix completion
- Tensor theta norms and low rank recovery
- Provably optimal sparse solutions to overdetermined linear systems with non-negativity constraints in a least-squares sense by implicit enumeration
- Efficient proximal mapping computation for low-rank inducing norms
- Super-resolution for doubly-dispersive channel estimation
- On the robustness of minimum norm interpolators and regularized empirical risk minimizers
- Proof methods for robust low-rank matrix recovery
- Analysis of sparse recovery algorithms via the replica method
- Hierarchical isometry properties of hierarchical measurements
- Fundamental barriers to high-dimensional regression with convex penalties
- Noisy tensor completion via the sum-of-squares hierarchy
- The restricted isometry property of block diagonal matrices for group-sparse signal recovery
- Biorthogonal greedy algorithms in convex optimization
- Screening for a reweighted penalized conditional gradient method
- Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
- Blind three dimensional deconvolution via convex optimization
- Lasso guarantees for \(\beta \)-mixing heavy-tailed time series
- Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain
- Adaptive confidence sets in shape restricted regression
- Complex phase retrieval from subgaussian measurements
- Sparsity of solutions for variational inverse problems with finite-dimensional data
- Super-resolution by means of Beurling minimal extrapolation
- Superresolution 2D DOA estimation for a rectangular array via reweighted decoupled atomic norm minimization
- Approximate support recovery of atomic line spectral estimation: a tale of resolution and precision
- Sharp oracle inequalities for low-complexity priors
- Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions
- Solving equations of random convex functions via anchored regression
- Small-deviation inequalities for sums of random matrices
- On model selection consistency of regularized M-estimators
- Greedy approximation in convex optimization
- Average-case complexity without the black swans
- One condition for solution uniqueness and robustness of both _1-synthesis and _1-analysis minimizations
- Recovery analysis for weighted \(\ell_{1}\)-minimization using the null space property
- High-dimensional change-point estimation: combining filtering with convex optimization
- Recovery error analysis of noisy measurement in compressed sensing
- Learning with optimal interpolation norms
- Phase recovery, MaxCut and complex semidefinite programming
- On risk bounds in isotonic and other shape restricted regression problems
- Generalized notions of sparsity and restricted isometry property. II: Applications
- Almost everywhere injectivity conditions for the matrix recovery problem
- When does OMP achieve exact recovery with continuous dictionaries?
- \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
- Convex optimization in sums of Banach spaces
- Quadratic growth conditions and uniqueness of optimal solution to Lasso
- Generic error bounds for the generalized Lasso with sub-exponential data
- Terracini convexity
- Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
- Bernstein's inverse problem in metric linear spaces.
- Estimation in high dimensions: a geometric perspective
- Convex Recovery of a Structured Signal from Independent Random Linear Measurements
- Low complexity regularization of linear inverse problems
- 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
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Geometric inference for general high-dimensional linear inverse problems
- Book Review: A mathematical introduction to compressive sensing
- An introduction to compressed sensing
- Sharp MSE bounds for proximal denoising
- Learning by atomic norm regularization with polynomial kernels
- Compressed sensing, sparse inversion, and model mismatch
- Recovering structured signals in noise: least-squares meets compressed sensing
- Sparse model uncertainties in compressed sensing with application to convolutions and sporadic communication
- Cosparsity in Compressed Sensing
- Structured sparsity: discrete and convex approaches
- Low rank matrix recovery from rank one measurements
- scientific article; zbMATH DE number 4038559 (Why is no real title available?)
- Simple bounds for recovering low-complexity models
- Sharp recovery bounds for convex demixing, with applications
- Low-rank inducing norms with optimality interpretations
- Optimization methods for synthetic aperture radar imaging
- A tight bound of hard thresholding
- On efficiently solving the subproblems of a level-set method for fused lasso problems
- Multicompartment magnetic resonance fingerprinting
- Fast and reliable parameter estimation from nonlinear observations
- Robust analysis ℓ1-recovery from Gaussian measurements and total variation minimization
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Guarantees of total variation minimization for signal recovery
- Model selection with low complexity priors
- Time for dithering: fast and quantized random embeddings via the restricted isometry property
- High-dimensional estimation with geometric constraints
- Super-resolution radar
- Convex geometry of quantum resource quantification
- Stable low-rank matrix recovery via null space properties
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)
