Abstract

Describing the solutions of inverse problems arising in signal or image processing is an important issue both for theoretical and numerical purposes. We propose a principle which describes the solutions to convex variational problems involving a finite number of measurements. We discuss its optimality on various problems concerning the recovery of Radon measures.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • Representer theorem
  • convex optimization
  • Carathéodory theorem

Mathematics Subject Classification

52A41, 90C25, 90C49

References

  1. A. I. Barvinok: Problems of distance geometry and convex properties of quadratic maps, Discrete Comp. Geometry 13/2 (1995) 189–202.https://doi.org/10.1007/BF02574037Google Scholar
  2. N. Boyd, G. Schiebinger, B. Recht: The alternating descent conditional gradient method for sparse inverse problems, SIAM J. Optimization 27/2 (2017) 616–639.https://doi.org/10.1137/15M1035793Google Scholar
  3. C. Boyer, A. Chambolle, Y. De Castro, V. Duval, F. de Gournay, P. Weiss: On representer theorems and convex regularization, SIAM J. Optimization 29/2 (2019) 1260–1281.https://doi.org/10.1137/18M1200750Google Scholar
  4. K. Bredies, M. Carioni: Sparsity of solutions for variational inverse problems with finite-dimensional data, Calc. Var. Partial Diff. Equations 59 (2020), art. no. 14.https://doi.org/10.1007/s00526-019-1658-1Google Scholar
  5. K. Bredies, H. K. Pikkarainen: Inverse problems in spaces of measures, ESAIM: Control, Optimisation Calc. Variations 19/1 (2013) 190–218.https://doi.org/10.1051/cocv/2011205Google Scholar
  6. E. J. Candès, C. Fernandez-Granda: Towards a mathematical theory of super-resolution, Comm. Pure Appl. Math. 67/6 (2014) 906–956.https://doi.org/10.1002/cpa.21455Google Scholar
  7. C. Carathéodory: Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Annalen 64/1 (1907) 95–115.https://doi.org/10.1007/BF01449883Google Scholar
  8. V. Chandrasekaran, B. Recht, P. A. Parrilo, A. S. Willsky: The convex geometry of linear inverse problems, Found. Comp. Math. 12/6 (2012) 805–849.https://doi.org/10.1007/s10208-012-9135-7Google Scholar
  9. L. Condat: Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain, J. Approximation Theory 258 (2020).https://doi.org/10.1016/j.jat.2020.105456Google Scholar
  10. Y. de Castro, F. Gamboa: Exact reconstruction using Beurling minimal extrapolation, J. Math. Analysis Appl. 395/1 (2012) 336–354.https://doi.org/10.1016/j.jmaa.2012.05.011Google Scholar
  11. L. E. Dubins: On extreme points of convex sets, J. Math. Analysis Appl. 5/2 (1962) 237–244.https://doi.org/10.1016/S0022-247X(62)80007-9Google Scholar
  12. V. Duval, G. Peyré: Exact support recovery for sparse spikes deconvolution, Found. Comp. Math. 15/5 (2015) 1315–1355.https://doi.org/10.1007/s10208-014-9228-6Google Scholar
  13. S. D. Fisher, J. W. Jerome: Spline solutions to L1 extremal problems in one and several variables, J. Approximation Theory 13/1 (1975) 73–83.https://doi.org/10.1016/0021-9045(75)90016-7Google Scholar
  14. A. Flinth, P. Weiss: Exact solutions of infinite dimensional total-variation regularized problems, Inform. Inference: J. IMA 8/3 (2019) 407–443.https://doi.org/10.1093/imaiai/iay016Google Scholar
  15. H. Gupta, J. Fageot, M. Unser: Continuous-domain solutions of linear inverse problems with Tikhonov versus generalized TV regularization, IEEE Trans. Signal Processing 66/17 (2018) 4670–4684.https://doi.org/10.1109/TSP.2018.2860549Google Scholar
  16. V. Klee: Convex sets in linear spaces, Duke Math. J. 18/2 (1951) 443–466.https://doi.org/10.1215/S0012-7094-51-01835-2Google Scholar
  17. V. Klee: Extremal structure of convex sets, Archiv d. Mathematik 8/3 (1957) 234–240.https://doi.org/10.1007/BF01899998Google Scholar
  18. V. Klee: On a theorem of Dubins, J. Math. Analysis Appl. 7/3 (1963) 425–427.https://doi.org/10.1016/0022-247X(63)90063-5Google Scholar
  19. M. G. Krein, A. A. Nudelman: The Markov Moment Problem and Extremal Problems: Ideas and Problems of P. L. Cebysev and A. A. Markov and Their Further Development, Translations of Mathematical Monographs 50, American Mathematical Society, Providence (1977).https://doi.org/10.1090/mmono/050Google Scholar
  20. S. Lang: Algebra, rev. 3rd ed., Graduate Texts in Mathematics 211, Springer, New York (2002).https://doi.org/10.1007/978-1-4613-0041-0_1Google Scholar
  21. J. Matousek, B. Gärtner: Understanding and Using Linear Programming, Springer, Cham (2007).Google Scholar
  22. C. Poon, G. Peyré: Degrees of freedom for off-the-grid sparse estimation, Bernoulli (2021).https://doi.org/10.3150/21-BEJ1414Google Scholar
  23. R. T. Rockafellar: Conjugate Duality and Optimization, 2nd ed., Regional Conference Series in Applied Mathematics 16, SIAM, Philadelphia (1989).Google Scholar
  24. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1997).Google Scholar
  25. O. Toeplitz: Über die Fouriersche Entwicklung positiver Funktionen, Rend. Circ. Mat. Palermo 32 (1911) 191–192.https://doi.org/10.1007/BF03014794Google Scholar
  26. M. Unser, J. Fageot, J. P. Ward: Splines are universal solutions of linear inverse problems with generalized TV regularization, SIAM Review 59/4 (2017) 769–793.https://doi.org/10.1137/16M1061199Google Scholar
  27. S. I. Zuhovickiĭ: Remarks on problems in approximation theory (Ukrainian), Mat. Zbirnik KDU (1948) 169–183.Google Scholar

Suggested citation

V. Duval. “An Epigraphical Approach to the Representer Theorem.” Journal of Convex Analysis 28 (2021), No. 3, 819–836. https://doi.org/10.68381/jca28047

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2021. Rights now held by Banach Press.