Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Foundations of Computational Mathematics
Erschienen in: Foundations of Computational Mathematics 5/2016

01.10.2016

Generalized Sampling and Infinite-Dimensional Compressed Sensing

verfasst von: Ben Adcock, Anders C. Hansen

Erschienen in: Foundations of Computational Mathematics | Ausgabe 5/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce and analyze a framework and corresponding method for compressed sensing in infinite dimensions. This extends the existing theory from finite-dimensional vector spaces to the case of separable Hilbert spaces. We explain why such a new theory is necessary by demonstrating that existing finite-dimensional techniques are ill suited for solving a number of key problems. This work stems from recent developments in generalized sampling theorems for classical (Nyquist rate) sampling that allows for reconstructions in arbitrary bases. A conclusion of this paper is that one can extend these ideas to allow for significant subsampling of sparse or compressible signals. Central to this work is the introduction of two novel concepts in sampling theory, the stable sampling rate and the balancing property, which specify how to appropriately discretize an infinite-dimensional problem.
Vorheriger Artikel Plethysm and Lattice Point Counting
Nächster Artikel Deterministic Quadrature Formulas for SDEs Based on Simplified Weak Itô–Taylor Steps

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Since writing this paper, it has subsequently been shown that the term N / m can be removed and that noise can be incorporated in the data and recovery guarantees. See [7] for details.
 
Literatur
1.
2.
B. Adcock and A. C. Hansen. A generalized sampling theorem for stable reconstructions in arbitrary bases. J. Fourier Anal. Appl., 18(4):685–716, 2012.MathSciNetMATHCrossRef
3.
B. Adcock and A. C. Hansen. Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon. Appl. Comput. Harmon. Anal., 32(3):357–388, 2012.MathSciNetMATHCrossRef
4.
B. Adcock, A. C. Hansen, E. Herrholz, and G. Teschke. Generalized sampling: extension to frames and inverse and ill-posed problems. Inverse Problems, 29(1):015008, 2013.MathSciNetMATHCrossRef
5.
B. Adcock, A. C. Hansen, and C. Poon. Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem. SIAM J. Math. Anal., 45(5):3114–3131, 2013.MathSciNetMATHCrossRef
6.
B. Adcock, A. C. Hansen, and C. Poon. On optimal wavelet reconstructions from Fourier samples: linearity and universality of the stable sampling rate. Appl. Comput. Harmon. Anal., 36(3):387–415, 2014.MathSciNetMATHCrossRef
7.
B. Adcock, A. C. Hansen, C. Poon, and B. Roman. Breaking the coherence barrier: a new theory for compressed sensing. arXiv:​1302.​0561, 2014.
8.
B. Adcock, A. C. Hansen, B. Roman, and G. Teschke. Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum. Advances in Imaging and Electron Physics, 182:187–279, 2014.CrossRef
9.
B. Adcock, A. C. Hansen, and A. Shadrin. A stability barrier for reconstructions from Fourier samples. SIAM J. Numer. Anal., 52(1):125–139, 2014.MathSciNetMATHCrossRef
10.
11.
A. Averbuch, R. R. Coifman, D. L. Donoho, M. Israeli, and Y. Shkolnisky. A framework for discrete integral transformations. I. The pseudopolar Fourier transform. SIAM J. Sci. Comput., 30(2):764–784, 2008.MathSciNetMATHCrossRef
12.
A. Averbuch, R. R. Coifman, D. L. Donoho, M. Israeli, Y. Shkolnisky, and I. Sedelnikov. A framework for discrete integral transformations. II. The 2D discrete Radon transform. SIAM J. Sci. Comput., 30(2):785–803, 2008.MathSciNetMATHCrossRef
13.
A. Bastounis and A. C. Hansen. On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels. arXiv:​1411.​4449, 2014.
14.
T. Blu, P. L. Dragotti, M. Vetterli, P. Marziliano, and L. Coulout. Sparse sampling of signal innovations. IEEE Signal Process. Mag., 25(2):31–40, 2008.CrossRef
15.
A. Bourrier, M. E. Davies, T. Peleg, P. Pérez, and R. Gribonval. Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems. IEEE Trans. Inform. Theory, 60(12):7928–7946, 2014.MathSciNetCrossRef
16.
E. J. Candès. An introduction to compressive sensing. IEEE Signal Process. Mag., 25(2):21–30, 2008.CrossRef
17.
E. J. Candès and C. Fernandez-Granda. Towards a mathematical theory of super-resolution. Comm. Pure Appl. Math. (to appear), 67(6):906–956, 2014.MathSciNetMATHCrossRef
18.
E. J. Candes and Y. Plan. A Probabilistic and RIPless Theory of Compressed Sensing. IEEE Trans. Inform. Theory, 57(11):7235–7254, 2011.MathSciNetCrossRef
19.
E. J. Candès and J. Romberg. Sparsity and incoherence in compressive sampling. Inverse Problems, 23(3):969–985, 2007.MathSciNetMATHCrossRef
20.
E. J. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):489–509, 2006.MathSciNetMATHCrossRef
21.
E. J. Candès and T. Tao. Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory, 52(12):5406–5425, 2006.MathSciNetMATHCrossRef
22.
Y. Chi, L. L. Scharf, A. Pezeshki, and A. Calderbank. Sensitivity to basis mismatch in compressed sensing. IEEE Trans. Signal Process., 59(5):2182–2195, 2011.MathSciNetCrossRef
23.
A. Cohen, W. Dahmen, and R. DeVore. Compressed sensing and best \(k\)-term approximation. J. Amer. Math. Soc., 22(1):211–231, 2009.MathSciNetMATHCrossRef
24.
M. A. Davenport, M. F. Duarte, Y. C. Eldar, and G. Kutyniok. Introduction to compressed sensing. In Compressed Sensing: Theory and Applications. Cambridge University Press, 2011.
25.
26.
D. L. Donoho and J. Tanner. Counting faces of randomly projected polytopes when the projection radically lowers dimension. J. Amer. Math. Soc., 22(1):1–53, 2009.MathSciNetMATHCrossRef
27.
P. L. Dragotti, M. Vetterli, and T. Blu. Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang–Fix. IEEE Trans. Signal Process., 55(5):1741–1757, 2007.MathSciNetCrossRef
28.
I. Ekeland and T. Turnbull. Infinite-dimensional optimization and convexity. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 1983.
29.
Y. Eldar. Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors. J. Fourier Anal. Appl., 9(1):77–96, 2003.
30.
Y. C. Eldar. Compressed sensing of analog signals in shift-invariant spaces. IEEE Trans. Signal Process., 57(8):2986–2997, 2009.MathSciNetCrossRef
31.
Y. C. Eldar and T. Michaeli. Beyond Bandlimited Sampling. IEEE Signal Process. Mag., 26(3):48–68, 2009.MathSciNetCrossRef
32.
A. Fannjiang and W. Liao. Coherence pattern-guided compressive sensing with unresolved grids. SIAM J. Imaging Sci., 5:179–202, 2012.MathSciNetMATHCrossRef
33.
M. Fornasier and H. Rauhut. Compressive sensing. In Handbook of Mathematical Methods in Imaging, pages 187–228. Springer, 2011.
34.
S. Foucart and H. Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhauser, 2013.MATHCrossRef
35.
K. Gröchenig, Z. Rzeszotnik, and T. Strohmer. Quantitative estimates for the finite section method and Banach algebras of matrices. Integr Equat Oper Th., 67(2):183–202, 2011.
36.
D. Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory, 57(3):1548–1566, 2011.MathSciNetCrossRef
37.
D. Gross, F. Krahmer, and R. Kueng. A partial derandomization of phaselift using spherical designs. arXiv:​1310.​2267, 2014.
38.
M. Guerquin-Kern, M. Häberlin, K. P. Pruessmann, and M. Unser. A fast wavelet-based reconstruction method for Magnetic Resonance Imaging. IEEE Trans. Med. Imaging, 30(9):1649–1660, 2011.CrossRef
39.
M. Guerquin-Kern, L. Lejeune, K. P. Pruessmann, and M. Unser. Realistic analytical phantoms for parallel Magnetic Resonance Imaging. IEEE Trans. Med. Imaging, 31(3):626–636, 2012.CrossRef
40.
A. C. Hansen. On the approximation of spectra of linear operators on Hilbert spaces. J. Funct. Anal., 254(8):2092–2126, 2008.MathSciNetMATHCrossRef
41.
A. C. Hansen. On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators. J. Amer. Math. Soc., 24(1):81–124, 2011.MathSciNetMATHCrossRef
42.
E. Herrholz and G. Teschke. Compressive sensing principles and iterative sparse recovery for inverse and ill-posed problems. Inverse Problems, 26(12):125012, 2010.MathSciNetMATHCrossRef
43.
T. Hrycak and K. Gröchenig. Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method. J. Comput. Phys., 229(3):933–946, 2010.MathSciNetMATHCrossRef
44.
45.
M. Ledoux. The Concentration of Measure Phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, 2001.
46.
M. Lustig, D. L. Donoho, J. M. Santos, and J. M. Pauly. Compressed Sensing MRI. IEEE Signal Process. Mag., 25(2):72–82, March 2008.
47.
M. Mishali and Y. C. Eldar. Xampling: Analog to digital at sub-Nyquist rates. IET Circuits, Devices, & Systems, 5(1):8–20, 2011.CrossRef
48.
M. Mishali, Y. C. Eldar, and A. J. Elron. Xampling: Signal acquisition and processing in union of subspaces. IEEE Trans. Signal Process., 59(10):4719–4734, 2011.MathSciNetCrossRef
49.
S. K. Mitter. Convex optimization in infinite dimensional spaces. In Recent Advances in Learning and Control, volume 371 of Lecture Notes in Control and Information Science, pages 161–179. Springer, London, 2008.
50.
51.
H. Rauhut and R. Ward. Sparse recovery for spherical harmonic expansions. In Proceedings of the 9th International Conference on Sampling Theory and Applications, 2011.
52.
53.
54.
55.
G. Strang and T. Nguyen. Wavelets and filter banks. Wellesley-Cambridge Press, 1997.MATH
56.
T. Strohmer. Measure what should be measured: progress and challenges in compressive sensing. IEEE Signal Proc Let., 19(12):887–893, 2012.
57.
58.
B. P. Sutton, D. C. Noll, and J. A. Fessler. Fast, iterative image reconstruction for MRI in the presence of field inhomogeneities. IEEE Trans. Med. Imaging, 22(2):178–188, 2003.CrossRef
59.
60.
G. Tang, B. Bhaskar, P. Shah, and B. Recht. Compressed sensing off the grid. IEEE Trans. Inform. Theory., 59(11):7465–7490, 2013.MathSciNetCrossRef
61.
62.
M. Unser. Sampling–50 years after Shannon. Proc. IEEE, 88(4):569–587, 2000.CrossRef
63.
M. Unser and A. Aldroubi. A general sampling theory for nonideal acquisition devices. IEEE Trans. Signal Process., 42(11):2915–2925, 1994.CrossRef
64.
M. Vetterli, P. Marziliano, and T. Blu. Sampling signals with finite rate of innovation. IEEE Trans. Signal Process., 50(6):1417–1428, 2002.MathSciNetCrossRef
Metadaten
Titel
Generalized Sampling and Infinite-Dimensional Compressed Sensing
verfasst von
Ben Adcock
Anders C. Hansen
Publikationsdatum
01.10.2016
Verlag
Springer US
Erschienen in
Foundations of Computational Mathematics / Ausgabe 5/2016
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-015-9276-6

Weitere Artikel der Ausgabe 5/2016

Foundations of Computational Mathematics 5/2016 Zur Ausgabe

OriginalPaper

A Necessary and Sufficient Proximity Condition for Smoothness Equivalence of Nonlinear Subdivision Schemes

OriginalPaper

Dimensionality Reduction with Subgaussian Matrices: A Unified Theory

OriginalPaper

Sampling and Cubature on Sparse Grids Based on a B-spline Quasi-Interpolation

OriginalPaper

Deterministic Quadrature Formulas for SDEs Based on Simplified Weak Itô–Taylor Steps

OriginalPaper

Lattice Structures for Attractors II

OriginalPaper

Plethysm and Lattice Point Counting