Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Sensor-Fusion-Based Trajectory Reconstruction for Quadrotor Drones Read chapter Read first chapter

2019 | OriginalPaper | Chapter

A Simple and Exact Algorithm to Solve Linear Problems with \(\ell ^1\)-Based Regularizers

Authors : Yohann Tendero, Igor Ciril, Jérôme Darbon

Published in: Computer Vision, Imaging and Computer Graphics Theory and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper considers \(\ell ^1\)-based regularized signal estimation that are often used in applications. The estimated signal is obtained as the solution of an optimization problem and the quality of the recovered signal directly depends on the quality of the solver. This paper describes a simple algorithm that computes an exact minimizer of \( \Vert D \cdot \Vert _1\) under the constraints \(A\mathbf {x}=\mathbf {y}\). A comparative evaluation of the algorithm is presented. An illustrative application to real signals of bacterial flagellar motor is also presented.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Flash, Storm, and Mistral: Hardware-Friendly and High Quality Tone Mapping
next chapter Spatial and Spectral Calibration of a Multispectral-Augmented Endoscopic Prototype
Appendix
Available only for authorised users
Footnotes
Literature
1.
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)MathSciNetCrossRef
2.
Blumensath, T., Davies, M.E.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmonic Anal. 27(3), 265–274 (2009)MathSciNetCrossRef
3.
4.
Burger, M., Möller, M., Benning, M., Osher, S.: An adaptive inverse scale space method for compressed sensing. Math. Comput. 82(281), 269–299 (2013)MathSciNetCrossRef
5.
Cai, J.F., Osher, S., Shen, Z.: Linearized bregman iterations for compressed sensing. Math. Comput. 78(267), 1515–1536 (2009)MathSciNetCrossRef
6.
7.
Candes, E.J., Tao, T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 52(12), 5406–5425 (2006)MathSciNetCrossRef
8.
9.
Ciril, I., Darbon, J., Tendero, Y.: A simple and exact algorithm to solve l1 linear problems - application to the compressive sensing method. In: Proceedings of the 13th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications - Volume 4: VISAPP, pp. 54–62. INSTICC, SciTePress (2018)
10.
Dai, W., Milenkovic, O.: Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans. Inform. Theory 55(5), 2230–2249 (2009)MathSciNetCrossRef
11.
12.
Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell 1\) minimization. Proc. Natl. Acad. Sci. 100(5), 2197–2202 (2003)MathSciNetCrossRef
13.
14.
Grant, M.C., Boyd, S.P.: The CVX Users’ Guide, Release 2.1
15.
Hale, E.T., Yin, W., Zhang, Y.: A fixed-point continuation method for l1-Regularized minimization with applications to compressed sensing. CAAM Technical Report TR07-07 (2007)
16.
Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods. Grundlehren der mathematischen Wissenschaften. Springer, Heidelberg (1996)MATH
17.
Jain, P., Tewari, A., Dhillon, I.S.: Orthogonal matching pursuit with replacement. In: Advances in Neural Information Processing Systems, pp. 1215–1223 (2011)
18.
Maleki, A.: Coherence analysis of iterative thresholding algorithms. In: 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton, pp. 236–243. IEEE (2009)
19.
Mallat, S., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397–3415 (1993)CrossRef
20.
Moeller, M., Zhang, X.: Fast sparse reconstruction: greedy inverse scale space flows. Math. Comput. 85(297), 179–208 (2016)MathSciNetCrossRef
21.
Needell, D., Tropp, J.A.: CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmonic Anal. 26(3), 301–321 (2009)MathSciNetCrossRef
22.
Needell, D., Vershynin, R.: Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math. 9(3), 317–334 (2009)MathSciNetCrossRef
23.
Nirody, J.A., Sun, Y.R., Lo, C.J.: The biophysicist’s guide to the bacterial flagellar motor. Adv. Phys.: X 2(2), 324–343 (2017)
24.
Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4(2), 460–489 (2005)MathSciNetCrossRef
25.
Osher, S., Mao, Y., Dong, B., Yin, W.: Fast linearized bregman iteration for compressive sensing and sparse denoising. arXiv preprint arXiv:​1104.​0262 (2011)
26.
Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers, pp. 40–44. IEEE (1993)
27.
Sowa, Y., et al.: Direct observation of steps in rotation of the bacterial flagellar motor. Nature 437(7060), 916 (2005)CrossRef
28.
Tropp, J.A., Gilbert, A.C.: Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inform. Theory 53(12), 4655–4666 (2007)MathSciNetCrossRef
29.
Zhang, X., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on bregman iteration. J. Sci. Comput. 46(1), 20–46 (2011)MathSciNetCrossRef
Metadata
Title
A Simple and Exact Algorithm to Solve Linear Problems with -Based Regularizers
Authors
Yohann Tendero
Igor Ciril
Jérôme Darbon
Copyright Year
2019
Book
Computer Vision, Imaging and Computer Graphics Theory and Applications

Print ISBN: 978-3-030-26755-1

Electronic ISBN: 978-3-030-26756-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-26756-8_12

Premium Partner

    Image Credits