Low complexity regularization of linear inverse problems

DOI10.1007/978-3-319-19749-4_3MaRDI QIDQ2799919zbMATH OpenOpenAlexFDO

Authors Samuel Vaiter, Gabriel Peyré, Jalal Fadili

Publication date 14 April 2016

Published in Sampling Theory, a Renaissance (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: Inverse problems and regularization theory is a central theme in contemporary signal processing, where the goal is to reconstruct an unknown signal from partial indirect, and possibly noisy, measurements of it. A now standard method for recovering the unknown signal is to solve a convex optimization problem that enforces some prior knowledge about its structure. This has proved efficient in many problems routinely encountered in imaging sciences, statistics and machine learning. This chapter delivers a review of recent advances in the field where the regularization prior promotes solutions conforming to some notion of simplicity/low-complexity. These priors encompass as popular examples sparsity and group sparsity (to capture the compressibility of natural signals and images), total variation and analysis sparsity (to promote piecewise regularity), and low-rank (as natural extension of sparsity to matrix-valued data). Our aim is to provide a unified treatment of all these regularizations under a single umbrella, namely the theory of partial smoothness. This framework is very general and accommodates all low-complexity regularizers just mentioned, as well as many others. Partial smoothness turns out to be the canonical way to encode low-dimensional models that can be linear spaces or more general smooth manifolds. This review is intended to serve as a one stop shop toward the understanding of the theoretical properties of the so-regularized solutions. It covers a large spectrum including: (i) recovery guarantees and stability to noise, both in terms of $el{l}^2$-stability and model (manifold) identification; (ii) sensitivity analysis to perturbations of the parameters involved (in particular the observations), with applications to unbiased risk estimation ; (iii) convergence properties of the forward-backward proximal splitting scheme, that is particularly well suited to solve the corresponding large-scale regularized optimization problem.

Recommendations

• Model selection with low complexity priors
• Modern regularization methods for inverse problems
• The convex geometry of linear inverse problems
• Sparse recovery in inverse problems
• Sparsity regularization in inverse problems

Cites work

• scientific article; zbMATH DE number 3833218 (Why is no real title available?)
• scientific article; zbMATH DE number 5957408 (Why is no real title available?)
• scientific article; zbMATH DE number 5764862 (Why is no real title available?)
• scientific article; zbMATH DE number 5564093 (Why is no real title available?)
• scientific article; zbMATH DE number 45081 (Why is no real title available?)
• scientific article; zbMATH DE number 176973 (Why is no real title available?)
• scientific article; zbMATH DE number 3551792 (Why is no real title available?)
• scientific article; zbMATH DE number 1271133 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1064642 (Why is no real title available?)
• scientific article; zbMATH DE number 1174325 (Why is no real title available?)
• scientific article; zbMATH DE number 1502618 (Why is no real title available?)
• scientific article; zbMATH DE number 2155014 (Why is no real title available?)
• scientific article; zbMATH DE number 3444596 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 884923 (Why is no real title available?)
• scientific article; zbMATH DE number 3227378 (Why is no real title available?)
• scientific article; zbMATH DE number 3291403 (Why is no real title available?)
• A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Nonlinear Stein-Based Estimator for Multichannel Image Denoising
• A Probabilistic and RIPless Theory of Compressed Sensing
• A SURE Approach for Digital Signal/Image Deconvolution Problems
• A bias-variance approach for the nonlocal means
• A class of decomposition methods for convex optimization and monotone variational inclusions via the hybrid inexact proximal point framework
• A convergence rates result for Tikhonov regularization in Banach spaces with non-smooth operators
• A coordinate gradient descent method for nonsmooth separable minimization
• A data-driven block thresholding approach to wavelet estimation
• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A fast ``Monte-Carlo cross-validation procedure for large least squares problems with noisy data
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A generalized forward-backward splitting
• A mathematical introduction to compressive sensing
• A monotone+skew splitting model for composite monotone inclusions in duality
• A natural identity for exponential families with applications in multiparameter estimation
• A new approach to variable selection in least squares problems
• A proximal decomposition method for solving convex variational inverse problems
• A proximal-based deomposition method for compositions method for convex minimization problems
• A theory for multiresolution signal decomposition: the wavelet representation
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• A wavelet tour of signal processing. The sparse way.
• Active Sets, Nonsmoothness, and Sensitivity
• Adapting to Unknown Smoothness via Wavelet Shrinkage
• Adaptive Model Selection
• Adaptive wavelet estimation: A block thresholding and oracle inequality approach
• Alternating Projection-Proximal Methods for Convex Programming and Variational Inequalities
• Alternating Projections on Manifolds
• An Algorithm for Restricted Least Squares Regression
• An affine scaling methodology for best basis selection
• An introduction to total variation for image analysis
• Analysis versus synthesis in signal priors
• Asymptotics for Lasso-type estimators.
• Atomic Decomposition by Basis Pursuit
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Beyond coherence: Recovering structured time-frequency representations
• Beyond sparsity: recovering structured representations by \({\ell}^1\) minimization and greedy algorithms
• Certifying the Restricted Isometry Property is Hard
• Compressed sensing with coherent and redundant dictionaries
• Conditional gradient algorithms for norm-regularized smooth convex optimization
• Conditional gradient algorithms with open loop step size rules
• Consistency of the group Lasso and multiple kernel learning
• Consistency of trace norm minimization
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence rates and source conditions for Tikhonov regularization with sparsity constraints
• Convergence rates of convex variational regularization
• Convex analysis and monotone operator theory in Hilbert spaces
• Convexifying the set of matrices of bounded rank: applications to the quasiconvexification and convexification of the rank function
• Decoding by Linear Programming
• Degrees of freedom in lasso problems
• Dictionary Identification—Sparse Matrix-Factorization via $\ell_1$-Minimization
• Dykstras algorithm with bregman projections: A convergence proof
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Estimation of the mean of a multivariate normal distribution
• Exact matrix completion via convex optimization
• Exact reconstruction using Beurling minimal extrapolation
• Exact support recovery for sparse spikes deconvolution
• Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
• Fixed-Point Continuation for \ell₁-Minimization: Methodology and Convergence
• From Stein's unbiased risk estimates to the method of generalized cross- validation
• General Projective Splitting Methods for Sums of Maximal Monotone Operators
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• Generalized SURE for Exponential Families: Applications to Regularization
• Generic optimality conditions for semialgebraic convex programs
• Geometric categories and o-minimal structures
• Grassmannian frames with applications to coding and communication
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Homogeneous penalizers and constraints in convex image restoration
• How Biased is the Apparent Error Rate of a Prediction Rule?
• Identifiable Surfaces in Constrained Optimization
• Identifying active manifolds in regularization problems
• Identifying active manifolds.
• Image decomposition into a bounded variation component and an oscillating component
• Image decomposition via the combination of sparse representations and a variational approach
• Incorporating information on neighbouring coefficients into wavelet estimation
• Inverse problems in spaces of measures
• Iterative hard thresholding for compressed sensing
• Iteratively reweighted least squares minimization for sparse recovery
• Just relax: convex programming methods for identifying sparse signals in noise
• Learning the morphological diversity
• Least angle regression. (With discussion)
• Lectures on topics in finite element solution of elliptic problems. Notes by G. Vijayasundaram
• Linear Inversion of Band-Limited Reflection Seismograms
• Linear convergence of iterative soft-thresholding
• Linear convergence rates for Tikhonov regularization with positively homogeneous functionals
• Living on the edge: phase transitions in convex programs with random data
• Local behavior of sparse analysis regularization: applications to risk estimation
• Matching pursuits with time-frequency dictionaries
• Minimal penalties for Gaussian model selection
• Model Consistency of Partly Smooth Regularizers
• Model Selection and Estimation in Regression with Grouped Variables
• Model selection with low complexity priors
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Necessary and sufficient conditions for linear convergence of \(\ell^1\)-regularization
• Necessary conditions for variational regularization schemes
• Nonlinear total variation based noise removal algorithms
• Nonlocal Means With Dimensionality Reduction and SURE-Based Parameter Selection
• On Measuring and Correcting the Effects of Data Mining and Model Selection
• On Sparse Representations in Arbitrary Redundant Bases
• On model selection consistency of the elastic net when \(p \gg n\)
• On sparse reconstruction from Fourier and Gaussian measurements
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the Equivalence of Soft Wavelet Shrinkage, Total Variation Diffusion, Total Variation Regularization, and SIDEs
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• On the ``degrees of freedom of the lasso
• On the degrees of freedom in shape-restricted regression.
• On the degrees of freedom in shrinkage estimation
• Orthogonal invariance and identifiability
• Parallel alternating direction multiplier decomposition of convex programs
• Partial Smoothness, Tilt Stability, and Generalized Hessians
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
• Proximal splitting methods in signal processing
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Regularization Parameter Selection for Nonlinear Iterative Image Restoration and MRI Reconstruction Using GCV and SURE-Based Methods
• Regularization of ill-posed problems in Banach spaces: convergence rates
• Risk bounds for model selection via penalization
• Robust Sparse Analysis Regularization
• Robust principal component analysis?
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
• Short term spectral analysis, synthesis, and modification by discrete Fourier transform
• Should Penalized Least Squares Regression be Interpreted as Maximum A Posteriori Estimation?
• Signal Recovery and the Large Sieve
• Signal Recovery by Proximal Forward-Backward Splitting
• Simple bounds for recovering low-complexity models
• Simultaneous Support Recovery in High Dimensions: Benefits and Perils of Block $\ell _{1}/\ell _{\infty} $-Regularization
• Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
• Smooth minimization of non-smooth functions
• Some Comments on C P
• Sparse Approximate Solutions to Linear Systems
• Sparse Recovery of Streaming Signals Using <formula formulatype="inline"><tex Notation="TeX">$\ell_1$</tex></formula>-Homotopy
• Sparse and redundant representations. From theory to applications in signal and image processing.
• Sparse image and signal processing. Wavelets, curvelets, morphological diversity
• Sparse solutions to linear inverse problems with multiple measurement vectors
• Sparsity and Smoothness Via the Fused Lasso
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Stable signal recovery from incomplete and inaccurate measurements
• Structured variable selection with sparsity-inducing norms
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The composite absolute penalties family for grouped and hierarchical variable selection
• The convex geometry of linear inverse problems
• The cosparse analysis model and algorithms
• The degrees of freedom of partly smooth regularizers
• The degrees of freedom of the Lasso for general design matrix
• The mathematics of eigenvalue optimization
• The projected GSURE for automatic parameter tuning in iterative shrinkage methods
• The solution path of the generalized lasso
• The 𝒰-Lagrangian of a convex function
• Theoretical Results on Sparse Representations of Multiple-Measurement Vectors
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Total generalized variation
• Towards a Mathematical Theory of Super‐resolution
• Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
• Uncertainty Principles and Signal Recovery
• Uncertainty Principles and Vector Quantization
• Uncertainty principles and ideal atomic decomposition
• Variational Analysis
• Variational methods in imaging

Cited in

(18)

• Low Order Approximations in Deconvolution and Regression with Errors in Variables
• Distributed Learning with Sparse Communications by Identification
• Elastic-Net Regularization: Iterative Algorithms and Asymptotic Behavior of Solutions
• Nonsmoothness in machine learning: specific structure, proximal identification, and applications
• Regularized Linear Inversion with Randomized Singular Value Decomposition
• LASSO Reloaded: A Variational Analysis Perspective with Applications to Compressed Sensing
• Stable recovery of regularized linear inverse problems
• Square root LASSO: well-posedness, Lipschitz stability, and the tuning trade-off
• Sharp oracle inequalities for low-complexity priors
• Sensitivity analysis for mirror-stratifiable convex functions
• Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Iterative regularization for low complexity regularizers
• On the interplay between acceleration and identification for the proximal gradient algorithm
• On Different Facets of Regularization Theory
• Local linear convergence of a primal-dual algorithm for the augmented convex models
• Sampling from non-smooth distributions through Langevin diffusion
• A theory of optimal convex regularization for low-dimensional recovery

Describes a project that uses

Uses Software

• UNLocBoX
• PDCO

This page was built for publication: Low complexity regularization of linear inverse problems

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