The Geometry of Sparse Analysis Regularization

DOI10.1137/19M1271877MaRDI QIDQ6158006zbMATH OpenFDO

Authors Xavier Dupuis, Samuel Vaiter

Publication date 22 June 2023

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

geometryregularizationsparsityuniqueness

Mathematics Subject Classification ID

Nonsmooth analysis (49J52) Convex programming (90C25)

Abstract: Analysis sparsity is a common prior in inverse problem or machine learning including special cases such as Total Variation regularization, Edge Lasso and Fused Lasso. We study the geometry of the solution set (a polyhedron) of the analysis l1-regularization (with l2 data fidelity term) when it is not reduced to a singleton without any assumption of the analysis dictionary nor the degradation operator. In contrast with most theoretical work, we do not focus on giving uniqueness and/or stability results, but rather describe a worst-case scenario where the solution set can be big in terms of dimension. Leveraging a fine analysis of the sub-level set of the regularizer itself, we draw a connection between support of a solution and the minimal face containing it, and in particular prove that extremal points can be recovered thanks to an algebraic test. Moreover, we draw a connection between the sign pattern of a solution and the ambient dimension of the smallest face containing it. Finally, we show that any arbitrary sub-polyhedra of the level set can be seen as a solution set of sparse analysis regularization with explicit parameters.

Recommendations

• Sparse Regularization via Convex Analysis
• A geometric framework for sparse matrix problems
• An efficient sparse regularity concept
• An efficient sparse regularity concept
• Robust Sparse Analysis Regularization
• A Geometrical Study of Matching Pursuit Parametrization
• The Geometry of Compressed Sensing
• Maximal solutions of sparse analysis regularization
• Nonparametric sparsity and regularization

Cites work

• A Class of Convex Bodies
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A simple characterization of solutions sets of convex programs
• A unifying representer theorem for inverse problems and machine learning
• Analysis versus synthesis in signal priors
• Characterization of solution sets of convex programs
• Convex Analysis
• scientific article; zbMATH DE number 1804115 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• Least angle regression. (With discussion)
• Lectures on Polytopes
• Local behavior of sparse analysis regularization: applications to risk estimation
• Maximal solutions of sparse analysis regularization
• Minimum-support solutions of polyhedral concave programs^*
• Nonlinear total variation based noise removal algorithms
• On characterizing the solution sets of pseudolinear programs
• On representer theorems and convex regularization
• On the distribution, model selection properties and uniqueness of the Lasso estimator in low and high dimensions
• On the Equivalence of Soft Wavelet Shrinkage, Total Variation Diffusion, Total Variation Regularization, and SIDEs
• One condition for solution uniqueness and robustness of both _1-synthesis and _1-analysis minimizations
• Oriented Matroids
• Robust Sparse Analysis Regularization
• Some results on Tchebycheffian spline functions and stochastic processes
• Sparse regression with exact clustering
• Sparsity and Smoothness Via the Fused Lasso
• Sufficiency of McMullen’s conditions for 𝑓-vectors of simplicial polytopes
• The cosparse analysis model and algorithms
• The generalized Lasso problem and uniqueness
• The Lasso problem and uniqueness
• The maximum numbers of faces of a convex polytope
• The solution path of the generalized lasso

Cited in

(5)

• State-space regularization: Geometric theory
• A Geometrical Study of Matching Pursuit Parametrization
• Sparse Regularization via Convex Analysis
• A unified framework for pattern recovery in penalized and thresholded estimation and its geometry
• The geometry and well-posedness of sparse regularized linear regression

This page was built for publication: The Geometry of Sparse Analysis Regularization

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