Representer Theorems for Sparsity-Promoting $\ell _{1}$ Regularization
Open accessAbstract
We present a theoretical analysis and comparison of the effect of l1versus l2regularization for the resolution of ill-posed linear inverse and/or compressed sensing problems. Our formulation covers the most general setting where the solution is specified as the minimizer of a convex cost functional. We derive a series of representer theorems that give the generic form of the solution depending on the type of regularization. We start with the analysis of the problem in finite dimensions and then extend our results to the infinite-dimensional spaces l2(Z) and l1(Z). We also consider the use of linear transformations in the form of dictionaries or regularization operators. In particular, we show that the l2solution is forced to live in a predefined subspace that is intrinsically smooth and tied to the measurement operator. The l1solution, on the other hand, is formed by adaptively selecting a subset of atoms in a dictionary that is specified by the regularization operator. Beside the proof that l1solutions are intrinsically sparse, the main outcome of our investigation is that the use of l1regularization is much more favorable for injecting prior knowledge: it results in a functional form that is independent of the system matrix, while this is not so in the l2scenario.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
TV regularization should be optimal for piecewise constant phantoms.
“This is a reasonable results given that the phantom is piecewise constant and thus the TV regularization should be optimal [2], [47].”
From Deep Convolutional Neural Network for Inverse Problems in Imaging (2017) · cites this paper as [47]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482 · see citing works
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994 · see citing works
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949 · see citing works
Nonlinear total variation based noise removal algorithms
Rudin, L., Osher, S., & Fatemi, E. (1992) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(92)90242-f · Cited by 17,089 · see citing works
Donoho, D. L. (2004) · Cited by 17,049 · see citing works
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952 · see citing works
Stable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036 · see citing works
Sparse MRI: The application of compressed sensing for rapid MR imaging
Lustig, M., Donoho, D., & Pauly, J. M. (2007) · Magnetic Resonance in Medicine · doi:10.1002/mrm.21391 · Cited by 6,952 · see citing works
An iterative thresholding algorithm for linear inverse problems with a sparsity constraint.
Daubechies, I., Defrise, M., & De Mol, C. (2004) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20042 · Cited by 4,958 · see citing works
The Split Bregman Method for L1-Regularized Problems
Goldstein, T., & Osher, S. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080725891 · Cited by 4,243 · see citing works
The restricted isometry property and its implications for compressed sensing
Candès, E. J. (2008) · Comptes Rendus Mathématique · doi:10.1016/j.crma.2008.03.014 · Cited by 3,792 · see citing works
Figueiredo, M. A. T., Nowak, R. D., & Wright, S. J. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910281 · Cited by 3,531 · see citing works
Numerical Methods for Least Squares Problems
Björck, Å. (1996) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971484 · Cited by 3,276 · see citing works
Numerical methods for least squares problems
Björck, Å. (1996) · Choice Reviews Online · doi:10.5860/choice.34-1602 · Cited by 3,067 · see citing works
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
Donoho, D. L., & Elad, M. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0437847100 · Cited by 2,970 · see citing works
A Mathematical Introduction to Compressive Sensing
Foucart, S., & Rauhut, H. (2013) · Applied and numerical harmonic analysis · doi:10.1007/978-0-8176-4948-7 · Cited by 2,638 · see citing works
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,546 · see citing works
Solution of incorrectly formulated problems and the regularization method
Tikhonov, A. N. (1963) · Medical Entomology and Zoology · Cited by 2,381 · see citing works
Sparse and Redundant Representations
Elad, M. (2010) · Springer eBooks · doi:10.1007/978-1-4419-7011-4 · Cited by 2,198 · see citing works
From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
Bruckstein, A. M., Donoho, D. L., & Elad, M. (2009) · SIAM Review · doi:10.1137/060657704 · Cited by 2,141 · see citing works
Sparsity and incoherence in compressive sampling
Candès, E. J., & Romberg, J. K. (2007) · Inverse Problems · doi:10.1088/0266-5611/23/3/008 · Cited by 2,109 · see citing works
Probing the Pareto Frontier for Basis Pursuit Solutions
van den Berg, E., & Friedlander, M. P. (2008) · SIAM Journal on Scientific Computing · doi:10.1137/080714488 · Cited by 1,940 · see citing works
Introduction to Inverse Problems in Imaging
Bertero, M., & Boccacci, P. (1998) · Institute of Physics eBooks · doi:10.1887/0750304359 · Cited by 1,915 · see citing works
Topological vector spaces, distributions and kernels
Trèves, F. (2006) · Cited by 1,700 · see citing works
Convex Analysis and Variational Problems
Ekeland, I., & Témam, R. (1999) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971088 · Cited by 1,602 · see citing works
Image recovery via total variation minimization and related problems
Chambolle, A., & Lions, P. (1997) · Numerische Mathematik · doi:10.1007/s002110050258 · Cited by 1,601 · see citing works
Bredies, K., Kunisch, K. K., & Pock, T. (2010) · SIAM Journal on Imaging Sciences · doi:10.1137/090769521 · Cited by 1,540 · see citing works
Spline Functions: Basic Theory
Schumaker, L. L. (2007) · Cambridge University Press eBooks · doi:10.1017/cbo9780511618994 · Cited by 1,290 · see citing works
An EM algorithm for wavelet-based image restoration
Figueiredo, M. A. T., & Nowak, R. D. (2003) · IEEE Transactions on Image Processing · doi:10.1109/tip.2003.814255 · Cited by 1,220 · see citing works
Splines and Variational Methods.
W., L. B., & Prenter, P. M. (1991) · Mathematics of Computation · doi:10.2307/2008555 · Cited by 1,134 · see citing works
Constrained restoration and the recovery of discontinuities
Geman, D., & Reynolds, G. (1992) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.120331 · Cited by 1,100 · see citing works
Afonso, M. V., Bioucas-Dias, J. M., & Figueiredo, M. A. T. (2010) · IEEE Transactions on Image Processing · doi:10.1109/tip.2010.2076294 · Cited by 946 · see citing works
Afonso, M. V., Bioucas‐Dias, J. M., & Figueiredo, M. A. T. (2011) · Cited by 783 · see citing works
Image reconstruction and restoration: overview of common estimation structures and problems
Demoment, G. (1989) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/29.45551 · Cited by 647 · see citing works
Linear and Nonlinear Functional Analysis with Applications
Ciarlet, P. G. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972597 · Cited by 572 · see citing works
Compressed Sensing and Redundant Dictionaries
Rauhut, H., Schnass, K., & Vandergheynst, P. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.920190 · Cited by 543 · see citing works
SPLINE FUNCTIONS AND THE PROBLEM OF GRADUATION
Schoenberg, I. J. (1964) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.52.4.947 · Cited by 440 · see citing works
An Introduction to Sparse Stochastic Processes
Unser, M. A., & Tafti, P. D. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781107415805 · Cited by 184 · see citing works
Self-citationHigher-Order TV Methods—Enhancement via Bregman Iteration
Benning, M., Brüne, C., Burger, M., & Müller, J. (2012) · Journal of Scientific Computing · doi:10.1007/s10915-012-9650-3 · Cited by 121 · see citing works
Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization
Unser, M. A., Fageot, J., & Ward, J. P. (2017) · SIAM Review · doi:10.1137/16m1061199 · Cited by 98 · see citing works
Self-citationRegularization theory in image restoration-the stabilizing functional approach
Karayiannis, N. B., & Venetsanopoulos, A. N. (1990) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/29.57544 · Cited by 95 · see citing works
Discrete Splines via Mathematical Programming
Mangasarian, O. L., & Schumaker, L. L. (1971) · SIAM Journal on Control · doi:10.1137/0309015 · Cited by 76 · see citing works
Splines in Higher Order TV Regularization
Steidl, G., Didas, S., & Neumann, J. K. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-8066-7 · Cited by 67 · see citing works
A Signal Processing Approach to Generalized 1-D Total Variation
Karahanoğlu, F. I., Bayram, İ., & Ville, D. V. D. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2164399 · Cited by 64 · see citing works
Flagged first, then by citations
1 of the 45 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Deep Convolutional Neural Network for Inverse Problems in Imaging
Jin, K. H., McCann, M. T., Froustey, E., & Unser, M. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2713099 · Cited by 2,529 · see citing works
Self-citationSplines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization
Unser, M. A., Fageot, J., & Ward, J. P. (2017) · SIAM Review · doi:10.1137/16m1061199 · Cited by 98 · see citing works
Self-citationOn Representer Theorems and Convex Regularization
Boyer, C., Chambolle, A., de Castro, Y., Duval, V., de Gournay, F., & Weiss, P. O. (2019) · SIAM Journal on Optimization · doi:10.1137/18m1200750 · Cited by 97 · see citing works
Robustness to Unknown Error in Sparse Regularization
Brugiapaglia, S., & Adcock, B. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2788445 · Cited by 64 · see citing works
A Unifying Representer Theorem for Inverse Problems and Machine Learning
Unser, M. A. (2020) · Foundations of Computational Mathematics · doi:10.1007/s10208-020-09472-x · Cited by 61 · see citing works
Self-citationGupta, H., Fageot, J., & Unser, M. A. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2860549 · Cited by 42 · see citing works
Self-citationMatrix Factorization Techniques in Machine Learning, Signal Processing, and Statistics
Du, K.-L., Swamy, M. N. S., Wang, Z., & Mow, W. H. (2023) · Mathematics · doi:10.3390/math11122674 · Cited by 29 · see citing works
Exact solutions of infinite dimensional total-variation regularized problems
Flinth, A., & Weiss, P. O. (2018) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iay016 · Cited by 28 · see citing works
Debarre, T., Fageot, J., Gupta, H., & Unser, M. A. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2902926 · Cited by 25 · see citing works
Self-citationTV-based reconstruction of periodic functions
Fageot, J., & Simeoni, M. (2020) · Inverse Problems · doi:10.1088/1361-6420/abbd7e · Cited by 17 · see citing works
Self-citationConvex optimization in sums of Banach spaces
Unser, M. A., & Aziznejad, S. (2021) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2021.07.002 · Cited by 15 · see citing works
Self-citationSparsest piecewise-linear regression of one-dimensional data
Debarre, T., Denoyelle, Q., Unser, M. A., & Fageot, J. (2021) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2021.114044 · Cited by 12 · see citing works
Self-citationPeriodic Splines and Gaussian Processes for the Resolution of Linear Inverse Problems
Badoual, A., Fageot, J., & Unser, M. A. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2873514 · Cited by 11 · see citing works
Self-citationFunctional penalised basis pursuit on spheres
Simeoni, M. (2021) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2020.12.004 · Cited by 10 · see citing works
Graph-based optimization approaches for machine learning, uncertainty quantification and networks
Bertozzi, A. L., & Merkurjev, E. (2019) · Handbook of numerical analysis · doi:10.1016/bs.hna.2019.04.001 · Cited by 10 · see citing works
Generalized representer theorems in Banach spaces
Huang, L., Liu, C., Tan, L., & Ye, Q. (2019) · Analysis and Applications · doi:10.1142/s0219530519410100 · Cited by 9 · see citing works
Kurukuru, V. S. B., Haque, A., Khan, M. A., & Blaabjerg, F. (2021) · Heliyon · doi:10.1016/j.heliyon.2021.e08609 · Cited by 9 · see citing works
RetractedA Fast and Scalable Polyatomic Frank-Wolfe Algorithm for the LASSO
Jarret, A., Fageot, J., & Simeoni, M. (2022) · IEEE Signal Processing Letters · doi:10.1109/lsp.2022.3149377 · Cited by 9 · see citing works
Self-citationSparse machine learning in Banach spaces
Xu, Y. (2023) · Applied Numerical Mathematics · doi:10.1016/j.apnum.2023.02.011 · Cited by 8 · see citing works
Stability of Image-Reconstruction Algorithms
Pla, P. D. A., Neumayer, S., & Unser, M. A. (2023) · IEEE Transactions on Computational Imaging · doi:10.1109/tci.2023.3236161 · Cited by 8 · see citing works
Self-citationWang, R., & Xu, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.14101 · Cited by 8 · see citing works
Chen, Y., Zhang, Z., Xu, Z., & He, Y. (2024) · Mechanical Systems and Signal Processing · doi:10.1016/j.ymssp.2024.111911 · Cited by 7 · see citing works
Jarret, A., Kashani, S., Rué‐Queralt, J., Hurley, P. K., Fageot, J., & Simeoni, M. (2024) · Astronomy and Astrophysics · doi:10.1051/0004-6361/202450970 · Cited by 6 · see citing works
Self-citationThe Sparsity of Cycle Spinning for Wavelet-Based Solutions of Linear Inverse Problems
Parhi, R., & Unser, M. A. (2023) · IEEE Signal Processing Letters · doi:10.1109/lsp.2023.3275916 · Cited by 6 · see citing works
Self-citationLazzaro, D., Morigi, S., & Ratti, L. (2024) · Journal of Scientific Computing · doi:10.1007/s10915-024-02689-w · Cited by 5 · see citing works
Minimum norm interpolation in the ℓ1(ℕ) space
Cheng, R., & Xu, Y. (2020) · Analysis and Applications · doi:10.1142/s0219530520400059 · Cited by 5 · see citing works
Physical model-driven deep networks for through-the-wall radar imaging
Wang, Y., Zhang, Y., Xiao, M., Zhou, H., Liu, Q., & Gao, J. (2022) · International Journal of Microwave and Wireless Technologies · doi:10.1017/s1759078722000071 · Cited by 4 · see citing works
Continuous-Domain Formulation of Inverse Problems for Composite Sparse-Plus-Smooth Signals
Debarre, T., Aziznejad, S., & Unser, M. A. (2021) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2021.3116482 · Cited by 3 · see citing works
Self-citationOn the uniqueness of solutions for the basis pursuit in the continuum
Debarre, T., Denoyelle, Q., & Fageot, J. (2022) · Inverse Problems · doi:10.1088/1361-6420/ac9998 · Cited by 3 · see citing works
Self-citationAnalysis vs synthesis with structure – An investigation of union of subspace models on graphs
Kotzagiannidis, M. S., & Davies, M. E. (2022) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2022.03.002 · Cited by 2 · see citing works
A duality approach to regularized learning problems in Banach spaces
Cheng, R., Wang, R., & Xu, Y. (2023) · Journal of Complexity · doi:10.1016/j.jco.2023.101818 · Cited by 1 · see citing works
Model-based temporal unmixing towards quantitative photo-switching optoacoustic tomography
Liu, Y., Chuah, J., Huang, Y., Stiel, A. C., Unser, M. A., & Dong, J. (2025) · Optics Express · doi:10.1364/oe.550253 · Cited by 1 · see citing works
Self-citation“FISTA” in Banach spaces with adaptive discretisations
Chambolle, A., & Tovey, R. C. (2022) · Computational Optimization and Applications · doi:10.1007/s10589-022-00418-3 · Cited by 1 · see citing works
Lifting up Imbalanced Data Classification to SVM Based Ensemble Level on Oversampling Feature Spaces
Zhang, J., & Wang, S. (2021) · International Conference on Intelligent Systems and Knowledge Engineering (ISKE) · doi:10.1109/iske54062.2021.9755318
Zolduoarrati, E., Licorish, S. A., & Stanger, N. (2025) · Empirical Software Engineering · doi:10.1007/s10664-025-10692-4
Mohamed, K. S., Adam, A., Saad, S. A. A., Mohammed, N., & Himadan, A. (2026) · Mathematics · doi:10.3390/math14122078
- Authors
- Unser, M., Fageot, J., & Gupta, H.
- Affiliations
- École Polytechnique Fédérale de Lausanne (CH)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2016-09
- Volume
- 62
- Issue
- 9
- Pages
- 5167-5180
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2500060407
- Cited by
- 36
- References
- 45
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 3 · 2023: 5 · 2022: 5 · 2021: 6 · 2020: 4 · 2019: 4 · 2018: 4 · 2017: 2
- FWCI
- 2.88
- Type
- journal article
- Language
- en
- Open access
- green
- infoscience.epfl.ch
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion)
- Funders
- European Research Council (No 267439 - FUN-SP)
- Topics
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Physical Sciences › Mathematics › Mathematical Physics › Numerical methods in inverse problems
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image and Signal Denoising Methods
- Keywords
- representer theorem, L1 regularization, Tikhonov regularization, sparsity-promoting regularization, ill-posed linear inverse problems, compressed sensing, convex optimization, dictionaries, regularization operators, sparse solutions, prior knowledge incorporation, infinite-dimensional function spaces
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
